Solving dangling if, elsif, and else in Bison without associativity declarations

Question

I am implementing a parser for a language that has if-elsif-else statements and can't seem to make my grammar unambiguous. Our compilers class was given a handout on solving the dangling else problem for if-else statements using a match/unmatched approaches as follows:

%token IF EXP ELSE XX

stmts: stmts stmt ';'
     | stmt ';' 
     ; 

stmt : matched
     | unmatched
     ;

matched: IF '(' EXP ')' matched ELSE matched
      | XX
      ;

unmatched : IF '(' EXP ')' matched 
      | IF '(' EXP ')' unmatched
      | IF '(' EXP ')' matched ELSE unmatched
      ;

The grammar documentation provided for our language is defined to have productions involving if - elsif- else where:

selectionStmt → IF simpleExpression THEN statement elsifList 
      | IF simpleExpression THEN statement elsifList ELSE statement

elsifList → elsifList ELSIF simpleExpression THEN statement
      | *empty*

where the lowercase words are productions and the uppercase are terminals.

These provided productions are ambiguous and have to be solved in the grammar implementation in bison. Here is the progress I've made on actually implementing it into Bison:

statement: stmtMatched
     | selectionStmtUnmatched

elsifList: elsifList ELSIF simpleExpression THEN statement
     | %empty

stmtMatched: IF simpleExpression THEN stmtMatched elsifList ELSE 
stmtMatched
       | otherStatement

selectionStmtUnmatched: IF simpleExpression THEN statement elsifList
       | IF simpleExpression THEN stmtMatched elsifList ELSE 
selectionStmtUnmatched

otherStatement: expressionStmt
          | compoundStmt
          | iterationStmt
          | returnStmt
          | breakStmt

Any suggestions on changing the grammar to accommodate the elsif productions similarly to using matched and unmatched statements to solving the dangling if-else problem and get rid of any shift/reduce and reduce/reduce errors?

Edit 1: I've made more progress on a simpler version of the grammar to ensure that elsifLists can only follow matched statements:

stmt: matched
| unmatched

matched: IF '(' EXP ')' THEN matched elsifList ELSE matched
   | %empty

unmatched: IF '(' EXP ')' THEN matched elsifList
     | IF '(' EXP ')' THEN unmatched
     | IF '(' EXP ')' THEN matched elsifList ELSE unmatched

elsifList: elsifList ELSIF EXP THEN stmt
     | %empty

But I am still getting shift/reduce conflicts:

State 12

    3 matched: IF '(' EXP ')' THEN matched elsifList . ELSE matched
    5 unmatched: IF '(' EXP ')' THEN matched elsifList .
    7          | IF '(' EXP ')' THEN matched elsifList . ELSE unmatched
    8 elsifList: elsifList . ELSIF EXP THEN stmt

    ELSE   shift, and go to state 13
    ELSIF  shift, and go to state 14

    ELSE      [reduce using rule 5 (unmatched)]
    ELSIF     [reduce using rule 5 (unmatched)]
    $default  reduce using rule 5 (unmatched)

Edit 2: I've made enough progress with the simple grammar to ensure that elsif statements are preceeded by matched statements. The resulting grammar is:

stmt: matched
    | unmatched

matched: IF '(' EXP ')' THEN matched elsifList ELSE matched
       | %empty

unmatched: IF '(' EXP ')' THEN matched elsifList
         | IF '(' EXP ')' THEN unmatched
         | IF '(' EXP ')' THEN matched elsifList ELSE unmatched

elsifList: elsifList ELSIF EXP THEN matched
         | %empty

I've updated the actual grammar for the parser for the actual language to ensure that unmatched statements can not be followed by an elsifList and that elsifLists can only be followed by matched statements:

statement :     stmtMatched |
                selectionStmtUnmatched
                ;


otherStatement : expressionStmt 
                | compoundStmt 
                | iterationStmt 
                | returnStmt
                | breakStmt
                ;

elsifList :     elsifList ELSIF simpleExpression THEN stmtMatched 
                | %empty
                ;

stmtMatched : IF simpleExpression THEN stmtMatched elsifList ELSE stmtMatched
            | otherStatement
            ;

selectionStmtUnmatched : IF simpleExpression THEN stmtMatched elsifList
                | IF simpleExpression THEN selectionStmtUnmatched 
                | IF simpleExpression THEN stmtMatched elsifList ELSE selectionStmtUnmatched

The resulting grammar is still giving me 2 shift/reduce conflicts though:

State 164

   44 elsifList: elsifList . ELSIF simpleExpression THEN stmtMatched
   46 stmtMatched: IF simpleExpression THEN stmtMatched elsifList . ELSE stmtMatched
   48 selectionStmtUnmatched: IF simpleExpression THEN stmtMatched elsifList .
   50                       | IF simpleExpression THEN stmtMatched elsifList . ELSE selectionStmtUnmatched

   ELSIF  shift, and go to state 167
   ELSE   shift, and go to state 168

   ELSIF     [reduce using rule 48 (selectionStmtUnmatched)]
   ELSE      [reduce using rule 48 (selectionStmtUnmatched)]
   $default  reduce using rule 48 (selectionStmtUnmatched)

rici rici · Accepted Answer · 2020-02-15T23:53:37

The grammar in your handout does not allow an unmatched statement before an else. Why is that?

It's because the else must bind to the closest not-yet-matched if. You might want to try doing a few parse trees by hand to understand how this works. The essential point is that inside the unmatched statement, there is an unmatched if which the else should bind to. So the ambiguity can be removed by removing the possibility of skipping over that unmatched if.

Now, what changes when we add elsif? Not much. Both elsif and else must bind to the closest not-yet-matched if or elsif. And the way of guaranteeing that is exactly the same as the simple case. We need to ensure that the statement before the elsif is matched.

But your grammar only requires that the statement before the first elsif be matched. So ambiguities remain.

As a hint: the fix is very simple. You just need to do the grouping differently.

Solving dangling if, elsif, and else in Bison without associativity declarations

1 Answers