How to solve a shift/reduce conflict?

Question

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.

Epicenter

Answer 1

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.

Sylviesylvite

Yeah, you're rigth. The problem was in the line above this one. I've solved this problem 4 days ago. I've forgot to update the question. – Epicenter

Answer 2

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

Irritate

Thanks, but I'm having the same shift/reduce conflict even with this solution. I'm not having syntax errors so I'm pretty sure CUP doesn't use some weird "empty symbol" but I'm checking for it. – Epicenter

Answer 3

Try to set a precedence:

precedence left     LPAREN, RPARENT;

It forces CUP to decide the conflict, taking the left match.

Endomorphic