Why doesn't %prec have an effect in this bison grammar?

Question

Consider the following Bison grammar (this is stripped down from a much larger grammar I'm working on):

%token ident
%left '+'
%left CALLPREC

%%

start: add ';' ;
expr: ident | call |  add ;
call: expr '(' ')' %prec CALLPREC ;
add: expr '+' expr ;

Obviously without precedence there's a s/r conflict when parsing an expression like foo + bar(). I'm trying to understand why the %prec declaration doesn't resolve that conflict. I'm using Bison 3.0.2, which seems to think the directive is useless:

$ bison -r state,solved -Wall  ambigram.y 
ambigram.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
ambigram.y:5.1-5: warning: useless precedence and associativity for CALLPREC [-Wprecedence]

Oddly, eliminating the %prec CALLPREC and declaring %left '(' resolves the conflict, but declaring %left ')' does not. This is the opposite of what I'd expect from the Bison docs, which say that [by] default, the precedence of a rule is that of its last token.

Answer 1

Bison precedence resolution of shift/reduce conflicts works by having precedence level on both tokens and rules. When it finds a shift/reduce conflict, bison compares the precedence of the rule to be reduced and the precedence of the token to be shifted and chooses the higher precedence one. A %prec directive just sets the precedence of a rule; it has no effect on the precedence of tokens.

The conflict (ambiguity) in your grammar comes from input like

ident '+' ident '(' ')'

which can be parsed as either an add where the second operand is a call, or as a call where the called expr is an add. It manifests in a shift/reduce parser as a shift/reduce conflict between reducing the add rule and shifting a '(' token after seeing an expr + expr input. As such, all that matters is the precedence of the add rule and the '(' token -- the precedence of the call rule is irrelevant as a call has not yet been recognized.

You get the second warning in your case as the explicitly set precedence of the call rule is never used to resolve any conflicts.

I've toyed with the idea of writing a yacc variant that would handle precedence in a way more in line with most people's intuition. Instead of having precedence on tokens, it would have predecence only on rules. When a shift/reduce conflict ocurred, it would compare the precedence of the rule to be reduced with the precedences of rules that could be reduced after shifting the token. This might not resolve the conflict (if the shift leads to multiple rules that could be reduced, some higher precedence and some lower), but would generally be more flexible and less likely to get people in trouble by resolving conflicts in unexpected ways.