Bison/YACC - avoid reduce/reduce conflict with two negation rules

Question

The following grammar (where INTEGER is a sequence of digits) gives rise to a reduce/reduce conflict, because e.g. -4 can be reduced by expr -> -expr or expr -> num -> -INTEGER. In my grammar, num and expr return different types so that I have to distinguish -num and -expr. My goal is that -5 is reduced by num while e.g. -(...) is an expr. How could I achieve this?

%token      INTEGER

%left       '+'     '-'

%%

start: expr
    ;

expr: expr '+' expr
    | expr '-' expr
    | '-' expr
    | '(' expr ')'
    | num
    ;

num:  INTEGER
    | '-' INTEGER
    ;
%%

possible duplicate of Resolving reduce/reduce conflict in yacc/ocamlyacc — xtofl
I saw this one before I posted this question, and I think that the answers might be similar (increasing the complexity of the grammar), yet I did not come up with a solution yet. — Searles

Chris Dodd Chris Dodd · Accepted Answer · 2011-10-05T22:49:59

For this specific case, you could change the rule for negative expressions to

expr: '-' '(' expr ')'

and only recognize negations on parenthesized expressions. This however won't recognize double-negatives (eg - - x) and, more importantly, won't scale in that it will break if you try to add other unary operators.

Now you could simply put the num rules BEFORE the expr rules and allow the default reduce/reduce conflict resolution to deal with it (the first rule appearing in the file will be used if both are possible), but that's kind of ugly in that you get these conflict warnings every time you run bison, and ignoring them when you don't know exactly what is going on is a bad idea.

The general way of addressing this kind of ambiguity is by factoring the grammar to split the offending rule into two rules and using the appropriate version in each context so that you don't get conflicts. In this case, you'd split expr into num_expr for expressions that start with a num and non_num_expr for other expressions:

expr: num_expr | non_num_expr ;

num_expr: num_expr '+' expr
        | num_expr '-' expr
        | num
        ;

non_num_expr: non_num_expr '+' expr
            | non_num_expr '-' expr
            | '-' non_num_expr
            | '(' expr ')'
            ;

Basically, every rule for expr that begins with an expr on the RHS needs to be duplicated, and other uses of expr may need to be changed to one of the variants so as to avoid the conflict.

Unfortunately, in this case, it doesn't work cleanly, as you're using precedence levels to resolve the inherent ambiguity of the expression grammar, and the factored rules get in the way of that -- the extra one-step rules cause problems. So you need to either factor those rules out of existence (duplicating every rule with expr on the RHS -- one with the num_expr version and one with the non_num_version OR you need to refactor your grammar with extra rules for the precedence/associativity

expr: expr '+' term
    | expr '-' term
    | term
;

term: non_num_term | num_term ;

non_num_term: '-' non_num_term
            | '(' expr ')'
;

num_term: num ;

Note in this case, the num/non_num factoring has been done on term rather than expr

Bison/YACC - avoid reduce/reduce conflict with two negation rules

2 Answers