Shift/reduce conflicts in yacc

Question

I am learning lex and yacc programming and this yacc program to validate and evaluate arithmetic expression in giving me 10 shift/reduce conflicts. Can you point out whats wrong with this program

This is 611.y

%{
#include<stdio.h>
int flag=1;
%}

%token id num 
%left '(' ')'
%left '+' '-'
%left '/' '*'
%nonassoc UMINUS

%%

stmt:
    expression { printf("\n valid exprn");}
    ;

expression:
    '(' expression ')' 
    | '(' expression {printf("\n Syntax error: Missing right paranthesis");}
    | expression '+' expression {printf("\nplus recog!");$$=$1+$3;printf("\n %d",$$);}
    | expression '+' { printf ("\n Syntax error: Right operand is missing ");}
    | expression '-' expression {printf("\nminus recog!");$$=$1-$3;printf("\n %d",$$);}
    | expression '-' { printf ("\n Syntax error: Right operand is missing ");}
    | expression '*' expression {printf("\nMul recog!");$$=$1*$3;printf("\n %d",$$);}
    | expression '*' { printf ("\n Syntax error: Right operand is missing ");}
    | expression '/' expression {printf("\ndivision recog!");if($3==0) printf("\ndivision cant be done, as divisor is zero.");else {$$=$1+$3;printf("\n %d",$$);}}
    | expression '/' { printf ("\n Syntax error: Right operand is missing ");}
    | expression '%' expression
    | expression '%' { printf ("\n Syntax error: Right operand is missing ");}
    | id
    | num 
;

%%

main()
{
    printf(" Enter an arithmetic expression\n");
    yyparse();
}

yyerror()
{
    printf(" Invalid arithmetic Expression\n");
    exit(1);
}

This is 611.l

%{
#include "y.tab.h"
#include<stdio.h>
#include<ctype.h>
extern int yylval;
int val;
%}

%%

[a-zA-Z][a-zA-Z0-9]* {printf("\n enter the value of variable %s:",yytext);scanf("%d",&val);yylval=val;return id;}
[0-9]+[.]?[0-9]* {yylval=atoi(yytext);return num;}
[ \t] ;
\n {return 0;}
. {return yytext[0];}
%%

int yywrap()
{
    return 1;
}

When I complie the code like this

lex 611.l

yacc -d 611.y

It gives me

yacc:10 shift/reduce conflicts.

Please help me out here.

n. 1.8e9-where's-my-share m. n. 1.8e9-where's-my-share m. · Accepted Answer · 2014-04-25T13:45:04

Two things are wrong:

Precedence of '%' is missing, add it to '/' '*'
The '(' expression error handler is ambiguous (in an expression (4*(2+3)+5*7 there are many ways to insert a missing parenthesis) and is in fact in conflict with the normal '(' expression ')' rule. It is non-trivial to make such a handler work. I would recommend to remove it and rely on built-in yacc error handler.

Simple error handling can be implemented like this:

stmt:
    expression { printf("\n valid exprn");}
    | error { printf(" Invalid arithmetic Expression\n"); }
    ;

 expression:
    '(' expression ')' 
    | '(' error ')' { printf(" Invalid arithmetic Expression\n"); }
    | ... /* all the rest */

You won't need all other error handlers too.

Shift/reduce conflicts in yacc

1 Answers