[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Ignore %prec followup

From: Paul Hilfinger
Subject: Ignore %prec followup
Date: Sun, 27 May 2007 15:49:51 -0700

 > This is very unintuitive behavior and not very well documented either. 
 > Frankly after reading all this stuff I still do not understand how 
 > %prec can actually work for the unary minus example.

Well, the documentation is terse, but this all makes perfect sense if you
keep in mind how shift-reduce parsing works.  Specifically, the
next reduction in a shift-reduce parser always happens to the grammar
symbols *immediately to the left* of the current input position (that
is, immediately before the "lookahead symbol").  The parser never
reduces something beneath the top of the stack ("the stack" being the
sequence of grammar symbols---reduced or shifted over and as-yet
unreduced---that the parser has so far processed).  As a result, you
NEVER have a conflict between reductions

      expr '+' expr


      expr '*' expr

because these symbols cannot simultaneously be on top of the stack.

Instead, for an input such as a + x * y, the parser effectively must 
choose between using just x or x*y as the right operand of + at the
time it sees the '*': if it choose NOT to reduce at this time, we
eventually get the effect of a + (x * y), because then at the time 
y has been processed into an expr, the stack must contain

          expr + expr * expr

and only 'expr : expr '*' expr ' is eligible under the shift-reduce
procedure.  If on the other hand you choose to reduce on seeing *,
then you will also see expr * expr, but the first expr will have been
formed from expr + expr, giving the effect of (a + x) * y.

In other words, precedence only works in deciding between a *shift and
a reduce*, and therefore involves comparison of the precedence of a
rule and a terminal symbol.  In the case of a unary operator, such as

  - a * y

where we want to give unary '-' higher precedence than *, the relevant
decision by the parser occurs at the time it encounters the '*', NOT
after it has processed y.  The choice is between reducing 

      expr : '-' expr   

and shifting '*'.  So the REDUCTION expr : '-' expr must get higher
precedence than the SYMBOL '*'.  Since we have assigned '-' a lower
precedence than '*' for purposes of binary expressions, we must
override the default precedence that Bison assigns to this reduction,
and that is the role of %prec.  Alternatively, we could write

      /* Lowest precedence */
      %left BINARY_MINUS
      %left '*'
      %left '-'
      /* Highest precedence */


      expr : expr '*' expr
           | expr '-' expr     %prec BINARY_MINUS
           | '-' expr

 > Sorry for the earlier false report,

Not a problem.

Paul Hilfinger

reply via email to

[Prev in Thread] Current Thread [Next in Thread]