Re: bison/yacc: shift/reduce conflict using %prec for composition

longjonathan@comcast.net (J Long) wrote
> Would someone explain why a simple grammar such as this
>
> %left FUNCTION
>
> %%
>
> expr: 'A'
> | expr expr %prec FUNCTION
> ;
>
> causes a shift/reduce conflict in bison/yacc?
> [It's because precedences are attached to tokens, and there's no tokens
> in that rule. -John]


The esteemed moderator is almost right -- precedences are indeed on
tokens, but they are also on rules, which get precendences either from
their left-most token or from an explicit %prec declaration as above.


The problem in the above grammar is that 'A' has no precedence.


To understand this problem, you really need to understand in some
deatil how shift-reduce parsing works. Basically, at each state in
the machine, the parser looks at the next token to decide if it should
shift that token or reduce some rule. You get shift/reduce or
reduce/reduce conflicts if bison/yacc can't decide which it should be.
Precedence rules allow you to resolve these conflicts by telling it.


When there's a shift/reduce conflict, bison will compare the
precedence of the token to be shifted with the precedence of the rule
to be reduced. Whichever is higher gets done. So for the above
grammar, after having parsed two expressions, if it sees an 'A' it
needs to decide whether to reduce the two expressions to one, or shift
the A and parse more expressions.


So you neeed to give 'A' a higher precedence than FUNCTION, or, as it
declared `left', the same precedence.


To generalize this to more expressions, you need need to give any
token that might start an expression the same precedence as 'A'. This
can cause problems if you have some token that might be both the first
token in an expression, and some sort of infix operator, such as '-'.
In this case, you really want to give '-' two different precedences
depending on context. Unfortuntely there's no way to do that with
bison. The only real solution then is to use new non-terminal rules
instead of precendences to deal with the ambiguities.


Chris Dodd
cdodd@acm.org

Return to the comp.compilers page.
Search the comp.compilers archives again.