Solving dangling else with bison

Question

My grammar has these two token declarations:

%token RP
%token ELSE

And these two rules:

Statement  : IF LP Exp RP Statement;

Statement  : IF LP Exp RP Statement ELSE Statement;

From what I understand, a rule's priority is determined by the priority of its last nonterminal. Therefore, the first rule has RP priority and the second rule has ELSE priority which is higher than RP. Below is bison's output:

state 73

   11 Statement: IF LP Exp RP Statement .
   12          | IF LP Exp RP Statement . ELSE Statement

    ELSE  shift, and go to state 76

    ELSE      [reduce using rule 11 (Statement)]
    $default  reduce using rule 11 (Statement)

Shouldn't this conflict be solved by shifting since ELSE has higher priority ?

I flagged the question as a duplicate of [that one](http://stackoverflow.com/questions/12720219/bison-shift-reduce-conflict-unable-to-resolve) — zmo, Jun 09 '13 at 14:05
@zmo I understand that there's a conflict and I know I can modify the grammar so that the conflict goes away, what I don't understand is why the conflict isn't solved by giving higher priority to the ELSE token — Shmoopy, Jun 09 '13 at 14:07

Chris Dodd · Accepted Answer · 2013-06-09T19:41:09.220

No, because %token does not set the precedence (what you call the priority) of a token -- it declares the token to exist with NO precedence. If you want to declare a precedence for the token, you need to use %left, %right or %nonassoc all of which both declare the token AND set its precedence. If you change your code to

%nonassoc RP
%nonassoc ELSE

then RP and ELSE will have have their precedence set, and ELSE will have higher precedence, and the shift/reduce conflict will be resolved by precedence.

score 1 · Answer 2 · edited May 23 '17 at 12:32

1

you should have a look at this answer, the if/else ambiguity is a pretty common pattern for languages, and it is dealt in Bison's and Yacc's manual, as well as in the dragon books, and on several tutorials on Internet, like this one

Shouldn't this conflict be solved by shifting since ELSE has higher priority ?

as said in the other answer, it indeed is. The conflict is being solved automatically by bison doing an automatic shift, and it tells you about it.. It indeed selects the IF ELSE, and if you add the %expect declaration it won't warn you about that it did something "automatically".

edited May 23 '17 at 12:32

Community

1
1

answered Jun 09 '13 at 14:04

zmo

24,463
4
54
90

1

It's resolved by shifting as that is the default resolution of shift/reduce conflicts. The OP wants to resolve it by shifting via precedence, which requires setting precedence on the tokens. The same overall result, but it shuts up the complaint about an unresolved shift/reduce conflict. – Chris Dodd Jun 09 '13 at 19:40

Solving dangling else with bison

2 Answers2