Bison Shift/reduce error for C-like language

Question

I'm having an issue with my bison grammar, it is giving me shift/reduce errors, and I have already defined precedence for the operators.

I know that it is cause by the 'expr binop expr' bit of the expr rule. Here is my bison file, and the output I get. Any help would be very much appreciated.

%token ID KEYWORD INTCON FLOATCON TYPE STRING
%token IF WHILE FOR VOID RETURN
%token AND_OP OR_OP EQ_OP NEQ_OP LEQ_OP GEQ_OP

%left OR_OP
%left AND_OP
%nonassoc '<' LEQ_OP '>' GEQ_OP EQ_OP NEQ_OP
%left '+' '-'
%left '/' '*'
%right '!'
%%


expr      : unop expr
          | expr binop expr
          | ID
          | ID '[' expr ']'
          | ID '(' expr_list ')'
          | ID '(' ')'
          | '(' expr ')'
          | INTCON
          | FLOATCON
          ;

expr_list : expr
          | expr_list ',' expr
          ;

unop      : '!' ;

binop     : AND_OP | OR_OP | EQ_OP | NEQ_OP | '+' | '-' | '*' | '/' | LEQ_OP | '<' | GEQ_OP | '>' ;

And the output file:

Terminals unused in grammar

   KEYWORD
   TYPE
   STRING
   IF
   WHILE
   FOR
   VOID
   RETURN


State 25 conflicts: 12 shift/reduce
State 31 conflicts: 12 shift/reduce


Grammar

    0 $accept: expr $end

    1 expr: unop expr
    2     | expr binop expr
    3     | ID
    4     | ID '[' expr ']'
    5     | ID '(' expr_list ')'
    6     | ID '(' ')'
    7     | '(' expr ')'
    8     | INTCON
    9     | FLOATCON

   10 expr_list: expr
   11          | expr_list ',' expr

   12 unop: '!'

   13 binop: AND_OP
   14      | OR_OP
   15      | EQ_OP
   16      | NEQ_OP
   17      | '+'
   18      | '-'
   19      | '*'
   20      | '/'
   21      | LEQ_OP
   22      | '<'
   23      | GEQ_OP
   24      | '>'


Terminals, with rules where they appear

$end (0) 0
'!' (33) 12
'(' (40) 5 6 7
')' (41) 5 6 7
'*' (42) 19
'+' (43) 17
',' (44) 11
'-' (45) 18
'/' (47) 20
'<' (60) 22
'>' (62) 24
'[' (91) 4
']' (93) 4
error (256)
ID (258) 3 4 5 6
KEYWORD (259)
INTCON (260) 8
FLOATCON (261) 9
TYPE (262)
STRING (263)
IF (264)
WHILE (265)
FOR (266)
VOID (267)
RETURN (268)
AND_OP (269) 13
OR_OP (270) 14
EQ_OP (271) 15
NEQ_OP (272) 16
LEQ_OP (273) 21
GEQ_OP (274) 23


Nonterminals, with rules where they appear

$accept (32)
    on left: 0
expr (33)
    on left: 1 2 3 4 5 6 7 8 9, on right: 0 1 2 4 7 10 11
expr_list (34)
    on left: 10 11, on right: 5 11
unop (35)
    on left: 12, on right: 1
binop (36)
    on left: 13 14 15 16 17 18 19 20 21 22 23 24, on right: 2


state 0

    0 $accept: . expr $end
    1 expr: . unop expr
    2     | . expr binop expr
    3     | . ID
    4     | . ID '[' expr ']'
    5     | . ID '(' expr_list ')'
    6     | . ID '(' ')'
    7     | . '(' expr ')'
    8     | . INTCON
    9     | . FLOATCON
   12 unop: . '!'

    ID        shift, and go to state 1
    INTCON    shift, and go to state 2
    FLOATCON  shift, and go to state 3
    '!'       shift, and go to state 4
    '('       shift, and go to state 5

    expr  go to state 6
    unop  go to state 7


