Ambiguity


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:

  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.