| 1 |
The member function tt(parse()) is implemented using a finite-state |
| 2 |
machine. The values pushed on the parser stack are not simply token type |
| 3 |
codes; they represent the entire sequence of terminal and nonterminal symbols |
| 4 |
at or near the top of the stack. The current state collects all the |
| 5 |
information about previous input which is relevant to deciding what to do |
| 6 |
next. |
| 7 |
|
| 8 |
Each time a look-ahead token is read, the current parser state together with |
| 9 |
the current (not yet processed) token are looked up in a table. This table |
| 10 |
entry can say em(Shift the token). This also specifies a new parser state, |
| 11 |
which is then pushed onto the top of the parser stack. Or it can say em(Reduce |
| 12 |
using rule number n). This means that a certain number of tokens or |
| 13 |
nonterminals are removed from the stack, and that the rule's nonterminal |
| 14 |
becomes the `next token' to be considered. That `next token' is then used in |
| 15 |
combination with the state then at the stack's top, to determine the next |
| 16 |
state to consider. This (next) state is then again pushed on the stack, and a |
| 17 |
new token is requested from the lexical scanner, and the process repeats |
| 18 |
itself. |
| 19 |
|
| 20 |
There are two special situations the parsing algorithm must consider: |
| 21 |
itemization( |
| 22 |
it() First, the lexical scanner may reach em(end-of-input). If the current |
| 23 |
state on top of the parser's stack is the start-state, then the reduction |
| 24 |
(which is called for in this situation) is in fact the (successful) end of the |
| 25 |
parsing process, and tt(parse()) returns the value 0, indicating a successful |
| 26 |
parsing. |
| 27 |
it() There is one other alternative: the table can say that the |
| 28 |
token is erroneous in the current state. This causes error processing to begin |
| 29 |
(see chapter ref(RECOVERY)). |
| 30 |
) |