How to solve a shift/reduce conflict?

Question

Hi, 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
  Resolved in favor of shifting.

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 1

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 |;

Answer 2

Your problem is not in those rules at all. Although Michael Mrozek answer is correct approach to resolving the "dangling else problem", it does not grasp the problem at hand.

If you look at the error message, you see that the shift / reduce conflict is present when lexing LPAREN. I am pretty sure that the rules alone will not create a conflict.

I can't see your grammar, so I can't help you. But your conflict is probably when a command is followed by a different rule that start with a LPAREN.

Look at any other rules that can potentially be after command and start with LPAREN. You will then have to consolidate the rules. There is a very good chance that your grammar is erroneous for a specific input.