Editing LR parser (section)

=== Finding the reachable item sets and the transitions between them ===

The first step of constructing the tables consists of determining the transitions between the closed item sets. These transitions will be determined as if we are considering a finite automaton that can read terminals as well as nonterminals. The begin state of this automaton is always the closure of the first item of the added rule: S → <big>{{color|#f7f|•}}</big> E eof:
: '''Item set 0'''
: S → <big>{{color|#f7f|•}}</big> E eof
: '''+''' E → <big>{{color|#f7f|•}}</big> E * B
: '''+''' E → <big>{{color|#f7f|•}}</big> E + B
: '''+''' E → <big>{{color|#f7f|•}}</big> B
: '''+''' B → <big>{{color|#f7f|•}}</big> 0
: '''+''' B → <big>{{color|#f7f|•}}</big> 1

The [[boldface]]d "'''+'''" in front of an item indicates the items that were added for the closure (not to be confused with the mathematical '+' operator which is a terminal). The original items without a "'''+'''" are called the ''kernel'' of the item set.

Starting at the begin state (S0), all of the states that can be reached from this state are now determined. The possible transitions for an item set can be found by looking at the symbols (terminals and nonterminals) found following the dots; in the case of item set 0 those symbols are the terminals '0' and '1' and the nonterminals E and B. To find the item set that each symbol <math display="inline">x \in \{0, 1, E, B\}</math> leads to,  the following procedure is followed for each of the symbols:
# Take the subset, ''S'', of all items in the current item set where there is a dot in front of the symbol of interest, ''x''.
# For each item in ''S'', move the dot to the right of ''x''.
# Close the resulting set of items.

For the terminal '0' (i.e. where x = '0') this results in:
: '''Item set 1'''
: B → 0 <big>{{color|#f7f|•}}</big>
and for the terminal '1' (i.e. where x = '1') this results in:
: '''Item set 2'''
: B → 1 <big>{{color|#f7f|•}}</big>
and for the nonterminal E (i.e. where x = E) this results in:
: '''Item set 3'''
: S → E <big>{{color|#f7f|•}}</big> eof
: E → E <big>{{color|#f7f|•}}</big> * B
: E → E <big>{{color|#f7f|•}}</big> + B
and for the nonterminal B (i.e. where x = B) this results in:
: '''Item set 4'''
: E → B <big>{{color|#f7f|•}}</big>

The closure does not add new items in all cases - in the new sets above, for example, there are no nonterminals following the dot.

Above procedure is continued until no more new item sets are found. For the item sets 1, 2, and 4 there will be no transitions since the dot is not in front of any symbol. For item set 3 though, we have dots in front of terminals '*' and '+'. For symbol <math display="inline">x = \texttt{*}</math> the transition goes to:
: '''Item set 5'''
: E → E * <big>{{color|#f7f|•}}</big> B
: '''+''' B → <big>{{color|#f7f|•}}</big> 0
: '''+''' B → <big>{{color|#f7f|•}}</big> 1
and for  <math display="inline">x = \texttt{+}</math> the transition goes to:
: '''Item set 6'''
: E → E + <big>{{color|#f7f|•}}</big> B
: '''+''' B → <big>{{color|#f7f|•}}</big> 0
: '''+''' B → <big>{{color|#f7f|•}}</big> 1

Now, the third iteration begins.

For item set 5, the terminals '0' and '1' and the nonterminal B must be considered, but the resulting closed item sets for the terminals are equal to already found item sets 1 and 2, respectively. For the nonterminal B, the transition goes to:
: '''Item set 7'''
: E → E * B <big>{{color|#f7f|•}}</big>

For item set 6, the terminal '0' and '1' and the nonterminal B must be considered, but as before, the resulting item sets for the terminals are equal to the already found item sets 1 and 2. For the nonterminal B the transition goes to:
: '''Item set 8'''
: E → E + B <big>{{color|#f7f|•}}</big>

These final item sets 7 and 8 have no symbols beyond their dots so no more new item sets are added, so the item generating procedure is complete. The finite automaton, with item sets as its states is shown below.

The transition table for the automaton now looks as follows:

{| class="wikitable" style="text-align:center"
|- style="background:#e0e0d0;"
!  style="background:#d0e0ff; width:28%;"|Item Set
! style="width:12%;"|*
! style="width:12%;"|+
! style="width:12%;"|0
! style="width:12%;"|1
! style="width:12%;"|E
! style="width:12%;"|B
|-
!0 
|&nbsp; ||&nbsp; ||1      ||2      ||3      ||4
|-
!1 
|&nbsp; ||&nbsp; ||&nbsp; ||&nbsp; ||&nbsp; ||&nbsp;
|-
!2 
|&nbsp; ||&nbsp; ||&nbsp; ||&nbsp; ||&nbsp; ||&nbsp;
|-
!3 
|5      ||6      ||&nbsp; ||&nbsp; ||&nbsp; ||&nbsp;
|-
!4 
|&nbsp; ||&nbsp; ||&nbsp; ||&nbsp; ||&nbsp; ||&nbsp;
|-
!5 
|&nbsp; ||&nbsp; ||1      ||2      ||&nbsp; ||7
|-
!6 
|&nbsp; ||&nbsp; ||1      ||2      ||&nbsp; ||8
|-
!7 
|&nbsp; ||&nbsp; ||&nbsp; ||&nbsp; ||&nbsp; ||&nbsp;
|-
!8 
|&nbsp; ||&nbsp; ||&nbsp; ||&nbsp; ||&nbsp; ||&nbsp;
|}