[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |

### 5.3.1 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 subtraction 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 difference.
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)`’. Clearly, then, the choice of shift or reduce should depend on the relative precedence of the operators ‘

`op`3`-`’ 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 lookahead token is ‘`-`’: shifting
makes right-associativity.

[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |

This document was generated on *December 1, 2013* using *texi2html 5.0*.