i'am trying to write a basic C parser but i get many shift/reduce conflicts. I've tried many suggestions from other questions but nothing seems to work. I tried to add some precedence based on C language but i keep getting shift/reduces conflicts. What i am missing? Any help would be appreciated !
bison :
%union {char* var; char* type}
%token <type> INT DOUBLE BOOL CHAR
%token FOR WHILE
%token IF ELSE PRINTF
%token BYREF BREAK CONTINUE RETURN DELETE FALSE TRUE NEW NULL VOID
%token NUM
%token INCLUDE
%token DOT
%token <var> ID
%nonassoc ELSE
%right '[' ']'
%right '!' '-' '+' '?' ':'
%left AND OR
%right DELETE
%left '&' '*' '/' '%'
%left '<' '>' LE GE EQ NE LT GT
%right MUL_AS DIV_AS ADD_AS MIN_AS MOD_AS INCR DCRS
%error-verbose
%%
expr
: ID
| TRUE
| FALSE
| NULL
|"(" expr ")"
| ID "(" expr_list ")"
| expr "[" expr "]"
| expr '&' expr
| expr '*' expr
| expr '!' expr
| expr INCR
| expr DCRS
| expr '=' expr %prec '='
| expr DIV_AS expr %prec MOD_AS
| expr MOD_AS expr
| expr MUL_AS expr
| expr ADD_AS expr
| expr MIN_AS expr
| expr LE expr
| expr GE expr
| expr NE expr
| expr EQ expr
| expr GT expr
| expr LT expr
| "(" data_type ")" expr
| expr "?" expr ":" expr
| NEW data_type
| NEW data_type "[" expr "]"
| DELETE expr
;
Part of the report: (Almost all shift/reduces conflicts are coming from this part of my code)
State 88
49 expr: expr . "[" expr "]"
50 | expr . '&' expr
51 | expr . '*' expr
52 | expr . '!' expr
53 | expr . INCR
54 | expr . DCRS
55 | expr . '=' expr
55 | expr '=' expr . ['!', '&', '*', LE, GE, EQ, NE, LT, GT, MUL_AS, DIV_AS, ADD_AS, MIN_AS, MOD_AS, INCR, DCRS, ";", "[", "]", ")", ')', ';', '=', "?", ":", ',']
56 | expr . DIV_AS expr
57 | expr . MOD_AS expr
58 | expr . MUL_AS expr
59 | expr . ADD_AS expr
60 | expr . MIN_AS expr
61 | expr . LE expr
62 | expr . GE expr
63 | expr . NE expr
64 | expr . EQ expr
65 | expr . GT expr
66 | expr . LT expr
68 | expr . "?" expr ":" expr
'!' shift, and go to state 44
'&' shift, and go to state 45
'*' shift, and go to state 46
LE shift, and go to state 47
GE shift, and go to state 48
EQ shift, and go to state 49
NE shift, and go to state 50
LT shift, and go to state 51
GT shift, and go to state 52
MUL_AS shift, and go to state 53
DIV_AS shift, and go to state 54
ADD_AS shift, and go to state 55
MIN_AS shift, and go to state 56
MOD_AS shift, and go to state 57
INCR shift, and go to state 58
DCRS shift, and go to state 59
"[" shift, and go to state 60
'=' shift, and go to state 61
"?" shift, and go to state 62
'!' [reduce using rule 55 (expr)]
'&' [reduce using rule 55 (expr)]
'*' [reduce using rule 55 (expr)]
LE [reduce using rule 55 (expr)]
GE [reduce using rule 55 (expr)]
EQ [reduce using rule 55 (expr)]
NE [reduce using rule 55 (expr)]
LT [reduce using rule 55 (expr)]
GT [reduce using rule 55 (expr)]
MUL_AS [reduce using rule 55 (expr)]
DIV_AS [reduce using rule 55 (expr)]
ADD_AS [reduce using rule 55 (expr)]
MIN_AS [reduce using rule 55 (expr)]
MOD_AS [reduce using rule 55 (expr)]
INCR [reduce using rule 55 (expr)]
DCRS [reduce using rule 55 (expr)]
"[" [reduce using rule 55 (expr)]
'=' [reduce using rule 55 (expr)]
"?" [reduce using rule 55 (expr)]
$default reduce using rule 55 (expr)
If you use precedence declarations to disambiguate expression parses:
You need to declare every operator. (In the state whose transitions you cite, the error is the related specifically to =, whose precedence you have not declared.)
You need to list the precedence relations in the correct order, according to the grammar. (For example, & does not bind nearly as tightly as *.) Also, + and - are left associative.
Alternatively, you could use the expression syntax in the C grammar in the C standard as a basis. It is written with explicit precedence -- i.e. without the need for precedence declarations. In either case, it is worthwhile taking the time to understand how the grammar works, both as a description of the language and to drive the parse. Precedence declarations work by forcing the parser to resolve certain ambiguities definitely as shifts or reductions, so they are very similar in practice to the unambiguous grammar which does not use precedence.