Bison LALR shift/reduce conflicts

Question

I recently picked up bison again, but i'm still fighting with the way precedence works and how to solve basic shift/reduce conflicts. I'm quite comfortable with writing the grammar rules and how recursion works etc. but i still cant wrap my head around the precedence rules.

I would be very much appreciating some comments on the the following examples and my problems and understandings of them.

test1.y

%token              ID
%token              TYPE_NAME
%token              ASTERIX

%nonassoc           F_T
%nonassoc           P_T

%%
f_type:
                    ID type         %prec F_T
;

type:
                    TYPE_NAME
|                   type ASTERIX    %prec P_T
|                   f_type
;
%%

test1.output

State 5

     1 f_type: ID type .
     3 type: type . ASTERIX

     ASTERIX  shift, and go to state 7

     ASTERIX   [reduce using rule 1 (f_type)]
     $default  reduce using rule 1 (f_type)

This example produces a shift reduce conflict, because the state machine cant figure out if it should reduce ID type* -> type* -> type or ID type* -> ID type -> type. That latter is the desired result. I tried resolving this conflict by giving the rule type: type ASTERIX a higher precedence than f_type: ID type but that doesn't seem to work. I also would rather not assign any precedence to the terminal ASTERIX, as i would like to use it in other contexts.

test2.y

%token      ID
%token      DOUBLE_PLUS

%left       POSTFIX_OP
%right      PREFIX_OP

%%
exp:
            ID
|           exp DOUBLE_PLUS     %prec POSTFIX_OP
|           DOUBLE_PLUS exp     %prec PREFIX_OP
;
%%

test2.output

State 4

    2 exp: exp . DOUBLE_PLUS
    3    | DOUBLE_PLUS exp .

    DOUBLE_PLUS  shift, and go to state 6

    DOUBLE_PLUS  [reduce using rule 3 (exp)]
    $default     reduce using rule 3 (exp)

This example produces a shift/reduce conflict, because there is ambiguity in the reduction of DOUBLE_PLUS exp DOUBLE_PLUS. So i tried to assign a higher precedence to DOUBLE_PLUS exp than exp DOUBLE_PLUS, but that doesn't work either. It is possible to resolve this conflict by assigning a left or right precedence to the terminal DOUBLE_PLUS and i'm guessing assigning a left precedence means that exp DOUBLE_PLUS gets reduced first and right means DOUBLE_PLUS exp gets reduced first, but i'm also hoping that there is some way of doing this just by using the %prec annotation.

I'm also unsure if i understand the .output file correctly. The . in the rules indicates what's on the stack and what the lookahead token is, but why is the rule 2 in the latter example even mentioned then? I mean exp: exp . DOUBLE_PLUS shouldn't be of any conflicts?

rici rici · Accepted Answer · 2018-09-02T20:18:31

Here's a quote from another answer I wrote about the yacc/bison precedence algorithm. I don't know if it's clearer than the documentation or the description in the Dragon Book, but it's the best I've been able to do so far. Please let me know if you found it confusing:

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.

Since precedence comparisons are never between two rules -- they are always between a rule and a lookahead token -- the precedence order declarations must include both rules (whether implicitly or explicitly) and token names. So in your first example, the precedence ordering between F_T and P_T has no effect whatsoever. Similarly, in the second example, PREFIX_OP and POSTFIX_OP are precedences associated only with rules, so the precedence ordering has no effect.

If both a shift and a reduce are possible, and the comparison between a rule and a lookahead token eould reveal that the rule has higher precedence, then a reduce action will be generated. If the lookahead token has higher precedence, then a shift action will be generated. But the declarations are only consulted if both a shift and a reduce are possible. If the grammar could only perform one action, that's the action it will perform, regardless. (Exception: %nonassoc declarations will actually ban certain reductions.)

If the comparison results in equality -- both the rule and the token are in the same precedence group -- then shift will be favoured for %left groups and reduce for %right groups. This case will not generally be applied in the case of unary operators, whether prefix or postfix, because in such contexts, only one action is possible.

If inserting tokens into the precedence rules will create a conflict with a precedence order in another part of the grammar, then you can't use precedence declarations as a short-cut; you'll just have to write your grammar to make precedence explicit. That usually isn't difficult. On the other hand, conflicting precedences in two different grammatical contexts can be very confusing for human beings, so you might want to reconsider.

With respect to the state machine output in the .output file, the entire state is printed, not just the part which gives rise to conflicts. The conflicts are indicated in the actions; actions enclosed by […] conflicted with other actions and were eliminated by bison's default conflict-resolution mechanism (prefer shift to reduce; prefer the reduce whose rule is earlier in the file). Roughly speaking, a shift rule has the . before a token; a reduce rule has the . at the end of the rule.

Bison LALR shift/reduce conflicts

1 Answers