Debian Codegraph @

documentation/manual/algorithm/lookahead.yo

raw
1 The b() parser does em(not) always perform a reduction when a state is reached
2 where an item has its dot position beyond the last element of its production
3 rule. For most languages such a simple strategy is incorrect. Instead, when a
4 reduction is possible, the parser sometimes `looks ahead' to the next token to
5 decide what to do.
6
7 Whenever a token is read, it is not immediately shifted; first it becomes the
8 em(look-ahead) token, which is not yet shifted on the stack. This allows the
9 parser to perform one or more reductions, with the look-ahead token still
10 waiting to be processed. Only when all available reductions have been
11 performed the look-ahead token is shifted on the stack. The phrase `all
12 em(available) reductions' does not necessarily mean all em(possible)
13 reductions. Depending on the look-ahead token, a shift rather than a reduce
14 may be performed in states in which both actions are possible.
15
16 Here is a simple case where a look-ahead token is required. The production
17 rules define expressions which may contain binary addition operators and
18 postfix unary factorial operators (`tt(!)'), as well as parentheses for
19 grouping expressions:
20 verb(
21 expr:
22 term '+' expr
23 |
24 term
25 ;
26
27 term:
28 '(' expr ')'
29 |
30 term '!'
31 |
32 NUMBER
33 ;
34 )
35 Suppose that the tokens `tt(1 + 2)' have been read and shifted; what
36 should be done? If the following token is `CLOSEPAR', then the first three
37 tokens must be reduced, forming an tt(expr). This is the only valid course,
38 because shifting the `CLOSEPAR' would produce the sequence of symbols
39 verb(
40 term 'CLOSEPAR'
41 )
42 which is not syntactically correct.
43
44 But if the next token is `tt(!)', then that token must be shifted so that
45 `tt(2 !)' can be reduced to recognize a tt(term). If in this case the parser
46 would perform a reduction then `tt(1 + 2)' would become an tt(expr). In that
47 case the `tt(!)' can't be shifted because doing so would result in the
48 sequence
49 verb(
50 expr '!'
51 )
52 which is also syntactically incorrect.
53
54 COMMENT(
55 As a technical aside: the current look-ahead token is stored in the parser's
56 private data member tt(d_token). This data member is not normally modified by
57 user-defined member functions. See section ref(SPECIAL).
58 END)
59
60