Slide 3.3: Ambiguity (cont.)

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:

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

The presence of the else-part is required.

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;