state 1

    3 expr: ID .  [$end, AND_OP, OR_OP, EQ_OP, NEQ_OP, LEQ_OP, GEQ_OP, '<', '>', '+', '-', '/', '*', ']', ')', ',']
    4     | ID . '[' expr ']'
    5     | ID . '(' expr_list ')'
    6     | ID . '(' ')'

    '('  shift, and go to state 8
    '['  shift, and go to state 9

    $default  reduce using rule 3 (expr)


state 2

    8 expr: INTCON .

    $default  reduce using rule 8 (expr)


state 3

    9 expr: FLOATCON .

    $default  reduce using rule 9 (expr)


state 4

   12 unop: '!' .

    $default  reduce using rule 12 (unop)


state 5

    1 expr: . unop expr
    2     | . expr binop expr
    3     | . ID
    4     | . ID '[' expr ']'
    5     | . ID '(' expr_list ')'
    6     | . ID '(' ')'
    7     | . '(' expr ')'
    7     | '(' . expr ')'
    8     | . INTCON
    9     | . FLOATCON
   12 unop: . '!'

    ID        shift, and go to state 1
    INTCON    shift, and go to state 2
    FLOATCON  shift, and go to state 3
    '!'       shift, and go to state 4
    '('       shift, and go to state 5

    expr  go to state 10
    unop  go to state 7


state 6

    0 $accept: expr . $end
    2 expr: expr . binop expr
   13 binop: . AND_OP
   14      | . OR_OP
   15      | . EQ_OP
   16      | . NEQ_OP
   17      | . '+'
   18      | . '-'
   19      | . '*'
   20      | . '/'
   21      | . LEQ_OP
   22      | . '<'
   23      | . GEQ_OP
   24      | . '>'

    $end    shift, and go to state 11
    AND_OP  shift, and go to state 12
    OR_OP   shift, and go to state 13
    EQ_OP   shift, and go to state 14
    NEQ_OP  shift, and go to state 15
    LEQ_OP  shift, and go to state 16
    GEQ_OP  shift, and go to state 17
    '<'     shift, and go to state 18
    '>'     shift, and go to state 19
    '+'     shift, and go to state 20
    '-'     shift, and go to state 21
    '/'     shift, and go to state 22
    '*'     shift, and go to state 23

    binop  go to state 24


state 7

    1 expr: . unop expr
    1     | unop . expr
    2     | . expr binop expr
    3     | . ID
    4     | . ID '[' expr ']'
    5     | . ID '(' expr_list ')'
    6     | . ID '(' ')'
    7     | . '(' expr ')'
    8     | . INTCON
    9     | . FLOATCON
   12 unop: . '!'

    ID        shift, and go to state 1
    INTCON    shift, and go to state 2
    FLOATCON  shift, and go to state 3
    '!'       shift, and go to state 4
    '('       shift, and go to state 5

    expr  go to state 25
    unop  go to state 7


state 8

    1 expr: . unop expr
    2     | . expr binop expr
    3     | . ID
    4     | . ID '[' expr ']'
    5     | . ID '(' expr_list ')'
    5     | ID '(' . expr_list ')'
    6     | . ID '(' ')'
    6     | ID '(' . ')'
    7     | . '(' expr ')'
    8     | . INTCON
    9     | . FLOATCON
   10 expr_list: . expr
   11          | . expr_list ',' expr
   12 unop: . '!'

    ID        shift, and go to state 1
    INTCON    shift, and go to state 2
    FLOATCON  shift, and go to state 3
    '!'       shift, and go to state 4
    '('       shift, and go to state 5
    ')'       shift, and go to state 26

    expr       go to state 27
    expr_list  go to state 28
    unop       go to state 7


state 9

    1 expr: . unop expr
    2     | . expr binop expr
    3     | . ID
    4     | . ID '[' expr ']'
    4     | ID '[' . expr ']'
    5     | . ID '(' expr_list ')'
    6     | . ID '(' ')'
    7     | . '(' expr ')'
    8     | . INTCON
    9     | . FLOATCON
   12 unop: . '!'

    ID        shift, and go to state 1
    INTCON    shift, and go to state 2
    FLOATCON  shift, and go to state 3
    '!'       shift, and go to state 4
    '('       shift, and go to state 5

    expr  go to state 29
    unop  go to state 7


