Example 7

Consider the following grammar for IF-THEN-ELSE statements:


        S -- > IF b THEN S ELSE S
             |IF b THEN S 
  
             |a

where b represents a boolean condition and a represents some other statements. Then

  IF b THEN IF b THEN a ELSE a

has two parse trees.

The second parse, with ELSE associated with the closest IF is considered the way this should be parsed.

We can rewrite this grammar to be unambiguous:


 
 
 S1 -- > IF b THEN S1 | IF b THEN S2 ELSE S1 | a
 S2 -- > IF b THEN S2 ELSE S2 | a