Removing shift/reduce conflict on optional else block

Question

I'm in the process of defining a grammar with Bison and I stumbled upon a shift/reduce conflict I'd like to eliminate. The conflict is caused by a rule that aims to match if/else statements:

state 17

   13 Stmt: IfBlock . OptionalElseBlock

    ELSE  shift, and go to state 42

    ELSE      [reduce using rule 16 (OptionalElseBlock)]
    $default  reduce using rule 16 (OptionalElseBlock)

    OptionalElseBlock  go to state 43

The OptionalElseBlock was defined as follows:

   16 OptionalElseBlock: /* empty */
   17                  | ELSE Stmt

States 42 and 43 look like this with the shift and reduce info omitted:

state 42
   17 OptionalElseBlock: ELSE . Stmt

state 43
   13 Stmt: IfBlock OptionalElseBlock .

I've used optional tokens before, but I'm guessing that since the parser's lookahead buffer only contains 1 terminal OptionalElseBlock causes a conflict. Is there an easy way to resolve this conflict?

rici · Accepted Answer · 2012-11-25T19:41:57.603

This is the classic shift/reduce conflict. The problem is the following:

if (c1) if (c2) stmt1; else stmt2;

The question is which if the else belongs to. If it were not optional, there would be no problem, or if the if statement had to be terminated (say with fi or end, to choose two popular alternatives), but the C syntax seems to have won, and hence we have shift/reduce conflicts.

It is possible but non-trivial to write a grammar which does not exhibit this problem. You can hide the conflict, either by playing games with precedence rules or by simply "expecting" the shift/reduce conflict. (I prefer the latter but there are many who would say that the precedence hack is better, although it amounts to the same thing imho.)

The rewritten grammar is an exercise in the dragon book, and probably other parsing texts, so it might be worth doing for learning purposes, but it's a real pain in terms of grammar maintenance and it makes the grammar much harder to read, if that's at all a concern.

The classic paper on how to use precedence and shift-preference to simplify parsing is "Deterministic parsing of ambiguous grammars" by Aho, Johnson and Ullman, published in 1975 or so. Google will probably find you a copy you can read online if you don't have access to a good library.

Thanks for explaining! I'll probably just use `%expect` then. Why is changing the precedence considered a hack here? — Pieter, Nov 25 '12 at 18:45
@Pieter, well, I consider it a hack :) because there is no other operator which competes with the `else` and `bison` and `yacc` already prefer shift to reduce (which is almost always what you want). So all the precedence rule does is suppress the warning. Just my opinion, I wouldn't want to claim that it is universal. — rici, Nov 25 '12 at 19:40

score 0 · Answer 2 · edited May 23 '17 at 12:04

0

You might want to have a look at my answer to the same question. This is an FAQ.

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

I would recommend not using %expect n for anything but 0.

edited May 23 '17 at 12:04

Community

1
1

answered Nov 26 '12 at 08:27

akim

8,255
3
44
60

Removing shift/reduce conflict on optional else block

2 Answers2

Linked