state 10

    2 expr: expr . binop expr
    7     | '(' expr . ')'
   13 binop: . AND_OP
   14      | . OR_OP
   15      | . EQ_OP
   16      | . NEQ_OP
   17      | . '+'
   18      | . '-'
   19      | . '*'
   20      | . '/'
   21      | . LEQ_OP
   22      | . '<'
   23      | . GEQ_OP
   24      | . '>'

    AND_OP  shift, and go to state 12
    OR_OP   shift, and go to state 13
    EQ_OP   shift, and go to state 14
    NEQ_OP  shift, and go to state 15
    LEQ_OP  shift, and go to state 16
    GEQ_OP  shift, and go to state 17
    '<'     shift, and go to state 18
    '>'     shift, and go to state 19
    '+'     shift, and go to state 20
    '-'     shift, and go to state 21
    '/'     shift, and go to state 22
    '*'     shift, and go to state 23
    ')'     shift, and go to state 30

    binop  go to state 24


state 11

    0 $accept: expr $end .

    $default  accept


state 12

   13 binop: AND_OP .

    $default  reduce using rule 13 (binop)


state 13

   14 binop: OR_OP .

    $default  reduce using rule 14 (binop)


state 14

   15 binop: EQ_OP .

   $default  reduce using rule 15 (binop)


state 15

   16 binop: NEQ_OP .

    $default  reduce using rule 16 (binop)


state 16

   21 binop: LEQ_OP .

    $default  reduce using rule 21 (binop)


state 17

   23 binop: GEQ_OP .

    $default  reduce using rule 23 (binop)


state 18

   22 binop: '<' .

    $default  reduce using rule 22 (binop)


state 19

   24 binop: '>' .

    $default  reduce using rule 24 (binop)


state 20

   17 binop: '+' .

    $default  reduce using rule 17 (binop)


state 21

   18 binop: '-' .

    $default  reduce using rule 18 (binop)


state 22

   20 binop: '/' .

    $default  reduce using rule 20 (binop)


state 23

   19 binop: '*' .

    $default  reduce using rule 19 (binop)


state 24

    1 expr: . unop expr
    2     | . expr binop expr
   2     | expr binop . expr
    3     | . ID
    4     | . ID '[' expr ']'
    5     | . ID '(' expr_list ')'
    6     | . ID '(' ')'
    7     | . '(' expr ')'
    8     | . INTCON
    9     | . FLOATCON
   12 unop: . '!'

    ID        shift, and go to state 1
    INTCON    shift, and go to state 2
    FLOATCON  shift, and go to state 3
    '!'       shift, and go to state 4
    '('       shift, and go to state 5

    expr  go to state 31
    unop  go to state 7


state 25

    1 expr: unop expr .  [$end, AND_OP, OR_OP, EQ_OP, NEQ_OP, LEQ_OP, GEQ_OP, '<', '>', '+', '-', '/', '*', ']', ')', ',']
    2     | expr . binop expr
   13 binop: . AND_OP
   14      | . OR_OP
   15      | . EQ_OP
   16      | . NEQ_OP
   17      | . '+'
   18      | . '-'
   19      | . '*'
   20      | . '/'
   21      | . LEQ_OP
   22      | . '<'
   23      | . GEQ_OP
   24      | . '>'

    AND_OP  shift, and go to state 12
    OR_OP   shift, and go to state 13
    EQ_OP   shift, and go to state 14
    NEQ_OP  shift, and go to state 15
    LEQ_OP  shift, and go to state 16
    GEQ_OP  shift, and go to state 17
    '<'     shift, and go to state 18
    '>'     shift, and go to state 19
    '+'     shift, and go to state 20
    '-'     shift, and go to state 21
    '/'     shift, and go to state 22
    '*'     shift, and go to state 23

    AND_OP    [reduce using rule 1 (expr)]
    OR_OP     [reduce using rule 1 (expr)]
    EQ_OP     [reduce using rule 1 (expr)]
    NEQ_OP    [reduce using rule 1 (expr)]
    LEQ_OP    [reduce using rule 1 (expr)]
    GEQ_OP    [reduce using rule 1 (expr)]
    '<'       [reduce using rule 1 (expr)]
    '>'       [reduce using rule 1 (expr)]
    '+'       [reduce using rule 1 (expr)]
    '-'       [reduce using rule 1 (expr)]
    '/'       [reduce using rule 1 (expr)]
    '*'       [reduce using rule 1 (expr)]
    $default  reduce using rule 1 (expr)

    binop  go to state 24


