Re: Yacc precedence bug

In article <7993.9101101030@guava.seg.npl.co.uk> slv@seg.npl.co.uk (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
shift-reduce conflict


      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
      operator precedence)?


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)
then reduce
else shift


Thus writing


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


In summary:


    * the only way to change the operator precedence of PLUS
        and MUL is to exchange their order in the %left
        statements.


    * The way to reason about `%prec TOKEN' is to ask yourself
        the question `How would this be parsed if this rule
        contained TOKEN?'


    * 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 University
Southampton SO9 5NH, UK
--

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