Chapter 3 Describing Syntax and SemanticsIntroductionWhy and HowSyntax OverviewSlide 5Lexical Structure of Programming LanguagesGrammarsBNF (continued)BNFBNFBNF ExampleDerivation using BNFAnother BNF ExampleDerivationParse TreeAnother Parse TreeGrammarGrammarSlide 19Grammar (continued)An Expression GrammarA derivationA parse treePrecedenceAssociativityAnother example: conditionalsExtended BNFSlide 28Syntax GraphsParsingRecursive Decent ParsingRecursive Decent Parsing ExampleSemanticsSemantics OverviewStatic SemanticsAttribute GrammarsAttribute Grammar ExampleSlide 38Slide 39Slide 40Slide 41Attribute Grammars (continued)Slide 43Dynamic SemanticsOperational SemanticsSlide 46Slide 47Vienna Definition LanguageAxiomatic SemanticsLogic 101Slide 51Slide 52Example: Assignment StatementsSlide 54ConditionsLoopsLoop InvariantsEvaluation of Axiomatic SemanticsDenotational SemanticsSlide 60Denotational Semantics (continued)Example: Decimal NumbersExpressionsAssignment StatementsLogical Pretest LoopsSlide 66Slide 67SummaryCMSC 331, Some material © 1998 by Addison Wesley Longman, Inc. 1Chapter 3Chapter 3 Describing Syntax and SemanticsCMSC 331, Some material © 1998 by Addison Wesley Longman, Inc. 2We usually break down the problem of defining a programming language into two parts.•Defining the PL’s syntax•Defining the PL’s semanticsSyntax - the form or structure of the expressions, statements, and program unitsSemantics - the meaning of the expressions, statements, and program units.Note: There is not always a clear boundary between the two.IntroductionCMSC 331, Some material © 1998 by Addison Wesley Longman, Inc. 3Why and HowWhy? We want specifications for several communities:–Other language designers•Implementors•Programmers (the users of the language)How? One ways is via natural language descriptions (e.g., user’s manuals, text books) but there are a number of techniques for specifying the syntax and semantics that are more formal.CMSC 331, Some material © 1998 by Addison Wesley Longman, Inc. 4Syntax Overview•Language preliminaries•Context-free grammars and BNF•Syntax diagramsCMSC 331, Some material © 1998 by Addison Wesley Longman, Inc. 5A sentence is a string of characters over some alphabet.A language is a set of sentences.A lexeme is the lowest level syntactic unit of a language (e.g., *, sum, begin).A token is a category of lexemes (e.g., identifier).Formal approaches to describing syntax: 1. Recognizers - used in compilers 2. Generators - what we'll studyIntroductionCMSC 331, Some material © 1998 by Addison Wesley Longman, Inc. 6Lexical Structure of Programming Languages•The structure of its lexemes (words or tokens)–token is a category of lexeme•The scanning phase (lexical analyser) collects characters into tokens•Parsing phase(syntactic analyser)determines syntactic structureStream of charactersResult of parsingtokens and valueslexical analyserSyntactic analyserCMSC 331, Some material © 1998 by Addison Wesley Longman, Inc. 7GrammarsContext-Free Grammars•Developed by Noam Chomsky in the mid-1950s.•Language generators, meant to describe the syntax of natural languages.•Define a class of languages called context-free languages.Backus Normal/Naur Form (1959)•Invented by John Backus to describe Algol 58 and refined by Peter Naur for Algol 60.•BNF is equivalent to context-free grammarsCMSC 331, Some material © 1998 by Addison Wesley Longman, Inc. 8A metalanguage is a language used to describe another language.In BNF, abstractions are used to represent classes of syntactic structures--they act like syntactic variables (also called nonterminal symbols), e.g.<while_stmt> ::= while <logic_expr> do <stmt>This is a rule; it describes the structure of a while statementBNF (continued)CMSC 331, Some material © 1998 by Addison Wesley Longman, Inc. 9BNF •A rule has a left-hand side (LHS) which is a single non-terminal symbol and a right-hand side (RHS), one or more terminal or nonterminal symbols.•A grammar is a finite nonempty set of rules•A non-terminal symbol is “defined” by one or more rules.•Multiple rules can be combined with the | symbol so that<stmts> ::= <stmt><stmts> ::= <stmnt> ; <stmnts>And this rule are equivalent<stmts> ::= <stmt> | <stmnt> ; <stmnts>CMSC 331, Some material © 1998 by Addison Wesley Longman, Inc. 10Syntactic lists are described in BNF using recursion <ident_list> -> ident | ident, <ident_list>A derivation is a repeated application of rules, starting with the start symbol and ending with a sentence (all terminal symbols)BNFCMSC 331, Some material © 1998 by Addison Wesley Longman, Inc. 11BNF Example Here is an example of a simple grammar for a subset of English. A sentence is noun phrase and verb phrase followed by a period.<sentence> ::= <noun-phrase><verb-phrase>.<noun-phrase> ::= <article><noun><article> ::= a | the<noun> ::= man | apple | worm | penguin<verb-phrase> ::= <verb> | <verb><noun-phrase><verb> ::= eats | throws | sees | isCMSC 331, Some material © 1998 by Addison Wesley Longman, Inc. 12Derivation using BNF<sentence> -> <noun-phrase><verb-phrase>. <article><noun><verb_phrase>. the<noun><verb_phrase>. the man <verb_phrase>. the man <verb><noun-phrase>. the man eats <noun-phrase>. the man eats <article> < noun>. the man eats the <noun>. the man eats the apple.CMSC 331, Some material © 1998 by Addison Wesley Longman, Inc. 13Another BNF Example<program> -> <stmts><stmts> -> <stmt> | <stmt> ; <stmts><stmt> -> <var> = <expr><var> -> a | b | c | d<expr> -> <term> + <term> | <term> - <term><term> -> <var> | constHere is a derivation:<program> => <stmts> => <stmt> => <var> = <expr> => a = <expr> => a = <term> + <term> => a = <var> + <term> => a = b + <term> => a = b + constNote: There is some variation in notation for BNF grammars. Here we are using -> in the rules instead of ::= .CMSC 331, Some material © 1998 by Addison Wesley Longman, Inc. 14Every string of symbols in the derivation is a sentential form.A sentence is a sentential form that has only terminal symbols.A leftmost derivation is one in which the leftmost nonterminal in each sentential form is the one that is expanded.A derivation may be neither leftmost nor rightmost (or something else)DerivationCMSC 331, Some material © 1998 by Addison Wesley Longman, Inc. 15Parse Tree