state 26

    6 expr: ID '(' ')' .
   $default  reduce using rule 6 (expr)


state 27

    2 expr: expr . binop expr
   10 expr_list: expr .  [')', ',']
   13 binop: . AND_OP
   14      | . OR_OP
   15      | . EQ_OP
   16      | . NEQ_OP
   17      | . '+'
   18      | . '-'
   19      | . '*'
   20      | . '/'
   21      | . LEQ_OP
   22      | . '<'
   23      | . GEQ_OP
   24      | . '>'

    AND_OP  shift, and go to state 12
    OR_OP   shift, and go to state 13
    EQ_OP   shift, and go to state 14
    NEQ_OP  shift, and go to state 15
    LEQ_OP  shift, and go to state 16
    GEQ_OP  shift, and go to state 17
    '<'     shift, and go to state 18
    '>'     shift, and go to state 19
    '+'     shift, and go to state 20
    '-'     shift, and go to state 21
    '/'     shift, and go to state 22
    '*'     shift, and go to state 23

    $default  reduce using rule 10 (expr_list)

    binop  go to state 24


state 28

    5 expr: ID '(' expr_list . ')'
   11 expr_list: expr_list . ',' expr

    ')'  shift, and go to state 32
    ','  shift, and go to state 33


state 29

    2 expr: expr . binop expr
    4     | ID '[' expr . ']'
   13 binop: . AND_OP
   14      | . OR_OP
   15      | . EQ_OP
   16      | . NEQ_OP
   17      | . '+'
   18      | . '-'
   19      | . '*'
   20      | . '/'
   21      | . LEQ_OP
   22      | . '<'
   23      | . GEQ_OP
   24      | . '>'

    AND_OP  shift, and go to state 12
    OR_OP   shift, and go to state 13
    EQ_OP   shift, and go to state 14
    NEQ_OP  shift, and go to state 15
    LEQ_OP  shift, and go to state 16
    GEQ_OP  shift, and go to state 17
    '<'     shift, and go to state 18
    '>'     shift, and go to state 19
    '+'     shift, and go to state 20
    '-'     shift, and go to state 21
    '/'     shift, and go to state 22
    '*'     shift, and go to state 23
    ']'     shift, and go to state 34

    binop  go to state 24


state 30

    7 expr: '(' expr ')' .

    $default  reduce using rule 7 (expr)


state 31

    2 expr: expr . binop expr
    2     | expr binop expr .  [$end, AND_OP, OR_OP, EQ_OP, NEQ_OP, LEQ_OP, GEQ_OP, '<', '>', '+', '-', '/', '*', ']', ')', ',']
   13 binop: . AND_OP
   14      | . OR_OP
   15      | . EQ_OP
   16      | . NEQ_OP
   17      | . '+'
   18      | . '-'
   19      | . '*'
   20      | . '/'
   21      | . LEQ_OP
   22      | . '<'
   23      | . GEQ_OP
   24      | . '>'

    AND_OP  shift, and go to state 12
    OR_OP   shift, and go to state 13
    EQ_OP   shift, and go to state 14
    NEQ_OP  shift, and go to state 15
    LEQ_OP  shift, and go to state 16
    GEQ_OP  shift, and go to state 17
    '<'     shift, and go to state 18
    '>'     shift, and go to state 19
    '+'     shift, and go to state 20
    '-'     shift, and go to state 21
    '/'     shift, and go to state 22
    '*'     shift, and go to state 23

    AND_OP    [reduce using rule 2 (expr)]
    OR_OP     [reduce using rule 2 (expr)]
    EQ_OP     [reduce using rule 2 (expr)]
    NEQ_OP    [reduce using rule 2 (expr)]
    LEQ_OP    [reduce using rule 2 (expr)]
    GEQ_OP    [reduce using rule 2 (expr)]
    '<'       [reduce using rule 2 (expr)]
    '>'       [reduce using rule 2 (expr)]
    '+'       [reduce using rule 2 (expr)]
    '-'       [reduce using rule 2 (expr)]
    '/'       [reduce using rule 2 (expr)]
    '*'       [reduce using rule 2 (expr)]
    $default  reduce using rule 2 (expr)

    binop  go to state 24


