A grammar is ambiguous if two or more different parse trees can be desire
the same token string. Equivalently, an ambiguous grammar allows two different
derivations for a token string.
Grammar for complier should be unambiguous since different parse trees will give
a token string different meaning.
Consider the following grammar
string → string + string
| string - string
| 0 | 2 | . . . | 9
To show that a grammar is ambiguous all we need to find a "single" stringthat has more than one perse tree.
Figure:23 --- pg.31
Above figure show two different parse trees for the token string 9 - 5 + 2 that corresponds to two different way of parenthesizing the expression:
( - 5) + 2 and 9 -(5 + 2).
The first parenthesization evaluates to 2.
Perhaps, the most famous example of ambiguity in a programming language is the dangling 'ELSE'.
Consider the grammar G with the production:
S → IF b THEN S ELSE S
| IF b THEN S
| a
G is ambiguous since the sentence
IF b THEN IF b THEN a ELSE a
has two different parse trees or derivation trees.
Parse tree I
figure
This parse tree imposes the interpretation
IF b THEN (IF b THEN a ) ELSE a
Parse Tree II
Figure
This parse tree imposes the interpretation
IF b THEN (IF b THEN a ELSE a)
The reason that the grammar G is ambiguous is that an 'ELSE' can be associated with two different THENs. For this reason, programming languages which allows both IF-THEN-ELSE and IF-THEN constant can be ambiguous.
