Trying to Resolve Shift Reduce Conflicts by Changing Grammar

Question

Given the following specification for a grammar:

Statement → { Statement* }
      → VarDecl
      → if ( Exp ) Statement else Statement
      → while ( Exp ) Statement
      → System.out.println ( Exp ) ;
      → id = Exp ;
      → id [ Exp ]= Exp ;

These are the rules I've come up with to use in a YACC/BISON program. I have Shift/Reduce Conflicts though.

StatementList:
    '{' StatementList Statement '}'
     |  Statement
     ;

Statement: 
    |   VarDecl
    |   IF '('Exp')' StatementList ELSE StatementList
    |   WHILE'('Exp')' StatementList
    |   SOP'('Exp')' ';'
    |   ID '=' Exp ';'
    |   ID'['Exp']' '=' Exp';'
    ;

Also tried this grammar:

CompoundStatement:
        '{' StatementList '}'

StatementList:
    StatementList Statement
    |   Statement
    ;

Statement: 
    |   VarDecl
    |   IF '('Exp')' Statement ELSE Statement
    |   WHILE'('Exp')' Statement
    |   SOP'('Exp')' ';'
    |   ID '=' Exp ';'
    |   ID'['Exp']' '=' Exp';'
    |   CompoundStatement
    ;

Did not work either. Still had conflicts. (Though this passed the testcases I'd set up)

And neither did this:

StatementList
     : %empty /* Explicit empty production, bison 3.0+ */
     | StatementList Statement

Statement
     : '{' StatementList '}'
     | IF '('Exp')' Statement ELSE Statement
     | /* ... and the rest of the statements */

Any help?

My solution is conflict-free when I try it. Did you remember to change StatementList to Statement in the WHILE statement? Otherwise, there is something going on in the declaration of VarDecl or Exp, which are not shown in your question. — rici
Oh, and your second attempt also has an empty production for Statement. That's ambiguous in a StatementList because you don't know how many empty Statements an empty StatementList comprises. — rici

rici rici · Accepted Answer · 2015-10-02T02:16:34

You have an empty production for Statement. You probably didn't intend to; you certainly don't need to; and it is probably the cause of your conflicts.

Your production for blocks is wrong. You need to define StatementList in order to implement Statement*, and then follow through with your original grammar:

StatementList
     : %empty /* Explicit empty production, bison 3.0+ */
     | StatementList Statement

Statement
     : '{' StatementList '}'
     | IF '('Exp')' Statement ELSE Statement
     | /* ... and the rest of the statements */

Trying to Resolve Shift Reduce Conflicts by Changing Grammar

1 Answers