| 1 |
Consider the following ambiguous grammar fragment (ambiguous because the input |
| 2 |
`tt(1 - 2 * 3)' can be parsed in two different ways): |
| 3 |
verb( |
| 4 |
expr: |
| 5 |
expr '-' expr |
| 6 |
| |
| 7 |
expr '*' expr |
| 8 |
| |
| 9 |
expr '<' expr |
| 10 |
| |
| 11 |
'(' expr ')' |
| 12 |
... |
| 13 |
; |
| 14 |
) |
| 15 |
Suppose the parser has seen the tokens `tt(1)', `tt(-') and `tt(2)'; |
| 16 |
should it reduce them via the rule for the addition operator? It depends on |
| 17 |
the next token. Of course, if the next token is `CLOSEPAR', we must reduce; |
| 18 |
shifting is invalid because no single rule can reduce the token sequence `tt(- |
| 19 |
2) CLOSEPAR' or anything starting with that. But if the next token is `tt(*)' |
| 20 |
or `tt(<)', we have a choice: either shifting or reduction would allow the |
| 21 |
parse to complete, but with different results. |
| 22 |
|
| 23 |
To decide which one b() should do, we must consider the results. If |
| 24 |
the next operator token tt(op) is shifted, then it must be reduced first in |
| 25 |
order to permit another opportunity to reduce the sum. The result is (in |
| 26 |
effect) `tt(1 - (2 op 3))'. On the other hand, if the subtraction is reduced |
| 27 |
before shifting tt(op), the result is `tt((1 - 2) op 3)'. Clearly, then, the |
| 28 |
choice of shift or reduce should depend on the relative precedence of the |
| 29 |
operators `tt(-)' and tt(op): `tt(*)' should be shifted first, but not |
| 30 |
`tt(<)'. |
| 31 |
|
| 32 |
What about input such as `tt(1 - 2 - 5)'; should this be `tt((1 - 2) - 5)' or |
| 33 |
should it be `tt(1 - (2 - 5))'? For most operators we prefer the former, which |
| 34 |
is called em(left association). The latter alternative, em(right association), |
| 35 |
is desirable for, e.g., assignment operators. The choice of left or right |
| 36 |
association is a matter of whether the parser chooses to shift or reduce when |
| 37 |
the stack contains `tt(1 - 2)' and the look-ahead token is `tt(-)': shifting |
| 38 |
results in right-associativity. |