warning: shift/reduce conflict

user_12311535 0
Viewed 98

I am trying to write a yacc program to find out whether an Arithmetic Expression is valid or not. My program seems to be running properly but I am getting a warning in console.

 warning: 2 shift/reduce conflicts [-Wconflicts-sr]

lex code

%{
    #include "y.tab.h"
%}

%%
[0-9]+ { return NUMBER; }
[_a-zA-Z][_a-zA-Z0-9]* { return ID; }
[-+*/] { return OPERATOR; }
.|\n { return *yytext; }
%%

int yywrap(){
    return 1;
}

yacc code

%{
    #include<stdio.h>
    int yylex();
    void yyerror(const char*);
%}

%token NUMBER ID OPERATOR

%%
E : E '\n' { return 0; }
  | E OPERATOR E
  | '(' E ')'
  | NUMBER
  | ID
  ;
%%

void yyerror(const char* s){
    printf("%s\n", s);
}

int main(){
    if(yyparse() == 0)
        printf("Valid Arithmetic Expression\n");
    else
        printf("Invalid Arithmetic Expression\n");
}

How can I get rid of this?

lex yacc bison compiler-construction
1 Answers

Your grammar is ambiguous; E OPERATOR E can apply to a + b * c in two ways (with two different meanings), depending on whether the first E is used to derive a or a + b.

Ambiguous grammars always have conflicts, because there is always a point in the parse where the parser could use more than one conflicting action. (The inverse is not true: a grammar with a conflict is not necessarily ambiguous. That will come later in your course, I suppose.)

So if you want to eliminate the conflict, you need to choose which of the two possible derivations above is correct (and all the similar ambiguities, but since they all have the same cause a relatively simple fix is possible).

user_15662210
Related