Shift/Reduce Error in Bison

Question

The grammar from the yacc is below :

18. Stmt_list : Stmt | Stmt_list ';' Stmt;
19. Stmt : Variable assignop Expression;
20. Variable : id | id'['Expression']';
21. Expression : Simple_expression | Simple_expression relop Simple_expression;
22. Simple_expression : Term | Simple_expression addop Term;
23. Term : Factor | Term mulop Factor;
24. Factor : id | num | '('Expression')' | id'['Expression']' | not Factor;

Now when I am running bison on my .y file, I am getting the following errors:

subc.y: conflicts: 8 shift/reduce, 26 reduce/reduce
subc.y:21.21-45: warning: rule useless in parser due to conflicts: expr: simp_ex
pr relop simp_expr
subc.y:22.20-39: warning: rule useless in parser due to conflicts: simp_expr: si
mp_expr addop term
subc.y:23.17-33: warning: rule useless in parser due to conflicts: term: term mu
lop factor
subc.y:24.40-49: warning: rule useless in parser due to conflicts: factor: not f
actor

I am a complete noob in bison. I don't know how to resolve the problem here.

/** Input and Output Files **/

Input:

%{
#include<stdio.h>
#include "lex.yy.c"
    void yyerror (char *s);
%}

        /* Yacc definitions */
%start stmt_list
%token id
%token num
%token relop
%token mulop
%token addop
%token assignop
%token not
%%
/* descriptions of expected inputs corresponding actions (in C) */
stmt_list   : stmt| stmt_list ';' stmt  { printf("SUCCESS"); };
stmt  : var assignop expr ;
var   : id| id'['expr']' ;
expr  : simp_expr | simp_expr relop simp_expr;
simp_expr  : term| simp_expr addop term;
term  : factor| term mulop factor;
factor  : id| num| expr| id'['expr']'| not factor;
%%

void yyerror (char *s) {printf (stderr, "%s\n", s);}

Output:

    Rules useless in parser due to conflicts

    7 expr: simp_expr relop simp_expr

    9 simp_expr: simp_expr addop term

   11 term: term mulop factor

   16 factor: not factor


State 12 conflicts: 1 shift/reduce
State 13 conflicts: 2 shift/reduce
State 14 conflicts: 1 shift/reduce
State 17 conflicts: 2 reduce/reduce
State 20 conflicts: 6 reduce/reduce
State 25 conflicts: 1 shift/reduce
State 26 conflicts: 2 shift/reduce, 6 reduce/reduce
State 27 conflicts: 1 shift/reduce, 6 reduce/reduce
State 28 conflicts: 6 reduce/reduce


Grammar

    0 $accept: stmt_list $end

    1 stmt_list: stmt
    2          | stmt_list ';' stmt

    3 stmt: var assignop expr

    4 var: id
    5    | id '[' expr ']'

    6 expr: simp_expr
    7     | simp_expr relop simp_expr

    8 simp_expr: term
    9          | simp_expr addop term

   10 term: factor
   11     | term mulop factor

   12 factor: id
   13       | num
   14       | expr
   15       | id '[' expr ']'
   16       | not factor


Terminals, with rules where they appear

$end (0) 0
';' (59) 2
'[' (91) 5 15
']' (93) 5 15
error (256)
id (258) 4 5 12 15
num (259) 13
relop (260) 7
mulop (261) 11
addop (262) 9
assignop (263) 3
not (264) 16


Nonterminals, with rules where they appear

$accept (13)
    on left: 0
stmt_list (14)
    on left: 1 2, on right: 0 2
stmt (15)
    on left: 3, on right: 1 2
var (16)
    on left: 4 5, on right: 3
expr (17)
    on left: 6 7, on right: 3 5 14 15
simp_expr (18)
    on left: 8 9, on right: 6 7 9
term (19)
    on left: 10 11, on right: 8 9 11
factor (20)
    on left: 12 13 14 15 16, on right: 10 11 16


