ISBN 0-321-33025-0Chapter 3Chapter 3Chapter 3Chapter 3Describing Syntax and SemanticsCopyright © 2006 Addison-Wesley. All rights reserved. 1-2Chapter 3 Topics• Introduction• The General Problem of Describing Syntax• Formal Methods of Describing Syntax• Attribute Grammars• Describing the Meanings of Programs: Dynamic SemanticsCopyright © 2006 Addison-Wesley. All rights reserved. 1-3Introduction• Syntax:Syntax:Syntax:Syntax: the form or structure of the expressions, statements, and program units• Semantics:Semantics:Semantics: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 © 2006 Addison-Wesley. All rights reserved. 1-4The General Problem of Describing Syntax: Terminology• A sentence is a string of characters over some alphabet• A languageis a set of sentences• Alexeme is the lowest level syntactic unit of a language (e.g., *, sum, begin)• A token is a category of lexemes (e.g., identifier)Copyright © 2006 Addison-Wesley. All rights reserved. 1-5Formal Definition of Languages• RecognizersRecognizersRecognizersRecognizers– A recognition device reads input strings of the language and decides whether the input strings belong to the language – Example: syntax analysis part of a compiler– Detailed discussion in Chapter 4• GeneratorsGeneratorsGeneratorsGenerators– A device that generates sentences of a language– One can determine if the syntax of a particular sentence is correct by comparing it to the structure of the generatorCopyright © 2006 Addison-Wesley. All rights reserved. 1-6Formal Methods of Describing Syntax• Backus-Naur Form and Context-Free Grammars– Most widely known method for describing programming language syntax• Extended BNF– Improves readability and writability of BNF• Grammars and RecognizersCopyright © 2006 Addison-Wesley. All rights reserved. 1-7BNF 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 languagesCopyright © 2006 Addison-Wesley. All rights reserved. 1-8Backus-Naur Form (BNF)• Backus-Naur Form (1959)– Invented by John Backus to describe Algol 58– BNF is equivalent to context-free grammars – BNF is a metalanguageused to describe another language– In BNF, abstractions are used to represent classes of syntactic structures--they act like syntactic variables (also called nonterminal symbols)Copyright © 2006 Addison-Wesley. All rights reserved. 1-9BNF Fundamentals• Non-terminals: BNF abstractions• Terminals: lexemes and tokens• Grammar: a collection of rules– Examples of BNF rules:<ident_list> → identifier | identifier, <ident_list><if_stmt> → if <logic_expr> then <stmt><number> → <digit> | <number> <digit> <digit> → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9Copyright © 2006 Addison-Wesley. All rights reserved. 1-10BNF Rules• A rule has a left-hand side (LHS) and a right-hand side (RHS), and consists of terminaland nonterminalsymbols• A grammar is a finite nonempty set of rules• An abstraction (or nonterminal symbol) can have more than one RHS<stmt> → <single_stmt> | begin <stmt_list> endCopyright © 2006 Addison-Wesley. All rights reserved. 1-11Describing 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 © 2006 Addison-Wesley. All rights reserved. 1-12An Example Grammar<program> → <stmts><stmts> → <stmt> | <stmt> ; <stmts><stmt> → <var> = <expr><var> → a | b | c | d<expr> → <term> + <term> | <term> - <term><term> → <var> | constCopyright © 2006 Addison-Wesley. All rights reserved. 1-13An Example Derivation<program> => <stmts> => <stmt> => <var> = <expr> => a =<expr> => a = <term> + <term>=> a = <var> + <term> => a = b + <term>=> a = b + constCopyright © 2006 Addison-Wesley. All rights reserved. 1-14Derivation• Every 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 rightmostCopyright © 2006 Addison-Wesley. All rights reserved. 1-15Parse Tree• A hierarchical representation of a derivation<program><stmts><stmt>consta<var> = <expr><var>b<term> + <term>Copyright © 2006 Addison-Wesley. All rights reserved. 1-16Ambiguity in Grammars• A grammar is ambiguousif and only if it generates a sentential form that has two or more distinct parse treesCopyright © 2006 Addison-Wesley. All rights reserved. 1-17An 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 © 2006 Addison-Wesley. All rights reserved. 1-18An 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> <term>const constconst/-Copyright © 2006 Addison-Wesley. All rights reserved. 1-19dangling elsedangling elsedangling elsedangling else• An example in programming languages is the An example in programming languages is the An example in programming languages is the An example in programming languages is the "dangling else""dangling else""dangling else""dangling else"if A then if B then C else Dif A then if B then C else Dif A then if B then C else Dif A then if B then C else DIs thisIs thisIs thisIs thisif A then (if B then C else D)if A then (if B then C else D)if A then (if B then C else D)if A then (if B then C else D)ororororif A then (if B then C) else Dif A then (if B then C) else Dif A then (if B then C) else Dif A then (if B then C) else D????Sometimes it is possible to rewrite the grammar Sometimes it is possible to rewrite the grammar Sometimes it is possible to rewrite the grammar Sometimes it is possible to rewrite the grammar productions to eliminate