Editing LR parser (section)

== Additional example 1 + 1 ==
<!-- This section holds examples and narrative retained from an earlier, pre- May 2012 version of the LR parser article.-->
<!-- Further work is needed to reduce overlap and use a single notation throughout the old and new sections.-->
[[Image:LR Parser.png|right|framed|Bottom-up parse of 1+1]]

This example of LR parsing uses the following small grammar with goal symbol E:
: (1)   E → E * B
: (2)   E → E + B
: (3)   E → B
: (4)   B → 0
: (5)   B → 1

to parse the following input:
: '''1 + 1'''

=== Action and goto tables ===

The two LR(0) parsing tables for this grammar look as follows:

{| class=wikitable
|-  style="text-align:center; background:#e0e0e0;"
| '''''state'''''
| colspan="5"|'''''action'''''
| colspan="2"|'''''goto'''''
|- style="text-align:center;"
| style="width:12%;"|&nbsp;
|  style="width:11%; background:#d0e0ff;"|'''*'''
|  style="width:11%; background:#d0e0ff;"|'''+'''
|  style="width:11%; background:#d0e0ff;"|'''0'''
|  style="width:11%; background:#d0e0ff;"|'''1'''
|  style="width:11%; background:#d0e0ff;"|'''$'''
|  style="width:11%; background:#c0e0d0;"|'''E'''
|  style="width:11%; background:#c0e0d0;"|'''B'''
|- style="text-align:center;"
| '''0''' || &nbsp; || &nbsp; || s1     || s2    || &nbsp; ||  3     || 4
|- style="text-align:center;"
| '''1''' || r4     || r4     || r4     || r4     || r4     || &nbsp; || &nbsp;
|- style="text-align:center;"
| '''2''' || r5     || r5     || r5     || r5     || r5     || &nbsp; || &nbsp;
|- style="text-align:center;"
| '''3''' || s5     || s6     || &nbsp; || &nbsp; || acc    || &nbsp; || &nbsp;

|- style="text-align:center;"
| '''4''' || r3     || r3     || r3     || r3     || r3     || &nbsp; || &nbsp;
|- style="text-align:center;"
| '''5''' || &nbsp; || &nbsp; || s1     || s2     || &nbsp; || &nbsp; || 7
|- style="text-align:center;"
| '''6''' || &nbsp; || &nbsp; || s1     || s2     || &nbsp; || &nbsp; || 8
|- style="text-align:center;"
| '''7''' || r1     || r1     || r1     || r1     || r1     || &nbsp; || &nbsp;
|- style="text-align:center;"
| '''8''' || r2     || r2     || r2     || r2     || r2     || &nbsp; || &nbsp;
|}

The '''action table''' is indexed by a state of the parser and a terminal (including a special terminal $ that indicates the end of the input stream) and contains three types of actions:
* ''shift'', which is written as "s''n''" and indicates that the next state is ''n''
* ''reduce'', which is written as "r''m''" and indicates that a reduction with grammar rule ''m'' should be performed
* ''accept'', which is written as "acc" and indicates that the parser accepts the string in the input stream.

The '''goto table''' is indexed by a state of the parser and a nonterminal and simply indicates what the next state of the parser will be if it has recognized a certain nonterminal. This table is important to find out the next state after every reduction. After a reduction, the next state is found by looking up the '''goto table''' entry for top of the stack (i.e. current state) and the reduced rule's LHS (i.e. non-terminal).

=== Parsing steps ===

The table below illustrates each step in the process. Here the state refers to the element at the top of the stack (the right-most element), and the next action is determined by referring to the action table above. A $ is appended to the input string to denote the end of the stream.

{| class="wikitable"
! State
! Input stream
! Output stream
! Stack
! Next action
|-
| 0
| 1 + 1 $
|
| [0]
| Shift 2
|-
| 2
| + 1 $
|
| [0,2]
| Reduce 5
|-
| 4
| + 1 $
| 5
| [0,4]
| Reduce 3
|-
| 3
| + 1 $
| 5,3
| [0,3]
| Shift 6
|-
| 6
| 1 $
| 5,3
| [0,3,6]
| Shift 2
|-
| 2
| $
| 5,3
| [0,3,6,2]
| Reduce 5
|-
| 8
| $
| 5,3,5
| [0,3,6,8]
| Reduce 2
|-
| 3
| $
| 5,3,5,2
| [0,3]
| Accept
|}

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