How to fix the yacc error: (conflicts: 3 shift/reduce)

Question

How to fix the yacc error: (conflicts: 3 shift/reduce)

---

%{
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
char *scat2(char *a1,char *a2) {
char *t;
t = malloc( strlen(a1) + strlen(a2) + 1 );
strcat( t, a1 );
strcat( t, a2 );
return t;
}
char *scat3(char *a1,char *a2,char *a3) {
return scat2(scat2(a1,a2),a3);
}
char *scat4(char *a1,char *a2,char *a3,char *a4) {
return scat2(scat3(a1,a2,a3),a4);
}
char *scat5(char *a1,char *a2,char *a3,char *a4,char *a5) {
return scat2(scat4(a1,a2,a3,a4),a5);
}
char *scat6(char *a1,char *a2,char *a3,char *a4,char *a5, char *a6) {
return scat2(scat5(a1,a2,a3,a4,a5),a6);
}
char *scat7(char *a1,char *a2,char *a3,char *a4,char *a5, char *a6, char *a7) {
return scat2(scat6(a1,a2,a3,a4,a5,a6),a7);
}
%}
%union {
char *name;
}
%start program
%token ASSIGN NEG IF THEN ELSE TRUE FALSE EQ AND LE WHILE DO SKIP
%token <name> ID INTdenotation
%type <name> stmnt_list stmnt a_expr b_expr b_exp
%type <name> sum term primary
%%
program : stmnt_list
{ printf("%s\n", $1); }
;
stmnt_list : stmnt
{ $$ = $1; }
| stmnt_list ';' stmnt
{ $$ = scat5("Comp (",$1,") (",$3,")"); }
| '(' stmnt_list ')'
{ $$ = $2; }
;
stmnt : SKIP
{ $$ = "Skip"; }
| IF b_expr THEN stmnt_list ELSE stmnt_list
{ $$ = scat7("If (",$2,") (",$4,") (",$6,")"); }
| WHILE b_expr DO stmnt_list
{ $$ = scat5("While (",$2,") (",$4,")"); }
| ID ASSIGN a_expr
{ $$ = scat5("Ass \"", $1, "\" (",$3,")"); }
;
b_expr : b_expr AND b_exp
{ $$ = scat5("And (",$1,") (",$3,")"); }
| b_exp
{ $$ = $1; }
;
b_exp : TRUE
{ $$ = "TRUE"; }
| FALSE
{ $$ = "FALSE"; }
| a_expr EQ a_expr
{ $$ = scat5("Eq (",$1,") (",$3,")"); }
| a_expr LE a_expr
{ $$ = scat5("Le (",$1,") (",$3,")"); }
| NEG b_expr
{ $$ = scat3("Neg (",$2,")"); }
| '(' b_expr ')'
{ $$ = $2; }
;
a_expr : sum
{ $$ = $1; }
;
sum : term
{ $$ = $1; }
| sum '+' term
{ $$ = scat5("Add (",$1,") (",$3,")"); }
| sum '-' term
{ $$ = scat5("Sub (",$1,") (",$3,")"); }
;
term : primary
{ $$ = $1; }
| term '*' primary
{ $$ = scat5("Mult (",$1,") (",$3,")"); }
;
primary : INTdenotation
{ $$ = scat2("N ", $1); }
| ID
{ $$ = scat3("V \"", $1,"\""); }
| '(' a_expr ')'
{ $$ = $2; }
;
%%
#include "lex.yy.c"
main()
{
yyparse();
}

Answer 1

Use the -v option to produce a y.output file giving more detail on the grammar and conflicts. In your case, you have three conflicts that spring from two ambiguities in the grammar.

First, the rule bexpr : NEG b_expr means that an input like NEG a AND b can be parsed as either NEG ( a AND b ) or (NEG a) AND b. If you want the latter, you should move the NEG production to primary as (eg. primary : NEG primary)

In the y.output file, this shows up as a conflict in a state between reducing the NEG rule and shifting the AND rule, something like:

state 26

    9 b_expr: b_expr . AND b_exp
   15 b_exp: NEG b_expr .

    AND  shift, and go to state 30

    AND       [reduce using rule 15 (b_exp)]
    $default  reduce using rule 15 (b_exp)

You can see how this maps directly to the example I gave above.

Second, you have 'dangling statements' problem in both your IF and WHILE rules. For an input that looks something like WHILE x DO a; b it can't tell if both statements should be in the loop, or if one should be after (eg, is this (WHILE x DO a); b or WHILE x DO (a; b);. To fix this, you probably want to have only a single stmnt after a DO or ELSE rather than a stmnt_list

If you look in the y.output file at the other two conflict states, you again see this immediately