I'm trying to write a programming language using flex/bison in C. However, it reports 117 shift/reduce conflicts in my grammar. Of these, 44 are from the expression grammar. I don't understand why, since I have specified the precedence.
I have already tried adding precedence rules in my bison grammar file:
%token INTEGER DOUBLE IDENTIFIER STRING RUNE TUPLEID
%token BEGIN END WHILE IF CLASS METHOD
%nonassoc BLOCKSTMT
%nonassoc ELSE
%nonassoc IFX
%right '=' INC DEC ASSIGN INCN DECN MULN DIVN MODN
%nonassoc ASSIGNBLOCK
%right STOP
%left GE LE EQ NE
%left '+' '-'
%left '*' '/' '%'
%nonassoc UMINUS
This did not fix the problem. I have looked here on Stack Overflow for answers, but I find none that address the type of grammar I have written (which is pretty much just expanded on from a yacc tutorial).
expr:
INTEGER {
node_t *newInt = initNode(line, LEAFINT);
newInt->leaf.Integer = $1;
$$ = newInt;
}
| DOUBLE {
node_t *newDouble = initNode(line, LEAFDOUBLE);
newDouble->leaf.Double = $1;
$$ = newDouble;
}
| id { $$ = $1; }
| STRING {
node_t *newStr = initNode(line, LEAFSTRING);
newStr->leaf.String = $1;
$$ = newStr;
}
| RUNE {
node_t *newRune = initNode(line, LEAFRUNE);
if (strcmp($1, "\\n") == 0) {
newRune->leaf.Rune = '\n';
} else if (strcmp($1, "\\t") == 0) {
newRune->leaf.Rune = '\t';
} else if (strcmp($1, "\\\\") == 0) {
newRune->leaf.Rune = '\\';
} else if (strcmp($1, "\\'") == 0) {
newRune->leaf.Rune = '\'';
} else if (strlen($1) < 2) {
newRune->leaf.Rune = *$1;
} else {
yyerror("Error: Invalid rune literal.", line);
}
$$ = newRune;
}
| list { $$ = $1; }
| '-' expr %prec UMINUS {
node_t *negative = initNode(line, OPERATOR);
negative->operation = "-";
addOperand(negative, $2);
$$ = negative;
}
| expr '=' expr { $$ = binOpr(line, "=", $1, $3); }
| expr '+' expr { $$ = binOpr(line, "+", $1, $3); }
| expr '-' expr { $$ = binOpr(line, "-", $1, $3); }
| expr '*' expr { $$ = binOpr(line, "*", $1, $3); }
| expr '/' expr { $$ = binOpr(line, "/", $1, $3); }
| expr '%' expr { $$ = binOpr(line, "%", $1, $3); }
| expr EQ expr { $$ = binOpr(line, "==", $1, $3); }
| expr NE expr { $$ = binOpr(line, "!=", $1, $3); }
| expr '<' expr { $$ = binOpr(line, "<", $1, $3); }
| expr '>' expr { $$ = binOpr(line, ">", $1, $3); }
| expr LE expr { $$ = binOpr(line, "<=", $1, $3); }
| expr GE expr { $$ = binOpr(line, ">=", $1, $3); }
| expr INC {
node_t *increment = initNode(line, OPERATOR);
increment->operation = "++";
addOperand(increment, $1);
$$ = increment;
}
| INC expr {
node_t *increment = initNode(line, OPERATOR);
increment->operation = "++";
addOperand(increment, $2);
$$ = increment;
}
| expr DEC {
node_t *decrement = initNode(line, OPERATOR);
decrement->operation = "--";
addOperand(decrement, $1);
$$ = decrement;
}
| DEC expr {
node_t *decrement = initNode(line, OPERATOR);
decrement->operation = "--";
addOperand(decrement, $2);
$$ = decrement;
}
| expr INCN expr { $$ = binOpr(line, "+=", $1, $3); }
| expr DECN expr { $$ = binOpr(line, "-=", $1, $3); }
| expr MULN expr { $$ = binOpr(line, "*=", $1, $3); }
| expr DIVN expr { $$ = binOpr(line, "/=", $1, $3); }
| expr MODN expr { $$ = binOpr(line, "%=", $1, $3); }
| '(' expr ')' { $$ = $2 }
| expr STOP IDENTIFIER {
node_t *newID = initNode(line, LEAFID);
newID->leaf.Identifier = $3;
$$ = binOpr(line, ".", $1, newID);
}
| expr '[' expr ']' %prec STOP { $$ = binOpr(line, "index", $1, $3); }
| expr '(' expr ')' {
node_t *newList = initNode(line, LIST);
addOperand(newList, $3);
node_t *newCall = initNode(line, CALL);
addOperand(newCall, $1);
addOperand(newCall, newList);
$$ = newCall;
}
| expr parenlist {
node_t *newCall = initNode(line, CALL);
addOperand(newCall, $1);
addOperand(newCall, $2);
$$ = newCall;
}
I expected it to compile my compiler normally, but instead, when I do "bison -d -v parse.y" it gives me the warning "parse.y: warning: 117 shift/reduce conflicts [-Wconflicts-sr]." The y.output file says the following:
State 122
40 expr: expr . '=' expr
41 | expr . '+' expr
42 | expr . '-' expr
43 | expr . '*' expr
44 | expr . '/' expr
45 | expr . '%' expr
46 | expr . EQ expr
47 | expr . NE expr
48 | expr . '<' expr
48 | expr '<' expr .
49 | expr . '>' expr
50 | expr . LE expr
51 | expr . GE expr
52 | expr . INC
54 | expr . DEC
56 | expr . INCN expr
57 | expr . DECN expr
58 | expr . MULN expr
59 | expr . DIVN expr
60 | expr . MODN expr
62 | expr . STOP IDENTIFIER
63 | expr . '[' expr ']'
64 | expr . '(' expr ')'
65 | expr . parenlist
'=' shift, and go to state 60
INC shift, and go to state 61
DEC shift, and go to state 62
INCN shift, and go to state 63
DECN shift, and go to state 64
MULN shift, and go to state 65
DIVN shift, and go to state 66
MODN shift, and go to state 67
STOP shift, and go to state 68
GE shift, and go to state 69
LE shift, and go to state 70
EQ shift, and go to state 71
NE shift, and go to state 72
'+' shift, and go to state 73
'-' shift, and go to state 74
'*' shift, and go to state 75
'/' shift, and go to state 76
'%' shift, and go to state 77
'(' shift, and go to state 79
'<' shift, and go to state 80
'>' shift, and go to state 81
'[' shift, and go to state 82
'=' [reduce using rule 48 (expr)]
INC [reduce using rule 48 (expr)]
DEC [reduce using rule 48 (expr)]
INCN [reduce using rule 48 (expr)]
DECN [reduce using rule 48 (expr)]
MULN [reduce using rule 48 (expr)]
DIVN [reduce using rule 48 (expr)]
MODN [reduce using rule 48 (expr)]
STOP [reduce using rule 48 (expr)]
GE [reduce using rule 48 (expr)]
LE [reduce using rule 48 (expr)]
EQ [reduce using rule 48 (expr)]
NE [reduce using rule 48 (expr)]
'+' [reduce using rule 48 (expr)]
'-' [reduce using rule 48 (expr)]
'*' [reduce using rule 48 (expr)]
'/' [reduce using rule 48 (expr)]
'%' [reduce using rule 48 (expr)]
'(' [reduce using rule 48 (expr)]
'<' [reduce using rule 48 (expr)]
'>' [reduce using rule 48 (expr)]
'[' [reduce using rule 48 (expr)]
$default reduce using rule 48 (expr)
parenlist go to state 83
arglist go to state 84
The next state, State 123, appears to be identical. State 124 is also identical but without the conflicts.