Unary precedence in Bison

Question

I am continuously getting shift/reduce conflicts when by parser tries to sort out whether something is a unary or binary operator.

%token <intconst> tHEX tOCT tDEC tRUNE
%token <stringconst> tBOOL INTERPRETEDSTRING RAWSTRING tIDENTIFIER
%token <floatconst> tFLOAT
%token <charconst> tRUNES
%token TRUE FALSE BREAK CASE CHAN CONST CONTINUE DEFAULT DEFER ELSE FALLTHROUGH FOR FUNC GO GOTO IF IMPORT INTERFACE MAP PACKAGE RANGE RETURN SELECT STRUCT SWITCH TYPE VAR INT PRINT FLOAT PRINTLN BOOL APPEND RUNE STRING SEMICOLON NEWLINE PLUS MINUS TIMES DIV MOD AMP PIPE CARAT COUT CIN AMPCARAT SELFPLUS SELFMINUS SELFTIMES SELFDIV SELFMOD AMPEQUALS PIPEEQUALS CARATEQUALS COUTEQUALS CINEQUALS WTF AND OR REDIRECT INCREMENT DECREMENT DOESEQUALS LT GT EQUALS NOT NEQ LE GE COMPAT ELLIPSIS LEFTPAREN RIGHTPAREN LEFTSQUARE RIGHTSQUARE LEFTBRACE RIGHTBRACE COMMA PERIOD FULLCOLON ESCAPEA ESCAPEB ESCAPEF ESCAPEV ESCAPESLASH ESCAPEAPOSTROPHE INVALID
/*%token unary*/
/*%token binary*/
%left OR
%left AND
%left DOESEQUALS NEQ GT GE LT LE
%left PLUS MINUS PIPE CARAT
%left TIMES DIV MOD COUT CIN AMP AMPCARAT
/*%left binary*/
%left UPLUS UMINUS UNOT UCARAT UTIMES UAMP UPAREN
%start expList

%%

expList: exp expList {}
       | /*empty*/
;
exp: exp OR addOp {}
   | exp AND addOp {}
   | exp NEQ addOp {}
   | exp GT addOp {}
   | exp GE addOp {}
   | exp LT addOp {}
   | exp LE addOp {}
   | addOp {}
;
addOp: addOp PLUS mulOp {}
     | addOp MINUS mulOp {}
     | addOp PIPE mulOp {}
     | addOp CARAT mulOp {}
     | mulOp {}
;  
mulOp: mulOp TIMES factor {}
     | mulOp DIV factor {}
     | mulOp MOD factor {}
     | mulOp COUT factor {}
     | mulOp CIN factor {}
     | mulOp AMP factor {}
     | mulOp AMPCARAT factor {}
     | factor {}
;
factor: LEFTPAREN exp RIGHTPAREN %prec UPAREN {}
      | PLUS factor %prec UPLUS {}
      | MINUS factor %prec UMINUS {}
      | NOT factor %prec UNOT {}
      | CARAT factor %prec UCARAT {}
      | TIMES factor %prec UTIMES {}
      | AMP factor %prec UAMP {}
      | tIDENTIFIER {}
      | tDEC {}
      | tFLOAT {}
      | tOCT {}
      | tHEX {}
      | tRUNES {}
      | INTERPRETEDSTRING {}
      | RAWSTRING {}
;
%%

I know I have a lot of tokens and I will eventually use them. I'm just trying to get the grammar for the expressions working. Here are the shift/reduce errors I'm getting

State 18

   10 exp: addOp .
   11 addOp: addOp . PLUS mulOp
   12      | addOp . MINUS mulOp
   13      | addOp . PIPE mulOp
   14      | addOp . CARAT mulOp

    PLUS   shift, and go to state 37
    MINUS  shift, and go to state 38
    PIPE   shift, and go to state 39
    CARAT  shift, and go to state 40

    PLUS      [reduce using rule 10 (exp)]
    MINUS     [reduce using rule 10 (exp)]
    CARAT     [reduce using rule 10 (exp)]
    $default  reduce using rule 10 (exp)

