bison shift/reduce problem moving add op into a subexpr

Question

Originally in the example there was this

expr:
        INTEGER
        | expr '+' expr           { $$ = $1 + $3; }
        | expr '-' expr           { $$ = $1 - $3; }
        ;

I wanted it to be 'more simple' so i wrote this (i realize it would do '+' for both add and subtract. But this is an example)

expr:
        INTEGER
        | expr addOp expr           { $$ = $1 + $3; }
        ;

addOp:
          '+' { $$ = $1; }
        | '-' { $$ = $1; }
        ;

Now i get a shift/reduce error. It should be exactly the same -_- (to me). What do i need to do to fix this?

edit: To make things clear. The first has NO warning/error. I use %left to set the precedence (and i will use %right for = and those other right ops). However it seems to not apply when going into sub expressions.

Answer 1

Are you sure the conflicts involve just those two rules? The first one should have more conflicts than the second. At least with one symbol of look-ahead the decision to shift to a state with addOp on the stack is easier the second time around.

Update (I believe I can prove my theory... :-):

$ cat q2.y
%% expr: '1' | expr '+' expr | expr '-' expr;
$ cat q3.y
%%  expr: '1' | expr addOp expr;
    addOp: '+' | '-';
$ yacc q2.y
conflicts: 4 shift/reduce
$ yacc q3.y
conflicts: 2 shift/reduce

---

Having said all that, it's normal for yacc grammars to have ambiguities, and any real-life system is likely to have not just a few but literally dozens of shift/reduce conflicts. By definition, this conflict occurs when there is a perfectly valid shift available, so if you don't mind the parser taking that shift, then don't worry about it.

Now, in yacc you should prefer left-recursive rules. You can achieve that and get rid of your grammar ambiguity with:

$ cat q4.y
%% expr: expr addOp '1' | '1';
  addOp: '+' | '-';
$ yacc q4.y
$

Note: no conflicts in the example above. If you like your grammar the way it is, just do:

 %expect 2
%%  expr: '1' | expr addOp expr;
    addOp: '+' | '-';

Answer 2

The problem is that the rule

expr: expr addOp expr { ..action.. }

has no precedence. Normally rules get the precedence of the first token on the RHS, but this rule has no tokens on its RHS. You need to add a %prec directive to it:

expr: expr addOp expr %prec '+' { ..action.. }

to explicitly give the rule a precedence.

Note that doing this doesn't get rid of the shift/reduce conflict, which was present in your original grammar. It just resolves it according to the precedence rules you specify, which means that bison won't give you a message about it. In general, using precedence to resolve conflicts can be tricky, since it can hide conflicts that you might have wanted to resolve differently, or might be unresolvable in your grammar as written.

Also see my answer to this question