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.

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.