State 19

   15 addOp: mulOp .
   16 mulOp: mulOp . TIMES factor
   17      | mulOp . DIV factor
   18      | mulOp . MOD factor
   19      | mulOp . COUT factor
   20      | mulOp . CIN factor
   21      | mulOp . AMP factor
   22      | mulOp . AMPCARAT factor

    TIMES     shift, and go to state 41
    DIV       shift, and go to state 42
    MOD       shift, and go to state 43
    AMP       shift, and go to state 44
    COUT      shift, and go to state 45
    CIN       shift, and go to state 46
    AMPCARAT  shift, and go to state 47

    TIMES     [reduce using rule 15 (addOp)]
    AMP       [reduce using rule 15 (addOp)]
    $default  reduce using rule 15 (addOp)

I've run out of ideas and would appreciate any help I can get.

Answer 1

Your basic problem is that your grammar allows consecutive expressions with nothing between them (an expList is just 0 or more expressions with no separating tokens), so any token that can be either infix or unary is ambiguous -- something like:

1 - 2

could be either a single expression, or a list of two expressions.

The default "prefer shift over reduce" resolution will treat this as one expression, which is probably what you want, but you'll get warnings about shift/reduce conflicts.

To quiet those warnings with precedence rules, you need to put %prec directives on the simple unitary rules with no operators (exp: addOp;, addOp: mulOp; etc). These should have LOWER precedence than any infix operator.

---

Note also that since you have precedence rules, you don't need separate addOp/mulOp/factor rules, and you can just use exp for everything:

expList: expList exp %prec _low_ {}
       | /*empty*/
;

exp: exp OR exp {}
   | exp AND exp {}
   | exp NEQ exp {}
   | exp GT exp {}
   | exp GE exp {}
   | exp LT exp {}
   | exp LE exp {}
   | exp PLUS exp {}
   | exp MINUS exp {}
   | exp PIPE exp {}
   | exp CARAT exp {}
   | exp TIMES exp {}
   | exp DIV exp {}
   | exp MOD exp {}
   | exp COUT exp {}
   | exp CIN exp {}
   | exp AMP exp {}
   | exp AMPCARAT exp {}
   | LEFTPAREN exp RIGHTPAREN {}
   | PLUS exp %prec UPLUS {}
   | MINUS exp %prec UMINUS {}
   | NOT exp %prec UNOT {}
   | CARAT exp %prec UCARAT {}
   | TIMES exp %prec UTIMES {}
   | AMP exp %prec UAMP {}
   | tIDENTIFIER {}
   | tDEC {}
   | tFLOAT {}
   | tOCT {}
   | tHEX {}
   | tRUNES {}
   | INTERPRETEDSTRING {}
   | RAWSTRING {}
;

However, doing this does require making the expList rule left-recursive rather than right recursive (which is generally better anyways), as a right-recursive rule here leads to reduce/reduce conflicts that can't be silenced by precedence directives.

Answer 2

Not sure how helpful the following will be but something like this worked for me:

exp :
     '(' exp ')'
   | unary_exp
   | exp bin_op term
   | exp bin_op unary_exp
   | exp bin_op '(' exp ')'
   | term

unary_exp : u_op exp %prec FIRST
term : CONSTANT | NUM

bin_op : '+' | '-' | '*' | '/'
u_op   : '-'

for more on prec

Answer 3

With precedence and associativity directives, you should start by simplify your grammar, to let them work, and check what conflicts still appear...

exp: exp OR exp {}
   | exp AND exp {}
   | exp NEQ exp {}
   | ...
   | exp PLUS exp {}
   | ... 
   | exp '*' exp {}
   | '(' exp ')' {}
   | MINUS exp %prec UMINUS {}
   | ...
   | tDEC {}
   | ...
   ;