Next: Using Precedence Up: Precedence
When Precedence is Needed
Consider the following ambiguous grammar fragment (ambiguous because
the input `1 - 2 * 3' can be parsed in two different ways):
expr: expr '-' expr
| expr '*' expr
| expr '<' expr
| '(' expr ')'
Suppose the parser has seen the tokens `1', `-' and `2'; should it
reduce them via the rule for the addition operator? It depends on the
next token. Of course, if the next token is `)', we must reduce;
shifting is invalid because no single rule can reduce the token
sequence `- 2 )' or anything starting with that. But if the next token
is `*' or `<', we have a choice: either shifting or reduction would
allow the parse to complete, but with different results.
To decide which one Bison should do, we must consider the results.
If the next operator token OP is shifted, then it must be reduced first
in order to permit another opportunity to reduce the sum. The result
is (in effect) `1 - (2 OP 3)'. On the other hand, if the subtraction
is reduced before shifting OP, the result is `(1 - 2) OP 3'. Clearly,
then, the choice of shift or reduce should depend on the relative
precedence of the operators `-' and OP: `*' should be shifted first,
but not `<'.
What about input such as `1 - 2 - 5'; should this be `(1 - 2) - 5'
or should it be `1 - (2 - 5)'? For most operators we prefer the
former, which is called "left association". The latter alternative,
"right association", is desirable for assignment operators. The choice
of left or right association is a matter of whether the parser chooses
to shift or reduce when the stack contains `1 - 2' and the look-ahead
token is `-': shifting makes right-associativity.
automatically generated by info2www