Why does this simple grammar have a shift / contraction conflict?
This is because the second is actually ambiguous. So the first grammar, but you solved the ambiguity by adding %left
.
This one %left
does not work in the second grammar because associativity and precedence are not inherited from rule to rule. That is, binaryop
nonterminal does not inherit any such thing, even if it produces PLUS
and MINUS
. Associativity and precedence are localized in the rule and revolve around terminal symbols.
We can't do it %left binaryop
, but we can refactor the grammar a bit:
exp : exp binaryop term
exp : term;
term : INT;
binaryop: PLUS | MINUS ;
This has no conflicts because it is implicitly left-associative. That is, the production of a longer and longer expression can only happen on the left side binaryop
, since the right side is term
, which only produces INTs.
source to share
You need to specify the priority for the rule exp binop exp
if you want the priority rules to resolve ambiguity:
exp : exp binaryop exp %prec PLUS;
With this change, all conflicts are resolved.
Edit
The comments seem to indicate some confusion as to what the precedence rules in yacc / bison do.
Precedence rules are a way to semi-automatically resolve shift / decrease conflicts in grammar. They are only semi-automatic in that you need to know what you are doing when you prioritize.
Basically, whenever there is a shift / decrease conflict between the token to be shifted and the rule to be reduced, yacc compares the priority of the token to be shifted and the rule to be reduced, and - as long as both have priorities - no matter which one is higher. If either the token or the rule has no priority, then the conflict is reported to the user.
%left
/ %right
/ %nonassoc
enter the image when the marker and rule have ONLY priority. In this case, %left
means abbreviation, %right
means shift, and %nonassoc
means that it is not, which leads to a syntax error at runtime if the parser works in this case.
Priority levels are assigned to tokens with %left
/ %right
/ %nonassoc
and rules with %prec
. The only oddity is that rules without %prec
and at least one terminal on the RHS take precedence over the last terminal on the RHS. This can sometimes lead to prioritizing rules that you really don't want to take precedence, which can sometimes lead to hiding conflicts due to mishandling them. You can avoid these problems by adding an extra layer of indirection in the rule in question - change the problem terminal to RHS to a new non-terminal that expands to that terminal.
source to share
I guess this falls under what the Bison management calls " Mysterious Conflicts ." You can replicate this with:
exp: exp plus exp;
exp: exp minus exp;
exp: INT;
plus: PLUS;
minus: MINUS;
which gives me four S / R conflicts.
source to share
The output file describing the conflicting grammar released by Bison (version 2.3) on Linux looks like this. The key information at the top is "State 7 has conflicts".
State 7 conflicts: 2 shift/reduce
Grammar
0 $accept: exp $end
1 exp: exp binaryop exp
2 | INT
3 binaryop: PLUS
4 | MINUS
Terminals, with rules where they appear
$end (0) 0
error (256)
PLUS (258) 3
MINUS (259) 4
INT (260) 2
Nonterminals, with rules where they appear
$accept (6)
on left: 0
exp (7)
on left: 1 2, on right: 0 1
binaryop (8)
on left: 3 4, on right: 1
state 0
0 $accept: . exp $end
INT shift, and go to state 1
exp go to state 2
state 1
2 exp: INT .
$default reduce using rule 2 (exp)
state 2
0 $accept: exp . $end
1 exp: exp . binaryop exp
$end shift, and go to state 3
PLUS shift, and go to state 4
MINUS shift, and go to state 5
binaryop go to state 6
state 3
0 $accept: exp $end .
$default accept
state 4
3 binaryop: PLUS .
$default reduce using rule 3 (binaryop)
state 5
4 binaryop: MINUS .
$default reduce using rule 4 (binaryop)
state 6
1 exp: exp binaryop . exp
INT shift, and go to state 1
exp go to state 7
And here is information about "State 7":
state 7
1 exp: exp . binaryop exp
1 | exp binaryop exp .
PLUS shift, and go to state 4
MINUS shift, and go to state 5
PLUS [reduce using rule 1 (exp)]
MINUS [reduce using rule 1 (exp)]
$default reduce using rule 1 (exp)
binaryop go to state 6
The problem is described by markers .
in the lines marked with 1
. For some reason, it %left
doesn't act as you'd expect, so Bison identifies a conflict when it reads exp PLUS exp
and finds after it PLUS
or MINUS
. In such cases, Bison (and Yacc) perform a shift, not a reduction. In this context, it seems to me to be tantamount to rules taking precedence.
Changing %left
to %right
and excluding it does not change the result (in terms of conflict warnings). I also tried Yacc on Solaris and created essentially the same conflict.
So why does the first grammar work? Here's the output:
Grammar
0 $accept: exp $end
1 exp: exp PLUS exp
2 | exp MINUS exp
3 | INT
Terminals, with rules where they appear
$end (0) 0
error (256)
PLUS (258) 1
MINUS (259) 2
INT (260) 3
Nonterminals, with rules where they appear
$accept (6)
on left: 0
exp (7)
on left: 1 2 3, on right: 0 1 2
state 0
0 $accept: . exp $end
INT shift, and go to state 1
exp go to state 2
state 1
3 exp: INT .
$default reduce using rule 3 (exp)
state 2
0 $accept: exp . $end
1 exp: exp . PLUS exp
2 | exp . MINUS exp
$end shift, and go to state 3
PLUS shift, and go to state 4
MINUS shift, and go to state 5
state 3
0 $accept: exp $end .
$default accept
state 4
1 exp: exp PLUS . exp
INT shift, and go to state 1
exp go to state 6
state 5
2 exp: exp MINUS . exp
INT shift, and go to state 1
exp go to state 7
state 6
1 exp: exp . PLUS exp
1 | exp PLUS exp .
2 | exp . MINUS exp
$default reduce using rule 1 (exp)
state 7
1 exp: exp . PLUS exp
2 | exp . MINUS exp
2 | exp MINUS exp .
$default reduce using rule 2 (exp)
The difference seems to be that in states 6 and 7, she is able to distinguish what to do based on the following.
One way to fix the problem:
%token <token> PLUS MINUS INT
%left PLUS MINUS
%%
exp : exp binaryop term;
exp : term;
term : INT;
binaryop: PLUS | MINUS;
source to share