Reforming the grammar to remove shift reduce conflict in if-then-else

Question

How do I remove shift-reduce conflict for bison for the given grammar?

 selection-stmt -> if ( expression ) statement |
                      if ( expression ) statement else statement

A solution giving the modified grammar would be highly appreciated.

Answer 1

There is a much simpler solution. If you know how LR parsers work, then you know that the conflict happens here:

if ( expression ) statement * else statement

where the star marks the current position of the cursor. The question the parser must answer is "should I shift, or should I reduce". Usually, you want to bind the else to the closest if, which means you want to shift the else token now. Reducing now would mean that you want the else to wait to be bound to an "older" if.

Now you want to "tell" your parser generator that "when there is a shift/reduce conflict between the token "else" and the rule "stm -> if ( exp ) stm", then the token must win". To do so, "give a name" to the precedence of your rule (e.g., "then"), and specify that "then" has less precedence than "else". Something like:

// Precedences go increasing, so "then" < "else".
%nonassoc "then"
%nonassoc "else"
%%
stm: "if" "(" exp ")" stm            %prec "then"
   | "if" "(" exp ")" stm "else" stm

using Bison syntax.

Actually, my favorite answer is even to give "then" and "else" the same precedence. When the precedences are equal, to break the tie between the token that wants to be shifted, and the rule that wants to be reduced, Bison/Yacc will look at associativity. Here, you want to promote right-associativity so to speak (more exactly, you want to promote "shift"), so:

%right "then" "else" // Same precedence, but "shift" wins.

will suffice.