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

Answer 2

Precedence relations are only used to resolve shift/reduce conflicts. They cannot be used to resolve reduce/reduce conflicts because the precedence comparison is always between a production (which could be reduced) and a token (which could be shifted).

With that in mind, consider the process of parsing the expression:

div 7 - 3 - 2

(assuming that div is how you write div_token).

Each - could be either an infix subtraction operator or a prefix negation operator. In this context, since div must be followed by exactly two expressions, exactly one of the minus signs must be infix. But which? Is it

div (7-3) (-2)

or

div (7) (-3-2)

But of course, other contexts are also possible. If the expression were div 7 - 3 - 2 a then the only valid parse would be div ((7-3)-2) 8, whereas if the expression were div div 7 - 3 - 2 then the parse would have to be div (div 7 (-3)) (-2).

You can get more insight into the conflict by asking bison to create a parsing report using the -v option and looking at the .output file produced. With your grammar, that report shows that the reduce/reduce conflict is at State 35, which is:

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)]

(actions truncated for space)

The possible reductions correspond to LR items with a . at the end, which are E '-' E . and '-' E .. For most (but not quite all) lookahead tokens, either of these reductions are possible. (The precedence of * over the E: E '-' E rule precludes the possibility of the first reduction if * is the lookahead character; similarly for /.)

Mixing infix and prefix expressions like this is not usually a good idea, precisely because of this ambiguity.