Slide 3.2: Ambiguity (cont.)

Context-Free Grammars (Cont.)

Ambiguity (Cont.)
Two basic methods are used to deal with ambiguities:

A disambiguating rule specifies in each ambiguous case which of the parse trees is the correct one.
Change the grammar into a form that forces the construction of the correct parse tree, thus removing the ambiguity.

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