Re: Yacc precedence bug

> %token NUMBER
> %left PLUS
> %left MUL
>
> %%
>
> expr : expr PLUS expr %prec MUL
> { $$ = $1 + $3; }
> | expr MUL expr %prec PLUS
> { $$ = $1 * $3; }
> | NUMBER
> ;
> %%


The above parses 2*7+4 like (2*7)+4, which is not what the author
wants. Apparently, because of other productions, he can not simply
reverse the $left PLUS and %left MUL declarations.


The problem lies in the fact that (Berkeley) yacc uses the
same array internally to specify both the production's precedence and
its associativity. (Was it fuzzy thinking, or saving the then-precious
few bytes of memory?) Thus the %prec PLUS directive above not only
changes the production's precedence to PLUS, it also changes it
so that it resolves the shift/reduce confict on PLUS to a reduce action,
because PLUS is left-associative. The fix would probably be more trouble
than it is worth: keep two arrays, one for precedence and one indicating
the token which gives a production its associativity. Make the %prec
directive change only the precedence array. When resolving the shift/reduce
on PLUS, first check the associativity array to determine if it
contains the same token that is potentially being shifted. If so, use the
applicable associativity rule. If not, use precedence.


But be of good cheer. You can get the job done without resorting to
precedence. The following is untested, but you'll get the idea...




  %token NUMBER
  %left PLUS /* "left" is redundant. "token" would do. */
  %left MUL /* Ditto */


  %%


  /* The following is backwards to the usual precedence. */
  expr : mulop;
  ;


  mulop : mulop MUL addop { $$ = $1 * $3; }
                | addop
  ;


  addop : addop PLUS factor { $$ = $1 + $3; }
                | factor
  ;


  factor : NUMBER
                | '(' expr ')' { $$ = $2; /* I just threw this in. */ }
  ;


  %%
--

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