Bison shift-reduce conflict - Unable to resolve

Question

The grammar is as follows:

1. program -> declaration-list
2. declaration-list -> declaration-list declaration | declaration
3. declaration -> var-declaration | fun-declaration
4. var-declaration -> type-specifier ID ; | type-specifier ID [ NUM ] ;
5. type-specifier -> int | void
6. fun-declaration -> type-specifier ID ( params ) compound-stmt
7. params -> param-list | void
8. param-list -> param-list , param | param
9. param -> type-specifier ID | type-specifier ID [ ]
10. compound-stmt -> { local-declarations statement-list }
11. local-declarations -> local-declarations var-declarations | empty
12. statement-list -> statement-list statement | empty
13. statement -> expression-stmt | compound-stmt | selection-stmt |
iteration-stmt | return-stmt
14. expression-stmt -> expression ; | ;
15. selection-stmt -> if ( expression ) statement |
if ( expression ) statement else statement
16. iteration-stmt -> while ( expression ) statement
17. return-stmt -> return ; | return expression ;
18. expression -> var = expression | simple-expression
19. var -> ID | ID [ expression ]
20. simple-expression -> additive-expression relop additive-expression |
additive-expression
21. relop -> <= | < | > | >= | == | !=
22. additive-expression -> additive-expression addop term | term
23. addop -> + | -
24. term -> term mulop factor | factor
25. mulop -> * | /
26. factor -> ( expression ) | var | call | NUM
27. call -> ID ( args )
28. args -> arg-list | empty
29. arg-list -> arg-list , expression | expression

The shift reduce conflict that I get through bison -d -v xyz.l is in state 97

state 97

   29 selection-stmt: IF LFT_BRKT expression RGT_BRKT statement .
   30               | IF LFT_BRKT expression RGT_BRKT statement . ELSE statement

    ELSE  shift, and go to state 100

    ELSE      [reduce using rule 29 (selection-stmt)]
    $default  reduce using rule 29 (selection-stmt)

But I do not know how to resolve this conflict. Waiting for an answer.

Reinert

Answer 1

You would want to resolve the conflict in favour of shifting the 'else'. Fortunately, bison has done that for you automatically (but it still lets you know about it.)

Section 5.2 of the Bison manual is about precisely this shift/reduce conflict. As it says there, you can eliminate the warning message if you want to with a %expect declaration. Alternatively, you can explicitly declare the "prefer to shift the else" resolution by using bison/yacc's precedence declarations: give the else token a higher precedence than the if productions without an else clause. (You'll probably want to use something like %prec IF in the productions themselves, because by default a production has the precedence of its last terminal, which in this case will be a right parenthesis.)

This specific shift/reduce conflict was a large part of the motivation for the resolution strategy of the original yacc parser-generator, as described in the historic paper on yacc, or in the Dragon book, because it is somewhat annoying to eliminate the conflict from a grammar. The solution to this question is a nice brain-teaser, but in practice it is usually easier and more maintainable to use the precedence declaration or Bison's built-in ambiguity elimination.

This problem is one of the exercises in the Dragon book. The basic outline of the solution goes like this:

1. There would not be an issue if the statement in if (expression) statement could not be an if statement. else cannot begin a statement, so if ( 0 ) break; cannot be reduced with else in the lookahead. The problem is if (0) if (0) break; else Now, it's not obvious whether else should be shifted (and thereby attached to the second if) or if the second if should be reduced, leaving the else to be shifted onto the first if. Normal practice (and yacc's ambiguity resolution algorithm) dictate the first.

2. So let's distinguish between complete if-statements and incomplete if-statements. An incomplete if-statement is a statement which could have been completed with an else clause, and so it cannot be immediately followed by else (since it would have included the else). A complete statement cannot be extended with an else, so it also must not end with an incomplete statement.

So we can try something like:

statement              : complete_statement
                       | incomplete_conditional

complete_statement     : complete_conditional
                       | statement_other_than_conditional

complete_conditional   : "if" '(' expression ')' complete_statement "else" complete_statement

incomplete_conditional : "if" '(' expression ')' statement
                       | "if" '(' expression ')' complete_statement "else" incomplete_conditional

Languages like C have other statement types which can end with enclosed statements (looping statements, for example). All of those also have to be divided between "complete" and "incomplete", depending on the completeness of the terminating statement. That's what makes this solution annoying.

Note: The above grammar has been corrected from the incorrect version posted nine years ago. Several answers refer to the incorrect answer; unfortunately, none of them thought to signal the error with a comment which I might see. I apologise if anyone used the incorrect code.

Griffie

Thank you for your answer. But I want to know how do I change the grammar to remove the conflict, rather than just ignoring it. – Reinert

Also tell me how do we know which action bison takes by default? You are saying that it has been taken in the favour of shifting the else, but i see the reduction in the dafault. Please help – Reinert

@user1506031: "This situation, where either a shift or a reduction would be valid, is called a shift/reduce conflict. Bison is designed to resolve these conflicts by choosing to shift, unless otherwise directed by operator precedence declarations." (From the page I linked to in my answer.) The eliminated reduction is in brackets, indicating that it has been overridden. (At least, I'm pretty sure that's what those brackets mean.) – Griffie

I am not able to get your grammar. Please explain. Can you provide a grammar for the code selection-stmt -> if ( expression ) statement | if ( expression ) statement else statement – Reinert

Answer 2

See my answer here: Reforming the grammar to remove shift reduce conflict in if-then-else. In my experience, you should never leave "known conflicts", solve them. Using %expect N with N != 0 is not safe, IMHO (GLR aside, of course).

Fokine

Answer 3

I have tried @rici 's answer (the accepted answer), and it fails.

statement: conditional | statement_other_than_conditional;
conditional: complete_conditional | incomplete_conditional;
complete_conditional: L_IF '(' expression ')' statement_other_than_conditional L_ELSE statement
| L_IF '(' expression ')' complete_conditional L_ELSE statement;
incomplete_conditional: L_IF '(' expression ')' statement;
statement_other_than_conditional: ';';
expression: IDENTIFIER;

---

$ bison --report=all rrr.y
rrr.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]

---

State 14 conflicts: 1 shift/reduce
State 15 conflicts: 1 shift/reduce

---

State 14

3 conditional: complete_conditional .  [$end, L_ELSE]
6 complete_conditional: L_IF '(' expression ')' complete_conditional . L_ELSE statement

L_ELSE  shift, and go to state 16

L_ELSE    [reduce using rule 3 (conditional)]
$default  reduce using rule 3 (conditional)


State 15

2 statement: statement_other_than_conditional .  [$end, L_ELSE]
5 complete_conditional: L_IF '(' expression ')' statement_other_than_conditional . L_ELSE statement

L_ELSE  shift, and go to state 17

L_ELSE    [reduce using rule 2 (statement)]
$default  reduce using rule 2 (statement)

---

Chris Dodd's answer is (at least seems to be) good. A bit adapted:

statement: if_statement | noif_statement;

if_statement:
  IF '(' expression ')' statement
| IF '(' expression ')' noif_statement ELSE if_statement
;

noif_statement:
  IF '(' expression ')' noif_statement ELSE noif_statement
| RETURN ';'
;

expression: IDENTIFIER;

If you have further statement rules: if it is not right recursive (does not end with statement) then add just to noif_statement (like RETURN ';'). Else, for example

statement: blah '(' blah ')' statement ;

Duplicate it:

| blah '(' blah ')' if_statement
| blah '(' blah ')' noif_statement

And add the first variant to the if_statements and the second to the noif_statements.

Foal

My incorrect answer has now been updated. – Griffie