Resolve conflict in bison grammar with space separated expression lists + if/then/else

Question

I have the following yacc/bison/happy grammar:

%token 
  if              TokenIf
  then            TokenThen
  else            TokenElse
  true            TokenTrue
  false           TokenFalse

%left APP
%right IF

%%

Hungry
  : NoHungry
  | Hungry NoHungry %prec APP
  | if Hungry then Hungry else Hungry %prec IF

NoHungry
  : true
  | false

bison -v tells me there are two conflicts in the following situation:

State 12

    2 Hungry: Hungry . NoHungry
    3       | if Hungry then Hungry else Hungry .

    true   shift, and go to state 2
    false  shift, and go to state 3

    true      [reduce using rule 3 (Hungry)]
    false     [reduce using rule 3 (Hungry)]
    $default  reduce using rule 3 (Hungry)

    NoHungry  go to state 8

I tried to resolve the conflict by giving explicit precedence declaration with %prec, but to no avail. Given that bison resolves the conflict as wanted (e.g. shifts rather than reduces), this is not so bad, but I wonder how we can get rid of the conflict without changing the accepted language.

rici rici · Accepted Answer · 2018-05-29T16:58:26

As you can see from the bison report, the conflicts are with the terminals true and false, which are not listed in the precedence relations. Consequently, the precedence rules do not apply to these conflicts.

Recall that a precedence relation is defined between a production and a terminal. It does not relate two terminals nor two productions (and so cannot be used to resolve reduce-reduce conflicts). The comparison between precedence of the production which could be reduced and the lookahead terminal determines whether a reduce or a shift will occur. For notational convenience, productions are represented by the name of a terminal, usually the only terminal in the production; this corresponds to a common use case but it is sometimes confusing. In particular, the %prec declaration only serves to give a rule a name for use in precedence declarations, and it is probably better to think about it in that way rather than as an "explicit" declaration.

In short, the conflict in the simplified grammar in your question can be resolved by explicitly adding the appropriate terminals into the precedence relations:

%precedence "if"
%precedence "true" "false"

%%

Hungry
  : NoHungry
  | Hungry NoHungry
  | "if" Hungry "then" Hungry "else" Hungry %prec "if"

NoHungry
  : "true"
  | "false"

Excerpt from -v output:

State 12

    2 Hungry: Hungry . NoHungry
    3       | "if" Hungry "then" Hungry "else" Hungry .

    "true"   shift, and go to state 2
    "false"  shift, and go to state 3

    $default  reduce using rule 3 (Hungry)

    NoHungry  go to state 8

By using -r solved instead of -v, you can see the resolution more explicitly:

    Conflict between rule 3 and token "true" resolved as shift ("if" < "true").
    Conflict between rule 3 and token "false" resolved as shift ("if" < "false").

I could have used "else" as the name for the if production, which would have been the default without the %prec declaration, but "if" seems more intuitive.

The %precedence declaration (available in recent bison versions) does not imply either left or right associativity; in this case, associativity does not apply because there is no case in which a conflict involves a production and terminal of equal precedence. If Happy does not implement it, either %left or %right could be used for the same reason (associativity is irrelevant) but I think %precedence better documents the situation.

Since this is undoubtedly a reduced example, it's worth noting that a more complete grammar would require some grammar analysis. In particular, the list of terminals with precedence greater than "if" would have to include all terminals in FIRST(NoHungry), and bison does not provide an automatic tool to perform that computation, although you can usually extract the list from the shift-reduce conflict reports. (It could even be that "if" is part of the set, in which case associativity would matter.)

Resolve conflict in bison grammar with space separated expression lists + if/then/else

1 Answers