Re: Yacc precedence bug

Stephen Adams <>
Fri, 11 Jan 91 13:04:53 GMT

          From comp.compilers

Related articles
Yacc precedence bug (S Voogd10 Jan 91 11:20 GMT) (1991-01-10)
Re: Yacc precedence bug megatest! (1991-01-11)
Re: Yacc precedence bug corbett@road.Eng.Sun.COM (1991-01-11)
Re: Yacc precedence bug (Stephen Adams) (1991-01-11)
Re: Yacc precedence bug (Lars Henrik Mathiesen) (1991-01-11)
Re: Yacc precedence bug (Klaus Thalhofer) (1991-01-14)
| List of all articles for this month |

Newsgroups: comp.compilers
From: Stephen Adams <>
In-Reply-To:'s message of 10 Jan 91 10:30:02 GMT
Keywords: yacc, parse, debug
Organization: Compilers Central
References: <>
Date: Fri, 11 Jan 91 13:04:53 GMT

In article <> (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

  > %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

    * 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
Computer Science S.R.Adams@sot-ecs.uucp
Southampton University
Southampton SO9 5NH, UK

Post a followup to this message

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