Chapter 3IntroductionThe General Problem of Describing Syntax: TerminologyFormal Definition of LanguagesBNF and Context-Free GrammarsBNF FundamentalsBNF Fundamentals (continued)BNF RulesDescribing ListsAn Example GrammarAn Example DerivationDerivationsParse TreeAmbiguity in GrammarsAn Ambiguous Expression GrammarAn Unambiguous Expression GrammarAssociativity of OperatorsPart 2Extended BNFBNF and EBNFRecent Variations in EBNFAttribute GrammarsAttribute Grammars : DefinitionAttribute Grammars: DefinitionAttribute Grammars: An ExampleAttribute Grammar (continued)Attribute Grammars (continued)Slide 28Part 3SemanticsOperational SemanticsOperational SemanticsOperational Semantics (continued)Slide 34Slide 35Lisp tutorial https://cs.gmu.edu/~sean/lisp/LispTutorial.htmlSlide 378/31 – to continueDenotational SemanticsDenotational Semantics - continuedDenotational Semantics: program stateDecimal NumbersExpressionsSlide 44Assignment StatementsLogical Pretest LoopsLoop MeaningEvaluation of Denotational SemanticsDenotation Semantics vs Operational SemanticsAxiomatic SemanticsAxiomatic Semantics (continued)Axiomatic Semantics FormProgram Proof ProcessAxiomatic Semantics: AssignmentAxiomatic Semantics: SequencesSlide 56Axiomatic Semantics: SelectionAxiomatic Semantics: LoopsAxiomatic Semantics: AxiomsLoop InvariantEvaluation of Axiomatic SemanticsSummaryPowerPoint PresentationLoop Invariant – Example (p.159)Slide 65Slide 66Slide 67Slide 68Slide 69Slide 70Slide 71Slide 72Chapter 3Describing Syntax and SemanticsCopyright © 2012 Addison-Wesley. All rights reserved. 1-2Introduction•Syntax: the form or structure of the expressions, statements, and program units•Semantics: the meaning of the expressions, statements, and program units•Syntax and semantics provide a language’s definition– Users of a language definition•Other language designers•Implementers•Programmers (the users of the language)Copyright © 2012 Addison-Wesley. All rights reserved. 1-3The General Problem of Describing Syntax: Terminology•A 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)Copyright © 2012 Addison-Wesley. All rights reserved. 1-4Formal Definition of Languages•Recognizers–A recognition device reads input strings over the alphabet of the language and decides whether the input strings belong to the language –Example: syntax analysis part of a compiler - Detailed discussion of syntax analysis appears in Chapter 4•Generators–A device that generates sentences of a language–One can determine if the syntax of a particular sentence is syntactically correct by comparing it to the structure of the generatorCopyright © 2012 Addison-Wesley. All rights reserved. 1-5BNF and Context-Free Grammars•Context-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-Naur Form (1959)–Invented by John Backus to describe the syntax of Algol 58–BNF is equivalent to context-free grammarsCopyright © 2012 Addison-Wesley. All rights reserved. 1-6BNF Fundamentals•In BNF, abstractions are used to represent classes of syntactic structures--they act like syntactic variables (also called nonterminal symbols, or just terminals)•Terminals are lexemes or tokens •A rule has a left-hand side (LHS), which is a nonterminal, and a right-hand side (RHS), which is a string of terminals and/or nonterminalsBNF Fundamentals (continued)•Nonterminals are often enclosed in angle brackets–Examples of BNF rules:<ident_list> → identifier | identifier, <ident_list><if_stmt> → if <logic_expr> then <stmt>•Grammar: a finite non-empty set of rules•A start symbol is a special element of the nonterminals of a grammarCopyright © 2012 Addison-Wesley. All rights reserved. 1-7Copyright © 2012 Addison-Wesley. All rights reserved. 1-8BNF RulesAn abstraction (or nonterminal symbol) can have more than one RHS <stmt>  <single_stmt> | begin <stmt_list> endis same as <stmt>  <single_stmt> <stmt>  begin <stmt_list> endCopyright © 2012 Addison-Wesley. All rights reserved. 1-9Describing Lists•Syntactic lists are described 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)Copyright © 2012 Addison-Wesley. All rights reserved. 1-10An Example GrammarGiven Grammar<program>  <stmts> <stmts>  <stmt> | <stmt> ; <stmts> <stmt>  <var> = <expr> <var>  a | b | c | d <expr>  <term> + <term> | <term> - <term> <term>  <var> | constDerivation for a = b + constCopyright © 2012 Addison-Wesley. All rights reserved. 1-11An Example Derivation<program> => <stmts> => <stmt> => <var> = <expr> => a = <expr> => a = <term> + <term> => a = <var> + <term> => a = b + <term> => a = b + constCopyright © 2012 Addison-Wesley. All rights reserved. 1-12Derivations•Every string of symbols in a 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 rightmostCopyright © 2012 Addison-Wesley. All rights reserved. 1-13Parse Tree•A hierarchical representation of a derivation <program><stmts><stmt>consta<var> = <expr><var>b<term> + <term>Copyright © 2012 Addison-Wesley. All rights reserved. 1-14Ambiguity in Grammars•A grammar is ambiguous if and only if it generates a sentential form that has two or more distinct parse treesCopyright © 2012 Addison-Wesley. All rights reserved. 1-15An Ambiguous Expression Grammar<expr>  <expr> <op> <expr> | const<op>  / | -<expr><expr> <expr><expr> <expr><expr><expr> <expr><expr> <expr><op><op><op><op>const const const const const const- -/ /<op>Copyright © 2012 Addison-Wesley. All rights reserved. 1-16An Unambiguous Expression Grammar•If we use the parse tree to indicate precedence levels of the operators, we cannot have ambiguity<expr>  <expr> - <term> | <term><term>  <term> / const| const<expr><expr> <term><term>