Context-Free Grammars (Cont.)


Ambiguity (Cont.)
Consider the dangling else problem:
if (0)  if (1) other  else other
Two parse trees can be built for the above statement. It is the ambiguity of association of the else-part with the first if-statement or the second if-statement. Most languages apply the most closely nested rule:
if (0) { if (1) other  else other }
which “matches each else with the closest unmatched then.” There are three ways to solve the ambiguity:
  1. Rewrite the grammar:
     <statement> ::= <if-stmt> | <other>
     <if-stmt> ::= if ( <exp> ) <statement>
        | if ( <exp> ) <statement> else <statement>
     <exp> ::= 0 | 1 
                  ⇓
     <statement> ::= <matched-stmt> | <unmatched-stmt>
     <matched-stmt> ::= if ( <exp> ) <matched-stmt> else 
        <matched-stmt> | <other>
     <unmatched-stmt> ::= if ( <exp> ) <statement>
        | if ( <exp> ) <matched-stmt> else <unmatched-stmt>
     <exp> ::= 0 | 1
  2. The presence of the else-part is required.

  3. Use a bracketing keyword, for example,
       if x ≠ 0  then
          if y = 1/x  then ok := true;
          else z := 1/x;
          end if;
       end if;