How to solve the shift / reduction conflict?

Question

I use CUP to create the parser that I need for my dissertation. I have a shift / reduction conflict in my grammar. I have this 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 really wanted him to move, so I'm fine with him, but my professor told me to find a way to resolve the conflict. I am blind. I have always read about the if / else conflict, but it doesn’t seem like to me. Can you help me?

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

Answer 1

Your problem is not with these rules at all. Although Michael Mrozek is responding to the right approach to resolving "problems with the dangling others," he does not understand the problem.

If you look at the error message, you will see that a shift / decrease conflict is present during LPAREN lexing . I am sure that only the rules will not create conflict.

I do not see your grammar, so I can not help you. But your conflict probably occurs when command followed by another rule starting with LPAREN .

Look at any other rules that could potentially be after command and begin with LPAREN . Then you have to consolidate the rules. There is a very good chance that your grammar is wrong for a specific input.

Answer 2

You have two productions:

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

This is a shift / decrease conflict when IDENTIFIER LPAREN input tokens, because:

• LPAREN may be the beginning of a new release that you have not yet specified, in which case the analyzer should reduce the IDENTIFIER already on the stack to command and leave command LPAREN
• Both of them can be the beginning of the second production, so he should push LPAREN the stack next to IDENTIFIER and continue reading, trying to find the parlist .

You can fix this by doing something like this:

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

Answer 3

Try setting priority:

 precedence left LPAREN, RPARENT; 

It forces the CUP to resolve the conflict by accepting a left match.