state 0

    0 $accept: . stmt_list $end
    1 stmt_list: . stmt
    2          | . stmt_list ';' stmt
    3 stmt: . var assignop expr
    4 var: . id
    5    | . id '[' expr ']'

    id  shift, and go to state 1

    stmt_list  go to state 2
    stmt       go to state 3
    var        go to state 4


state 1

    4 var: id .  [assignop]
    5    | id . '[' expr ']'

    '['  shift, and go to state 5

    $default  reduce using rule 4 (var)


state 2

    0 $accept: stmt_list . $end
    2 stmt_list: stmt_list . ';' stmt

    $end  shift, and go to state 6
    ';'   shift, and go to state 7


state 3

    1 stmt_list: stmt .

    $default  reduce using rule 1 (stmt_list)


state 4

    3 stmt: var . assignop expr

    assignop  shift, and go to state 8


state 5

    5 var: id '[' . expr ']'
    6 expr: . simp_expr
    7     | . simp_expr relop simp_expr
    8 simp_expr: . term
    9          | . simp_expr addop term
   10 term: . factor
   11     | . term mulop factor
   12 factor: . id
   13       | . num
   14       | . expr
   15       | . id '[' expr ']'
   16       | . not factor

    id   shift, and go to state 9
    num  shift, and go to state 10
    not  shift, and go to state 11

    expr       go to state 12
    simp_expr  go to state 13
    term       go to state 14
    factor     go to state 15


state 6

    0 $accept: stmt_list $end .

    $default  accept


state 7

    2 stmt_list: stmt_list ';' . stmt
    3 stmt: . var assignop expr
    4 var: . id
    5    | . id '[' expr ']'

    id  shift, and go to state 1

    stmt  go to state 16
    var   go to state 4


state 8

    3 stmt: var assignop . expr
    6 expr: . simp_expr
    7     | . simp_expr relop simp_expr
    8 simp_expr: . term
    9          | . simp_expr addop term
   10 term: . factor
   11     | . term mulop factor
   12 factor: . id
   13       | . num
   14       | . expr
   15       | . id '[' expr ']'
   16       | . not factor

    id   shift, and go to state 9
    num  shift, and go to state 10
    not  shift, and go to state 11

    expr       go to state 17
    simp_expr  go to state 13
    term       go to state 14
    factor     go to state 15


state 9

   12 factor: id .  [$end, relop, mulop, addop, ';', ']']
   15       | id . '[' expr ']'

    '['  shift, and go to state 18

    $default  reduce using rule 12 (factor)


state 10

   13 factor: num .

    $default  reduce using rule 13 (factor)


state 11

    6 expr: . simp_expr
    7     | . simp_expr relop simp_expr
    8 simp_expr: . term
    9          | . simp_expr addop term
   10 term: . factor
   11     | . term mulop factor
   12 factor: . id
   13       | . num
   14       | . expr
   15       | . id '[' expr ']'
   16       | . not factor
   16       | not . factor

    id   shift, and go to state 9
    num  shift, and go to state 10
    not  shift, and go to state 11

    expr       go to state 19
    simp_expr  go to state 13
    term       go to state 14
    factor     go to state 20


state 12

    5 var: id '[' expr . ']'
   14 factor: expr .  [relop, mulop, addop, ']']

    ']'  shift, and go to state 21

    ']'       [reduce using rule 14 (factor)]
    $default  reduce using rule 14 (factor)


state 13

    6 expr: simp_expr .  [$end, relop, mulop, addop, ';', ']']
    7     | simp_expr . relop simp_expr
    9 simp_expr: simp_expr . addop term

    relop  shift, and go to state 22
    addop  shift, and go to state 23

    relop     [reduce using rule 6 (expr)]
    addop     [reduce using rule 6 (expr)]
    $default  reduce using rule 6 (expr)


