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