Problem Solving in Automata, Languages, and Complexity

3.3 Parsing and Ambiguity

I I

Figure 3.6: A parse tree for X.

Example 3.23 Consider the following grammar G, in which a word of the
form ( l. l ) denotes a nonterminal, and other words denote terminals:

(stmt) + if (cond) then (matchstmt) 1 (matchstmt)

(matchstmt) + if ( cond) then (matchstmt) else (stmt) 1 (simplestmt)

(con~)+G I c2 I c3

(simplestmt) + Al 1 A2 1 As.

Let x be the sentence

if Cl then if C2 then Al else if C3 then A2 else A3.

Find two different parse trees for x.

Solution. We show two parse trees for x in Figure 3.6 and Figure 3.7. They
imply two different syntactic structures of the sentence x and, hence, two
different semantic interpretations of x. For instance, if condition Cl is false
then, in the first parse tree (a), none of the simple statement Al, A2 or A3
will be executed, while in the second parse tree (b), A3 is to be executed.^0

From the above example, we can see that if a context-free grammar is
ambiguous, then it would be difficult to determine the meaning of the sentence
from its different parse trees. Therefore, it is desirable to design unambiguous
grammars whenever it is possible. In the following two examples, we show how
to modify an ambiguous grammar into an equivalent unambiguous grammar.