Context-Free Grammars (Cont.)


Ambiguity (Cont.)
Two basic methods are used to deal with ambiguities: In general, removing the ambiguity is to rewrite the grammar rather than stating disambiguating rules. Also, the new grammar does not change the basic strings being recognized. Consider the ambiguous grammar again:

The ambiguity is removed by including the precedence information first and left association next. Two parse trees are generated by using the final unambiguous grammar as follows:
<exp> ::= <exp> <op> <exp> | ( <exp> ) | number 
<op>  ::= + |  | * 
       ⇓   Precedence cascade
<exp> ::= <exp> <addop> <exp> | <term>
<addop> ::= + | 
<term> ::= <term> <mulop> <term> | <factor>
<mulop> ::= *
<factor> ::= ( <exp> ) | number 
       ⇓   Left associative
<exp> ::= <exp> <addop> <term> | <term>
<addop> ::= + | 
<term> ::= <term> <mulop> <factor> | <factor>
<mulop> ::= * 
<factor> ::= ( <exp> ) | number