Debian Codegraph @

documentation/manual/algorithm/input.yo

raw
1 B() implements the parsing function in the member function tt(parse()). This
2 function obtains its tokens from the member tt(lex()) and processes all tokens
3 until a syntactic error, a non-recoverable error, or the end of input is
4 encountered.
5
6 The algorithm used by tt(parse()) is the same, irrespective of the used
7 grammar. In fact, the tt(parse()) member's behavior is completely determined
8 by the tables generated by b().
9
10 The parsing algorithm is known as the em(shift-reduce) (S/R) algorithm, and it
11 allows tt(parse()) to perform two actions while processing series of tokens:
12 itemization(
13 it() When a token is received in a state in which that token is required
14 for a transition to another state (e.g., a tt(NR) token is observed in
15 state 1 of the example's grammar) a transition to state 3 is performed.
16 it() When a state is reached which calls for a (default) reduction (e.g.,
17 state 3 of the example's grammar) a reduction is performed.
18 )
19
20 The parsing function maintains two stacks, which are manipulated by the above
21 two actions: a state stack and a value stack. These stacks are not accessible
22 to the parser: they are private data structures defined in the parser's base
23 class. The parsing member tt(parse()) may use the following member functions
24 to manipulate these stacks:
25 itemization(
26 itt(push_(stateIdx)) pushes tt(stateIdx) on the state stack and pushes
27 the current semantic value (i.e., tt(LTYPE_ d_val_)) on the value stack;
28 itt(pop_(size_t count = 1)) removes tt(count) elements from the two
29 stacks;
30 itt(top_()) returns the state currently on top of the state stack;
31 )
32
33 Apart from the state- and semantic stacks, the S/R algorithm itself sometimes
34 needs to push a token on a two-element stack. Rather than using a formal
35 stack, two variables (tt(d_token_) and tt(d_nextToken_)) are used to
36 implement this little token-stack. The member function tt(pushToken_())
37 pushes a new value on the token stack, the member tt(popToken_())
38 pops a previously pushed value from the token stack. At any time,
39 tt(d_token_) contains the topmost element of the token stack.
40
41 The member tt(nextToken()) determines the next token to be processed. If the
42 token stack contains a value it is returned. Otherwise, tt(lex()) is called to
43 obtain the next token to be pushed on the token stack.
44
45 The member tt(lookup()) looks up the current token in the current state's
46 tt(SR_) table. For this a simple linear search algorithm is used. If
47 searching fails to find an action for the token an tt(UNEXPECTED_TOKEN_)
48 exception is thrown, which starts the error recovery. If an action was found,
49 it is returned.
50
51 Rules may have actions associated with them. These actions are executed when a
52 grammatical rule has been completely recognized. This is always at the end of
53 a rule: mid-rule actions are converted by b() into pseudo nonterminals,
54 replacing mid-rule action blocks by these pseudo nonterminals. The pseudo
55 nonterminals show up in the verbose grammar output as rules having LHSs
56 starting with tt(#). So, once a rule has been recognized its action (if
57 defined) is executed. For this the member function tt(executeAction()) is
58 available.
59
60 Finally, the token stack can be cleared using the member tt(clearin()).
61
62 Now that the relevant support functions have been introduced, the S/R
63 algorithm itself turns out to be a fairly simple algorithm. First, the
64 parser's stack is initialized with state 0 and the token stack is
65 cleared. Then, in a never ending loop:
66 itemization(
67 it() If a state needs a token (i.e., tt(REQ_TOKEN) has been specified for
68 that state), tt(nextToken()) is called to obtain the next token;
69 it() From the token and the current state tt(lookup()) determines the next
70 action;
71 it() If a shifting action was called for the next state is pushed on
72 the stack and the token is popped off the token stack.
73 it() If a reduction was called for that rule's action block is executed
74 followed by a reduction of the production rule (performed by tt(reduce_())):
75 the semantic and state stacks are reduced by the number of elements found in
76 that production rule, and the production rule's LHS is pushed on the token
77 stack
78 it() If the state/token combination indicates that the input is accepted
79 (normally: when tt(EOF) is encountered in state 1) then the parsing function
80 terminates, returning 0.
81 )
82
83 The following table shows the S/R algorithm in action when the example grammar
84 is given the input tt(3 + 4 + 5). The first column shows the (remaining)
85 input, the second column the current token stack (with tt(-) indicating an
86 empty token stack), the third column the state stack. The fourth column
87 provides a short description. The leftmost elements of
88 the stacks represent the tops of the stacks. The information shown below is
89 also (in more elaborate form) shown when the tt(--debug) option is provided to
90 B() when generating the parsing function.
91
92 table(7)(rllrlll)(
93 rowline()
94 row(cell(remaining input)cell( )cell(token stack)cell( )cell(state stack)
95 cell( )cell(description))
96 rowline()
97 ttrow(3 + 4 + 5) (-) ( 0) (initialization)
98 ttrow(3 + 4 + 5) (start) ( 0) (reduction by rule 2)
99 ttrow(3 + 4 + 5) (-) ( 1 0) (shift `start')
100 ttrow( + 4 + 5) (NR) ( 1 0) (obtain NR token)
101 ttrow( + 4 + 5) (-) ( 3 1 0) (shift NR)
102 ttrow( + 4 + 5) (expr) ( 1 0) (reduction by rule 3)
103 ttrow( + 4 + 5) (-) ( 2 1 0) (shift `expr')
104 ttrow( 4 + 5) (+) ( 2 1 0) (obtain `+' token)
105 ttrow( 4 + 5) (-) ( 4 2 1 0) (shift `+')
106 ttrow( + 5) (NR) ( 4 2 1 0) (obtain NR token)
107 ttrow( + 5) (-) (3 4 2 1 0) (shift NR)
108 ttrow( + 5) (expr) ( 4 3 1 0) (reduction by rule 3)
109 ttrow( + 5) (-) (5 4 3 1 0) (shift `expr')
110 ttrow( 5) (+) (5 4 3 1 0) (obtain `+' token)
111 ttrow( 5) (expr +) ( 1 0) (reduction by rule 4)
112 ttrow( 5) (+) ( 2 1 0) (shift `expr')
113 ttrow( 5) (-) ( 4 2 1 0) (shift '+')
114 ttrow( ) (NR) ( 4 2 1 0) (obtain NR token)
115 ttrow( ) (-) (3 4 2 1 0) (shift NR)
116 ttrow( ) (expr) ( 4 2 1 0) (reduction by rule 3)
117 ttrow( ) (-) (5 4 2 1 0) (shift `expr')
118 ttrow( ) (EOF) (5 4 2 1 0) (obtain EOF)
119 ttrow( ) (expr EOF) ( 1 0) (reduction by rule 4)
120 ttrow( ) (EOF) ( 2 1 0) (shift `expr')
121 ttrow( ) (start EOF) ( 2 1 0) (reduction by rule 1)
122 ttrow( ) (EOF) ( 1 0) (shift `start')
123 ttrow( ) (EOF) ( 1 0) (ACCEPT)
124 rowline()
125 )
126
127
128