B() implements the parsing function in the member function tt(parse()). This function obtains its tokens from the member tt(lex()) and processes all tokens until a syntactic error, a non-recoverable error, or the end of input is encountered. The algorithm used by tt(parse()) is the same, irrespective of the used grammar. In fact, the tt(parse()) member's behavior is completely determined by the tables generated by b(). The parsing algorithm is known as the em(shift-reduce) (S/R) algorithm, and it allows tt(parse()) to perform two actions while processing series of tokens: itemization( it() When a token is received in a state in which that token is required for a transition to another state (e.g., a tt(NR) token is observed in state 1 of the example's grammar) a transition to state 3 is performed. it() When a state is reached which calls for a (default) reduction (e.g., state 3 of the example's grammar) a reduction is performed. ) The parsing function maintains two stacks, which are manipulated by the above two actions: a state stack and a value stack. These stacks are not accessible to the parser: they are private data structures defined in the parser's base class. The parsing member tt(parse()) may use the following member functions to manipulate these stacks: itemization( itt(push_(stateIdx)) pushes tt(stateIdx) on the state stack and pushes the current semantic value (i.e., tt(LTYPE_ d_val_)) on the value stack; itt(pop_(size_t count = 1)) removes tt(count) elements from the two stacks; itt(top_()) returns the state currently on top of the state stack; ) Apart from the state- and semantic stacks, the S/R algorithm itself sometimes needs to push a token on a two-element stack. Rather than using a formal stack, two variables (tt(d_token_) and tt(d_nextToken_)) are used to implement this little token-stack. The member function tt(pushToken_()) pushes a new value on the token stack, the member tt(popToken_()) pops a previously pushed value from the token stack. At any time, tt(d_token_) contains the topmost element of the token stack. The member tt(nextToken()) determines the next token to be processed. If the token stack contains a value it is returned. Otherwise, tt(lex()) is called to obtain the next token to be pushed on the token stack. The member tt(lookup()) looks up the current token in the current state's tt(SR_) table. For this a simple linear search algorithm is used. If searching fails to find an action for the token an tt(UNEXPECTED_TOKEN_) exception is thrown, which starts the error recovery. If an action was found, it is returned. Rules may have actions associated with them. These actions are executed when a grammatical rule has been completely recognized. This is always at the end of a rule: mid-rule actions are converted by b() into pseudo nonterminals, replacing mid-rule action blocks by these pseudo nonterminals. The pseudo nonterminals show up in the verbose grammar output as rules having LHSs starting with tt(#). So, once a rule has been recognized its action (if defined) is executed. For this the member function tt(executeAction()) is available. Finally, the token stack can be cleared using the member tt(clearin()). Now that the relevant support functions have been introduced, the S/R algorithm itself turns out to be a fairly simple algorithm. First, the parser's stack is initialized with state 0 and the token stack is cleared. Then, in a never ending loop: itemization( it() If a state needs a token (i.e., tt(REQ_TOKEN) has been specified for that state), tt(nextToken()) is called to obtain the next token; it() From the token and the current state tt(lookup()) determines the next action; it() If a shifting action was called for the next state is pushed on the stack and the token is popped off the token stack. it() If a reduction was called for that rule's action block is executed followed by a reduction of the production rule (performed by tt(reduce_())): the semantic and state stacks are reduced by the number of elements found in that production rule, and the production rule's LHS is pushed on the token stack it() If the state/token combination indicates that the input is accepted (normally: when tt(EOF) is encountered in state 1) then the parsing function terminates, returning 0. ) The following table shows the S/R algorithm in action when the example grammar is given the input tt(3 + 4 + 5). The first column shows the (remaining) input, the second column the current token stack (with tt(-) indicating an empty token stack), the third column the state stack. The fourth column provides a short description. The leftmost elements of the stacks represent the tops of the stacks. The information shown below is also (in more elaborate form) shown when the tt(--debug) option is provided to B() when generating the parsing function. table(7)(rllrlll)( rowline() row(cell(remaining input)cell( )cell(token stack)cell( )cell(state stack) cell( )cell(description)) rowline() ttrow(3 + 4 + 5) (-) ( 0) (initialization) ttrow(3 + 4 + 5) (start) ( 0) (reduction by rule 2) ttrow(3 + 4 + 5) (-) ( 1 0) (shift `start') ttrow( + 4 + 5) (NR) ( 1 0) (obtain NR token) ttrow( + 4 + 5) (-) ( 3 1 0) (shift NR) ttrow( + 4 + 5) (expr) ( 1 0) (reduction by rule 3) ttrow( + 4 + 5) (-) ( 2 1 0) (shift `expr') ttrow( 4 + 5) (+) ( 2 1 0) (obtain `+' token) ttrow( 4 + 5) (-) ( 4 2 1 0) (shift `+') ttrow( + 5) (NR) ( 4 2 1 0) (obtain NR token) ttrow( + 5) (-) (3 4 2 1 0) (shift NR) ttrow( + 5) (expr) ( 4 3 1 0) (reduction by rule 3) ttrow( + 5) (-) (5 4 3 1 0) (shift `expr') ttrow( 5) (+) (5 4 3 1 0) (obtain `+' token) ttrow( 5) (expr +) ( 1 0) (reduction by rule 4) ttrow( 5) (+) ( 2 1 0) (shift `expr') ttrow( 5) (-) ( 4 2 1 0) (shift '+') ttrow( ) (NR) ( 4 2 1 0) (obtain NR token) ttrow( ) (-) (3 4 2 1 0) (shift NR) ttrow( ) (expr) ( 4 2 1 0) (reduction by rule 3) ttrow( ) (-) (5 4 2 1 0) (shift `expr') ttrow( ) (EOF) (5 4 2 1 0) (obtain EOF) ttrow( ) (expr EOF) ( 1 0) (reduction by rule 4) ttrow( ) (EOF) ( 2 1 0) (shift `expr') ttrow( ) (start EOF) ( 2 1 0) (reduction by rule 1) ttrow( ) (EOF) ( 1 0) (shift `start') ttrow( ) (EOF) ( 1 0) (ACCEPT) rowline() )