A grammar can be used to define associativity and precedence among the operators in an expression. A grammar is ambiguous if one of its strings has two or more diffferent parse trees. Chapter 2b provides knowledge of grammars: Associativity and precedence, ambiguous grammars. | Programming Languages 2nd edition Tucker and Noonan Chapter 2 Syntax A language that is simple to parse for the compiler is also simple to parse for the human programmer. N. Wirth Contents Grammars Backus-Naur Form Derivations Parse Trees Associativity and Precedence Ambiguous Grammars Extended BNF Syntax of a Small Language: Clite Lexical Syntax Concrete Syntax Compilers and Interpreters Linking Syntax and Semantics Abstract Syntax Abstract Syntax Trees Abstract Syntax of Clite Associativity and Precedence A grammar can be used to define associativity and precedence among the operators in an expression. ., + and - are left-associative operators in mathematics; * and / have higher precedence than + and - . Consider the more interesting grammar G1: Expr -> Expr + Term | Expr – Term | Term Term -> Term * Factor | Term / Factor | Term % Factor | Factor Factor -> Primary ** Factor | Primary Primary -> 0 | . | 9 | ( Expr ) Parse of 4**2**3+5*6+7 for Grammar G1 Figure Precedence Associativity Operators 3 right ** 2 left * / % 1 left + - Note: These relationships are shown by the structure of the parse tree: highest precedence at the bottom, and left-associativity on the left at each level. Associativity and Precedence for Grammar G1 Table Ambiguous Grammars A grammar is ambiguous if one of its strings has two or more diffferent parse trees. ., Grammar G1 above is unambiguous. C, C++, and Java have a large number of operators and precedence levels Instead of using a large grammar, we can: Write a smaller ambiguous grammar, and Give separate precedence and associativity (., Table ) An Ambiguous Expression Grammar G2 Expr -> Expr Op Expr | ( Expr ) | Integer Op -> + | - | * | / | % | ** Notes: G2 is equivalent to G1. ., its language is the same. G2 has fewer productions and nonterminals than G1. However, G2 is ambiguous. Ambiguous Parse of 5-4+3 Using Grammar | Programming Languages 2nd edition Tucker and Noonan Chapter 2 Syntax A language that is simple to parse for the compiler is also simple to parse for the human programmer. N. Wirth Contents Grammars Backus-Naur Form Derivations Parse Trees Associativity and Precedence Ambiguous Grammars Extended BNF Syntax of a Small Language: Clite Lexical Syntax Concrete Syntax Compilers and Interpreters Linking Syntax and Semantics Abstract Syntax Abstract Syntax Trees Abstract Syntax of Clite Associativity and Precedence A grammar can be used to define associativity and precedence among the operators in an expression. ., + and - are left-associative operators in mathematics; * and / have higher precedence than + and - . Consider the more interesting grammar G1: Expr -> Expr + Term | Expr – Term | Term Term -> Term * Factor | Term / Factor | Term % Factor | Factor Factor -> Primary ** Factor | Primary Primary ->