state 14

    8 simp_expr: term .  [$end, relop, mulop, addop, ';', ']']
   11 term: term . mulop factor

    mulop  shift, and go to state 24

    mulop     [reduce using rule 8 (simp_expr)]
    $default  reduce using rule 8 (simp_expr)


state 15

   10 term: factor .

    $default  reduce using rule 10 (term)


state 16

    2 stmt_list: stmt_list ';' stmt .

    $default  reduce using rule 2 (stmt_list)


state 17

    3 stmt: var assignop expr .  [$end, ';']
   14 factor: expr .  [$end, relop, mulop, addop, ';']

    $end      reduce using rule 3 (stmt)
    $end      [reduce using rule 14 (factor)]
    ';'       reduce using rule 3 (stmt)
    ';'       [reduce using rule 14 (factor)]
    $default  reduce using rule 14 (factor)


state 18

    6 expr: . simp_expr
    7     | . simp_expr relop simp_expr
    8 simp_expr: . term
    9          | . simp_expr addop term
   10 term: . factor
   11     | . term mulop factor
   12 factor: . id
   13       | . num
   14       | . expr
   15       | . id '[' expr ']'
   15       | id '[' . expr ']'
   16       | . not factor

    id   shift, and go to state 9
    num  shift, and go to state 10
    not  shift, and go to state 11

    expr       go to state 25
    simp_expr  go to state 13
    term       go to state 14
    factor     go to state 15


state 19

   14 factor: expr .

    $default  reduce using rule 14 (factor)


state 20

   10 term: factor .  [$end, relop, mulop, addop, ';', ']']
   16 factor: not factor .  [$end, relop, mulop, addop, ';', ']']

    $end      reduce using rule 10 (term)
    $end      [reduce using rule 16 (factor)]
    relop     reduce using rule 10 (term)
    relop     [reduce using rule 16 (factor)]
    mulop     reduce using rule 10 (term)
    mulop     [reduce using rule 16 (factor)]
    addop     reduce using rule 10 (term)
    addop     [reduce using rule 16 (factor)]
    ';'       reduce using rule 10 (term)
    ';'       [reduce using rule 16 (factor)]
    ']'       reduce using rule 10 (term)
    ']'       [reduce using rule 16 (factor)]
    $default  reduce using rule 10 (term)


state 21

    5 var: id '[' expr ']' .

    $default  reduce using rule 5 (var)


state 22

    6 expr: . simp_expr
    7     | . simp_expr relop simp_expr
    7     | simp_expr relop . simp_expr
    8 simp_expr: . term
    9          | . simp_expr addop term
   10 term: . factor
   11     | . term mulop factor
   12 factor: . id
   13       | . num
   14       | . expr
   15       | . id '[' expr ']'
   16       | . not factor

    id   shift, and go to state 9
    num  shift, and go to state 10
    not  shift, and go to state 11

    expr       go to state 19
    simp_expr  go to state 26
    term       go to state 14
    factor     go to state 15


state 23

    6 expr: . simp_expr
    7     | . simp_expr relop simp_expr
    8 simp_expr: . term
    9          | . simp_expr addop term
    9          | simp_expr addop . term
   10 term: . factor
   11     | . term mulop factor
   12 factor: . id
   13       | . num
   14       | . expr
   15       | . id '[' expr ']'
   16       | . not factor

    id   shift, and go to state 9
    num  shift, and go to state 10
    not  shift, and go to state 11

    expr       go to state 19
    simp_expr  go to state 13
    term       go to state 27
    factor     go to state 15


state 24

    6 expr: . simp_expr
    7     | . simp_expr relop simp_expr
    8 simp_expr: . term
    9          | . simp_expr addop term
   10 term: . factor
   11     | . term mulop factor
   11     | term mulop . factor
   12 factor: . id
   13       | . num
   14       | . expr
   15       | . id '[' expr ']'
   16       | . not factor

    id   shift, and go to state 9
    num  shift, and go to state 10
    not  shift, and go to state 11

    expr       go to state 19
    simp_expr  go to state 13
    term       go to state 14
    factor     go to state 28


