bison precedence doesn't work

Question

This is my flex code

%{
 #include "fl.tab.h"
%} 
    %% 
    [0-9]+  { yylval = atoi(yytext); 
        return INTEGER; } 
    \n  return 0;   
    [ \t]   ;   
    .   return yytext[0];
    %% 

And my bison code

%{ 
    #include <stdio.h> 
%} 
%token INTEGER
%left '+' '-'
%left '*'
%% 
Statement : expr {printf("%d\n",$1);}
        ;
expr :  expr '+' INTEGER  {$$ = $1 + $3;}
     |  expr '-' INTEGER  {$$ = $1 - $3;}
     |  expr '*' INTEGER  {$$ = $1 * $3;}        
     |  INTEGER {$$ = $1;}
     ;
%% 

int main(void){
   yyparse();
   return 0;
}

when i input 4 + 5 * 2 it give the output as 18. But the correct answer should be 14. Where am i getting it wrong ?

Answer 1

Your problem is that you have expr OP INTEGER for each rule.

The way you have it bison parses it as:

expr * 2 -> (4 + 5) * 2

It forces precedence to go to the left instead of precedence being determined by your precedence rules.

Precedence only applies when there is more than one way to parse the text, instead of what you have, try

expr :  expr '+' expr  {$$ = $1 + $3;}
     |  expr '-' expr  {$$ = $1 - $3;}
     |  expr '*' expr  {$$ = $1 * $3;}        
     |  INTEGER {$$ = $1;}
     ;

That way 5 + 4 * 2 can be parsed as either ((5 + 4) * 2) or (5 + (4 * 2)), and bison will consult precedence to determine the correct parse.