《编译原理》课程教学资源：第二章（2-4-1）One parse tree only

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