state 25

   14 factor: expr .  [relop, mulop, addop, ']']
   15       | id '[' expr . ']'

    ']'  shift, and go to state 29

    ']'       [reduce using rule 14 (factor)]
    $default  reduce using rule 14 (factor)


state 26

    6 expr: simp_expr .  [$end, relop, mulop, addop, ';', ']']
    7     | simp_expr . relop simp_expr
    7     | simp_expr relop simp_expr .  [$end, relop, mulop, addop, ';', ']']
    9 simp_expr: simp_expr . addop term

    relop  shift, and go to state 22
    addop  shift, and go to state 23

    $end      reduce using rule 6 (expr)
    $end      [reduce using rule 7 (expr)]
    relop     [reduce using rule 6 (expr)]
    relop     [reduce using rule 7 (expr)]
    mulop     reduce using rule 6 (expr)
    mulop     [reduce using rule 7 (expr)]
    addop     [reduce using rule 6 (expr)]
    addop     [reduce using rule 7 (expr)]
    ';'       reduce using rule 6 (expr)
    ';'       [reduce using rule 7 (expr)]
    ']'       reduce using rule 6 (expr)
    ']'       [reduce using rule 7 (expr)]
    $default  reduce using rule 6 (expr)


state 27

    8 simp_expr: term .  [$end, relop, mulop, addop, ';', ']']
    9          | simp_expr addop term .  [$end, relop, mulop, addop, ';', ']']
   11 term: term . mulop factor

    mulop  shift, and go to state 24

    $end      reduce using rule 8 (simp_expr)
    $end      [reduce using rule 9 (simp_expr)]
    relop     reduce using rule 8 (simp_expr)
    relop     [reduce using rule 9 (simp_expr)]
    mulop     [reduce using rule 8 (simp_expr)]
    mulop     [reduce using rule 9 (simp_expr)]
    addop     reduce using rule 8 (simp_expr)
    addop     [reduce using rule 9 (simp_expr)]
    ';'       reduce using rule 8 (simp_expr)
    ';'       [reduce using rule 9 (simp_expr)]
    ']'       reduce using rule 8 (simp_expr)
    ']'       [reduce using rule 9 (simp_expr)]
    $default  reduce using rule 8 (simp_expr)


state 28

   10 term: factor .  [$end, relop, mulop, addop, ';', ']']
   11     | term mulop factor .  [$end, relop, mulop, addop, ';', ']']

    $end      reduce using rule 10 (term)
    $end      [reduce using rule 11 (term)]
    relop     reduce using rule 10 (term)
    relop     [reduce using rule 11 (term)]
    mulop     reduce using rule 10 (term)
    mulop     [reduce using rule 11 (term)]
    addop     reduce using rule 10 (term)
    addop     [reduce using rule 11 (term)]
    ';'       reduce using rule 10 (term)
    ';'       [reduce using rule 11 (term)]
    ']'       reduce using rule 10 (term)
    ']'       [reduce using rule 11 (term)]
    $default  reduce using rule 10 (term)


state 29

   15 factor: id '[' expr ']' .

    $default  reduce using rule 15 (factor)

Do you mind posting the whole input file and the .output file (make sure you add the --report=all to the command line)? — Jeremy Rodi

Brian Tompsett - 汤莱恩 Brian Tompsett - 汤莱恩 · Accepted Answer · 2015-08-17T20:10:35

It is quite simple, the construct:

id '[' expr ']' | id

can be both a var and a factor.

The grammar is ambiguous and this is what bison is telling you....

The solution is to remove them from factor and insert var in their place.

You also have a loop in the grammar:

expr -> simp_exp -> term -> factor -> expr

Remove expr from factor to eliminate that loop, or to reflect what was in the original grammar, perhaps that should be:

  '(' expr ')'

(you forgot the brackets around the expression)

Shift/Reduce Error in Bison

1 Answers