Is it possible to define operator precedence for operators who are defined as a non-terminal in Bison?

Question

I haven't been able to find a solution to apply operator precedence for the current grammar rules I have. These are concerning unary and binary operators like +, -, *, etc. These operations are then considered as expressions.

The grammar/precedence rules I have are like the following (with uppercase words as tokens):

%left PLUS MINUS
%left MUL DIV
%left UMINUS NOT

expr    : expr binop expr           {$$ = new BinOpExpression($1, $3, $2);}
        | NOT expr                  {$$ = new UnaryBooleanNegationExpression($2);}
        | MINUS expr %prec UMINUS   {$$ = new UnaryNumericNegationExpression($2);}
        | LPAREN expr RPAREN        {$$ = $2;}
        ;

binop
    : PLUS  { $$ = new Add(); }
    | MINUS { $$ = new Sub(); }
    | MUL   { $$ = new Mul(); }
    | DIV   { $$ = new Div(); }
    | GT    { $$ = new GreaterThan(); }
    | GE    { $$ = new GreaterOrEqual(); }
    | ...
    ;

The problem with this is that the precedence rules are only applied on the unary minus operator. For example, the solution my compiler returned for the expression "1+-2*3-8" was 11 and not -13. The expression was evaluated as (prefix notation):

+(
  1,
  *(
    -2,
    -(3, 8)
   )
 )

This shows that the operators were applied in the order they were found. To solve this I added a new rule to expr for each operator (like below) which solved the problem:

expr    : expr PLUS expr            {$$ = new BinOpExpression($1, $3, new Add());}
        | expr MINUS expr           {$$ = new BinOpExpression($1, $3, new Sub());}
        | expr MUL expr             {$$ = new BinOpExpression($1, $3, new Mul());}
        | expr DIV expr             {$$ = new BinOpExpression($1, $3, new Div());}
        | ...
        ;

But I'd like to avoid this because then I have to convert 1 rule (e.g. expr binop expr) to 19 different rules (one for each unary, binary and assignment operation) just to add correct operator precedence. Is there a way to avoid this but still get the correct operator precedence?

Answer 1

The basic problem you're seeing is that each rule can only have one precedence, so what should the precedence of the rule expr: expr binop expr be? So you need to have at least one rule for each precedence level. You could do something like:

expr : expr addop expr %prec PLUS
     | expr mulop expr %prec MUL
     ...

addop : PLUS | MINUS
mulop : MUL | DIV

which does not require quite as many expr rules, but isn't really any simpler than just using a separate rule for each operator.