Bison reduce/reduce conflicts

Question

I have written following grammar:

%union{
    string *s;
    float num;
}
%token div_token mod_token sqrt_token it_token abs_token
%token <num> num_token 
%token <s> Stampa
%type <num> E


%left '+' '-'
%left '*' '/' div_token mod_token
%left UMINUS
%left abs_token sqrt_token


%%

Program: Program Line '\n'   { }
| Line  '\n' { }
;

Line: Stampa    {cout<<*$1<<endl;}
| E         {cout<<$1<<endl; broj = $1;}
| it_token      {cout<<broj<<endl;}
;

E: E '+' E {$$ = $1 + $3;}
| E '-' E {$$ = $1 - $3;}
| E '*' E {$$ = $1 * $3;}
| E '/' E {if($3!=0) 
              $$ = $1 / $3;
            else
              yyerror("Deljenje nulom");
            }
| mod_token E E {$$ = (float)((int)$2 % (int)$3);}
| div_token E E {$$ = (float)((int)($2 / $3));}
| sqrt_token E  { $$ = sqrt($2); }
| '(' E ')' {$$=$2;}
| abs_token E { $$ = abs($2);}
| '-' E %prec UMINUS {$$=-$2;}
| num_token {$$ = $1;}
;

Now, bison found 8 reduce/reduce conflicts. When I delete line

| '-' E %prec UMINUS {$$=-$2;}

there are none. I think priorities and associative property are well defined. Can someone tell me how to resolve conflicts?

Answer 1

Now, bison found 8 reduce/reduce conflicts. When I delete line

| '-' E %prec UMINUS {$$=-$2;}

there are none. I think priorities and associative property are well defined. Can someone tell me how to resolve conflicts?

This should fix the problem:

%union{
      string *s;
      float num;
}
%token div_token mod_token sqrt_token it_token abs_token
%token <num> num_token 
%token <s> Stampa
%type <num> E

%left '+' '-'
%left '*' '/' div_token mod_token
%left UMINUS
%left abs_token sqrt_token

%%

Program: Program Line '\n'   { }
| Line  '\n' { }
;

Line: Stampa    {cout<<*$1<<endl;}
| E         {cout<<$1<<endl; broj = $1;}
| it_token      {cout<<broj<<endl;}
;

E: E '+' E {$$ = $1 + $3;}
| E '-' E {$$ = $1 - $3;}
| E '*' E {$$ = $1 * $3;}
| E '/' E {if($3!=0) 
                $$ = $1 / $3;
                    else
                yyerror("Deljenje nulom");
          }
| E mod_token E {$$ = (float)((int)$1 % (int)$3);}
| E div_token E {$$ = (float)((int)($1 / $3));}
| sqrt_token E  { $$ = sqrt($2); }
| '(' E ')' {$$=$2;}
| abs_token E { $$ = abs($2);}
| '-' %prec UMINUS E {$$=-$2;}
| num_token {$$ = $1;}
;

This fixes a couple of issues. You probably meant:

| E mod_token E {$$ = (float)((int)$1 % (int)$3);}
| E div_token E {$$ = (float)((int)($1 / $3));}

And it is more clear to write the following:

| '-' %prec UMINUS E {$$=-$2;}

You can see the conflicts with bison option -v which produces a xyz.output:

state 35

    6 E: E . '+' E
    7  | E . '-' E
    7  | E '-' E .
    8  | E . '*' E
    9  | E . '/' E
   15  | '-' E 

.

    div_token   reduce using rule 7 (E)
    div_token   [reduce using rule 15 (E)]
    mod_token   reduce using rule 7 (E)
    mod_token   [reduce using rule 15 (E)]
    sqrt_token  reduce using rule 7 (E)
    sqrt_token  [reduce using rule 15 (E)]
    abs_token   reduce using rule 7 (E)
    abs_token   [reduce using rule 15 (E)]
    num_token   reduce using rule 7 (E)
    num_token   [reduce using rule 15 (E)]
    '+'         reduce using rule 7 (E)
    '+'         [reduce using rule 15 (E)]
    '-'         reduce using rule 7 (E)
    '-'         [reduce using rule 15 (E)]
    '*'         reduce using rule 15 (E)
    '/'         reduce using rule 15 (E)
    '\n'        reduce using rule 15 (E)
    '('         reduce using rule 7 (E)
    '('         [reduce using rule 15 (E)]
    ')'         reduce using rule 15 (E)
    $default    reduce using rule 7 (E)

The operator reductions on div_token and mod_token are suspect. The ambiguity of the grammar is caused by these operators applied to two expressions E.

EDIT

Perhaps you are looking to keep the prefix div and mod operators. If so, you need to disambiguate the grammar. One possible solution is:

| mod_token F F {$$ = (float)((int)$2 % (int)$3);}
| div_token F F {$$ = (float)((int)($2 / $3));}
| F
;
F: '(' E ')' {$$=$2;}
| sqrt_token E  { $$ = sqrt($2); }
| abs_token E { $$ = abs($2);}
| '-' %prec UMINUS E {$$=-$2;}
| num_token {$$ = $1;}
;

and add the type of F:

%type <num> E F