Where is the shift/reduce conflict in this yacc grammar?

Question

I'm writing a parser for a language called C-. I have to write the grammar so its not ambiguous and I can't use any %prec statements in Bison. I've corrected all but 1 shift/reduce conflict and I can't figure out where it is. Any ideas? My .output file gives the following info for where its occurring:

State 163

   44 matched: IF '(' simpleExp ')' matched . ELSE matched
   46 unmatched: IF '(' simpleExp ')' matched .
   48          | IF '(' simpleExp ')' matched . ELSE unmatched

    ELSE  shift, and go to state 169

    ELSE      [reduce using rule 46 (unmatched)]
    $default  reduce using rule 46 (unmatched)

The grammar:

stmt                : selectStmt
                    ;

expStmt             : exp ';'
                    | ';'

compoundStmt        : '{' localDecls stmtList '}'
                    ;  

stmtList            : stmtList stmt
                    |
                    ;

otherStmt           : compoundStmt
                    | expStmt
                    | iterStmt
                    | returnStmt
                    | breakStmt
                    ;     

localDecls          : localDecls scopedVarDecl
                    |
                    ;

selectStmt          : matched
                    | unmatched
                    ;
                
matched             : IF '(' simpleExp ')' matched ELSE matched
                    | otherStmt
                    ;

unmatched           : IF '(' simpleExp ')' matched
                    | IF '(' simpleExp ')' unmatched
                    | IF '(' simpleExp ')' matched ELSE unmatched
                    ;
                    
iterStmt            : WHILE simpleExp DO selectStmt
                    | FOR ID '=' iterRange DO selectStmt
                    ;

iterRange           : simpleExp
                    | simpleExp TO simpleExp
                    | simpleExp TO simpleExp BY simpleExp
                    ;

returnStmt          : RETURN ';'
                    | RETURN exp ';'
                    ;

breakStmt           : BREAK ';'
                    ;

The matched/unmatched is supposed to eliminate the dangling else problem. If I remove that statement, there would be no way to have an unmatched if statement after a matched if else. So "if else if" would be impossible — Connor Williams

rici rici · Accepted Answer · 2021-02-04T22:40:55

The problem is that it is not only if statements which can be "matched". An iteration statement which ends with an unmatched statement is just as unmatched as an if statement which ends with an unmatched statement. That's what "matched" means.

So you have to divide your iterative statements into matched and unmatched variants. (This is why most people use precedence or expect declarations to deal with dangling else.)

Here's a simple example in case it becomes useful in the future. (Many of the non-terminals haven't been changed, so their definitions have been omitted. I also expanded a lot of abbreviations.)

statement: matched
         | unmatched
/* Statements which could have been extended with an else clause,
 * but haven't been. An unmatched statement can be the body of an
 * unmatched compound statement, which includes an `if` statement
 * whose `else` clause is unmatched. Unmatched also includes `if`
 * statements without an `else` clause.
 */
unmatched: "if" '(' simpleExp ')' statement
         | "if" '(' simpleExp ')' matched "else" unmatched
         | "while" '(' simpleExp ')' "do" unmatched
         | "for" IDENT '=' iterRange "do" unmatched
/* Statements which cannot be extended with an else clause.
 * In other words, in a `matched` every `else` matches some `if`.
 * Only `matched` statements can come between `if` and `else`, because
 * an unmatched statement would grab the `else` for itself.
 */
matched  : "if" '(' simpleExp ')' matched "else" matched
         | "while" '(' simpleExp ')' "do" matched
         | "for" IDENT '=' iterRange "do" matched
         | expStatement
         | returnStatement
         | breakStatement
         | '{' localDeclarations statementList '}'

Where is the shift/reduce conflict in this yacc grammar?

1 Answers