state 32

    5 expr: ID '(' expr_list ')' .

    5 expr: ID '(' expr_list ')' .

    $default  reduce using rule 5 (expr)


state 33

    1 expr: . unop expr
    2     | . expr binop expr
    3     | . ID
    4     | . ID '[' expr ']'
    5     | . ID '(' expr_list ')'
    6     | . ID '(' ')'
    7     | . '(' expr ')'
    8     | . INTCON
    9     | . FLOATCON
   11 expr_list: expr_list ',' . expr
   12 unop: . '!'

    ID        shift, and go to state 1
    INTCON    shift, and go to state 2
    FLOATCON  shift, and go to state 3
    '!'       shift, and go to state 4
    '('       shift, and go to state 5

    expr  go to state 35
    unop  go to state 7


state 34

    4 expr: ID '[' expr ']' .

    $default  reduce using rule 4 (expr)


state 35

    2 expr: expr . binop expr
   11 expr_list: expr_list ',' expr .  [')', ',']
   13 binop: . AND_OP
   14      | . OR_OP
   15      | . EQ_OP
   16      | . NEQ_OP
   17      | . '+'
   18      | . '-'
   19      | . '*'
   20      | . '/'
   21      | . LEQ_OP
   22      | . '<'
   23      | . GEQ_OP
   24      | . '>'

    AND_OP  shift, and go to state 12
    OR_OP   shift, and go to state 13
    EQ_OP   shift, and go to state 14
    NEQ_OP  shift, and go to state 15
    LEQ_OP  shift, and go to state 16
    GEQ_OP  shift, and go to state 17
    '<'     shift, and go to state 18
    '>'     shift, and go to state 19
    '+'     shift, and go to state 20
    '-'     shift, and go to state 21
    '/'     shift, and go to state 22
    '*'     shift, and go to state 23

    $default  reduce using rule 11 (expr_list)

    binop  go to state 24

FIX BY RICI BELOW:#

(Removed the unop and binop rules and enumerated them in the expr rule)

%token ID KEYWORD INTCON FLOATCON TYPE STRING
%token IF WHILE FOR VOID RETURN
%token AND_OP OR_OP EQ_OP NEQ_OP LEQ_OP GEQ_OP

%left "||"
%left "&&"
%nonassoc '<' "<=" '>' ">=" "==" "!="
%left '+' '-'
%left '/' '*'
%right '!'
%%    

expr      : ID
          | ID '[' expr ']'
          | ID '(' expr_list ')'
          | ID '(' ')'
          | '(' expr ')'
          | INTCON
          | FLOATCON
          | '!'  expr
          | '-' expr
          | expr '+' expr
          | expr '-' expr
          | expr '/' expr
          | expr '*' expr
          | expr '<' expr
          | expr '>' expr
          | expr "<=" expr
          | expr ">=" expr
          | expr "==" expr
          | expr "!=" expr
          | expr "&&" expr
          | expr "||" expr
          ;

expr_list : expr
          | expr_list ',' expr
          ;
%%

Answer 1

Precedence only works if the productions directly include terminals named in the precedence declaration.

In other words, you cannot use expr: expr binop expr because the precedence relations can't help bison decide whether to shift the reduced binop non-terminal or reduce the expr on the top of the parse stack. Bison would have to know what the terminal inside the binop was, but it doesn't know that any more. (That's why reductions are called "reductions".)

To make it work, you have to write the productions out in full:

expr: expr '+' expr
    | expr '-' expr
    | expr '*' expr
    |...