I'm new in Bison. I'm getting reduce/reduce conflict error but not getting where it is happening .The error message is "conflicts: 1 reduce/reduce". This is my grammar rule .
%token INT FLOAT CHAR EXIT V_MAIN BS BE NL EQU CM ADD SUB MUL DIV LT GT LP RP PRINT IF ELSE THN HH
%token <VarNm> V_NM
%token <num> NUMBER
%token <flt> R_NUM
%type <num> EXP TERM FACTOR CON STATEMENTS
%type <VarNm> X
%nonassoc THN
%nonassoc ELSE
%start STRT
%left LT GT
%left PLUS MINUS
%left MULT DIV
%%
STRT : V_MAIN BS CODE BE {printf("Compilation complete. :)\n");}
| EXIT {exit(EXIT_SUCCESS);}
;
CODE : /* empty */
| CODE STATEMENTS NL {printf("Statements complete\n");}
| CODE DECLARATION NL {printf("Declaration complete\n");}
| STMNT
;
DECLARATION : TYPE V {printf("D\n");}
;
TYPE : INT {printf("I\n");}
| FLOAT {printf("F\n");}
| CHAR
;
V : V CM V_NM {AddNewVar($3);printf("V\n");}
| V_NM {AddNewVar($1);printf("Vn %s\n",$1);}
| /* empty */ {printf("E\n");}
;
STATEMENTS : { $$ = 0; }
| EXP EQU X {AsgnVal($3,$1);}
| PRINT EXP {printf("Output: %d\n",$2);}
| EXP { $$ = $1 ;}
;
STMNT : MIF NL
| UIF NL
;
MIF : IF CON THN HH MIF HH ELSE HH MIF HH {printf("MIF1\n");}
| CODE STATEMENTS NL
;
UIF : IF CON THN HH STMNT HH {printf("UIF1\n");}
| IF CON THN HH MIF HH ELSE HH UIF HH {printf("UIF2\n");}
;
CON : EXP GT EXP { $$ = $1 > $3? 1: 0 ; }
| EXP LT EXP { $$ = $1 < $3? 1: 0 ; }
| EXP EQU EXP { $$ = $1 == $3? 1: 0 ; }
;
X : V_NM { $$=$1;CheckIfFound($1);}
;
EXP : TERM
| EXP ADD TERM { $$ = $1 + $3; }
| EXP SUB TERM { $$ = $1 - $3; }
;
TERM : TERM MUL FACTOR { $$ = $1 * $3; }
| TERM DIV FACTOR { if($3){$$ = $1 / $3;}
else {printf("Division by zero\n");}
}
| FACTOR { $$ = $1; }
| X { $$=VarVal($1); }
;
FACTOR : NUMBER { $$ = $1; }
| LP EXP RP { $$ = $2; }
;
The conflict error started when I inserted the grammar for IF/ELSE. Excluding that portion my code works just fine . I would also like to know if there is any way to detect where is this conflict happening using command .
The problem is indeed triggered by your if
productions. It goes like this (leaving out other irrelevant productions):
MIF : CODE STATEMENTS NL
CODE : STMNT
| CODE STATEMENTS NL
STATEMENTS: %empty
STMNT: MIF NL
Note that NL
is always a possible lookahead for CODE
because CODE: CODE STATEMENTS NL
and STATEMENTS: %empty
, which means that CODE
can derive CODE NL
.)
CODE NL⇒ CODE STATEMENTS NL NL (CODE: CODE STATEMENTS NL)
⇒ STMNT STATEMENTS NL NL (CODE: STMNT)
⇒ MIF NL STATEMENTS NL NL (STMNT: MIF NL)
⇒ MIF NL STATEMENTS NL NL (MIF: CODE STATEMENTS NL)
⇒ CODE STATEMENTS NL NL STATEMENTS NL NL
That's certainly a reduce-reduce conflict. When the parser has found CODE STATEMENTS NL
and sees NL
as the lookahead, it could use either the reduction CODE: CODE STATEMENTS NL
or MIF: CODE STATEMENTS NL
.
If you were using the Wikipedia dangling-else page as a guide (or even if you weren't), take a careful look at the production closed_statement: non_if_statement
. (closed_statement
is the equivalent of your MIF
).
Although there is no magic command where_is_my_error
, it's pretty easy to see that problem using the report file which bison will produce if requested (with the -v
or --report
options). See a fully worked out example in the bison manual debugging chapter. Also super-useful is bison's trace facility, which will save you from having to scatter printf
statements throughout your parser (and later remove them).
Your grammar would be a lot more readable (to people other than you) if you conformed to the usual style guidelines:
UPPER_CASE
for tokens and lower_case
or camelCase
for non-terminals.Use bison's alias feature to write keywords as the keyword itself (in quotes):
%token T_THEN "then" T_IF "if" T_ELSE "else"
%%
matchedIf: "if" condition "then" HH matchedIf HH "else" HH matchedIf HH
See the bison manual chapter on Symbols
You can also use single-quoted character tokens to simplify your grammar. These don't even need to be declared:
term: term '*' factor
factor: '(' expression ')'