|Yacc precedence bug firstname.lastname@example.org (S Voogd10 Jan 91 11:20 GMT) (1991-01-10)|
|Re: Yacc precedence bug email@example.com (1991-01-11)|
|Re: Yacc precedence bug corbett@road.Eng.Sun.COM (1991-01-11)|
|Re: Yacc precedence bug S.R.Adams@ecs.southampton.ac.uk (Stephen Adams) (1991-01-11)|
|Re: Yacc precedence bug firstname.lastname@example.org (Lars Henrik Mathiesen) (1991-01-11)|
|Re: Yacc precedence bug klaus%ipkima.hanse.de@RELAY.CS.NET (Klaus Thalhofer) (1991-01-14)|
|From:||Stephen Adams <S.R.Adams@ecs.southampton.ac.uk>|
|In-Reply-To:||email@example.com's message of 10 Jan 91 10:30:02 GMT|
|Keywords:||yacc, parse, debug|
|Date:||Fri, 11 Jan 91 13:04:53 GMT|
In article <firstname.lastname@example.org> email@example.com (S Voogd) writes:
> Dear comp.compiler-readers,
> While working with YACC, we came across a POSSIBLE BUG
> in the precedence mechanism of YACC.
Simon Voogd goes on to express surprise that the following
example grammar does not correctly swap the precedence of
PLUS and MUL:
> %token NUMBER
> %left PLUS
> %left MUL
> expr : expr PLUS expr %prec MUL
> | expr MUL expr %prec PLUS
> | NUMBER
> BUT the enclosed calculator gives the following results :
> 4+7*2 = 22 [ = (4+7)*2 ]
> 2*7+4 = 18 [ = (2*7)+4 ] (surely should be 22 !!!!!)
To understand why this does not work as you expected requires
understanding what yacc does with the precedence information.
Yacc does not `understand' precedence as the programming language concept
of operator precedence. To yacc, precedence is a number which is assigned
to *rules* (productions) and to *tokens*. This can be used to give the
effect of operator precedence and associativity.
When parsing 2*7+4 the decision whether to parse it as (2*7)+4 or 2*(7+4)
depends on the precedence of the rule expr : expr MUL expr *and* the
precedence of the token PLUS. By default the precedence of the rule is
taken from the token which appears in it. The %prec annotation only
changes the precedence of the rule, and not the token.
Yacc uses the precedence information to resolve the
with `expr MUL expr' on the stack and `PLUS' in the input
should I reduce `expr MUL expr' to an expr (the effect of
which is to give MUL a higher operator precedence) or
should I shift the PLUS (and eventually reduce a `expr
PLUS expr' to and expr effectively giving PLUS a higher
The decision is made by comparing the yacc-precedence of the
rule with that of the next input token.
if yacc-precedence(rule) > yacc-precedence(token)
expr : expr MUL expr %prec PLUS
causes the input 2*7+4 to be parsed with the precedence normally expected
of 2+7+4. This behaviour is almost impossible to understand if you think
+ and * have a fixed precedence.
If you want to get more confused change the associativity of PLUS from
%left to %right. Then 2*7+4 will parse as 2*(7+4) but only because 2+7+4
parses now as 2+(7+4).
* the only way to change the operator precedence of PLUS
and MUL is to exchange their order in the %left
* The way to reason about `%prec TOKEN' is to ask yourself
the question `How would this be parsed if this rule
* When trying things like this out use - and / rather than
+ and *. That way you will also be able to check that
the associativity of the operators is what you intended.
2+(3+4) = (2+3)+4 but 2-(3-4) != (2-3)-4, so you can
tell which way it has been parsed.
Stephen Adams S.R.Adams@ecs.soton.ac.uk
Computer Science S.R.Adams@sot-ecs.uucp
Southampton SO9 5NH, UK
Return to the
Search the comp.compilers archives again.