Editing LR parser (section)

=== Walkthrough ===

The parser starts out with the stack containing just the initial state ('0'):
: ['''0''']

The first symbol from the input string that the parser sees is '1'. To find the next action (shift, reduce, accept or error), the action table is indexed with the current state (the "current state" is just whatever is on the top of the stack), which in this case is 0, and the current input symbol, which is '1'. The action table specifies a shift to state 2, and so state 2 is pushed onto the stack (again, all the state information is in the stack, so "shifting to state 2" is the same as pushing 2 onto the stack). The resulting stack is
: ['''0''' '1' '''2''']

where the top of the stack is 2. For the sake of explaining the symbol (e.g., '1', B) is shown that caused the transition to the next state, although strictly speaking it is not part of the stack.

In state 2, the action table says to reduce with grammar rule 5 (regardless of what terminal the parser sees on the input stream), which means that the parser has just recognized the right-hand side of rule 5. In this case, the parser writes 5 to the output stream, pops one state from the stack (since the right-hand side of the rule has one symbol), and pushes on the stack the state from the cell in the goto table for state 0 and B, i.e., state 4. The resulting stack is:
: ['''0''' B '''4''']

However, in state 4, the action table says the parser should now reduce with rule 3. So it writes 3 to the output stream, pops one state from the stack, and finds the new state in the goto table for state 0 and E, which is state 3. The resulting stack:
: ['''0''' E '''3''']

The next terminal that the parser sees is a '+' and according to the action table it should then shift to state 6:
: ['''0''' E '''3''' '+' '''6''']

The resulting stack can be interpreted as the history of a [[finite-state machine]] that has just read a nonterminal E followed by a terminal '+'. The transition table of this automaton is defined by the shift actions in the action table and the goto actions in the goto table.

The next terminal is now '1' and this means that the parser performs a shift and go to state 2:
: ['''0''' E '''3''' '+' '''6''' '1' '''2''']

Just as the previous '1' this one is reduced to B giving the following stack:
: ['''0''' E '''3''' '+' '''6''' B '''8''']

The stack corresponds with a list of states of a finite automaton that has read a nonterminal E, followed by a '+' and then a nonterminal B. In state 8 the parser always performs a reduce with rule 2. The top 3 states on the stack correspond with the 3 symbols in the right-hand side of rule 2. This time we pop 3 elements off of the stack (since the right-hand side of the rule has 3 symbols) and look up the goto state for E and 0, thus pushing state 3 back onto the stack
: ['''0''' E '''3''']

Finally, the parser reads a '$' (end of input symbol) from the input stream, which means that according to the action table (the current state is 3) the parser accepts the input string. The rule numbers that will then have been written to the output stream will be [5, 3, 5, 2] which is indeed a [[rightmost derivation]] of the string "1 + 1" in reverse.