Parsing - Introduction to Compiler Construction in a Java World - page 68

or multiplication? From our math days, we would like the multiplication operator * to be
more binding than the addition operator + . Notice that the grammar in (3.11) does not
capture this precedence of operators in the way that the grammar in (3.9) does.

Example. As another example, consider the grammar describing conditional statements

S ::= if( E ) S
j if( E ) S else S
j s
E ::= e

(3.12)

Here, the token e represents an arbitrary expression and the s represents a (non-
conditional) statement.
Consider the sentence

if(e)if(e)selses

(3.13)

If we look at this sentence carefully, we see that it nests one conditional statement within
another. One might ask: To which if does the else belong? We cannot know; the sentence
is ambiguous. More formally, there exist two left-most derivations for this sentence:

S ) if( E ) S else S
) if(e) S else S
) if (e) if( E ) S else S
) if (e) if(e) S else S
) if(e)if(e)selse S
) if(e)if(e)selses

and

S ) if( E ) S
) if(e) S
) if(e)if( E ) S else S
) if(e)if(e) S else S
) if(e)if(e)selse S
) if(e)if(e)selses

The two differing parse trees in Figure 3.4 for the same sentence (3.13) also demonstrate
ambiguity.

FIGURE 3.4 Two parse trees for if(e)if(e)selses .