Problem Solving in Automata, Languages, and Complexity

114 CONTEXT-FREE LANGUAGES

if

Figure 3.7: Another parse tree for (xf.

(a) (b)

Figure 3.8: Two parse trees for a + a * a.

Example 3.24 (a) Sh ow that the following context-free grammar G for arith~
metic expressions over variables a and b is ambiguous:

E,-kE+EIE-EIE*EIE+Ej(E)IaIb.

(b,J Find an e~uivaZe~t unambiguous grammar for L(G).

Solution. (a) The expression a + a a has two pa.rse trees, as shown in Figure
3.8. Note that the two parse trees have different semantic interpretations. If
we evaluate the expression following the order given by the parse tree, then
the first tree Figure 3.8(a) gives us a + a a = a + (a a) = a + a2? and the
second tree Figure 3.8(b) gives us a + a a = (a + a) a = 2a2.
(b) Usually, ambiguity comes from ~araZ~eZ substitutions for a nonterminal
symbol in a sentential form. For instance, in grammar G, E can be replaced by
either E + E or E E, and each sentential form can derive E + E * E. To avoid
this problem, we use different nonterminal symbols to represent operands of
different operators. In the following, we use symbol T (standing for term) to