Debian Codegraph @

documentation/manual/algorithm/whenprec.yo

raw
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.