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 +