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
;
%%
