How to solve a shift/reduce conflict?
I'm using CUP to开发者_如何学C 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.
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.
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 theIDENTIFIER
already on the stack intocommand
, and havecommand LPAREN
remaining- They could both be the start of the second production, so it should shift the
LPAREN
onto the stack next toIDENTIFIER
and keep reading, trying to find aparlist
.
You can fix it by doing something like this:
command ::= IDENTIFIER command2
command2 ::= LPAREN parlist RPAREN |;
Try to set a precedence:
precedence left LPAREN, RPARENT;
It forces CUP to decide the conflict, taking the left match.
精彩评论