Removing Ambiguity
Removing Ambiguity
One parse tree only The role of the grammar a distinguish between syntactically legal and illegal programs a But that' s not enough it must also define a parse tree a the parse tree conveys the meaning of the program What if a string can be parsed with multiple parse trees? a we say the grammar is ambiguous a must fix the grammar ( the problem is not in the parser a Note: often a string can be derived in more than one way D ie, with more than one derivation sequence a this does not mean the grammar is ambiguous
One parse tree only! ◼ The role of the grammar distinguish between syntactically legal and illegal programs ◼ But that’s not enough: it must also define a parse tree the parse tree conveys the meaning of the program ◼ What if a string can be parsed with multiple parse trees? we say the grammar is ambiguous must fix the grammar (the problem is not in the parser) ◼ Note: often a string can be derived in more than one way ie, with more than one derivation sequence this does not mean the grammar is ambiguous 2
Ambiguity: EXample ■ Grammar EE+EeE(E)int ■ Strings nt int int nt x int int
3 Ambiguity: Example ◼ Grammar E E + E | E * E | ( E ) | int ◼ Strings int + int + int int * int + int
Ambiguity. EXample This string has two parse trees E E E E t E E +E int int e+ E int int int int +is left-associative
4 Ambiguity. Example This string has two parse trees E E E E + E int + int int E E E E + E + int int int + is left-associative
Ambiguity. EXample This string has two parse trees E E E E E E *E int int e+ E int int int int has higher precedence than
5 Ambiguity. Example This string has two parse trees E E E E * E int + int int E E E E + E int * int int * has higher precedence than +
Ambiguity( Cont) aA grammar is ambiguous D if it has more than one parse tree for any string ■ Ambiguity is bad lEaves meaning of some programs ill-defined Ambiguity is common in programming languages D Arithmetic expressions 口|F-THEN-ELSE
6 Ambiguity (Cont.) ◼ A grammar is ambiguous if it has more than one parse tree for any string ◼ Ambiguity is bad Leaves meaning of some programs ill-defined ◼ Ambiguity is common in programming languages Arithmetic expressions IF-THEN-ELSE
Dealing with Ambiguity There are two ways to remove ambiguity 1)Rewrite the grammar into a unambiguous grammar EE+T T TT*int int I(E) 口 Enforces precedence(优先级)of*over+ 口 Enforces left- associativity(左结合)of+and* 2) Declarations: instruct parser to pick desired parse trees a using %left, %right, %prec declarations
7 Dealing with Ambiguity There are two ways to remove ambiguity: 1) Rewrite the grammar into a unambiguous grammar E E + T | T T T * int | int | ( E ) Enforces precedence（优先级） of * over + Enforces left-associativity（左结合） of + and * 2) Declarations: instruct parser to pick desired parse trees using %left, %right, %prec declarations
Ambiguity. EXample The int* int+ int has on one parse tree now E+ T E t e nt int int int
8 Ambiguity. Example The int * int + int has ony one parse tree now E E E E * E int + int int E T T int + T int * E int
Rewriting the grammar: what's the trick? Trick 1: Fixing precedence( computed before + EE+E IE*E I id/ a In the parse tree for id+ id *id, we want id*id to a Create a new nonterminal(m//t by be subtree of E+E. How to accomplisk-that rewriting make it deriⅳ eid*id, T|7 ensureS trees are nested in Es of E+E I ■ New grammar
Rewriting the grammar: what’s the trick? Trick 1: Fixing precedence (* computed before +) E E + E | E * E | id ◼ In the parse tree for id + id * id, we want id*id to be subtree of E+E. How to accomplish that by rewriting? ◼ Create a new nonterminal (T) make it derive id*id, … ensure T’s trees are nested in E’s of E+E ◼ New grammar: 9
Rewriting the grammar: what's the trick?(part 2) Trick 2: Fixing associativity(+, associate to the left) EE+ET TT*T id a In the parse tree for id+ id id, we want tha left id+id to be subtree of the right E+idE TSafhe for id"id "id ■ Use left! recursion a it will ensure that + *associate to theeftid +id a New grammar (a simple change)
Rewriting the grammar: what’s the trick? (part 2) Trick 2: Fixing associativity (+, *, associate to the left) E E + E | T T T * T | id ◼ In the parse tree for id + id + id, we want the left id+id to be subtree of the right E+id. Same for id*id*id. ◼ Use left recursion it will ensure that +, * associate to the left ◼ New grammar (a simple change): 10