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