Bison: If/Else reduce/reduce conflict

Question

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 .

rici rici · Accepted Answer · 2018-11-29T15:43:42

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:
1. Use UPPER_CASE for tokens and lower_case or camelCase for non-terminals.
2. Write words out in full. Rmvng vwls frm dntfrs mks yr cd nrdbl.
3. 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
4. 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 ')'
```

Bison: If/Else reduce/reduce conflict

1 Answers