Fixing conflict in given code? "25 shift/reduce conflicts [-Wconflicts-sr] "

Question

// Lex file: for.l

alpha [A-Za-z]  
digit [0-9]  
%%  
[\t \n]   
for         return FOR;  
{digit}+    return NUM;  
{alpha}({alpha}|{digit})* return ID;  
"<="         return LE;  
">="         return GE;  
"=="         return EQ;  
"!="          return NE;  
"||"          return OR;  
"&&"         return AND;  
.            return yytext[0];  
%% 

// Yacc file: for.y

%{  
#include<stdio.h>  
#include<stdlib.h>  
%}  
%token ID NUM FOR LE GE EQ NE OR AND  
%right "="  
%left OR AND  
%left '>' '<' LE GE EQ NE  
%left '+' '-'  
%left '*' '/'  
%right UMINUS  
%left '!'  
%%  
S         : ST {printf("Input accepted\n"); exit(0);}  
ST       : FOR '(' E ';' E2 ';' E ')' DEF  
;  
DEF    : '{' BODY '}'  
| E';'   
| ST  
|  
;   
BODY  : BODY BODY  
| E ';'          
| ST  
|               
;  
E     : ID '=' E   
| E '+' E   
| E '-' E  
| E '*' E  
| E '/' E  
| E '<' E  
| E '>' E  
| E LE E  
| E GE E  
| E EQ E  
| E NE E  
| E OR E  
| E AND E  
| E '+' '+'   
| E '-' '-'  
| ID    
| NUM  
;
E2     : E'<'E  
| E'>'E  
| E LE E  
| E GE E  
| E EQ E  
| E NE E  
| E OR E  
| E AND E  
;      
%%  
#include "lex.yy.c"  
main() 
{  
printf("Enter the expression:\n");  
yyparse();  
}        

When I run it, it shows:

warning: 25 shift/reduce conflicts [-Wconflicts-sr]  
warning: 4 reduce/reduce conflicts [-Wconflicts-rr]  

How do I fix it?

Compiling method:

$ lex c.l  
$ yacc c.y  

Answer 1

There are various problems with your grammar; here are the most obvious ones:

1. You allow DEF to be empty. That means that

    for (i=0;i<1;i++)  for (j=0;j<1;j++) 
   

   could be two for statements with empty bodies, or a for statement whose body is another for statement (whose body is empty). So the empty production makes the grammar ambiguous.

2. BODY: BODY BODY is exponentially ambiguous, and no precedence declaration can compensate. The problem is made worse by the fact that you have an (also unnecessary) empty production for BODY.

3. E '+' '+' implies that the two + in i++ are separate tokens (and, indeed, your flex definition doesn't recognize ++ as a single tomen, unlime, for example, <=. That means that your grammar would consider i + + to be a valid post-increment. Perhaps that was intentional, but it certainly differs from any language I know. Anyway, it will turn out that the precedence declaration for + will apply, which is incorrect: 3*j++ should be parsed as 3*(j++), not (3*j)++. (The same is true for the post-decrement operator.)