Shift/reduce problem with C-like grammar under Bison

Question

Hello folks,

I've been working on a C-like grammar for my personal amusement. However, I've been running into shift/reduce conflicts, and I'm quite sure they could be resolved.

Right now my expressions look like this, in a simplified form, stripped of actions:

%left '+' '-'

%%
expr
 : NUMBER
 | IDENTIFIER
 | expr '+' expr
 | expr '-' expr
 /* other operators like '*', '/', etc. */
 | expr '(' expr ')' /* function call */
%%

However, this results in shift/reduce conflicts: the parser is unsure about how to treat parentheses. From what -v tells me, it is unclear whether an expression like expr '+' expr '(' should reduce expr '+' expr into expr or shift the parenthesis.

Obviously, I want the parenthesis to be shifted. foo % bar(4) shouldn't end up being (foo % bar)(4). However, I've had no success using the %prec directive to that mean. Adding %left FUNCALL and %prec FUNCALL after the rule yields no change.

I know that the default path Bison's LARL parsers will go when encountering a shift/reduce will be to shift, and that I could just use %expect to fix work around the problem. However, one conflict is generated for each expression, and would I ever need to change that list, I'll also need to change the %expect declaration, which looks like a rather ugly solution to me. Besides, I'm sure one of you wise kids have a solution to that problem.

My goal is to have a rule similar to the one above, for which Bison will know that whenever it encounters the '(' from the function call rule, it has shift the parenthesis, without a possible shift/reduce conflict. For the record, my use of the %prec directive is the following, so if I'm just doing it wrong you can correct me. It does have the shift/reduce conflict.

%left '+' '-'
%left FUNCALL

%%

expr
    : NUMBER
    | IDENTIFIER
    | expr '+' expr
    | expr '-' expr
    /* other operators like '*', '/', etc. */
    | expr '(' expr ')' %prec FUNCALL /* function call */

%%

Answer 1

You need to add %left '(' to your precedence rules (or %nonassoc '(' might be better).

The way that precedence works to resolve shift/reduce conflicts in yacc/bison is that it compares the precedence of the rule to be reduced with the precedence of the token to be shifted. In your example, the conflict is between reducing expr: expr '+' expr and shifting a '(', so to resolve it, you need a precedence on '(' (and you want it to be higher than the rule, which comes from '+')

The %prec directive just sets the precedence of a rule, overriding its default precedence which comes from the first token on its rhs. It doesn't affect the precedence of tokens that appear in the rule in any way.