CODEWITHSUNDEEP
bison
user574183
user574183

Reputation: 716

bison precedence doesn't work

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 ?

Upvotes: 4

Views: 4006

Answers (4)

Sundar
Sundar

Reputation: 25

Consider for instance the following grammar:

           %nonassoc "="
           %left "+"
           %left "*"
           %precedence "("
           %%
           stmt:
             exp
           | "var" "=" exp
           ;

           exp:
             exp "+" exp
           | exp "*" "num"
           | "(" exp ")"
           | "num"
           ;

Bison reports:

           warning: useless precedence and associativity for "="
            %nonassoc "="
                      ^^^
           warning: useless associativity for "*", use %precedence
            %left "*"
                  ^^^
           warning: useless precedence for "("
            %precedence "("
                        ^^^

One would get the exact same parser with the following directives instead:

           %left "+"
           %precedence "*"

please try this you will get right answer.....

Upvotes: -2

Cooper Burns
Cooper Burns

Reputation: 91

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.

Upvotes: 9

dsrbecky
dsrbecky

Reputation: 151

I think all rules have precedence of 'INTEGER' since it is the last terminal

Upvotes: 0

Linus Kleen
Linus Kleen

Reputation: 34652

You can force precedence using reduction:

expr    : sum
        ;

sum     : sum '+' product {$$ = $1 + $3;}
        | product
        ;

product : number '*' product {$$ = $1 * $3;}
        | number
        ;

number  : INTEGER
        ;

That way, product is reduced before sum.

Upvotes: 2

Related Questions