Node:Why Precedence, Next:Using Precedence, Up:Precedence
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.