How to solve a shift/reduce conflict?

dierre picture dierre · Jul 2, 2010 · Viewed 25.2k times · Source

I'm using CUP to create a parser that I need for my thesis. I have a shift/reduce conflict in my grammar. I have this production rule:

command ::= IDENTIFIER | IDENTIFIER LPAREN parlist RPAREN;

and I have this warning:

Warning : *** Shift/Reduce conflict found in state #3
between command ::= IDENTIFIER (*) 
and     command ::= IDENTIFIER (*) LPAREN parlist RPAREN 
under symbol LPAREN

Now, I actually wanted it to shift so I'm pretty ok with it, but my professor told me to find a way to solve the conflict. I'm blind. I've always read about the if/else conflict but to me this doesn't seem the case. Can you help me?

P.S.: IDENTIFIER, LPAREN "(" and RPAREN ")" are terminal, parlist and command are not.

Answer

Michael Mrozek picture Michael Mrozek · Jul 2, 2010

You have two productions:

command ::= IDENTIFIER
command ::= IDENTIFIER LPAREN parlist RPAREN;

It's a shift/reduce conflict when the input tokens are IDENTIFIER LPAREN, because:

  • LPAREN could be the start of a new production you haven't listed, in which case the parser should reduce the IDENTIFIER already on the stack into command, and have command LPAREN remaining
  • They could both be the start of the second production, so it should shift the LPAREN onto the stack next to IDENTIFIER and keep reading, trying to find a parlist.

You can fix it by doing something like this:

command ::= IDENTIFIER command2
command2 ::= LPAREN parlist RPAREN |;