[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
and
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
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- Ignore %prec followup,
Paul Hilfinger <=