dangling-else

The Dangling Else Problem

General

Original grammar:

S -> if E then S
S -> if E then S else S
S -> T

Now:

S -> if E then S
S -> if E then L else S
L -> if E then L else L
L -> T

• Insights
  • Think of L as limited, in that L rule must have an else.
  • We now require the statement in the middle must have an else paired with it.
  • Otherwise, if the statement in the middle can have no else, the else can be assigned to the if at the very beginning!
  • For any rules that have S on the LHS, create another version with L on the LHS.

B-Minor

Code snippet from Bison grammar file for B-Minor compiler.

stmt : open_stmt | closed_stmt ;
 
open_stmt   : if_stmt_open   | for_stmt_open ;
closed_stmt : if_stmt_closed | for_stmt_closed | simple_stmt ;
 
if_stmt_open   : if_cond stmt |
                 if_cond closed_stmt TOKEN_ELSE if_stmt_open
if_stmt_closed : if_cond closed_stmt TOKEN_ELSE closed_stmt
 
for_stmt_open   : for_header open_stmt
for_stmt_closed : for_header closed_stmt

Mid-Term

This problem appears in mid-term. Simplified.

P -> S
S -> id = R
R -> R ^ R
R -> int

Solution:

P -> S
S -> id = R
R -> L ^ R
L -> int
R -> int