Debian Codegraph @

documentation/manual/algorithm/pstates.yo

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