%token <token> PLUS MINUS INT
%left PLUS MINUS
THIS WORKS:
exp : exp PLUS exp;
exp : exp MINUS exp;
exp : INT;
THIS HAS 2 SHIFT/REDUCE CONFLICTS:
exp : exp binaryop exp;
exp : INT;
binaryop: PLUS | MINUS ;
WHY?
%token <token> PLUS MINUS INT
%left PLUS MINUS
THIS WORKS:
exp : exp PLUS exp;
exp : exp MINUS exp;
exp : INT;
THIS HAS 2 SHIFT/REDUCE CONFLICTS:
exp : exp binaryop exp;
exp : INT;
binaryop: PLUS | MINUS ;
WHY?
You need to specify a precedence for the
exp binop exp
rule if you want the precedence rules to resolve the ambiguity:With that change, all the conflicts are resolved.
Edit
The comments seem to indicate some confusion as to what the precedence rules in yacc/bison do.
The precedence rules are a way of semi-automatically resolving shift/reduce conflicts in the grammar. They're only semi-automatic in that you have to know what you are doing when you specify the precedences.
Bascially, whenever there is a shift/reduce conflict between a token to be shifted and a rule to be reduced, yacc compares the precedence of the token to be shifted and the rule to be reduced, and -- as long as both have assigned precedences -- does whichever is higher precedence. If either the token or the rule has no precedence assigned, then the conflict is reported to the user.
%left
/%right
/%nonassoc
come into the picture when the token and rule have the SAME precedence. In that case%left
means do the reduce,%right
means do the shift, and%nonassoc
means do neither, causing a syntax error at runtime if the parser runs into this case.The precedence levels themselves are assigned to tokens with
%left
/%right
/%nonassoc
and to rules with%prec
. The only oddness is that rules with no%prec
and at least one terminal on the RHS get the precedence of the last terminal on the RHS. This can sometimes end up assigning precedences to rules that you really don't want to have precedence, which can sometimes result in hiding conflicts due to resolving them incorrectly. You can avoid these problems by adding an extra level of indirection in the rule in question -- change the problematic terminal on the RHS to to a new non-terminal that expands to just that terminal.This is because the second is in fact ambiguous. So is the first grammar, but you resolved the ambiguity by adding
%left
.This
%left
does not work in the second grammar, because associativity and precedence are not inherited from rule to rule. I.e. thebinaryop
nonterminal does not inherit any such thing even though it producesPLUS
andMINUS
. Associativity and predecence are localized to a rule, and revolve around terminal symbols.We cannot do
%left binaryop
, but we can slightly refactor the grammar:That has no conflicts now because it is implicitly left-associative. I.e. the production of a longer and longer expression can only happen on the left side of the
binaryop
, because the right side is aterm
which produces only an INT.The output file describing the conflicted grammar produced by Bison (version 2.3) on Linux is as follows. The key information at the top is 'State 7 has conflicts'.
And here is the information about 'State 7':
The trouble is described by the
.
markers in the the lines marked1
. For some reason, the%left
is not 'taking effect' as you'd expect, so Bison identifies a conflict when it has readexp PLUS exp
and finds aPLUS
orMINUS
after it. In such cases, Bison (and Yacc) do the shift rather than the reduce. In this context, that seems to me to be tantamount to giving the rules right precedence.Changing the
%left
to%right
and omitting it do not change the result (in terms of the conflict warnings). I also tried Yacc on Solaris and it produce essentially the same conflict.So, why does the first grammar work? Here's the output:
The difference seems to be that in states 6 and 7, it is able to distinguish what to do based on what comes next.
One way of fixing the problem is:
I assume that this falls under what the Bison manual calls "Mysterious Conflicts". You can replicate that with:
which gives four S/R conflicts for me.