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

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开发者_JAVA技巧 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
    ;
%%

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

You are not clear on why num needs to represent negative numbers. I can't tell if you use num elsewhere in your grammar. You also don't say why you want num and expr to be distinct.

Normally, negative numbers are handled at the lexer level. In your case, the rule would be something like -?[0-9]+. This eliminates the need for num at all, and results in the following:

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

EDIT: Chris Dodd has a point. So you need to move negation entirely into the parser. You still get rid of num, just don't test for negatives in the INTEGER lexer pattern (i.e. the pattern would be something like [0-9]+, which is what you're doing now, right?). The expr rule I gave above does not change.

• A negative number (-5) parses as: '-' INTEGER, which becomes '-' expr (choice 5), then expr (choice 3).
• A difference between two integers (3-2) parses as INTEGER '-' INTEGER, which becomes expr - expr (choice 5 twice), then expr (choice 2).
• A difference between an integer and a negative integer (5--1) parses as INTEGER '-' '-' INTEGER, which becomes expr '-' '-' expr (choice 5 twice), then expr '-' expr (choice 3), then expr (choice 2).

And so forth. The fundamental problem is you have negation in two different places and there is no way that can't be ambiguous.