Slide 3.2: Ambiguity (cont.)
Slide 3.4: Abstract syntax
Home

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;