Revision: 2.1, 2006-01-01
Author: David R. Tribble
(david@tribble.com)
This document describes the various stages of the Honalee LR parser generator algorithm as it generates the item sets for a particular sample grammar.
This document is somewhat lengthy because it details every iteration and phase of the Honalee LR algorithm. Even though the chosen grammar is small, the algorithm performs quite a lot of work (19 iterations of its main loop).
The algorithm generates every possible canonical LR(1) item set for the grammar
at least once, merging and discarding the sets whenever possible,
eventually producing the minimal collection of LR(1) item sets
necessary for recognizing the grammar.
Since the chosen LR grammar is also LALR, the resulting collection of
LR(1) item sets contains exactly the same sets that
an LALR(1) item set generator produces.
Grammar
The grammar was chosen because it is fairly small, producing only a dozen or so LALR item sets (parser states). In spite of its small size, it contains enough complexity to illustrate how the algorithm handles duplicate and merged item sets.
%token '+'
%token '*'
%token '(' ')'
%token id
r0. $accept : Expr
r1. Expr : Expr '+' Term
r2. Expr : Term
r3. Term : Term '*' Factor
r4. Term : Factor
r5. Factor : '(' Expr ')'
r6. Factor : id
This grammar is ambiguous, containing two shift/reduce conflicts.
Such conflicts are typical of most grammars used for actual
programming languages.
First Sets
The following First sets (with one-symbol look-ahead) are generated from the grammar, and are used to generate closure items:
First($accept) = { '(', id }
First(Expr) = { '(', id }
First(Term) = { '(', id }
First(Factor) = { '(', id }
The algorithm is started by first initializing all of its lists and pointers. The state of the algorithm at any point in time is represented by the following elements, comprising a "to-do" list of item sets, an "incomplete" list, a "done" list, and a "come from" item set, and is depicted like this:
toDoList: - (empty) doneList: - (empty) incList: - (empty) comeFrom: - (empty)
Prior to entering the main loop of the algorithm, the initial item set i0 is created from the augmented grammar rule (r0). As each new item set is created, it is given a name of xN, starting with x0.
x0. initial item set [$accept -> . Expr, $end]* (-, -)
A brief note here on the notation used. Each item set is labeled by its name (e.g., "x0") and the transition that generated it (in the case of set x0, it is generated specially as the initial item set). Each item set is composed of one or more items, which depict the grammar rule they are derived from and the "." marker that indicates the progress of the recognition (i.e., the symbols within the rule that have been shifted onto the parser stack) up to that point. In the item above, for example, the rule is "$accept : Expr" and the marker is positioned immediately before the symbol "Expr". This is followed by n look-ahead symbols for an LR(n) parser (for this example, n is 1). These components of the item are enclosed within "[ ]" brackets. The bracket is followed by a "*" mark if the item is a kernel item. This is followed by an action enclosed within "( )" parentheses, and composed of either a look-ahead symbol and a reduction rule number, or a shifted symbol and a goto state number. An action of "(-, -)" indicates an action that has not yet been marked.
Once it has been created, the initial item set x0 is then appended to the to-do list. Since the to-do list is initially empty, item set x0 becomes the sole element of the list. The state of the algorithm, with the new additions underlined, is now:
doneList: - incList: - toDoList: x0 comeFrom: -
The main loop of the algorithm then begins. Phase 1 of the first iteration has no work to do because the incomplete list is empty.
The algorithm then proceeds to phase 2 of the first iteration, which pops the first item set from the to-do list, set x0. This phase generates all of the closure items for set x0. Shown here are the closure items that are added during each iteration of the closure generation algorithm:
kernel items:
[$accept -> . Expr, $end]* (-, -) kernel => 1
iteration 1:
[Expr -> . Expr '+' Term, $end] (-, -) closure 1 => 2
[Expr -> . Term, $end] (-, -) closure 1 => 3
iteration 2:
[Expr -> . Expr '+' Term, '+' ] (-, -) closure 2 => 4
[Expr -> . Term, '+' ] (-, -) closure 2 => 5
iteration 3:
[Term -> . Term '*' Factor, $end] (-, -) closure 3 => 6
[Term -> . Factor, $end] (-, -) closure 3 => 7
iteration 4:
[Expr -> . Expr '+' Term, '+' ] (-, -) duplicate
[Expr -> . Term, '+' ] (-, -) duplicate
iteration 5:
[Term -> . Term '*' Factor, '+' ] (-, -) closure 5 => 8
[Term -> . Factor, '+' ] (-, -) closure 5 => 9
iteration 6:
[Term -> . Term '*' Factor, '*' ] (-, -) closure 6 => 10
[Term -> . Factor, '*' ] (-, -) closure 6 => 11
iteration 7:
[Factor -> . '(' Expr ')', $end] (-, -) closure 7
[Factor -> . id, $end] (-, -) closure 7
iteration 8:
[Term -> . Term '*' Factor, '*' ] (-, -) duplicate
[Term -> . Factor, '*' ] (-, -) duplicate
iteration 9:
[Factor -> . '(' Expr ')', '+' ] (-, -) closure 9
[Factor -> . id, '+' ] (-, -) closure 9
iteration 10:
[Term -> . Term '*' Factor, '*' ] (-, -) duplicate
[Term -> . Factor, '*' ] (-, -) duplicate
iteration 11:
[Factor -> . '(' Expr ')', '*' ] (-, -) closure 11
[Factor -> . id, '*' ] (-, -) closure 11
The resulting item set, after rearranging the items for clarity, now looks like:
x0. initial item set
[$accept -> . Expr, $end]* (-, -) kernel
[Expr -> . Expr '+' Term, $end] (-, -) closure 1
[Expr -> . Expr '+' Term, '+' ] (-, -) closure 2
[Expr -> . Term, $end] (-, -) closure 1
[Expr -> . Term, '+' ] (-, -) closure 2
[Term -> . Term '*' Factor, $end] (-, -) closure 3
[Term -> . Term '*' Factor, '+' ] (-, -) closure 5
[Term -> . Term '*' Factor, '*' ] (-, -) closure 6
[Term -> . Factor, $end] (-, -) closure 3
[Term -> . Factor, '+' ] (-, -) closure 5
[Term -> . Factor, '*' ] (-, -) closure 6
[Factor -> . '(' Expr ')', $end] (-, -) closure 7
[Factor -> . '(' Expr ')', '+' ] (-, -) closure 9
[Factor -> . '(' Expr ')', '*' ] (-, -) closure 11
[Factor -> . id, $end] (-, -) closure 7
[Factor -> . id, '+' ] (-, -) closure 9
[Factor -> . id, '*' ] (-, -) closure 11
There are no reduction items to mark in the set, and there are no other sets in the done or incomplete lists that it could be merged with. Item set x0 is then appended to the incomplete list, which is just the set of tail elements of the done list. As each item set xN is moved to the incomplete list, it is renamed to iM, and it becomes an official item set of the grammar. Thus item set x0 is renamed to i0 and is moved to the end of the incomplete list.
Normally when a set is renamed and moved to the incomplete list, the comeFrom set is updated. However, at this stage of the algorithm there has been no comeFrom set established, so this step is skipped.
At this point, the state of the algorithm is:
doneList: - incList: i0 toDoList: - comeFrom: -
There are no more item sets in the to-do list, so this iteration stops.
Phase 1 of the next iteration examines the first set in the incomplete list, which is again item set i0 (and the only item set in the list at this point). New transition item sets are generated from this set, each set being composed of new kernel items created by shifting the transition symbol in each item within the set, which moves the marker one position to the right:
i0x0. initial item set [$accept -> . Expr, $end]* (Expr, x1) shift [Expr -> . Expr '+' Term, $end] (Expr, x1) shift [Expr -> . Expr '+' Term, '+' ] (Expr, x1) shift [Expr -> . Term, $end] (Term, x2) shift [Expr -> . Term, '+' ] (Term, x2) shift [Term -> . Term '*' Factor, $end] (Term, x2) shift [Term -> . Term '*' Factor, '+' ] (Term, x2) shift [Term -> . Term '*' Factor, '*' ] (Term, x2) shift [Term -> . Factor, $end] (Factor, x3) shift [Term -> . Factor, '+' ] (Factor, x3) shift [Term -> . Factor, '*' ] (Factor, x3) shift [Factor -> . '(' Expr ')', $end] ('(', x4) shift [Factor -> . '(' Expr ')', '+' ] ('(', x4) shift [Factor -> . '(' Expr ')', '*' ] ('(', x4) shift [Factor -> . id, $end] (id, x5) shift [Factor -> . id, '+' ] (id, x5) shift [Factor -> . id, '*' ] (id, x5) shift
Item set i0 is established as the comeFrom set, and new transition item sets are generated from the shift actions in it:
x1. goto(Expr) from i0
[$accept -> Expr ., $end]* (-, -)
[Expr -> Expr . '+' Term, $end]* (-, -)
[Expr -> Expr . '+' Term, '+' ]* (-, -)
x2. goto(Term) from i0
[Expr -> Term ., $end]* (-, -)
[Expr -> Term ., '+' ]* (-, -)
[Term -> Term . '*' Factor, $end]* (-, -)
[Term -> Term . '*' Factor, '+' ]* (-, -)
[Term -> Term . '*' Factor, '*' ]* (-, -)
x3. goto(Factor) from i0
[Term -> Factor ., $end]* (-, -)
[Term -> Factor ., '+' ]* (-, -)
[Term -> Factor ., '*' ]* (-, -)
x4. goto('(') from i0
[Factor -> '(' . Expr ')', $end]* (-, -)
[Factor -> '(' . Expr ')', '+' ]* (-, -)
[Factor -> '(' . Expr ')', '*' ]* (-, -)
x5. goto(id) from i0
[Factor -> id ., $end]* (-, -)
[Factor -> id ., '+' ]* (-, -)
[Factor -> id ., '*' ]* (-, -)
These new transition sets are added to the to-do list. All of the transition items of set i0 are marked, the comeFrom pointer hase been set to i0 (because it is the item set from which the new transition sets were generated), and the set is marked as completed:
i0x0. initial item set complete [$accept -> . Expr, $end]* (Expr, x1) [Expr -> . Expr '+' Term, $end] (Expr, x1) [Expr -> . Expr '+' Term, '+' ] (Expr, x1) [Expr -> . Term, $end] (Term, x2) [Expr -> . Term, '+' ] (Term, x2) [Term -> . Term '*' Factor, $end] (Term, x2) [Term -> . Term '*' Factor, '+' ] (Term, x2) [Term -> . Term '*' Factor, '*' ] (Term, x2) [Term -> . Factor, $end] (Factor, x3) [Term -> . Factor, '+' ] (Factor, x3) [Term -> . Factor, '*' ] (Factor, x3) [Factor -> . '(' Expr ')', $end] ('(', x4) [Factor -> . '(' Expr ')', '+' ] ('(', x4) [Factor -> . '(' Expr ')', '*' ] ('(', x4) [Factor -> . id, $end] (id, x5) [Factor -> . id, '+' ] (id, x5) [Factor -> . id, '*' ] (id, x5)
Item set i0 is then moved to the done list (since it has been marked as completed), and the state of the algorithm is now:
doneList: i0 incList: - toDoList: x1 x2 x3 x4 x5 comeFrom: i0
Phase 2 of this iteration begins, popping set x1 from the to-do list. All of the closure items (none) for set x1 are generated, and all of its reduce actions are marked. It cannot be merged with any existing set in the done list (which contains only set i0), so x1 is renamed to i1 and moved to the incomplete list:
i1x1. goto(Expr) from i0 [$accept -> Expr ., $end]* ($end, accept) reduce [Expr -> Expr . '+' Term, $end]* (-, -) [Expr -> Expr . '+' Term, '+' ]* (-, -)
Phase 2 of this iteration continues, processing sets x2, x3, x4, and x5 from the to-do list in a similar fashion. All of their closure items are generated, all of their reduce items are marked, and at this point none of them can be merged with any existing sets in the done list. These item sets now look like:
i2x2. goto(Term) from i0 [Expr -> Term ., $end]* ($end, r2) reduce [Expr -> Term ., '+' ]* ('+', r2) reduce [Term -> Term . '*' Factor, $end]* (-, -) [Term -> Term . '*' Factor, '+' ]* (-, -) [Term -> Term . '*' Factor, '*' ]* (-, -) i3x3. goto(Factor) from i0 [Term -> Factor ., $end]* ($end, r4) reduce [Term -> Factor ., '+' ]* ('+', r4) reduce [Term -> Factor ., '*' ]* ('*', r4) reduce i4x4. goto('(') from i0 [Factor -> '(' . Expr ')', $end]* (-, -) [Factor -> '(' . Expr ')', '+' ]* (-, -) [Factor -> '(' . Expr ')', '*' ]* (-, -) [Expr -> . Expr '+' Term, $end] (-, -) closure [Expr -> . Expr '+' Term, '+' ] (-, -) closure [Expr -> . Expr '+' Term, '*' ] (-, -) closure [Expr -> . Expr '+' Term, ')' ] (-, -) closure [Expr -> . Term, $end] (-, -) closure [Expr -> . Term, '+' ] (-, -) closure [Expr -> . Term, '*' ] (-, -) closure [Expr -> . Term, ')' ] (-, -) closure [Term -> . Term '*' Factor, $end] (-, -) closure [Term -> . Term '*' Factor, '+' ] (-, -) closure [Term -> . Term '*' Factor, '*' ] (-, -) closure [Term -> . Term '*' Factor, ')' ] (-, -) closure [Term -> . Factor, $end] (-, -) closure [Term -> . Factor, '+' ] (-, -) closure [Term -> . Factor, '*' ] (-, -) closure [Term -> . Factor, ')' ] (-, -) closure [Factor -> . '(' Expr ')', $end] (-, -) closure [Factor -> . '(' Expr ')', '+' ] (-, -) closure [Factor -> . '(' Expr ')', '*' ] (-, -) closure [Factor -> . '(' Expr ')', ')' ] (-, -) closure [Factor -> . id, $end] (-, -) closure [Factor -> . id, '+' ] (-, -) closure [Factor -> . id, '*' ] (-, -) closure [Factor -> . id, ')' ] (-, -) closure i5x5. goto(id) from i0 [Factor -> id ., $end]* ($end, r6) reduce [Factor -> id ., '+' ]* ('+', r6) reduce [Factor -> id ., '*' ]* ('*', r6) reduce
During this processing of the items from the to-do list, the comeFrom pointer keeps track of the item set from which they were generated, which was previously set to i0. As each transition item set is renamed, the shift transition actions in set i0 are updated to reflect the renaming. As the item sets above are all processed, renamed, and moved to the incomplete list, item set i0 is updated, and eventually looks like:
i0x0. initial item set [$accept -> . Expr, $end]* (Expr, i1x1) updated [Expr -> . Expr '+' Term, $end] (Expr, i1x1) updated [Expr -> . Expr '+' Term, '+' ] (Expr, i1x1) updated [Expr -> . Term, $end] (Term, i2x2) updated [Expr -> . Term, '+' ] (Term, i2x2) updated [Term -> . Term '*' Factor, $end] (Term, i2x2) updated [Term -> . Term '*' Factor, '+' ] (Term, i2x2) updated [Term -> . Term '*' Factor, '*' ] (Term, i2x2) updated [Term -> . Factor, $end] (Factor, i3x3) updated [Term -> . Factor, '+' ] (Factor, i3x3) updated [Term -> . Factor, '*' ] (Factor, i3x3) updated [Factor -> . '(' Expr ')', $end] ('(', i4x4) updated [Factor -> . '(' Expr ')', '+' ] ('(', i4x4) updated [Factor -> . '(' Expr ')', '*' ] ('(', i4x4) updated [Factor -> . id, $end] (id, i5x5) updated [Factor -> . id, '+' ] (id, i5x5) updated [Factor -> . id, '*' ] (id, i5x5) updated
After all of the new sets have been renamed and moved to the incomplete list, the to-do list is empty and this iteration stops. The state of the algorithm is now:
doneList: i0 incList: i1 i2 i3 i4 i5 toDoList: - comeFrom: i0
Phase 1 of the next iteration begins, retrieving set i1 from the incomplete list, making it the comeFrom set and generating new shift transitions from it:
i1x1. goto(Expr) from i0 [$accept -> Expr ., $end]* ($end, accept) [Expr -> Expr . '+' Term, $end]* ('+', x6) shift [Expr -> Expr . '+' Term, '+' ]* ('+', x6) shift
A new transition item set is generated:
x6. goto('+') from i1
[Expr -> Expr '+' . Term, $end]* (-, -)
[Expr -> Expr '+' . Term, '+' ]* (-, -)
Set i1 is marked as completed, and the state of the algorithm is now:
doneList: i0 i1 incList: i2 i3 i4 i5 toDoList: x6 comeFrom: i1
Phase 2 pops item set x6 from the to-do list, adding closure items to it and renaming it to i6:
i6x6. goto('+') from i1 [Expr -> Expr '+' . Term, $end]* (-, -) [Expr -> Expr '+' . Term, '+' ]* (-, -) [Term -> . Term '*' Factor, $end] (-, -) closure [Term -> . Term '*' Factor, '+' ] (-, -) closure [Term -> . Term '*' Factor, '*' ] (-, -) closure [Term -> . Factor, $end] (-, -) closure [Term -> . Factor, '+' ] (-, -) closure [Term -> . Factor, '*' ] (-, -) closure [Factor -> . '(' Expr ')', $end] (-, -) closure [Factor -> . '(' Expr ')', '+' ] (-, -) closure [Factor -> . '(' Expr ')', '*' ] (-, -) closure [Factor -> . id, $end] (-, -) closure [Factor -> . id, '+' ] (-, -) closure [Factor -> . id, '*' ] (-, -) closure
Shift items in comeFrom set i1 are updated to reflect the renaming of set x6 to i6:
i1x1. goto(Expr) from i0 [$accept -> Expr ., $end]* ($end, accept) [Expr -> Expr . '+' Term, $end]* ('+', i6x6) [Expr -> Expr . '+' Term, '+' ]* ('+', i6x6)
The state of the algorithm is now:
doneList: i0 i1 incList: i2 i3 i4 i5 i6 toDoList: - comeFrom: i1
Phase 1 of the next iteration pops set i2 from the incomplete list, generating a new transition set x7 from it:
i2x2. goto(Term) from i0 [Expr -> Term ., $end]* ($end, r2) [Expr -> Term ., '+' ]* ('+', r2) [Term -> Term . '*' Factor, $end]* ('*', x7) shift [Term -> Term . '*' Factor, '+' ]* ('*', x7) shift [Term -> Term . '*' Factor, '*' ]* ('*', x7) shift x7. goto('*') from i2 [Term -> Term '*' . Factor, $end]* (-, -) [Term -> Term '*' . Factor, '+' ]* (-, -) [Term -> Term '*' . Factor, '*' ]* (-, -)
The state of the algorithm is now:
doneList: i0 i1 i2 incList: i3 i4 i5 i6 toDoList: x7 comeFrom: i2
This iteration continues by processing set x7 from the to-do list, adding its closure items and marking its reduction items (none). There are no existing item sets in the done/incomplete list that it can be merged with, so x7 is renamed to i7 and moved to the incomplete list:
i7x7. goto('*') from i2 [Term -> Term '*' . Factor, $end]* (-, -) [Term -> Term '*' . Factor, '+' ]* (-, -) [Term -> Term '*' . Factor, '*' ]* (-, -) [Factor -> . '(' Expr ')', $end] (-, -) closure [Factor -> . '(' Expr ')', '+' ] (-, -) closure [Factor -> . '(' Expr ')', '*' ] (-, -) closure [Factor -> . id, $end] (-, -) closure [Factor -> . id, '+' ] (-, -) closure [Factor -> . id, '*' ] (-, -) closure
The comeFrom set i2 is updated to reflect the renaming:
i2x2. goto(Term) from i0 [Term -> Term . '*' Factor, $end]* ('*', i7x7) [Term -> Term . '*' Factor, '+' ]* ('*', i7x7) [Term -> Term . '*' Factor, '*' ]* ('*', i7x7) (other items not shown)
Phase 1 processes set i3 from the incomplete list:
i3x3. goto(Factor) from i0 [Term -> Factor ., $end]* ($end, r4) [Term -> Factor ., '+' ]* ('+', r4) [Term -> Factor ., '*' ]* ('*', r4)
No new transition sets are generated from i3 because it contains only reduction items. The set is marked as completed and moved to the done list. The algorithm state is now:
doneList: i0 i1 i2 i3 incList: i4 i5 i6 i7 toDoList: - comeFrom: i3
There are no item sets in the to-do list for phase 2 to process.
Phase 1 processes set i4, from which are generated new shift actions:
i4x4. goto('(') from i0 [Factor -> '(' . Expr ')', $end]* (Expr, x8) shift [Factor -> '(' . Expr ')', '+' ]* (Expr, x8) shift [Factor -> '(' . Expr ')', '*' ]* (Expr, x8) shift [Expr -> . Expr '+' Term, $end] (Expr, x8) shift [Expr -> . Expr '+' Term, '+' ] (Expr, x8) shift [Expr -> . Expr '+' Term, '*' ] (Expr, x8) shift [Expr -> . Expr '+' Term, ')' ] (Expr, x8) shift [Expr -> . Term, $end] (Term, x9) shift [Expr -> . Term, '+' ] (Term, x9) shift [Expr -> . Term, '*' ] (Term, x9) shift [Expr -> . Term, ')' ] (Term, x9) shift [Term -> . Term '*' Factor, $end] (Term, x9) shift [Term -> . Term '*' Factor, '+' ] (Term, x9) shift [Term -> . Term '*' Factor, '*' ] (Term, x9) shift [Term -> . Term '*' Factor, ')' ] (Term, x9) shift [Term -> . Factor, $end] (Factor, x10) shift [Term -> . Factor, '+' ] (Factor, x10) shift [Term -> . Factor, '*' ] (Factor, x10) shift [Term -> . Factor, ')' ] (Factor, x10) shift [Factor -> . '(' Expr ')', $end] ('(', x11) shift [Factor -> . '(' Expr ')', '+' ] ('(', x11) shift [Factor -> . '(' Expr ')', '*' ] ('(', x11) shift [Factor -> . '(' Expr ')', ')' ] ('(', x11) shift [Factor -> . id, $end] (id, x12) shift [Factor -> . id, '+' ] (id, x12) shift [Factor -> . id, '*' ] (id, x12) shift [Factor -> . id, ')' ] (id, x12) shift
New transition item sets are generated from the shift actions in set i4:
x8. goto(Expr) from i4
[Factor -> '(' Expr . ')', $end]* (-, -)
[Factor -> '(' Expr . ')', '+' ]* (-, -)
[Factor -> '(' Expr . ')', '*' ]* (-, -)
[Expr -> Expr . '+' Term, $end]* (-, -)
[Expr -> Expr . '+' Term, '+' ]* (-, -)
[Expr -> Expr . '+' Term, '*' ]* (-, -)
[Expr -> Expr . '+' Term, ')' ]* (-, -)
x9. goto(Term) from i4
[Expr -> Term ., $end]* (-, -)
[Expr -> Term ., '+' ]* (-, -)
[Expr -> Term ., '*' ]* (-, -)
[Expr -> Term ., ')' ]* (-, -)
[Term -> Term . '*' Factor, $end]* (-, -)
[Term -> Term . '*' Factor, '+' ]* (-, -)
[Term -> Term . '*' Factor, '*' ]* (-, -)
[Term -> Term . '*' Factor, ')' ]* (-, -)
x10. goto(Factor) from i4
[Term -> Factor ., $end]* (-, -)
[Term -> Factor ., '+' ]* (-, -)
[Term -> Factor ., '*' ]* (-, -)
[Term -> Factor ., ')' ]* (-, -)
x11. goto('(') from i4
[Factor -> '(' . Expr ')', $end]* (-, -)
[Factor -> '(' . Expr ')', '+' ]* (-, -)
[Factor -> '(' . Expr ')', '*' ]* (-, -)
[Factor -> '(' . Expr ')', ')' ]* (-, -)
x12. goto(id) from i4
[Factor -> id ., $end]* (-, -)
[Factor -> id ., '+' ]* (-, -)
[Factor -> id ., '*' ]* (-, -)
[Factor -> id ., ')' ]* (-, -)
The new transition item sets are added to the to-do list, set i4 becomes the comeFrom set, and set i4 is marked as completed and moved to the done list. The algorithm state is now:
doneList: i0 i1 i2 i3 i4 incList: i5 i6 i7 toDoList: x8 x9 x10 x11 x12 comeFrom: i4
Phase 2 again processes all of the item sets in the to-do list. Item set x8 is the first to be processed. Closure items (none) are added to the set, its reduction actions (none) are marked, and the set is renamed to i8 and is moved to the incomplete list:
i8x8. goto(Expr) from i4 [Factor -> '(' Expr . ')', $end]* (-, -) [Factor -> '(' Expr . ')', '+' ]* (-, -) [Factor -> '(' Expr . ')', '*' ]* (-, -) [Expr -> Expr . '+' Term, $end]* (-, -) [Expr -> Expr . '+' Term, '+' ]* (-, -) [Expr -> Expr . '+' Term, '*' ]* (-, -) [Expr -> Expr . '+' Term, ')' ]* (-, -)
The transition items in the comeFrom set i4 are also updated, changing them from x8 to i8:
i4x4. goto('(') from i0 [Factor -> '(' . Expr ')', $end]* (Expr, i8x8) updated [Factor -> '(' . Expr ')', '+' ]* (Expr, i8x8) updated [Factor -> '(' . Expr ')', '*' ]* (Expr, i8x8) updated [Expr -> . Expr '+' Term, $end] (Expr, i8x8) updated [Expr -> . Expr '+' Term, '+' ] (Expr, i8x8) updated [Expr -> . Expr '+' Term, '*' ] (Expr, i8x8) updated [Expr -> . Expr '+' Term, ')' ] (Expr, i8x8) updated (other items not shown)
The algorithm state is now:
doneList: i0 i1 i3 i4 incList: i5 i6 i7 i8 toDoList: x9 x10 x11 x12 comeFrom: i4
Up to this point, no items sets have been merged. Set x9 is now the first set to be merged with an already existing item set. After its closure items (none) have been added and its reduction actions marked, item set x9 looks like:
x9. goto(Term) from i4
[Expr -> Term ., $end]* ($end, r2) reduce
[Expr -> Term ., '+' ]* ('+', r2) reduce
[Expr -> Term ., '*' ]* ('*', r2) reduce
[Expr -> Term ., ')' ]* (')', r2) reduce
[Term -> Term . '*' Factor, $end]* (-, -)
[Term -> Term . '*' Factor, '+' ]* (-, -)
[Term -> Term . '*' Factor, '*' ]* (-, -)
[Term -> Term . '*' Factor, ')' ]* (-, -)
The mergeLoop of phase 2 locates item set i2 in the done/incomplete lists as a candidate set that can be merged with set x9, i.e., both sets have identical kernel LR(0) item cores and merging the two sets will introduce no reduce/reduce conflicts. Prior to merging, item set i2 looks like:
i2x2. goto(Term) from i0 [Expr -> Term ., $end]* ($end, r2) [Expr -> Term ., '+' ]* ('+', r2) [Term -> Term . '*' Factor, $end]* ('*', i7x7) [Term -> Term . '*' Factor, '+' ]* ('*', i7x7) [Term -> Term . '*' Factor, '*' ]* ('*', i7x7)
Set x9 is merged into i2, adding new items to i2 in the process. The resulting merged set looks like:
i2x2. goto(Term) from i0,i4 merged with x9 [Expr -> Term ., $end]* ($end, r2) [Expr -> Term ., '+' ]* ('+', r2) [Expr -> Term ., '*' ]* ('*', r2) added [Expr -> Term ., ')' ]* (')', r2) added [Term -> Term . '*' Factor, $end]* ('*', i7x7) [Term -> Term . '*' Factor, '+' ]* ('*', i7x7) [Term -> Term . '*' Factor, '*' ]* ('*', i7x7) [Term -> Term . '*' Factor, ')' ]* (-, -) added
Since item set i2 was previously marked as complete and the merge added new shift items, the item set must be reset and marked as incomplete. This means clearing all of the shift actions and then moving the set from the done list to the incomplete list. Doing so forces subsequent iterations of the algorithm to regenerate the set's shift transition item sets anew, ensuring that the newly added items are used to properly generate all of the shift transition item sets (with all of the appropriate look-ahead symbols). Item set i2 now looks like:
i2x2. goto(Term) from i0,i4 merged with x9, incomplete [Expr -> Term ., $end]* ($end, r2) [Expr -> Term ., '+' ]* ('+', r2) [Expr -> Term ., '*' ]* ('*', r2) [Expr -> Term ., ')' ]* (')', r2) [Term -> Term . '*' Factor, $end]* (-, -) reset [Term -> Term . '*' Factor, '+' ]* (-, -) reset [Term -> Term . '*' Factor, '*' ]* (-, -) reset [Term -> Term . '*' Factor, ')' ]* (-, -) reset
Item set i2 is then removed from the done list and added to the incomplete list.
Items within comeFrom set i4 are updated, replacing the transitions to x9 with i2.
i4x4. goto('(') from i0 [Expr -> . Term, $end] (Term, i2x9) updated [Expr -> . Term, '+' ] (Term, i2x9) updated [Expr -> . Term, '*' ] (Term, i2x9) updated [Expr -> . Term, ')' ] (Term, i2x9) updated [Term -> . Term '*' Factor, $end] (Term, i2x9) updated [Term -> . Term '*' Factor, '+' ] (Term, i2x9) updated [Term -> . Term '*' Factor, '*' ] (Term, i2x9) updated [Term -> . Term '*' Factor, ')' ] (Term, i2x9) updated (other items not shown)
Item set x9 is then discarded, being entirely replaced by the newly merged set i2.
The algorithm state is now:
doneList: i0 i1 i3 i4 incList: i5 i6 i7 i8 i2 toDoList: x10 x11 x12 comeFrom: i4
Phase 2 continues, processing the next set in the to-do list, x10. Its closure items (none) are added and its reduction actions are marked:
x10. goto(Factor) from i4
[Term -> Factor ., $end]* ($end, r4) reduce
[Term -> Factor ., '+' ]* ('+', r4) reduce
[Term -> Factor ., '*' ]* ('*', r4) reduce
[Term -> Factor ., ')' ]* (')', r4) reduce
As before, the mergeLoop of the algorithm identifies existing set i3 as a candidate to be merged with set x10:
i3x3. goto(Factor) from i0 [Term -> Factor ., $end]* ($end, r4) [Term -> Factor ., '+' ]* ('+', r4) [Term -> Factor ., '*' ]* ('*', r4)
Since merging x10 with i3 will not create any reduce/reduce conflicts, the two sets are merged:
i3x3. goto(Factor) from i0,i4 merged with x10, complete [Term -> Factor ., $end]* ($end, r4) [Term -> Factor ., '+' ]* ('+', r4) [Term -> Factor ., '*' ]* ('*', r4) [Term -> Factor ., ')' ]* (')', r4) added
Item set i3 was previously marked as completed, but since the merge did not add a shift item, the set remains marked as completed and stays in the done list.
The comeFrom set i4 is also updated accordingly, replacing its transitions to x10 with i3.
i4x4. goto('(') from i0 [Term -> . Factor, $end] (Factor, i3x10) [Term -> . Factor, '+' ] (Factor, i3x10) [Term -> . Factor, '*' ] (Factor, i3x10) [Term -> . Factor, ')' ] (Factor, i3x10) (other items not shown)
Set x10 is then discarded, being replaced entirely by set i3. The algorithm state is now:
doneList: i0 i1 i3 i4 incList: i5 i6 i7 i8 i2 toDoList: x11 x12 comeFrom: i4
Phase 2 continues, processing the next set in the to-do list, x11. Its closure items are added and its reduction actions (none) are marked:
x11. goto('(') from i4
[Factor -> '(' . Expr ')', $end]* (-, -)
[Factor -> '(' . Expr ')', '+' ]* (-, -)
[Factor -> '(' . Expr ')', '*' ]* (-, -)
[Factor -> '(' . Expr ')', ')' ]* (-, -)
[Expr -> . Expr '+' Term, '+' ] (-, -) closure
[Expr -> . Expr '+' Term, ')' ] (-, -) closure
[Expr -> . Term, '+' ] (-, -) closure
[Expr -> . Term, ')' ] (-, -) closure
[Term -> . Term '*' Factor, '+' ] (-, -) closure
[Term -> . Term '*' Factor, '*' ] (-, -) closure
[Term -> . Term '*' Factor, ')' ] (-, -) closure
[Term -> . Factor, '+' ] (-, -) closure
[Term -> . Factor, '*' ] (-, -) closure
[Term -> . Factor, ')' ] (-, -) closure
[Factor -> . '(' Expr ')', '+' ] (-, -) closure
[Factor -> . '(' Expr ')', '*' ] (-, -) closure
[Factor -> . '(' Expr ')', ')' ] (-, -) closure
[Factor -> . id, '+' ] (-, -) closure
[Factor -> . id, '*' ] (-, -) closure
[Factor -> . id, ')' ] (-, -) closure
As before, the mergeLoop of the algorithm identifies existing set i4 as a candidate to be merged with set x11, having the same kernel core items:
i4x4. goto('(') from i0 [Factor -> '(' . Expr ')', $end]* (Expr, i8x8) [Factor -> '(' . Expr ')', '+' ]* (Expr, i8x8) [Factor -> '(' . Expr ')', '*' ]* (Expr, i8x8) (non-kernel items not shown)
Since merging x11 with i4 will not create any reduce/reduce conflicts (neither set has any reduction items), the two sets are merged, which adds a new item to set i4:
[Factor -> '(' . Expr ')', ')' ]* (-, -) added
Since item set i4 was previously marked as completed and the merging added a new shift item to it, the set must be cleared and marked as incomplete.
Note that if set i4 did not have to be marked as incomplete, the items that shift '(' and transition to x11 would have been replaced by transitions to i4 itself:
[Factor -> . '(' Expr ')', $end] ('(', i4 x11)
[Factor -> . '(' Expr ')', '+' ] ('(', i4 x11)
[Factor -> . '(' Expr ')', '*' ] ('(', i4 x11)
[Factor -> . '(' Expr ')', ')' ] ('(', i4 x11)
These items will be processed in later iterations of the algorithm.
Item set x11 is discarded, having been completely replaced by set i4. Set i4 is marked as incomplete, all of its shift actions are reset, and it is moved to the incomplete list:
i4x4. goto('(') from i0,i4 merged with x11, incomplete [Factor -> '(' . Expr ')', $end]* (-, -) reset [Factor -> '(' . Expr ')', '+' ]* (-, -) reset [Factor -> '(' . Expr ')', '*' ]* (-, -) reset [Factor -> '(' . Expr ')', ')' ]* (-, -) reset [Expr -> . Expr '+' Term, $end] (-, -) reset [Expr -> . Expr '+' Term, '+' ] (-, -) reset [Expr -> . Expr '+' Term, '*' ] (-, -) reset [Expr -> . Expr '+' Term, ')' ] (-, -) reset [Expr -> . Term, $end] (-, -) reset [Expr -> . Term, '+' ] (-, -) reset [Expr -> . Term, '*' ] (-, -) reset [Expr -> . Term, ')' ] (-, -) reset [Term -> . Term '*' Factor, $end] (-, -) reset [Term -> . Term '*' Factor, '+' ] (-, -) reset [Term -> . Term '*' Factor, '*' ] (-, -) reset [Term -> . Term '*' Factor, ')' ] (-, -) reset [Term -> . Factor, $end] (-, -) reset [Term -> . Factor, '+' ] (-, -) reset [Term -> . Factor, '*' ] (-, -) reset [Term -> . Factor, ')' ] (-, -) reset [Factor -> . '(' Expr ')', $end] (-, -) reset [Factor -> . '(' Expr ')', '+' ] (-, -) reset [Factor -> . '(' Expr ')', '*' ] (-, -) reset [Factor -> . '(' Expr ')', ')' ] (-, -) reset [Factor -> . id, $end] (-, -) reset [Factor -> . id, '+' ] (-, -) reset [Factor -> . id, '*' ] (-, -) reset [Factor -> . id, ')' ] (-, -) reset
The algorithm state is now:
doneList: i0 i1 i3 incList: i5 i6 i7 i8 i2 i4 toDoList: x12 comeFrom: i4
Phase 2 continues, processing the next set in the to-do list, x12. Its closure items (none) are added and its reduction actions are marked:
x12. goto(id) from i4
[Factor -> id ., $end]* ($end, r6) reduce
[Factor -> id ., '+' ]* ('+', r6) reduce
[Factor -> id ., '*' ]* ('*', r6) reduce
[Factor -> id ., ')' ]* (')', r6) reduce
As before, the mergeLoop of the algorithm identifies existing set i5 as a candidate to be merged with set x12, having the same kernel core items:
i5x5. goto(id) from i0 [Factor -> id ., $end]* ($end, r6) [Factor -> id ., '+' ]* ('+', r6) [Factor -> id ., '*' ]* ('*', r6)
Since merging x12 with i5 will not create any reduce/reduce conflicts (neither set has any reduction items), the two sets are merged, which adds a new item to set i5:
i5x5. goto(id) from i0,i4 merged with x12, complete [Factor -> id ., $end]* ($end, r6) [Factor -> id ., '+' ]* ('+', r6) [Factor -> id ., '*' ]* ('*', r6) [Factor -> id ., ')' ]* (')', r6) added
Item set i5 has not yet been marked as completed, so it remains unmarked and stays in the incomplete list.
Note that if comeFrom set i4 had not been previously cleared and marked as incomplete, its transition items would be updated to change the gotos from x12 to i5. But even though those items in i4 are not updated at this point, they will be updated in later iterations of the algorithm.
Item set x12 is discarded. The algorithm state is now:
doneList: i0 i1 i3 incList: i5 i6 i7 i8 i2 i4 toDoList: - comeFrom: i4
Phase 2 of this iteration has no work to do because the to-do list is empty.
Phase 1 pops item set i5 from the incomplete list:
i5x5. goto(id) from i0,i4 [Factor -> id ., $end]* ($end, r6) [Factor -> id ., '+' ]* ('+', r6) [Factor -> id ., '*' ]* ('*', r6) [Factor -> id ., ')' ]* (')', r6)
No new transition item sets can be generated from set i5, so it is just marked as completed and moved to the done list. The algorithm state is now:
doneList: i0 i1 i3 i5 incList: i6 i7 i8 i2 i4 toDoList: - comeFrom: i5
Phase 2 of this iteration has no work to do because the to-do list is empty.
Phase 1 pops item set i6 from the incomplete list, and new transition item sets are generated from its shift actions:
i6x6. goto('+') from i1 [Expr -> Expr '+' . Term, $end]* (Term, x13) shift [Expr -> Expr '+' . Term, '+' ]* (Term, x13) shift [Term -> . Term '*' Factor, $end] (Term, x13) shift [Term -> . Term '*' Factor, '+' ] (Term, x13) shift [Term -> . Term '*' Factor, '*' ] (Term, x13) shift [Term -> . Factor, $end] (Factor, x14) shift [Term -> . Factor, '+' ] (Factor, x14) shift [Term -> . Factor, '*' ] (Factor, x14) shift [Factor -> . '(' Expr ')', $end] ('(', x15) shift [Factor -> . '(' Expr ')', '+' ] ('(', x15) shift [Factor -> . '(' Expr ')', '*' ] ('(', x15) shift [Factor -> . id, $end] (id, x16) shift [Factor -> . id, '+' ] (id, x16) shift [Factor -> . id, '*' ] (id, x16) shift
These new shift transition item sets are generated from i6:
x13. goto(Term) from i6
[Expr -> Expr '+' Term ., $end]* (-, -)
[Expr -> Expr '+' Term ., '+' ]* (-, -)
[Term -> Term . '*' Factor, $end]* (-, -)
[Term -> Term . '*' Factor, '+' ]* (-, -)
[Term -> Term . '*' Factor, '*' ]* (-, -)
x14. goto(Factor) from i6
[Term -> Factor ., $end]* (-, -)
[Term -> Factor ., '+' ]* (-, -)
[Term -> Factor ., '*' ]* (-, -)
x15. goto('(') from i6
[Factor -> '(' . Expr ')', $end]* (-, -)
[Factor -> '(' . Expr ')', '+' ]* (-, -)
[Factor -> '(' . Expr ')', '*' ]* (-, -)
x16. goto(id) from i6
[Factor -> id ., $end]* (-, -)
[Factor -> id ., '+' ]* (-, -)
[Factor -> id ., '*' ]* (-, -)
These new item sets are added to the incomplete list, comeFrom is set to i6, and i6 is marked as completed and moved to the done list. The algorithm state is now:
doneList: i0 i1 i3 i5 i6 incList: i7 i8 i2 i4 toDoList: x13 x14 x15 x16 comeFrom: i6
Phase 2 processes the item sets in the to-do list, starting with x13, adding its closure items (none) and marking its reduction actions. The mergeLoop does not find any existing item set as a candidate for merging with the set, so x13 is renamed to i9 and moved to the incomplete list:
i9x13. goto(Term) from i6 [Expr -> Expr '+' Term ., $end]* ($end, r1) [Expr -> Expr '+' Term ., '+' ]* ('+', r1) [Term -> Term . '*' Factor, $end]* (-, -) [Term -> Term . '*' Factor, '+' ]* (-, -) [Term -> Term . '*' Factor, '*' ]* (-, -)
The transitions in comeFrom set i6 are updated to reflect the renaming of x13 to i9:
i6x6. goto('+') from i1 [Expr -> Expr '+' . Term, $end]* (Term, i9x13) updated [Expr -> Expr '+' . Term, '+' ]* (Term, i9x13) updated [Term -> . Term '*' Factor, $end] (Term, i9x13) updated [Term -> . Term '*' Factor, '+' ] (Term, i9x13) updated [Term -> . Term '*' Factor, '*' ] (Term, i9x13) updated (other items not shown)
The algorithm state is now:
doneList: i0 i1 i3 i5 i6 incList: i7 i8 i2 i4 i9 toDoList: x14 x15 x16 comeFrom: i6
Phase 2 continues, processing set x14 from the to-do list, adding its closure items (none) and marking its reduction actions:
x14. goto(Factor) from i6
[Term -> Factor ., $end]* ($end, r4) reduce
[Term -> Factor ., '+' ]* ('+', r4) reduce
[Term -> Factor ., '*' ]* ('*', r4) reduce
The mergeLoop finds existing item set i3 as a candidate for merging with set x14:
i3x3. goto(Factor) from i0,i4,i6 merged with x14 [Term -> Factor ., $end]* ($end, r4) [Term -> Factor ., '+' ]* ('+', r4) [Term -> Factor ., '*' ]* ('*', r4) [Term -> Factor ., ')' ]* (')', r4)
Since the two sets have the same kernel core items and merging them creates no reduce/reduce conflicts (all of the actions reduce rule 4), set x14 is merged into i3. The merging operation adds no new items to set i3, so the completed set remains on the done list.
The items in the comeFrom set i6 that transition to set x14 are updated to transition to i3, and set x14 is discarded.
i6x6. goto('+') from i1 [Term -> . Factor, $end] (Factor, i3x14) updated [Term -> . Factor, '+' ] (Factor, i3x14) updated [Term -> . Factor, '*' ] (Factor, i3x14) updated (other items not shown)
The algorithm state is now:
doneList: i0 i1 i3 i5 i6 incList: i7 i8 i2 i4 i9 toDoList: x15 x16 comeFrom: i6
Phase 2 continues, popping set x15 from the to-do list, adding its closure items (none) and marking its reduction actions (none):
x15. goto('(') from i6
[Factor -> '(' . Expr ')', $end]* (-, -)
[Factor -> '(' . Expr ')', '+' ]* (-, -)
[Factor -> '(' . Expr ')', '*' ]* (-, -)
[Expr -> . Expr '+' Term, '+' ] (-, -)
[Expr -> . Expr '+' Term, ')' ] (-, -)
[Expr -> . Term, '+' ] (-, -)
[Expr -> . Term, ')' ] (-, -)
[Term -> . Term '*' Factor, '+' ] (-, -)
[Term -> . Term '*' Factor, '*' ] (-, -)
[Term -> . Term '*' Factor, ')' ] (-, -)
[Term -> . Factor, '+' ] (-, -)
[Term -> . Factor, '*' ] (-, -)
[Term -> . Factor, ')' ] (-, -)
[Factor -> . '(' Expr ')', '+' ] (-, -)
[Factor -> . '(' Expr ')', '*' ] (-, -)
[Factor -> . '(' Expr ')', ')' ] (-, -)
[Factor -> . id, '+' ] (-, -)
[Factor -> . id, '*' ] (-, -)
[Factor -> . id, ')' ] (-, -)
The mergeLoop locates set i4 as a candidate to merge with set x15, both of them having the same kernel core items:
i4x4. goto('(') from i0,i4 [Factor -> '(' . Expr ')', $end]* (-, -) [Factor -> '(' . Expr ')', '*' ]* (-, -) [Factor -> '(' . Expr ')', '+' ]* (-, -) [Factor -> '(' . Expr ')', ')' ]* (-, -) (non-kernel items not shown)
Merging the two item sets does not create any reduce/reduce conflicts, so set x15 is merged into set i4. The merging operation does not add any new items to set i4.
The comeFrom set i6 is updated, replacing all of its transitions to x15 to be transitions to i4.
i6x6. goto('+') from i1 [Factor -> . '(' Expr ')', $end] ('(', i4x15) [Factor -> . '(' Expr ')', '+' ] ('(', i4x15) [Factor -> . '(' Expr ')', '*' ] ('(', i4x15) (other items not shown)
Set x15 is then discarded. The algorithm state is now:
doneList: i0 i1 i3 i5 i6 incList: i7 i8 i2 i4 i9 toDoList: x16 comeFrom: i6
Phase 2 continues, popping set x16 from the to-do list, adding its closure items (none) and marking its reduction actions:
x16. goto(id) from i6
[Factor -> id ., $end]* ($end, r6) reduce
[Factor -> id ., '+' ]* ('+', r6) reduce
[Factor -> id ., '*' ]* ('*', r6) reduce
The mergeLoop finds item set i5 as a candidate for merging with set x16:
i5x5. goto(id) from i0,i4,i6 merged with x16 [Factor -> id ., $end]* ($end, r6) [Factor -> id ., '+' ]* ('+', r6) [Factor -> id ., '*' ]* ('*', r6) [Factor -> id ., ')' ]* (')', r6)
Merging set x16 into i5 creates no reduce/reduce conflicts, and no new items are added to the resulting merged set. Items in comeFrom set i6 is updated, replacing transitions to x16 with transitions to i5:
i6x6. goto('+') from i1 [Factor -> . id, $end] (id, i5x16) updated [Factor -> . id, '+' ] (id, i5x16) updated [Factor -> . id, '*' ] (id, i5x16) updated (other items not shown)
Item set i5 is unchanged by the merge, so it remains in the done list. Item set x16 is discarded, and the algorithm state is now:
doneList: i0 i1 i3 i5 i6 incList: i7 i8 i2 i4 i9 toDoList: - comeFrom: i6
Phase 1 of the next iteration begins, popping item set i7 off of the incomplete list. New transition item sets are generated for all of its shift items:
i7x7. goto('*') from i2 [Term -> Term '*' . Factor, $end]* (Factor, x17) shift [Term -> Term '*' . Factor, '+' ]* (Factor, x17) shift [Term -> Term '*' . Factor, '*' ]* (Factor, x17) shift [Factor -> . '(' Expr ')', $end] ('(', x18) shift [Factor -> . '(' Expr ')', '+' ] ('(', x18) shift [Factor -> . '(' Expr ')', '*' ] ('(', x18) shift [Factor -> . id, $end] (id, x19) shift [Factor -> . id, '+' ] (id, x19) shift [Factor -> . id, '*' ] (id, x19) shift
New transition items sets are generated from comeFrom set i7 and added to the to-do-list:
x17. goto(Factor) from i7
[Term -> Term '*' Factor ., $end]* (-, -)
[Term -> Term '*' Factor ., '+' ]* (-, -)
[Term -> Term '*' Factor ., '*' ]* (-, -)
x18. goto('(') from i7
[Factor -> '(' . Expr ')', $end]* (-, -)
[Factor -> '(' . Expr ')', '+' ]* (-, -)
[Factor -> '(' . Expr ')', '*' ]* (-, -)
x19. goto(id) from i7
[Factor -> id ., $end]* (-, -)
[Factor -> id ., '+' ]* (-, -)
[Factor -> id ., '*' ]* (-, -)
Item set i7 is marked as completed and is moved to the done list. The algorithm state is now:
doneList: i0 i1 i3 i5 i6 i7 incList: i8 i2 i4 i9 toDoList: x17 x18 x19 comeFrom: i7
Phase 2 processes the item sets in the to-do list, starting with set x17. Closure items (none) are added to it and its reduction actions are marked. The mergeLoop does not find any existing item set that can be merged with x17, so it is renamed to i10 and moved to the incomplete list:
i10x17. goto(Factor) from i7 [Term -> Term '*' Factor ., $end]* ($end, r3) reduce [Term -> Term '*' Factor ., '+' ]* ('+', r3) reduce [Term -> Term '*' Factor ., '*' ]* ('*', r3) reduce
The transitions to x17 are also updated in comeFrom set i7:
i7x7. goto('*') from i2 [Term -> Term '*' . Factor, $end]* (Factor, i10x17) updated [Term -> Term '*' . Factor, '+' ]* (Factor, i10x17) updated [Term -> Term '*' . Factor, '*' ]* (Factor, i10x17) updated (other items not shown)
The algorithm state is now:
doneList: i0 i1 i3 i5 i6 i7 incList: i8 i2 i4 i9 i10 toDoList: x18 x19 comeFrom: i7
Phase 2 continues, processing item set x18 from the to-do list. Closure items are added to it and its reduction actions (none) are marked:
x18. goto('(') from i7
[Factor -> '(' . Expr ')', $end]* (-, -)
[Factor -> '(' . Expr ')', '+' ]* (-, -)
[Factor -> '(' . Expr ')', '*' ]* (-, -)
[Expr -> . Expr '+' Term, '+' ] (-, -)
[Expr -> . Expr '+' Term, ')' ] (-, -)
[Expr -> . Term, '+' ] (-, -)
[Expr -> . Term, ')' ] (-, -)
[Term -> . Term '*' Factor, '+' ] (-, -)
[Term -> . Term '*' Factor, '*' ] (-, -)
[Term -> . Term '*' Factor, ')' ] (-, -)
[Term -> . Factor, '+' ] (-, -)
[Term -> . Factor, '*' ] (-, -)
[Term -> . Factor, ')' ] (-, -)
[Factor -> . '(' Expr ')', '+' ] (-, -)
[Factor -> . '(' Expr ')', '*' ] (-, -)
[Factor -> . '(' Expr ')', ')' ] (-, -)
[Factor -> . id, '+' ] (-, -)
[Factor -> . id, '*' ] (-, -)
[Factor -> . id, ')' ] (-, -)
The mergeLoop finds item set i4 as a candidate for merging with x18:
i4x4. goto('(') from i0,i4 [Factor -> '(' . Expr ')', $end]* (-, -) [Factor -> '(' . Expr ')', '*' ]* (-, -) [Factor -> '(' . Expr ')', '+' ]* (-, -) [Factor -> '(' . Expr ')', ')' ]* (-, -) (non-kernel items not shown)
Item set x18 is merged into i4, which adds no new items to i4. The comeFrom set i7 is updated, replacing set x18 with i4:
i7x7. goto('*') from i2 [Factor -> . '(' Expr ')', $end] ('(', i4x18) updated [Factor -> . '(' Expr ')', '+' ] ('(', i4x18) updated [Factor -> . '(' Expr ')', '*' ] ('(', i4x18) updated (other items not shown)
Item set x18 is then discarded. The algorithm state is now:
doneList: i0 i1 i3 i5 i6 i7 incList: i8 i2 i4 i9 i10 toDoList: x19 comeFrom: i7
Phase 2 continues, processing item set x19 from the to-do list. Closure items (none) are added to it and its reduction actions are marked:
x19. goto(id) from i7
[Factor -> id ., $end]* ($end, r6) reduce
[Factor -> id ., '+' ]* ('+', r6) reduce
[Factor -> id ., '*' ]* ('*', r6) reduce
The mergeLoop finds item set i5 as a candidate for merging with x19:
i5x5. goto(id) from i0,i4 [Factor -> id ., $end]* ($end, r6) [Factor -> id ., '+' ]* ('+', r6) [Factor -> id ., '*' ]* ('*', r6) [Factor -> id ., ')' ]* (')', r6)
Merging x19 into i5 does adds no new items to i5, so it remains on the done list. Items in comeFrom set i7 are updated, item set i5 replacing x19:
i7x7. goto('*') from i2 [Factor -> . id, $end] (id, i5x19) updated [Factor -> . id, '+' ] (id, i5x19) updated [Factor -> . id, '*' ] (id, i5x19) updated (other items not shown)
Item set x19 is then discarded. The algorithm state is now:
doneList: i0 i1 i3 i5 i6 i7 incList: i8 i2 i4 i9 i10 toDoList: - comeFrom: i7
Phase 2 pops item set i8 from the incomplete list, and generates new transition item sets from its shift items:
i8x8. goto(Expr) from i4 [Factor -> '(' Expr . ')', $end]* (')', x20) shift [Factor -> '(' Expr . ')', '+' ]* (')', x20) shift [Factor -> '(' Expr . ')', '*' ]* (')', x20) shift [Expr -> Expr . '+' Term, $end]* ('+', x21) shift [Expr -> Expr . '+' Term, '+' ]* ('+', x21) shift [Expr -> Expr . '+' Term, '*' ]* ('+', x21) shift [Expr -> Expr . '+' Term, ')' ]* ('+', x21) shift
New transition item sets are generated from comeFrom set i8:
x20. goto(')') from i8
[Factor -> '(' Expr ')' ., $end]* (-, -)
[Factor -> '(' Expr ')' ., '+' ]* (-, -)
[Factor -> '(' Expr ')' ., '*' ]* (-, -)
x21. goto('+') from i8
[Expr -> Expr '+' . Term, $end]* (-, -)
[Expr -> Expr '+' . Term, '+' ]* (-, -)
[Expr -> Expr '+' . Term, '*' ]* (-, -)
[Expr -> Expr '+' . Term, ')' ]* (-, -)
The new transition item sets are added to the to-do list. Set i8 is marked as completed and moved to the done list. The algorithm state is now:
doneList: i0 i1 i3 i5 i6 i7 i8 incList: i2 i4 i9 i10 toDoList: x20 x21 comeFrom: i8
Phase 1 of the next iteration pops item set x20 from the to-do list, and adds its closure items (none) and marks its reduction actions.
The mergeLoop does not find any existing item sets to merge with x20, so the item set is renamed to i11 and moved to the incomplete list:
i11x20. goto(')') from i8 [Factor -> '(' Expr ')' ., $end]* ($end, r5) reduce [Factor -> '(' Expr ')' ., '+' ]* ('+', r5) reduce [Factor -> '(' Expr ')' ., '*' ]* ('*', r5) reduce
The comeFrom set i8 is updated to reflect the renaming:
i8x8. goto(Expr) from i4 [Factor -> '(' Expr . ')', $end]* (')', i11x20) updated [Factor -> '(' Expr . ')', '+' ]* (')', i11x20) updated [Factor -> '(' Expr . ')', '*' ]* (')', i11x20) updated (other items not shown)
The algorithm state is now:
doneList: i0 i1 i3 i5 i6 i7 i8 incList: i2 i4 i9 i10 i11 toDoList: x21 comeFrom: i8
Phase 2 pops item set x21 from the to-do list, then adds its closure items and marks its reduction actions (none):
x21. goto('+') from i8
[Expr -> Expr '+' . Term, $end]* (-, -)
[Expr -> Expr '+' . Term, '+' ]* (-, -)
[Expr -> Expr '+' . Term, '*' ]* (-, -)
[Expr -> Expr '+' . Term, ')' ]* (-, -)
[Term -> . Term '*' Factor, $end] (-, -)
[Term -> . Term '*' Factor, '+' ] (-, -)
[Term -> . Term '*' Factor, '*' ] (-, -)
[Term -> . Term '*' Factor, ')' ] (-, -)
[Term -> . Factor, $end] (-, -)
[Term -> . Factor, '+' ] (-, -)
[Term -> . Factor, '*' ] (-, -)
[Term -> . Factor, ')' ] (-, -)
[Factor -> . '(' Expr ')', $end] (-, -)
[Factor -> . '(' Expr ')', '+' ] (-, -)
[Factor -> . '(' Expr ')', '*' ] (-, -)
[Factor -> . '(' Expr ')', ')' ] (-, -)
[Factor -> . id, $end] (-, -)
[Factor -> . id, '+' ] (-, -)
[Factor -> . id, '*' ] (-, -)
[Factor -> . id, ')' ] (-, -)
The mergeLoop finds existing item set i6 as a candidate for merging with set x21:
i6x6. goto('+') from i1 [Expr -> Expr '+' . Term, $end]* (Term, i9x13) [Expr -> Expr '+' . Term, '+' ]* (Term, i9x13) (non-kernel items not shown)
Item set x21 is merged into i6, which adds several shift items to i6. Since set i6 was marked as completed, it must be cleared and moved back to the incomplete list:
i6x6. goto('+') from i1,i8 merged with x21, incomplete [Expr -> Expr '+' . Term, $end]* (-, -) reset [Expr -> Expr '+' . Term, '+' ]* (-, -) reset [Expr -> Expr '+' . Term, '*' ]* (-, -) added [Expr -> Expr '+' . Term, ')' ]* (-, -) added [Term -> . Term '*' Factor, $end] (-, -) reset [Term -> . Term '*' Factor, '+' ] (-, -) reset [Term -> . Term '*' Factor, '*' ] (-, -) reset [Term -> . Term '*' Factor, ')' ] (-, -) added [Term -> . Factor, $end] (-, -) reset [Term -> . Factor, '+' ] (-, -) reset [Term -> . Factor, '*' ] (-, -) reset [Term -> . Factor, ')' ] (-, -) added [Factor -> . '(' Expr ')', $end] (-, -) reset [Factor -> . '(' Expr ')', '+' ] (-, -) reset [Factor -> . '(' Expr ')', '*' ] (-, -) reset [Factor -> . '(' Expr ')', ')' ] (-, -) added [Factor -> . id, $end] (-, -) reset [Factor -> . id, '+' ] (-, -) reset [Factor -> . id, '*' ] (-, -) reset [Factor -> . id, ')' ] (-, -) added
The comeFrom set i8 is updated, replacing the transitions to x21 with transitions to i6:
i8x8. goto(Expr) from i4 [Expr -> Expr . '+' Term, $end]* ('+', i6x21) [Expr -> Expr . '+' Term, '+' ]* ('+', i6x21) [Expr -> Expr . '+' Term, '*' ]* ('+', i6x21) [Expr -> Expr . '+' Term, ')' ]* ('+', i6x21) (other items not shown)
Item set x21 is then discarded. The algorithm state is now:
doneList: i0 i1 i3 i5 i7 i8 incList: i2 i4 i9 i10 i11 i6 toDoList: - comeFrom: i8
Phase 1 pops item set i2 from the incomplete list and generates new transition item sets from its shift actions. (Note that i2 was previously cleared and marked incomplete because it was merged with set x9.)
i2x2. goto(Term) from i0,i4 [Expr -> Term ., $end]* ($end, r2) [Expr -> Term ., '+' ]* ('+', r2) [Expr -> Term ., '*' ]* ('*', r2) [Expr -> Term ., ')' ]* (')', r2) [Term -> Term . '*' Factor, $end]* ('*', x22) shift [Term -> Term . '*' Factor, '+' ]* ('*', x22) shift [Term -> Term . '*' Factor, '*' ]* ('*', x22) shift [Term -> Term . '*' Factor, ')' ]* ('*', x22) shift
A new transition item set is generated:
x22. goto('*') from i2
[Term -> Term '*' . Factor, $end]* (-, -)
[Term -> Term '*' . Factor, '+' ]* (-, -)
[Term -> Term '*' . Factor, '*' ]* (-, -)
[Term -> Term '*' . Factor, ')' ]* (-, -)
The new transition item set x22 is added to the to-do list, then item set i2 is marked complete and added to the done list (again). The algorithm state is now:
doneList: i0 i1 i3 i5 i7 i8 i2 incList: i4 i9 i10 i11 i6 toDoList: x22 comeFrom: i2
Phase 2 pops item set x22 from the to-do list, and generates its closure items and marks its reduction actions (none):
x22. goto('*') from i2
[Term -> Term '*' . Factor, $end]* (-, -)
[Term -> Term '*' . Factor, '+' ]* (-, -)
[Term -> Term '*' . Factor, '*' ]* (-, -)
[Term -> Term '*' . Factor, ')' ]* (-, -)
[Factor -> . '(' Expr ')', $end] (-, -) closure
[Factor -> . '(' Expr ')', '+' ] (-, -) closure
[Factor -> . '(' Expr ')', '*' ] (-, -) closure
[Factor -> . '(' Expr ')', ')' ] (-, -) closure
[Factor -> . id, $end] (-, -) closure
[Factor -> . id, '+' ] (-, -) closure
[Factor -> . id, '*' ] (-, -) closure
[Factor -> . id, ')' ] (-, -) closure
The mergeLoop chooses item set i7 as a candidate for merging with set x22:
i7x7. goto('*') from i2 [Term -> Term '*' . Factor, $end]* (Factor, i10x17) [Term -> Term '*' . Factor, '+' ]* (Factor, i10x17) [Term -> Term '*' . Factor, '*' ]* (Factor, i10x17) (non-kernel items not shown)
Since merging creates no reduce/reduce conflicts, set x22 is merged into i7. The merge adds several shift items to i7, so it is cleared and moved back to the incomplete list:
i7x7. goto('*') from i2 merged with x22, incomplete [Term -> Term '*' . Factor, $end]* (-, -) reset [Term -> Term '*' . Factor, '+' ]* (-, -) reset [Term -> Term '*' . Factor, '*' ]* (-, -) reset [Term -> Term '*' . Factor, ')' ]* (-, -) added [Factor -> . '(' Expr ')', $end] (-, -) reset [Factor -> . '(' Expr ')', '+' ] (-, -) reset [Factor -> . '(' Expr ')', '*' ] (-, -) reset [Factor -> . '(' Expr ')', ')' ] (-, -) added [Factor -> . id, $end] (-, -) reset [Factor -> . id, '+' ] (-, -) reset [Factor -> . id, '*' ] (-, -) reset [Factor -> . id, ')' ] (-, -) added
At this point, it is instructive to note that the items added to set i7 are those shift items that were generated from the additional shift items that had been added to set i2 when it was merged with x9, which caused i2 to be cleared and moved back to the incomplete list. In other words, the algorithm is now propagating the additions previously made to i2, generating new transition items in i2 and adding them to the goto sets generated from (transitioning from) i2.
Item set x22 is actually a duplication of the original canonical LR(1) set i7 that was generated from i2. This explains why x22 can be merged with i7, since they are actually the same item set derived from the same shift transitions in i2.
After the merge, the comeFrom set i2 is updated, replacing x22 with i7 in its shift transition items:
i2x2. goto(Term) from i0,i4 [Term -> Term . '*' Factor, $end]* ('*', i7x22) updated [Term -> Term . '*' Factor, '+' ]* ('*', i7x22) updated [Term -> Term . '*' Factor, '*' ]* ('*', i7x22) updated [Term -> Term . '*' Factor, ')' ]* ('*', i7x22) updated (other items not shown)
Item set x22 is then discarded. The algorithm state is now:
doneList: i0 i1 i3 i5 i8 i2 incList: i4 i9 i10 i11 i6 i7 toDoList: - comeFrom: i2
Phase 1 pops item set i4 from the incomplete list and generates new transition item sets from its shift actions. (Note that i4 was previously cleared and marked incomplete because it was merged with set x11.)
i4x4. goto('(') from i0,i4,i7 [Factor -> '(' . Expr ')', $end]* (Expr, x23) shift [Factor -> '(' . Expr ')', '*' ]* (Expr, x23) shift [Factor -> '(' . Expr ')', '+' ]* (Expr, x23) shift [Factor -> '(' . Expr ')', ')' ]* (Expr, x23) shift [Expr -> . Expr '+' Term, $end] (Expr, x23) shift [Expr -> . Expr '+' Term, '+' ] (Expr, x23) shift [Expr -> . Expr '+' Term, ')' ] (Expr, x23) shift [Expr -> . Term, $end] (Term, x24) shift [Expr -> . Term, '+' ] (Term, x24) shift [Expr -> . Term, '*' ] (Term, x24) shift [Expr -> . Term, ')' ] (Term, x24) shift [Term -> . Term '*' Factor, $end] (Term, x24) shift [Term -> . Term '*' Factor, '+' ] (Term, x24) shift [Term -> . Term '*' Factor, '*' ] (Term, x24) shift [Term -> . Term '*' Factor, ')' ] (Term, x24) shift [Term -> . Factor, $end] (Factor, x25) shift [Term -> . Factor, '+' ] (Factor, x25) shift [Term -> . Factor, '*' ] (Factor, x25) shift [Term -> . Factor, ')' ] (Factor, x25) shift [Factor -> . '(' Expr ')', $end] ('(', x26) shift [Factor -> . '(' Expr ')', '+' ] ('(', x26) shift [Factor -> . '(' Expr ')', '*' ] ('(', x26) shift [Factor -> . '(' Expr ')', ')' ] ('(', x26) shift [Factor -> . id, $end] (id, x27) shift [Factor -> . id, '+' ] (id, x27) shift [Factor -> . id, '*' ] (id, x27) shift [Factor -> . id, ')' ] (id, x27) shift
New transition item sets are generated:
x23. goto(Expr) from i4
[Factor -> '(' Expr . ')', $end]* (-, -)
[Factor -> '(' Expr . ')', '*' ]* (-, -)
[Factor -> '(' Expr . ')', '+' ]* (-, -)
[Factor -> '(' Expr . ')', ')' ]* (-, -)
[Expr -> Expr . '+' Term, $end]* (-, -)
[Expr -> Expr . '+' Term, '+' ]* (-, -)
[Expr -> Expr . '+' Term, ')' ]* (-, -)
x24. goto(Term) from i4
[Expr -> Term ., $end]* (-, -)
[Expr -> Term ., '+' ]* (-, -)
[Expr -> Term ., '*' ]* (-, -)
[Expr -> Term ., ')' ]* (-, -)
[Term -> Term . '*' Factor, $end]* (-, -)
[Term -> Term . '*' Factor, '+' ]* (-, -)
[Term -> Term . '*' Factor, '*' ]* (-, -)
[Term -> Term . '*' Factor, ')' ]* (-, -)
x25. goto(Factor) from i4
[Term -> Factor ., $end]* (-, -)
[Term -> Factor ., '+' ]* (-, -)
[Term -> Factor ., '*' ]* (-, -)
[Term -> Factor ., ')' ]* (-, -)
x26. goto('(') from i4
[Factor -> '(' . Expr ')', $end]* (-, -)
[Factor -> '(' . Expr ')', '+' ]* (-, -)
[Factor -> '(' . Expr ')', '*' ]* (-, -)
[Factor -> '(' . Expr ')', ')' ]* (-, -)
x27. goto(id) from i4
[Factor -> id ., $end]* (-, -)
[Factor -> id ., '+' ]* (-, -)
[Factor -> id ., '*' ]* (-, -)
[Factor -> id ., ')' ]* (-, -)
These new item sets are added to the to-do list. Set i4 is marked as completed and moved to the done list. The algorithm state is now:
doneList: i0 i1 i3 i5 i8 i2 i4 incList: i9 i10 i11 i6 i7 toDoList: x23 x24 x25 x26 x27 comeFrom: i4
Phase 2 pops item set x23 from the to-do list, and generates its closure items (none) and marks its reduction actions (none):
x23. goto(Expr) from i4
[Factor -> '(' Expr . ')', $end]* (-, -)
[Factor -> '(' Expr . ')', '*' ]* (-, -)
[Factor -> '(' Expr . ')', '+' ]* (-, -)
[Factor -> '(' Expr . ')', ')' ]* (-, -)
[Expr -> Expr . '+' Term, $end]* (-, -)
[Expr -> Expr . '+' Term, '+' ]* (-, -)
[Expr -> Expr . '+' Term, ')' ]* (-, -)
The mergeLoop chooses item set i8 as a candidate for merging with set x23:
i8x8. goto(Expr) from i4 [Factor -> '(' Expr . ')', $end]* (')', i11x20) [Factor -> '(' Expr . ')', '+' ]* (')', i11x20) [Factor -> '(' Expr . ')', '*' ]* (')', i11x20) [Expr -> Expr . '+' Term, $end]* ('+', i6x21) [Expr -> Expr . '+' Term, '+' ]* ('+', i6x21) [Expr -> Expr . '+' Term, '*' ]* ('+', i6x21) [Expr -> Expr . '+' Term, ')' ]* ('+', i6x21)
Since merging creates no reduce/reduce conflicts, set x23 is merged into i8. The merge adds a shift item to i8, so it is cleared and moved back to the incomplete list:
i8x8. goto(Expr) from i4 merged with x23, incomplete [Factor -> '(' Expr . ')', $end]* (-, -) reset [Factor -> '(' Expr . ')', '+' ]* (-, -) reset [Factor -> '(' Expr . ')', '*' ]* (-, -) reset [Factor -> '(' Expr . ')', ')' ]* (-, -) added [Expr -> Expr . '+' Term, $end]* (-, -) reset [Expr -> Expr . '+' Term, '+' ]* (-, -) reset [Expr -> Expr . '+' Term, '*' ]* (-, -) reset [Expr -> Expr . '+' Term, ')' ]* (-, -) reset
As before with the merge of sets x22 and i7, it is instructive to note that the items added to set i8 are those shift items that were generated from the additional shift items that had been added to set i4 when it was merged with x11, which caused i4 to be cleared and moved back to the incomplete list. In other words, the algorithm is now propagating the additions previously made to i4, generating new transition items in i4 and adding them to the goto sets generated from (transitioning from) i4.
Item set x23 is actually a duplication of the original canonical LR(1) set i8 that was generated from i4. This explains why x23 can be merged with i8, since they are actually the same item set derived from the same shift transitions in i4.
After the merge, the comeFrom set i4 is updated, replacing x23 with i8 in its shift transition items:
i4x4. goto('(') from i0,i4,i7 [Factor -> '(' . Expr ')', $end]* (Expr, i8x23) [Factor -> '(' . Expr ')', '*' ]* (Expr, i8x23) [Factor -> '(' . Expr ')', '+' ]* (Expr, i8x23) [Factor -> '(' . Expr ')', ')' ]* (Expr, i8x23) [Expr -> . Expr '+' Term, $end] (Expr, i8x23) [Expr -> . Expr '+' Term, '+' ] (Expr, i8x23) [Expr -> . Expr '+' Term, ')' ] (Expr, i8x23) (other items not shown)
Item set x23 is then discarded. The algorithm state is now:
doneList: i0 i1 i3 i5 i2 i4 incList: i9 i10 i11 i6 i7 i8 toDoList: x24 x25 x26 x27 comeFrom: i4
Phase 2 continues, popping item set x24 from the to-do list, and generating its closure items (none) and marking its reduction actions:
x24. goto(Term) from i4
[Expr -> Term ., $end]* ($end, r2) reduce
[Expr -> Term ., '+' ]* ('+', r2) reduce
[Expr -> Term ., '*' ]* ('*', r2) reduce
[Expr -> Term ., ')' ]* (')', r2) reduce
[Term -> Term . '*' Factor, $end]* (-, -)
[Term -> Term . '*' Factor, '+' ]* (-, -)
[Term -> Term . '*' Factor, '*' ]* (-, -)
[Term -> Term . '*' Factor, ')' ]* (-, -)
The mergeLoop chooses item set i2 as a candidate for merging with set x24:
i2x2. goto(Term) from i0,i4 [Expr -> Term ., $end]* ($end, r2) [Expr -> Term ., '+' ]* ('+', r2) [Expr -> Term ., '*' ]* ('*', r2) [Expr -> Term ., ')' ]* (')', r2) [Term -> Term . '*' Factor, $end]* ('*', i7x22) [Term -> Term . '*' Factor, '+' ]* ('*', i7x22) [Term -> Term . '*' Factor, '*' ]* ('*', i7x22) [Term -> Term . '*' Factor, ')' ]* ('*', i7x22)
Item set x24 is merged into i2. This does not add any new items to i2, so it remains on the done list.
In fact, both sets are identical, which is an instance of the LR algorithm generating a duplicate item set. This duplication is simply the result of multiple item sets shifting the same symbol and transitioning to the same item set. This sort of situation occurs frequently in more complex grammars.
The comeFrom set i4 is updated, reflecting the replacement of x24 by i2:
i4x4. goto('(') from i0,i4,i7 [Expr -> . Term, $end] (Term, i2x24) updated [Expr -> . Term, '+' ] (Term, i2x24) updated [Expr -> . Term, ')' ] (Term, i2x24) updated [Term -> . Term '*' Factor, $end] (Term, i2x24) updated [Term -> . Term '*' Factor, '+' ] (Term, i2x24) updated [Term -> . Term '*' Factor, '*' ] (Term, i2x24) updated [Term -> . Term '*' Factor, ')' ] (Term, i2x24) updated (other items not shown)
Item set x24 is then discarded. The algorithm state is now:
doneList: i0 i1 i3 i5 i2 i4 incList: i9 i10 i11 i6 i7 i8 toDoList: x25 x26 x27 comeFrom: i4
Phase 2 continues, popping item set x25 from the to-do list, and generating its closure items (none) and marking its reduction actions:
x25. goto(Factor) from i4
[Term -> Factor ., $end]* ($end, r4) reduce
[Term -> Factor ., '+' ]* ('+', r4) reduce
[Term -> Factor ., '*' ]* ('*', r4) reduce
[Term -> Factor ., ')' ]* (')', r4) reduce
The mergeLoop chooses item set i3 as a candidate for merging with set x25:
i3x3. goto(Factor) from i0,i4,i6 [Term -> Factor ., $end]* ($end, r4) [Term -> Factor ., '+' ]* ('+', r4) [Term -> Factor ., '*' ]* ('*', r4) [Term -> Factor ., ')' ]* (')', r4)
In a situation similar to that of item set x24, item set x25 is a duplicate of set i3, so i3 entirely replaces x25. The comeFrom set i4 is updated, reflecting the replacement:
i4x4. goto('(') from i0,i4,i7 [Term -> . Factor, $end] (Factor, i3x25) [Term -> . Factor, '+' ] (Factor, i3x25) [Term -> . Factor, '*' ] (Factor, i3x25) [Term -> . Factor, ')' ] (Factor, i3x25) (other items not shown)
Item set x25 is then discarded. The algorithm state is now:
doneList: i0 i1 i3 i5 i2 i4 incList: i9 i10 i11 i6 i7 i8 toDoList: x26 x27 comeFrom: i4
Phase 2 continues, popping item set x26 from the to-do list, and generating its closure items and marking its reduction actions (none):
x26. goto('(') from i4
[Factor -> '(' . Expr ')', $end]* (-, -)
[Factor -> '(' . Expr ')', '+' ]* (-, -)
[Factor -> '(' . Expr ')', '*' ]* (-, -)
[Factor -> '(' . Expr ')', ')' ]* (-, -)
[Expr -> . Expr '+' Term, '+' ] (-, -) closure
[Expr -> . Expr '+' Term, ')' ] (-, -) closure
[Expr -> . Term, '+' ] (-, -) closure
[Expr -> . Term, ')' ] (-, -) closure
[Term -> . Term '*' Factor, '+' ] (-, -) closure
[Term -> . Term '*' Factor, '*' ] (-, -) closure
[Term -> . Term '*' Factor, ')' ] (-, -) closure
[Term -> . Factor, '+' ] (-, -) closure
[Term -> . Factor, '*' ] (-, -) closure
[Term -> . Factor, ')' ] (-, -) closure
[Factor -> . '(' Expr ')', '+' ] (-, -) closure
[Factor -> . '(' Expr ')', '*' ] (-, -) closure
[Factor -> . '(' Expr ')', ')' ] (-, -) closure
[Factor -> . id, '+' ] (-, -) closure
[Factor -> . id, '*' ] (-, -) closure
[Factor -> . id, ')' ] (-, -) closure
The mergeLoop chooses item set i4 as a candidate for merging with set x26:
i4x4. goto('(') from i0,i4,i7 [Factor -> '(' . Expr ')', $end]* (Expr, i8x23) [Factor -> '(' . Expr ')', '*' ]* (Expr, i8x23) [Factor -> '(' . Expr ')', '+' ]* (Expr, i8x23) [Factor -> '(' . Expr ')', ')' ]* (Expr, i8x23) (non-kernel items not shown)
Item set x26 is merged into i4. This does not add any new items to i4, so it remains on the done list. The comeFrom set i4 (which is the merged set itself) is then updated, replacing all transitions to x26 with transitions to i4 itself:
i4x4. goto('(') from i0,i4,i7 [Factor -> . '(' Expr ')', $end] ('(', i4x26) updated [Factor -> . '(' Expr ')', '+' ] ('(', i4x26) updated [Factor -> . '(' Expr ')', '*' ] ('(', i4x26) updated [Factor -> . '(' Expr ')', ')' ] ('(', i4x26) updated (other items not shown)
Item set x26 is then discarded. The algorithm state is now:
doneList: i0 i1 i3 i5 i2 i4 incList: i9 i10 i11 i6 i7 i8 toDoList: x27 comeFrom: i4
Phase 2 continues, popping item set x27 from the to-do list, and generating its closure items (none) and marking its reduction actions:
x27. goto(id) from i4
[Factor -> id ., $end]* ($end, r6) reduce
[Factor -> id ., '+' ]* ('+', r6) reduce
[Factor -> id ., '*' ]* ('*', r6) reduce
[Factor -> id ., ')' ]* (')', r6) reduce
The mergeLoop chooses item set i5 as a candidate for merging with set x27:
i5x5. goto(id) from i0,i4,i7 [Factor -> id ., $end]* ($end, r6) [Factor -> id ., '+' ]* ('+', r6) [Factor -> id ., '*' ]* ('*', r6) [Factor -> id ., ')' ]* (')', r6)
Item set x27 is a duplicate of set i5, so it is replaced entirely by i5. The transitions in comeFrom set i4 are then updated accordingly:
i4x4. goto('(') from i0,i4,i7 [Factor -> . id, $end] (id, i5x27) updated [Factor -> . id, '+' ] (id, i5x27) updated [Factor -> . id, '*' ] (id, i5x27) updated [Factor -> . id, ')' ] (id, i5x27) updated (other items not shown)
Item set x27 is then discarded. The algorithm state is now:
doneList: i0 i1 i3 i5 i2 i4 incList: i9 i10 i11 i6 i7 i8 toDoList: - comeFrom: i4
Phase 1 pops item set i9 from the incomplete list and generates new transition item sets from its shift actions:
i9x13. goto(Term) from i6 [Expr -> Expr '+' Term ., $end]* ($end, r1) [Expr -> Expr '+' Term ., '+' ]* ('+', r1) [Term -> Term . '*' Factor, $end]* ('*', x28) shift [Term -> Term . '*' Factor, '+' ]* ('*', x28) shift [Term -> Term . '*' Factor, '*' ]* ('*', x28) shift
A new transition item set is generated:
x28. goto('*') from i9
[Term -> Term '*' . Factor, $end]* (-, -)
[Term -> Term '*' . Factor, '+' ]* (-, -)
[Term -> Term '*' . Factor, '*' ]* (-, -)
The new item sets is added to the to-do list. Set i9 is marked as completed and moved to the done list. The algorithm state is now:
doneList: i0 i1 i3 i5 i2 i4 i9 incList: i10 i11 i6 i7 i8 toDoList: x28 comeFrom: i9
Phase 2 pops item set x28 from the to-do list, and generates its closure items and marks its reduction actions (none):
x28. goto('*') from i9
[Term -> Term '*' . Factor, $end]* (-, -)
[Term -> Term '*' . Factor, '+' ]* (-, -)
[Term -> Term '*' . Factor, '*' ]* (-, -)
[Factor -> . '(' Expr ')', $end] (-, -) closure
[Factor -> . '(' Expr ')', '+' ] (-, -) closure
[Factor -> . '(' Expr ')', '*' ] (-, -) closure
[Factor -> . id, $end] (-, -) closure
[Factor -> . id, '+' ] (-, -) closure
[Factor -> . id, '*' ] (-, -) closure
The mergeLoop chooses item set i7 as a candidate for merging with set x28:
i7x7. goto('*') from i2 [Term -> Term '*' . Factor, $end]* (-, -) [Term -> Term '*' . Factor, '+' ]* (-, -) [Term -> Term '*' . Factor, '*' ]* (-, -) [Term -> Term '*' . Factor, ')' ]* (-, -) (non-kernel items not shown)
Item set x28 is merged into i7, and the transitions in comeFrom set i9 are updated:
i9x13. goto(Term) from i6 [Term -> Term . '*' Factor, $end]* ('*', i7x28) updated [Term -> Term . '*' Factor, '+' ]* ('*', i7x28) updated [Term -> Term . '*' Factor, '*' ]* ('*', i7x28) updated
Item set x28 is then discarded. The algorithm state is now:
doneList: i0 i1 i3 i5 i2 i4 i9 incList: i10 i11 i6 i7 i8 toDoList: - comeFrom: i9
Phase 1 pops item set i10 from the incomplete list:
i10x17. goto(Factor) from i7 [Term -> Term '*' Factor ., $end]* ($end, r3) [Term -> Term '*' Factor ., '+' ]* ('+', r3) [Term -> Term '*' Factor ., '*' ]* ('*', r3)
There are no new transition item sets to be generated from i10 because it contains no shift actions, so the set is marked as completed and moved to the done list. The algorithm state is now:
doneList: i0 i1 i3 i5 i2 i4 i9 i10 incList: i11 i6 i7 i8 toDoList: - comeFrom: i10
Phase 2 has no work to do because the to-do list is empty.
Phase 1 pops item set i11 from the incomplete list:
i11x20. goto(')') from i8 [Factor -> '(' Expr ')' ., $end]* ($end, r5) [Factor -> '(' Expr ')' ., '+' ]* ('+', r5) [Factor -> '(' Expr ')' ., '*' ]* ('*', r5)
There are no new transition item sets to be generated from i11 because it contains no shift actions, so the set is marked as completed and moved to the done list. The algorithm state is now:
doneList: i0 i1 i3 i5 i2 i4 i9 i10 i11 incList: i6 i7 i8 toDoList: - comeFrom: i11
Phase 2 has no work to do because the to-do list is empty.
Phase 1 pops item set i6 from the incomplete list and generates new shift transitions from it:
i6x6. goto('+') from i1,i8 [Expr -> Expr '+' . Term, $end]* (Term, x29) shift [Expr -> Expr '+' . Term, '+' ]* (Term, x29) shift [Expr -> Expr '+' . Term, '*' ]* (Term, x29) shift [Expr -> Expr '+' . Term, ')' ]* (Term, x29) shift [Term -> . Term '*' Factor, $end] (Term, x29) shift [Term -> . Term '*' Factor, '+' ] (Term, x29) shift [Term -> . Term '*' Factor, '*' ] (Term, x29) shift [Term -> . Term '*' Factor, ')' ] (Term, x29) shift [Term -> . Factor, $end] (Factor, x30) shift [Term -> . Factor, '+' ] (Factor, x30) shift [Term -> . Factor, '*' ] (Factor, x30) shift [Term -> . Factor, ')' ] (Factor, x30) shift [Factor -> . '(' Expr ')', $end] ('(', x31) shift [Factor -> . '(' Expr ')', '+' ] ('(', x31) shift [Factor -> . '(' Expr ')', '*' ] ('(', x31) shift [Factor -> . '(' Expr ')', ')' ] ('(', x31) shift [Factor -> . id, $end] (id, x32) shift [Factor -> . id, '+' ] (id, x32) shift [Factor -> . id, '*' ] (id, x32) shift [Factor -> . id, ')' ] (id, x32) shift
Recall that i6 was cleared and marked as incomplete when it was merged with x21. New transition item sets are generated from it:
x29. goto(Term) from i6
[Expr -> Expr '+' Term ., $end]* (-, -)
[Expr -> Expr '+' Term ., '+' ]* (-, -)
[Expr -> Expr '+' Term ., '*' ]* (-, -)
[Expr -> Expr '+' Term ., ')' ]* (-, -)
[Term -> Term . '*' Factor, $end]* (-, -)
[Term -> Term . '*' Factor, '+' ]* (-, -)
[Term -> Term . '*' Factor, '*' ]* (-, -)
[Term -> Term . '*' Factor, ')' ]* (-, -)
x30. goto(Factor) from i6
[Term -> Factor ., $end]* (-, -)
[Term -> Factor ., '+' ]* (-, -)
[Term -> Factor ., '*' ]* (-, -)
[Term -> Factor ., ')' ]* (-, -)
x31. goto('(') from i6
[Factor -> '(' . Expr ')', $end]* (-, -)
[Factor -> '(' . Expr ')', '+' ]* (-, -)
[Factor -> '(' . Expr ')', '*' ]* (-, -)
[Factor -> '(' . Expr ')', ')' ]* (-, -)
x32. goto(id) from i6
[Factor -> id ., $end]* (-, -)
[Factor -> id ., '+' ]* (-, -)
[Factor -> id ., '*' ]* (-, -)
[Factor -> id ., ')' ]* (-, -)
The new item sets are moved to the to-do list, and item set i6 is marked as completed and moved to the done list. The algorithm state is now:
doneList: i0 i1 i3 i5 i2 i4 i9 i10 i11 i6 incList: i7 i8 toDoList: x29 x30 x31 x32 comeFrom: i6
Phase 2 processes the item sets on the to-do list, starting with x29, adding closure items (none) to it and marking its reduction actions:
x29. goto(Term) from i6
[Expr -> Expr '+' Term ., $end]* ($end, r1) reduce
[Expr -> Expr '+' Term ., '+' ]* ('+', r1) reduce
[Expr -> Expr '+' Term ., '*' ]* ('*', r1) reduce
[Expr -> Expr '+' Term ., ')' ]* (')', r1) reduce
[Term -> Term . '*' Factor, $end]* (-, -)
[Term -> Term . '*' Factor, '+' ]* (-, -)
[Term -> Term . '*' Factor, '*' ]* (-, -)
[Term -> Term . '*' Factor, ')' ]* (-, -)
The mergeLoop chooses item set i9 as a candidate for merging with set x29. Merging x29 into i9 adds a shift item to it, and because it was previously marked as completed, it is now cleared and marked as incomplete:
i9x13. goto(Term) from i6 [Expr -> Expr '+' Term ., $end]* ($end, r1) [Expr -> Expr '+' Term ., '+' ]* ('+', r1) [Expr -> Expr '+' Term ., '*' ]* ('*', r1) added [Expr -> Expr '+' Term ., ')' ]* (')', r1) added [Term -> Term . '*' Factor, $end]* (-, -) reset [Term -> Term . '*' Factor, '+' ]* (-, -) reset [Term -> Term . '*' Factor, '*' ]* (-, -) reset [Term -> Term . '*' Factor, ')' ]* (-, -) added
The comeFrom set i6 is updated:
i6x6. goto('+') from i1,i8 [Expr -> Expr '+' . Term, $end]* (Term, i9x29) updated [Expr -> Expr '+' . Term, '+' ]* (Term, i9x29) updated [Expr -> Expr '+' . Term, '*' ]* (Term, i9x29) updated [Expr -> Expr '+' . Term, ')' ]* (Term, i9x29) updated [Term -> . Term '*' Factor, $end] (Term, i9x29) updated [Term -> . Term '*' Factor, '+' ] (Term, i9x29) updated [Term -> . Term '*' Factor, '*' ] (Term, i9x29) updated [Term -> . Term '*' Factor, ')' ] (Term, i9x29) updated (other items not shown)
Item set x29 is discarded, and the algorithm state is now:
doneList: i0 i1 i3 i5 i2 i4 i10 i11 i6 incList: i7 i8 i9 toDoList: x30 x31 x32 comeFrom: i6
Phase 2 continues processing the item sets on the to-do list, popping the next item set x30, adding closure items (none) to it and marking its reduction actions:
x30. goto(Factor) from i6
[Term -> Factor ., $end]* ($end, r4) reduce
[Term -> Factor ., '+' ]* ('+', r4) reduce
[Term -> Factor ., '*' ]* ('*', r4) reduce
[Term -> Factor ., ')' ]* (')', r4) reduce
The mergeLoop chooses item set i3 as a candidate for merging with set x30. The two sets are identical, x30 being a duplicate of i3, so i3 replaces x30 and remains on the done list:
i3x3. goto(Factor) from i0,i4,i6 [Term -> Factor ., $end]* ($end, r4) [Term -> Factor ., '+' ]* ('+', r4) [Term -> Factor ., '*' ]* ('*', r4) [Term -> Factor ., ')' ]* (')', r4)
The comeFrom set i6 is updated:
i6x6. goto('+') from i1,i8 [Term -> . Factor, $end] (Factor, i3x30) updated [Term -> . Factor, '+' ] (Factor, i3x30) updated [Term -> . Factor, '*' ] (Factor, i3x30) updated [Term -> . Factor, ')' ] (Factor, i3x30) updated (other items not shown)
Item set x30 is discarded, and the algorithm state is now:
doneList: i0 i1 i3 i5 i2 i4 i10 i11 i6 incList: i7 i8 i9 toDoList: x31 x32 comeFrom: i6
Phase 2 continues processing the item sets on the to-do list, popping the next item set x31, adding closure items to it and marking its reduction actions (none):
x31. goto('(') from i6
[Factor -> '(' . Expr ')', $end]* (-, -)
[Factor -> '(' . Expr ')', '+' ]* (-, -)
[Factor -> '(' . Expr ')', '*' ]* (-, -)
[Factor -> '(' . Expr ')', ')' ]* (-, -)
[Expr -> . Expr '+' Term, '+' ] (-, -) closure
[Expr -> . Expr '+' Term, ')' ] (-, -) closure
[Expr -> . Term, '+' ] (-, -) closure
[Expr -> . Term, ')' ] (-, -) closure
[Term -> . Term '*' Factor, '+' ] (-, -) closure
[Term -> . Term '*' Factor, '*' ] (-, -) closure
[Term -> . Term '*' Factor, ')' ] (-, -) closure
[Term -> . Factor, '+' ] (-, -) closure
[Term -> . Factor, '*' ] (-, -) closure
[Term -> . Factor, ')' ] (-, -) closure
[Factor -> . '(' Expr ')', '+' ] (-, -) closure
[Factor -> . '(' Expr ')', '*' ] (-, -) closure
[Factor -> . '(' Expr ')', ')' ] (-, -) closure
[Factor -> . id, '+' ] (-, -) closure
[Factor -> . id, '*' ] (-, -) closure
[Factor -> . id, ')' ] (-, -) closure
The mergeLoop chooses item set i4 as a candidate for merging with set x31:
i4x4. goto('(') from i0,i4,i6,i7 [Factor -> '(' . Expr ')', $end]* (Expr, i8x23) [Factor -> '(' . Expr ')', '*' ]* (Expr, i8x23) [Factor -> '(' . Expr ')', '+' ]* (Expr, i8x23) [Factor -> '(' . Expr ')', ')' ]* (Expr, i8x23)
Merging x31 into i4 does not change it, so it remains on the done list. The comeFrom set i6 is updated:
i6x6. goto('+') from i1,i8 [Factor -> . '(' Expr ')', $end] ('(', i4x31) updated [Factor -> . '(' Expr ')', '+' ] ('(', i4x31) updated [Factor -> . '(' Expr ')', '*' ] ('(', i4x31) updated [Factor -> . '(' Expr ')', ')' ] ('(', i4x31) updated (other items not shown)
Item set x31 is discarded, and the algorithm state is now:
doneList: i0 i1 i3 i5 i2 i4 i10 i11 i6 incList: i7 i8 i9 toDoList: x32 comeFrom: i6
Phase 2 continues processing the item sets on the to-do list, popping the next item set x32, adding closure items (none) to it and marking its reduction actions:
x32. goto(id) from i6
[Factor -> id ., $end]* ($end, r6) reduce
[Factor -> id ., '+' ]* ('+', r6) reduce
[Factor -> id ., '*' ]* ('*', r6) reduce
[Factor -> id ., ')' ]* (')', r6) reduce
The mergeLoop chooses item set i5 as a candidate for merging with set x32. Set x32 is a duplicate of i5, so i5 replaces x32, and the comeFrom set i6 is updated accordingly:
i6x6. goto('+') from i1,i8 [Factor -> . id, $end] (id, i5x32) updated [Factor -> . id, '+' ] (id, i5x32) updated [Factor -> . id, '*' ] (id, i5x32) updated [Factor -> . id, ')' ] (id, i5x32) updated (other items not shown)
Item set x32 is discarded, and the algorithm state is now:
doneList: i0 i1 i3 i5 i2 i4 i10 i11 i6 incList: i7 i8 i9 toDoList: - comeFrom: i6
Phase 1 pops item set i7 from the incomplete list, and new shift transitions are generated from it:
i7x7. goto('*') from i2,i9 [Term -> Term '*' . Factor, $end]* (Factor, x33) shift [Term -> Term '*' . Factor, '+' ]* (Factor, x33) shift [Term -> Term '*' . Factor, '*' ]* (Factor, x33) shift [Term -> Term '*' . Factor, ')' ]* (Factor, x33) shift [Factor -> . '(' Expr ')', $end] ('(', x34) shift [Factor -> . '(' Expr ')', '+' ] ('(', x34) shift [Factor -> . '(' Expr ')', '*' ] ('(', x34) shift [Factor -> . '(' Expr ')', ')' ] ('(', x34) shift [Factor -> . id, $end] (id, x35) shift [Factor -> . id, '+' ] (id, x35) shift [Factor -> . id, '*' ] (id, x35) shift [Factor -> . id, ')' ] (id, x35) shift
New transition item sets are generated and added to the to-do list:
x33. goto(Factor) from i7
[Term -> Term '*' Factor ., $end]* (-, -)
[Term -> Term '*' Factor ., '+' ]* (-, -)
[Term -> Term '*' Factor ., '*' ]* (-, -)
[Term -> Term '*' Factor ., ')' ]* (-, -)
x34. goto('(') from i7
[Factor -> '(' . Expr ')', $end]* (-, -)
[Factor -> '(' . Expr ')', '+' ]* (-, -)
[Factor -> '(' . Expr ')', '*' ]* (-, -)
[Factor -> '(' . Expr ')', ')' ]* (-, -)
x35. goto(id) from i7
[Factor -> id ., $end]* (-, -)
[Factor -> id ., '+' ]* (-, -)
[Factor -> id ., '*' ]* (-, -)
[Factor -> id ., ')' ]* (-, -)
Item set i7 is made the comeFrom set, marked as completed, and moved to the done list. The algorithm state is now:
doneList: i0 i1 i3 i5 i2 i4 i10 i11 i6 i7 incList: i8 i9 toDoList: x33 x34 x35 comeFrom: i7
Phase 2 processes the item sets on the to-do list, starting with x33, adding closure items (none) to it and marking its reduction actions:
x33. goto(Factor) from i7
[Term -> Term '*' Factor ., $end]* ($end, r3) reduce
[Term -> Term '*' Factor ., '+' ]* ('+', r3) reduce
[Term -> Term '*' Factor ., '*' ]* ('*', r3) reduce
[Term -> Term '*' Factor ., ')' ]* (')', r3) reduce
The mergeLoop chooses item set i10 as a candidate for merging with set x33. Set x33 is a duplicate of i10, so i10 replaces it in the comeFrom set i7:
i7x7. goto('*') from i2,i9 [Term -> Term '*' . Factor, $end]* (Factor, i10x33) updated [Term -> Term '*' . Factor, '+' ]* (Factor, i10x33) updated [Term -> Term '*' . Factor, '*' ]* (Factor, i10x33) updated [Term -> Term '*' . Factor, ')' ]* (Factor, i10x33) updated (other items not shown)
Item set x33 is discarded, and the algorithm state is now:
doneList: i0 i1 i3 i5 i2 i4 i10 i11 i6 i7 incList: i8 i9 toDoList: x34 x35 comeFrom: i7
Phase 2 continues, processing item set x34 from the to-do list, adding closure items to it and marking its reduction actions (none):
x34. goto('(') from i7
[Factor -> '(' . Expr ')', $end]* (-, -)
[Factor -> '(' . Expr ')', '+' ]* (-, -)
[Factor -> '(' . Expr ')', '*' ]* (-, -)
[Factor -> '(' . Expr ')', ')' ]* (-, -)
[Expr -> . Expr '+' Term, '+' ] (-, -) closure
[Expr -> . Expr '+' Term, ')' ] (-, -) closure
[Expr -> . Term, '+' ] (-, -) closure
[Expr -> . Term, ')' ] (-, -) closure
[Term -> . Term '*' Factor, '+' ] (-, -) closure
[Term -> . Term '*' Factor, '*' ] (-, -) closure
[Term -> . Term '*' Factor, ')' ] (-, -) closure
[Term -> . Factor, '+' ] (-, -) closure
[Term -> . Factor, '*' ] (-, -) closure
[Term -> . Factor, ')' ] (-, -) closure
[Factor -> . '(' Expr ')', '+' ] (-, -) closure
[Factor -> . '(' Expr ')', '*' ] (-, -) closure
[Factor -> . '(' Expr ')', ')' ] (-, -) closure
[Factor -> . id, '+' ] (-, -) closure
[Factor -> . id, '*' ] (-, -) closure
[Factor -> . id, ')' ] (-, -) closure
The mergeLoop chooses item set i4 as a candidate for merging with set x34:
i4x4. goto('(') from i0,i4,i6,i7 [Factor -> '(' . Expr ')', $end]* (Expr, i8x23) [Factor -> '(' . Expr ')', '*' ]* (Expr, i8x23) [Factor -> '(' . Expr ')', '+' ]* (Expr, i8x23) [Factor -> '(' . Expr ')', ')' ]* (Expr, i8x23) (non-kernel items not shown)
Merging set x34 into i4 does not change i4, so it remains in the done list. The comeFrom set i7 is updated:
i7x7. goto('*') from i2,i9 [Factor -> . '(' Expr ')', $end] ('(', i4x34) [Factor -> . '(' Expr ')', '+' ] ('(', i4x34) [Factor -> . '(' Expr ')', '*' ] ('(', i4x34) [Factor -> . '(' Expr ')', ')' ] ('(', i4x34) (other items not shown)
Item set x34 is discarded, and the algorithm state is now:
doneList: i0 i1 i3 i5 i2 i4 i10 i11 i6 i7 incList: i8 i9 toDoList: x35 comeFrom: i7
Phase 2 continues, popping item set x35 from the to-do list, adding closure items (none) to it and marking its reduction actions:
x35. goto(id) from i7
[Factor -> id ., $end]* ($end, r6) reduce
[Factor -> id ., '+' ]* ('+', r6) reduce
[Factor -> id ., '*' ]* ('*', r6) reduce
[Factor -> id ., ')' ]* (')', r6) reduce
The mergeLoop chooses item set i5 as a candidate for merging with set x35. Set x35 is a duplicate of i5, so i5 replaces it in the comeFrom set i7:
i7x7. goto('*') from i2,i9 [Factor -> . id, $end] (id, i5x35) [Factor -> . id, '+' ] (id, i5x35) [Factor -> . id, '*' ] (id, i5x35) [Factor -> . id, ')' ] (id, i5x35) (other items not shown)
Item set x35 is discarded, and the algorithm state is now:
doneList: i0 i1 i3 i5 i2 i4 i10 i11 i6 i7 incList: i8 i9 toDoList: - comeFrom: i7
Phase 1 pops item set i8 from the incomplete list, and new shift transitions are generated from it:
i8x8. goto(Expr) from i4 [Factor -> '(' Expr . ')', $end]* (')', x36) shift [Factor -> '(' Expr . ')', '+' ]* (')', x36) shift [Factor -> '(' Expr . ')', '*' ]* (')', x36) shift [Factor -> '(' Expr . ')', ')' ]* (')', x36) shift [Expr -> Expr . '+' Term, $end]* ('+', x37) shift [Expr -> Expr . '+' Term, '+' ]* ('+', x37) shift [Expr -> Expr . '+' Term, '*' ]* ('+', x37) shift [Expr -> Expr . '+' Term, ')' ]* ('+', x37) shift
New transition item sets are generated and added to the to-do list:
x36. goto(')') from i8
[Factor -> '(' Expr ')' ., $end]* (-, -)
[Factor -> '(' Expr ')' ., '+' ]* (-, -)
[Factor -> '(' Expr ')' ., '*' ]* (-, -)
[Factor -> '(' Expr ')' ., ')' ]* (-, -)
x37. goto('+') from i8
[Expr -> Expr '+' . Term, $end]* (-, -)
[Expr -> Expr '+' . Term, '+' ]* (-, -)
[Expr -> Expr '+' . Term, '*' ]* (-, -)
[Expr -> Expr '+' . Term, ')' ]* (-, -)
Item set i8 is made the comeFrom set, marked as completed, and moved to the done list. The algorithm state is now:
doneList: i0 i1 i3 i5 i8 i2 i4 i10 i11 i6 i7 i8 incList: i9 toDoList: x36 x37 comeFrom: i8
Phase 2 processes the item sets on the to-do list, starting with x36, adding closure items (none) to it and marking its reduction actions:
x36. goto(')') from i8
[Factor -> '(' Expr ')' ., $end]* ($end, r5) reduce
[Factor -> '(' Expr ')' ., '+' ]* ('+', r5) reduce
[Factor -> '(' Expr ')' ., '*' ]* ('*', r5) reduce
[Factor -> '(' Expr ')' ., ')' ]* (')', r5) reduce
The mergeLoop chooses item set i11 as a candidate for merging with set x36:
i11x20. goto(')') from i8 [Factor -> '(' Expr ')' ., $end]* ($end, r5) [Factor -> '(' Expr ')' ., '+' ]* ('+', r5) [Factor -> '(' Expr ')' ., '*' ]* ('*', r5)
Merging x36 into i11 adds a reduction item but no shift items, so i11 remains on the done list. The comeFrom set i8 is updated, replacing x36 with i11:
i8x8. goto(Expr) from i4 [Factor -> '(' Expr . ')', $end]* (')', i11x36) updated [Factor -> '(' Expr . ')', '+' ]* (')', i11x36) updated [Factor -> '(' Expr . ')', '*' ]* (')', i11x36) updated [Factor -> '(' Expr . ')', ')' ]* (')', i11x36) updated (other items not shown)
Item set x36 is discarded, and the algorithm state is now:
doneList: i0 i1 i3 i5 i8 i2 i4 i10 i11 i6 i7 i8 incList: i9 toDoList: x37 comeFrom: i8
Phase 2 continues, popping item set x37, and adding closure items to it and marking its reduction actions (none):
x37. goto('+') from i8
[Expr -> Expr '+' . Term, $end]* (-, -)
[Expr -> Expr '+' . Term, '+' ]* (-, -)
[Expr -> Expr '+' . Term, '*' ]* (-, -)
[Expr -> Expr '+' . Term, ')' ]* (-, -)
[Term -> . Term '*' Factor, $end] (-, -) closure
[Term -> . Term '*' Factor, '+' ] (-, -) closure
[Term -> . Term '*' Factor, '*' ] (-, -) closure
[Term -> . Term '*' Factor, ')' ] (-, -) closure
[Term -> . Factor, $end] (-, -) closure
[Term -> . Factor, '+' ] (-, -) closure
[Term -> . Factor, '*' ] (-, -) closure
[Term -> . Factor, ')' ] (-, -) closure
[Factor -> . '(' Expr ')', $end] (-, -) closure
[Factor -> . '(' Expr ')', '+' ] (-, -) closure
[Factor -> . '(' Expr ')', '*' ] (-, -) closure
[Factor -> . '(' Expr ')', ')' ] (-, -) closure
[Factor -> . id, $end] (-, -) closure
[Factor -> . id, '+' ] (-, -) closure
[Factor -> . id, '*' ] (-, -) closure
[Factor -> . id, ')' ] (-, -) closure
The mergeLoop chooses item set i6 as a candidate for merging with set x37:
i6x6. goto('+') from i1,i8 [Expr -> Expr '+' . Term, $end]* (Term, i9x29) [Expr -> Expr '+' . Term, '+' ]* (Term, i9x29) [Expr -> Expr '+' . Term, '*' ]* (Term, i9x29) [Expr -> Expr '+' . Term, ')' ]* (Term, i9x29) (non-kernel items not shown)
Set x37 is a duplicate of i6, so i6 replaces it in the comeFrom set i8:
i8x8. goto(Expr) from i4 [Expr -> Expr . '+' Term, $end]* ('+', i6x37) updated [Expr -> Expr . '+' Term, '+' ]* ('+', i6x37) updated [Expr -> Expr . '+' Term, '*' ]* ('+', i6x37) updated [Expr -> Expr . '+' Term, ')' ]* ('+', i6x37) updated (other items not shown)
Item set x37 is discarded, and the algorithm state is now:
doneList: i0 i1 i3 i5 i8 i2 i4 i10 i11 i6 i7 i8 incList: i9 toDoList: - comeFrom: i8
Phase 1 pops item set i9 from the incomplete list, and new shift transitions are generated from it:
i9x13. goto(Term) from i6 [Expr -> Expr '+' Term ., $end]* ($end, r1) [Expr -> Expr '+' Term ., '+' ]* ('+', r1) [Expr -> Expr '+' Term ., '*' ]* ('*', r1) [Expr -> Expr '+' Term ., ')' ]* (')', r1) [Term -> Term . '*' Factor, $end]* ('*', x38) shift [Term -> Term . '*' Factor, '+' ]* ('*', x38) shift [Term -> Term . '*' Factor, '*' ]* ('*', x38) shift [Term -> Term . '*' Factor, ')' ]* ('*', x38) shift
A new transition item set is generated and added to the to-do list:
x38. goto('*') from i9
[Term -> Term '*' . Factor, $end]* (-, -)
[Term -> Term '*' . Factor, '+' ]* (-, -)
[Term -> Term '*' . Factor, '*' ]* (-, -)
[Term -> Term '*' . Factor, ')' ]* (-, -)
Item set i9 is made the comeFrom set, marked as completed, and moved to the done list. The algorithm state is now:
doneList: i0 i1 i3 i5 i8 i2 i4 i10 i11 i6 i7 i9 incList: - toDoList: x38 comeFrom: i9
Phase 2 processes final item set x38 from the to-do list, adding closure items to it and marking its reduction actions (none):
x38. goto('*') from i9
[Term -> Term '*' . Factor, $end]* (-, -)
[Term -> Term '*' . Factor, '+' ]* (-, -)
[Term -> Term '*' . Factor, '*' ]* (-, -)
[Term -> Term '*' . Factor, ')' ]* (-, -)
[Factor -> . '(' Expr ')', $end] (-, -) closure
[Factor -> . '(' Expr ')', '+' ] (-, -) closure
[Factor -> . '(' Expr ')', '*' ] (-, -) closure
[Factor -> . '(' Expr ')', ')' ] (-, -) closure
[Factor -> . id, $end] (-, -) closure
[Factor -> . id, '+' ] (-, -) closure
[Factor -> . id, '*' ] (-, -) closure
[Factor -> . id, ')' ] (-, -) closure
The mergeLoop chooses item set i7 as a candidate for merging with set x38:
i7x7. goto('*') from i2,i9 [Term -> Term '*' . Factor, $end]* (Factor, i10x33) [Term -> Term '*' . Factor, '+' ]* (Factor, i10x33) [Term -> Term '*' . Factor, '*' ]* (Factor, i10x33) [Term -> Term '*' . Factor, ')' ]* (Factor, i10x33) (non-kernel items not shown)
Set x38 is a duplicate of i7, so i7 replaces it in the comeFrom set i9:
i9x13. goto(Term) from i6 [Term -> Term . '*' Factor, $end]* ('*', i7x38) [Term -> Term . '*' Factor, '+' ]* ('*', i7x38) [Term -> Term . '*' Factor, '*' ]* ('*', i7x38) [Term -> Term . '*' Factor, ')' ]* ('*', i7x38) (other items not shown)
Item set x38 is then discarded.
Both the to-do list and the incomplete list are empty at this point, so the algorithm terminates. Its final state is:
doneList: i0 i1 i3 i5 i8 i2 i4 i10 i11 i6 i7 i9 incList: - toDoList: - comeFrom: i9
A total of 39 item sets (originally named x0 through x38) were created during the iterations of the algorithm. 27 of those sets were discarded, leaving 12 of them (renamed i0 through i11) as the final canonical LR(1) sets produced by the algorithm:
i0x0. initial item set [$accept -> . Expr, $end]* (Expr, i1x1) [Expr -> . Expr '+' Term, $end] (Expr, i1x1) [Expr -> . Expr '+' Term, '+' ] (Expr, i1x1) [Expr -> . Term, $end] (Term, i2x2) [Expr -> . Term, '+' ] (Term, i2x2) [Term -> . Term '*' Factor, $end] (Term, i2x2) [Term -> . Term '*' Factor, '+' ] (Term, i2x2) [Term -> . Term '*' Factor, '*' ] (Term, i2x2) [Term -> . Factor, $end] (Factor, i3x3) [Term -> . Factor, '+' ] (Factor, i3x3) [Term -> . Factor, '*' ] (Factor, i3x3) [Factor -> . '(' Expr ')', $end] ('(', i4x4) [Factor -> . '(' Expr ')', '+' ] ('(', i4x4) [Factor -> . '(' Expr ')', '*' ] ('(', i4x4) [Factor -> . id, $end] (id, i5x5) [Factor -> . id, '+' ] (id, i5x5) [Factor -> . id, '*' ] (id, i5x5) i1x1. goto(Expr) from i0 [$accept -> Expr ., $end]* ($end, accept) [Expr -> Expr . '+' Term, $end]* ('+', i6x6) [Expr -> Expr . '+' Term, '+' ]* ('+', i6x6) i2x2. goto(Term) from i0,i4 => merged with x9,x24 [Expr -> Term ., $end]* ($end, r2) [Expr -> Term ., '+' ]* ('+', r2) [Expr -> Term ., '*' ]* ('*', r2) [Expr -> Term ., ')' ]* (')', r2) [Term -> Term . '*' Factor, $end]* ('*', i7x7x22) [Term -> Term . '*' Factor, '+' ]* ('*', i7x7x22) [Term -> Term . '*' Factor, '*' ]* ('*', i7x7x22) [Term -> Term . '*' Factor, ')' ]* ('*', i7x22) i3x3. goto(Factor) from i0,i4,i6 => merged with x10,x14,x25,x30 [Term -> Factor ., $end]* ($end, r4) [Term -> Factor ., '+' ]* ('+', r4) [Term -> Factor ., '*' ]* ('*', r4) [Term -> Factor ., ')' ]* (')', r4) i4x4. goto('(') from i0,i4,i6,i7 => merged with x11,x15,x18,x26,x31,x34 [Factor -> '(' . Expr ')', $end]* (Expr, i8x8x23) [Factor -> '(' . Expr ')', '*' ]* (Expr, i8x8x23) [Factor -> '(' . Expr ')', '+' ]* (Expr, i8x8x23) [Factor -> '(' . Expr ')', ')' ]* (Expr, i8x8x23) [Expr -> . Expr '+' Term, $end] (Expr, i8x8x23) [Expr -> . Expr '+' Term, '+' ] (Expr, i8x8x23) [Expr -> . Expr '+' Term, ')' ] (Expr, i8x8x23) [Expr -> . Term, $end] (Term, i2x9x24) [Expr -> . Term, '+' ] (Term, i2x9x24) [Expr -> . Term, '*' ] (Term, i2x9x24) [Expr -> . Term, ')' ] (Term, i2x9x24) [Term -> . Term '*' Factor, $end] (Term, i2x9x24) [Term -> . Term '*' Factor, '+' ] (Term, i2x9x24) [Term -> . Term '*' Factor, '*' ] (Term, i2x9x24) [Term -> . Term '*' Factor, ')' ] (Term, i2x9x24) [Term -> . Factor, $end] (Factor, i3x10x25) [Term -> . Factor, '+' ] (Factor, i3x10x25) [Term -> . Factor, '*' ] (Factor, i3x10x25) [Term -> . Factor, ')' ] (Factor, i3x10x25) [Factor -> . '(' Expr ')', $end] ('(', i4x11x26) [Factor -> . '(' Expr ')', '+' ] ('(', i4x11x26) [Factor -> . '(' Expr ')', '*' ] ('(', i4x11x26) [Factor -> . '(' Expr ')', ')' ] ('(', i4x11x26) [Factor -> . id, $end] (id, i5x12x27) [Factor -> . id, '+' ] (id, i5x12x27) [Factor -> . id, '*' ] (id, i5x12x27) [Factor -> . id, ')' ] (id, i5x12x27) i5x5. goto(id) from i0,i4,i6,i7 => merged with x16,x19,x32,x35 [Factor -> id ., $end]* ($end, r6) [Factor -> id ., '+' ]* ('+', r6) [Factor -> id ., '*' ]* ('*', r6) [Factor -> id ., ')' ]* (')', r6) i6x6. goto('+') from i1,i8 => merged with x21 [Expr -> Expr '+' . Term, $end]* (Term, i9x13x29) [Expr -> Expr '+' . Term, '+' ]* (Term, i9x13x29) [Expr -> Expr '+' . Term, '*' ]* (Term, i9x29) [Expr -> Expr '+' . Term, ')' ]* (Term, i9x29) [Term -> . Term '*' Factor, $end] (Term, i9x13x29) [Term -> . Term '*' Factor, '+' ] (Term, i9x13x29) [Term -> . Term '*' Factor, '*' ] (Term, i9x13x29) [Term -> . Term '*' Factor, ')' ] (Term, i9x29) [Term -> . Factor, $end] (Factor, i3x14x30) [Term -> . Factor, '+' ] (Factor, i3x14x30) [Term -> . Factor, '*' ] (Factor, i3x14x30) [Term -> . Factor, ')' ] (Factor, i3x30) [Factor -> . '(' Expr ')', $end] ('(', i4x15x31) [Factor -> . '(' Expr ')', '+' ] ('(', i4x15x31) [Factor -> . '(' Expr ')', '*' ] ('(', i4x15x31) [Factor -> . '(' Expr ')', ')' ] ('(', i4x31) [Factor -> . id, $end] (id, i5x16x32) [Factor -> . id, '+' ] (id, i5x16x32) [Factor -> . id, '*' ] (id, i5x16x32) [Factor -> . id, ')' ] (id, i5x32) i7x7. goto('*') from i2,i9 => merged with x22,x28,x38 [Term -> Term '*' . Factor, $end]* (Factor, i10x17x33) [Term -> Term '*' . Factor, '+' ]* (Factor, i10x17x33) [Term -> Term '*' . Factor, '*' ]* (Factor, i10x17x33) [Term -> Term '*' . Factor, ')' ]* (Factor, i10x33) [Factor -> . '(' Expr ')', $end] ('(', i4x18x34) [Factor -> . '(' Expr ')', '+' ] ('(', i4x18x34) [Factor -> . '(' Expr ')', '*' ] ('(', i4x18x34) [Factor -> . '(' Expr ')', ')' ] ('(', i4x34) [Factor -> . id, $end] (id, i5x19x35) [Factor -> . id, '+' ] (id, i5x19x35) [Factor -> . id, '*' ] (id, i5x19x35) [Factor -> . id, ')' ] (id, i5x35) i8x8. goto(Expr) from i4 => merged with x23 [Factor -> '(' Expr . ')', $end]* (')', i11x20x36) [Factor -> '(' Expr . ')', '+' ]* (')', i11x20x36) [Factor -> '(' Expr . ')', '*' ]* (')', i11x20x36) [Factor -> '(' Expr . ')', ')' ]* (')', i11x36) [Expr -> Expr . '+' Term, $end]* ('+', i6x21x37) [Expr -> Expr . '+' Term, '+' ]* ('+', i6x21x37) [Expr -> Expr . '+' Term, '*' ]* ('+', i6x21x37) [Expr -> Expr . '+' Term, ')' ]* ('+', i6x21x37)x9. goto(Term) from i4 => merged into i2, discarded [Expr -> Term ., $end]* ($end, r2) [Expr -> Term ., '+' ]* ('+', r2) [Expr -> Term ., '*' ]* ('*', r2) [Expr -> Term ., ')' ]* (')', r2) [Term -> Term . '*' Factor, $end]* (-, -) [Term -> Term . '*' Factor, '+' ]* (-, -) [Term -> Term . '*' Factor, '*' ]* (-, -) [Term -> Term . '*' Factor, ')' ]* (-, -)x10. goto(Factor) from i4 => merged into i3, discarded [Term -> Factor ., $end]* ($end, r4) [Term -> Factor ., '+' ]* ('+', r4) [Term -> Factor ., '*' ]* ('*', r4) [Term -> Factor ., ')' ]* (')', r4)x11. goto('(') from i4 => merged into i4, discarded [Factor -> '(' . Expr ')', $end]* (-, -) [Factor -> '(' . Expr ')', '+' ]* (-, -) [Factor -> '(' . Expr ')', '*' ]* (-, -) [Factor -> '(' . Expr ')', ')' ]* (-, -) [Expr -> . Expr '+' Term, '+' ] (-, -) [Expr -> . Expr '+' Term, ')' ] (-, -) [Expr -> . Term, '+' ] (-, -) [Expr -> . Term, ')' ] (-, -) [Term -> . Term '*' Factor, '+' ] (-, -) [Term -> . Term '*' Factor, '*' ] (-, -) [Term -> . Term '*' Factor, ')' ] (-, -) [Term -> . Factor, '+' ] (-, -) [Term -> . Factor, '*' ] (-, -) [Term -> . Factor, ')' ] (-, -) [Factor -> . '(' Expr ')', '+' ] (-, -) [Factor -> . '(' Expr ')', '*' ] (-, -) [Factor -> . '(' Expr ')', ')' ] (-, -) [Factor -> . id, '+' ] (-, -) [Factor -> . id, '*' ] (-, -) [Factor -> . id, ')' ] (-, -)x12. goto(id) from i4 => merged into i5, discarded [Factor -> id ., $end]* ($end, r6) [Factor -> id ., '+' ]* ('+', r6) [Factor -> id ., '*' ]* ('*', r6) [Factor -> id ., ')' ]* (')', r6) i9x13. goto(Term) from i6 => merged with x29 [Expr -> Expr '+' Term ., $end]* ($end, r1) [Expr -> Expr '+' Term ., '+' ]* ('+', r1) [Expr -> Expr '+' Term ., '*' ]* ('*', r1) [Expr -> Expr '+' Term ., ')' ]* (')', r1) [Term -> Term . '*' Factor, $end]* ('*', i7x28x38) [Term -> Term . '*' Factor, '+' ]* ('*', i7x28x38) [Term -> Term . '*' Factor, '*' ]* ('*', i7x28x38) [Term -> Term . '*' Factor, ')' ]* ('*', i7x38)x14. goto(Factor) from i6 => merged into i3, discarded [Term -> Factor ., $end]* ($end, r4) [Term -> Factor ., '+' ]* ('+', r4) [Term -> Factor ., '*' ]* ('*', r4)x15. goto('(') from i6 => merged into i4, discarded [Factor -> '(' . Expr ')', $end]* (-, -) [Factor -> '(' . Expr ')', '+' ]* (-, -) [Factor -> '(' . Expr ')', '*' ]* (-, -)x16. goto(id) from i6 => merged into i5, discarded [Factor -> id ., $end]* ($end, r6) [Factor -> id ., '+' ]* ('+', r6) [Factor -> id ., '*' ]* ('*', r6) i10x17. goto(Factor) from i7 => merged with x33 [Term -> Term '*' Factor ., $end]* ($end, r3) [Term -> Term '*' Factor ., '+' ]* ('+', r3) [Term -> Term '*' Factor ., '*' ]* ('*', r3)x18. goto('(') from i7 => merged into i4, discarded [Factor -> '(' . Expr ')', $end]* (-, -) [Factor -> '(' . Expr ')', '+' ]* (-, -) [Factor -> '(' . Expr ')', '*' ]* (-, -) [Expr -> . Expr '+' Term, '+' ] (-, -) [Expr -> . Expr '+' Term, ')' ] (-, -) [Expr -> . Term, '+' ] (-, -) [Expr -> . Term, ')' ] (-, -) [Term -> . Term '*' Factor, '+' ] (-, -) [Term -> . Term '*' Factor, '*' ] (-, -) [Term -> . Term '*' Factor, ')' ] (-, -) [Term -> . Factor, '+' ] (-, -) [Term -> . Factor, '*' ] (-, -) [Term -> . Factor, ')' ] (-, -) [Factor -> . '(' Expr ')', '+' ] (-, -) [Factor -> . '(' Expr ')', '*' ] (-, -) [Factor -> . '(' Expr ')', ')' ] (-, -) [Factor -> . id, '+' ] (-, -) [Factor -> . id, '*' ] (-, -) [Factor -> . id, ')' ] (-, -)x19. goto(id) from i7 => merged into i5, discarded [Factor -> id ., $end]* ($end, r6) [Factor -> id ., '+' ]* ('+', r6) [Factor -> id ., '*' ]* ('*', r6) i11x20. goto(')') from i8 => merged with x36 [Factor -> '(' Expr ')' ., $end]* ($end, r5) [Factor -> '(' Expr ')' ., '+' ]* ('+', r5) [Factor -> '(' Expr ')' ., '*' ]* ('*', r5) [Factor -> '(' Expr ')' ., ')' ]* (')', r5)x21. goto('+') from i8 => merged into i6, discarded [Expr -> Expr '+' . Term, $end]* (-, -) [Expr -> Expr '+' . Term, '+' ]* (-, -) [Expr -> Expr '+' . Term, '*' ]* (-, -) [Expr -> Expr '+' . Term, ')' ]* (-, -) [Term -> . Term '*' Factor, $end] (-, -) [Term -> . Term '*' Factor, '+' ] (-, -) [Term -> . Term '*' Factor, '*' ] (-, -) [Term -> . Term '*' Factor, ')' ] (-, -) [Term -> . Factor, $end] (-, -) [Term -> . Factor, '+' ] (-, -) [Term -> . Factor, '*' ] (-, -) [Term -> . Factor, ')' ] (-, -) [Factor -> . '(' Expr ')', $end] (-, -) [Factor -> . '(' Expr ')', '+' ] (-, -) [Factor -> . '(' Expr ')', '*' ] (-, -) [Factor -> . '(' Expr ')', ')' ] (-, -) [Factor -> . id, $end] (-, -) [Factor -> . id, '+' ] (-, -) [Factor -> . id, '*' ] (-, -) [Factor -> . id, ')' ] (-, -)x22. goto('*') from i2 => merged into i7, discarded [Term -> Term '*' . Factor, $end]* (-, -) [Term -> Term '*' . Factor, '+' ]* (-, -) [Term -> Term '*' . Factor, '*' ]* (-, -) [Term -> Term '*' . Factor, ')' ]* (-, -) [Factor -> . '(' Expr ')', $end] (-, -) [Factor -> . '(' Expr ')', '+' ] (-, -) [Factor -> . '(' Expr ')', '*' ] (-, -) [Factor -> . '(' Expr ')', ')' ] (-, -) [Factor -> . id, $end] (-, -) [Factor -> . id, '+' ] (-, -) [Factor -> . id, '*' ] (-, -) [Factor -> . id, ')' ] (-, -)x23. goto(Expr) from i4 => merged into i8, discarded [Factor -> '(' Expr . ')', $end]* (-, -) [Factor -> '(' Expr . ')', '*' ]* (-, -) [Factor -> '(' Expr . ')', '+' ]* (-, -) [Factor -> '(' Expr . ')', ')' ]* (-, -) [Expr -> Expr . '+' Term, $end]* (-, -) [Expr -> Expr . '+' Term, '+' ]* (-, -) [Expr -> Expr . '+' Term, ')' ]* (-, -)x24. goto(Term) from i4 => merged into i2, discarded [Expr -> Term ., $end]* ($end, r2) [Expr -> Term ., '+' ]* ('+', r2) [Expr -> Term ., '*' ]* ('*', r2) [Expr -> Term ., ')' ]* (')', r2) [Term -> Term . '*' Factor, $end]* (-, -) [Term -> Term . '*' Factor, '+' ]* (-, -) [Term -> Term . '*' Factor, '*' ]* (-, -) [Term -> Term . '*' Factor, ')' ]* (-, -)x25. goto(Factor) from i4 => duplicate of i3, discarded [Term -> Factor ., $end]* ($end, r4) [Term -> Factor ., '+' ]* ('+', r4) [Term -> Factor ., '*' ]* ('*', r4) [Term -> Factor ., ')' ]* (')', r4)x26. goto('(') from i4 => merged into i4, discarded [Factor -> '(' . Expr ')', $end]* (-, -) [Factor -> '(' . Expr ')', '+' ]* (-, -) [Factor -> '(' . Expr ')', '*' ]* (-, -) [Factor -> '(' . Expr ')', ')' ]* (-, -) [Expr -> . Expr '+' Term, '+' ] (-, -) [Expr -> . Expr '+' Term, ')' ] (-, -) [Expr -> . Term, '+' ] (-, -) [Expr -> . Term, ')' ] (-, -) [Term -> . Term '*' Factor, '+' ] (-, -) [Term -> . Term '*' Factor, '*' ] (-, -) [Term -> . Term '*' Factor, ')' ] (-, -) [Term -> . Factor, '+' ] (-, -) [Term -> . Factor, '*' ] (-, -) [Term -> . Factor, ')' ] (-, -) [Factor -> . '(' Expr ')', '+' ] (-, -) [Factor -> . '(' Expr ')', '*' ] (-, -) [Factor -> . '(' Expr ')', ')' ] (-, -) [Factor -> . id, '+' ] (-, -) [Factor -> . id, '*' ] (-, -) [Factor -> . id, ')' ] (-, -)x27. goto(id) from i4 => duplicate of i5, discarded [Factor -> id ., $end]* ($end, r6) [Factor -> id ., '+' ]* ('+', r6) [Factor -> id ., '*' ]* ('*', r6) [Factor -> id ., ')' ]* (')', r6)x28. goto('*') from i9 => merged into i7, discarded [Term -> Term '*' . Factor, $end]* (-, -) [Term -> Term '*' . Factor, '+' ]* (-, -) [Term -> Term '*' . Factor, '*' ]* (-, -) [Factor -> . '(' Expr ')', $end] (-, -) [Factor -> . '(' Expr ')', '+' ] (-, -) [Factor -> . '(' Expr ')', '*' ] (-, -) [Factor -> . id, $end] (-, -) [Factor -> . id, '+' ] (-, -) [Factor -> . id, '*' ] (-, -)x29. goto(Term) from i6 => merged into i9, discarded [Expr -> Expr '+' Term ., $end]* ($end, r1) [Expr -> Expr '+' Term ., '+' ]* ('+', r1) [Expr -> Expr '+' Term ., '*' ]* ('*', r1) [Expr -> Expr '+' Term ., ')' ]* (')', r1) [Term -> Term . '*' Factor, $end]* (-, -) [Term -> Term . '*' Factor, '+' ]* (-, -) [Term -> Term . '*' Factor, '*' ]* (-, -) [Term -> Term . '*' Factor, ')' ]* (-, -)x30. goto(Factor) from i6 => duplicate of i3, discarded [Term -> Factor ., $end]* ($end, r4) [Term -> Factor ., '+' ]* ('+', r4) [Term -> Factor ., '*' ]* ('*', r4) [Term -> Factor ., ')' ]* (')', r4)x31. goto('(') from i6 => merged into i4, discarded [Factor -> '(' . Expr ')', $end]* (-, -) [Factor -> '(' . Expr ')', '+' ]* (-, -) [Factor -> '(' . Expr ')', '*' ]* (-, -) [Factor -> '(' . Expr ')', ')' ]* (-, -) [Expr -> . Expr '+' Term, '+' ] (-, -) [Expr -> . Expr '+' Term, ')' ] (-, -) [Expr -> . Term, '+' ] (-, -) [Expr -> . Term, ')' ] (-, -) [Term -> . Term '*' Factor, '+' ] (-, -) [Term -> . Term '*' Factor, '*' ] (-, -) [Term -> . Term '*' Factor, ')' ] (-, -) [Term -> . Factor, '+' ] (-, -) [Term -> . Factor, ')' ] (-, -) [Term -> . Factor, '*' ] (-, -) [Factor -> . '(' Expr ')', '+' ] (-, -) [Factor -> . '(' Expr ')', '*' ] (-, -) [Factor -> . '(' Expr ')', ')' ] (-, -) [Factor -> . id, '+' ] (-, -) [Factor -> . id, '*' ] (-, -) [Factor -> . id, ')' ] (-, -)x32. goto(id) from i6 => duplicate of i5, discarded [Factor -> id ., $end]* ($end, r6) [Factor -> id ., '+' ]* ('+', r6) [Factor -> id ., '*' ]* ('*', r6) [Factor -> id ., ')' ]* (')', r6)x33. goto(Factor) from i7 => duplicate of i10, discarded [Term -> Term '*' Factor ., $end]* ($end, r3) [Term -> Term '*' Factor ., '+' ]* ('+', r3) [Term -> Term '*' Factor ., '*' ]* ('*', r3) [Term -> Term '*' Factor ., ')' ]* (')', r3)x34. goto('(') from i7 => merged into i4, discarded [Factor -> '(' . Expr ')', $end]* (-, -) [Factor -> '(' . Expr ')', '+' ]* (-, -) [Factor -> '(' . Expr ')', '*' ]* (-, -) [Factor -> '(' . Expr ')', ')' ]* (-, -) [Expr -> . Expr '+' Term, '+' ] (-, -) [Expr -> . Expr '+' Term, ')' ] (-, -) [Expr -> . Term, '+' ] (-, -) [Expr -> . Term, ')' ] (-, -) [Term -> . Term '*' Factor, '+' ] (-, -) [Term -> . Term '*' Factor, '*' ] (-, -) [Term -> . Term '*' Factor, ')' ] (-, -) [Term -> . Factor, '+' ] (-, -) [Term -> . Factor, '*' ] (-, -) [Term -> . Factor, ')' ] (-, -) [Factor -> . '(' Expr ')', '+' ] (-, -) [Factor -> . '(' Expr ')', '*' ] (-, -) [Factor -> . '(' Expr ')', ')' ] (-, -) [Factor -> . id, '+' ] (-, -) [Factor -> . id, '*' ] (-, -) [Factor -> . id, ')' ] (-, -)x35. goto(id) from i7 => duplicate of i5, discarded [Factor -> id ., $end]* ($end, r6) [Factor -> id ., '+' ]* ('+', r6) [Factor -> id ., '*' ]* ('*', r6) [Factor -> id ., ')' ]* (')', r6)x36. goto(')') from i8 => duplicate of i11, discarded [Factor -> '(' Expr ')' ., $end]* ($end, r5) [Factor -> '(' Expr ')' ., '+' ]* ('+', r5) [Factor -> '(' Expr ')' ., '*' ]* ('*', r5) [Factor -> '(' Expr ')' ., ')' ]* (')', r5)x37. goto('+') from i8 => duplicate of i6, discarded [Expr -> Expr '+' . Term, $end]* (-, -) [Expr -> Expr '+' . Term, '+' ]* (-, -) [Expr -> Expr '+' . Term, '*' ]* (-, -) [Expr -> Expr '+' . Term, ')' ]* (-, -) [Term -> . Term '*' Factor, $end] (-, -) [Term -> . Term '*' Factor, '+' ] (-, -) [Term -> . Term '*' Factor, '*' ] (-, -) [Term -> . Term '*' Factor, ')' ] (-, -) [Term -> . Factor, $end] (-, -) [Term -> . Factor, '+' ] (-, -) [Term -> . Factor, '*' ] (-, -) [Term -> . Factor, ')' ] (-, -) [Factor -> . '(' Expr ')', $end] (-, -) [Factor -> . '(' Expr ')', '+' ] (-, -) [Factor -> . '(' Expr ')', '*' ] (-, -) [Factor -> . '(' Expr ')', ')' ] (-, -) [Factor -> . id, $end] (-, -) [Factor -> . id, '+' ] (-, -) [Factor -> . id, '*' ] (-, -) [Factor -> . id, ')' ] (-, -)x38. goto('*') from i9 => duplicate of i7, discarded [Term -> Term '*' . Factor, $end]* (-, -) [Term -> Term '*' . Factor, '+' ]* (-, -) [Term -> Term '*' . Factor, '*' ]* (-, -) [Term -> Term '*' . Factor, ')' ]* (-, -) [Factor -> . '(' Expr ')', $end] (-, -) [Factor -> . '(' Expr ')', '+' ] (-, -) [Factor -> . '(' Expr ')', '*' ] (-, -) [Factor -> . '(' Expr ')', ')' ] (-, -) [Factor -> . id, $end] (-, -) [Factor -> . id, '+' ] (-, -) [Factor -> . id, '*' ] (-, -) [Factor -> . id, ')' ] (-, -)
The following LR parser states are derived from the item sets:
s0. initial item set
$accept : . Expr
Expr : . Expr '+' Term
Expr : . Term
Term : . Term '*' Factor
Term : . Factor
Factor : . '(' Expr ')'
Factor : . id
'(' shift s4
id shift s5
Expr goto s1
Term goto s2
Factor goto s3
s1. goto(Expr) from s0
$accept : Expr . (r0)
Expr : Expr . '+' Term
$end accept
'+' shift s6
s2. goto(Term) from s0,s4
Expr : Term . (r2)
Term : Term . '*' Factor
$end reduce r2
'+' reduce r2
'*' shift s7 s/r conflict
'*' reduce r2 s/r conflict
')' reduce r2
s3. goto(Factor) from s0,s4,s6
Term : Factor . (r4)
$end reduce r4
'+' reduce r4
'*' reduce r4
')' reduce r4
s4. goto('(') from s0,s4,s6,s7
Factor : '(' . Expr ')'
Expr : . Expr '+' Term
Expr : . Term
Term : . Term '*' Factor
Term : . Factor
Factor : . '(' Expr ')'
Factor : . id
'(' shift s4
id shift s5
Expr goto s8
Term goto s2
Factor goto s3
s5. goto(id) from s0,s4,s6,s7
Factor : id . (r6)
$end reduce r6
'+' reduce r6
'*' reduce r6
')' reduce r6
s6. goto('+') from s1,s8
Expr : Expr '+' . Term
Term : . Term '*' Factor
Term : . Factor
Factor : . '(' Expr ')'
Factor : . id
'(' shift s4
id shift s5
Term goto s9
Factor goto s3
s7. goto('*') from s2,s9
Term : Term '*' . Factor
Factor : . '(' Expr ')'
Factor : . id
'(' shift s4
id shift s5
Factor goto s10
s8. goto(Expr) from s4
Factor : '(' Expr . ')'
Expr : Expr . '+' Term
'+' shift s6
')' shift s11
s9. goto(Term) from s6
Expr : Expr '+' Term . (r1)
Term : Term . '*' Factor
$end reduce r1
'+' reduce r1
'*' shift s7 s/r conflict
'*' reduce r1 s/r conflict
')' reduce r1
s10. goto(Factor) from s7
Term : Term '*' Factor . (r3)
$end reduce r3
'+' reduce r3
'*' reduce r3
s11. goto(')') from s8
Factor : '(' Expr ')' . (r5)
$end reduce r5
'+' reduce r5
'*' reduce r5
')' reduce r5
The parser states are summarized in this table:
| State | Terminals | Nonterminals | Default | |||||||
|---|---|---|---|---|---|---|---|---|---|---|
| $end | '+' | '*' | '(' | ')' | id | Expr | Term | Factor | ||
| 0 | - | - | - | s4 | - | s5 | s1 | s2 | s3 | - |
| 1 | acc | s6 | - | - | - | - | - | - | - | - |
| 2 | r2 | r2 | s7 / r2 | - | r2 | - | - | - | - | r2 |
| 3 | r4 | r4 | r4 | r4 | r4 | - | - | - | - | r4 |
| 4 | - | - | - | s4 | - | s5 | s8 | s2 | s3 | - |
| 5 | r6 | r6 | r6 | - | r6 | - | - | - | - | r6 |
| 6 | - | - | - | s4 | - | s5 | - | s9 | s3 | - |
| 7 | - | - | - | s4 | - | s5 | - | - | s10 | - |
| 8 | - | s6 | - | - | s11 | - | - | - | - | - |
| 9 | r1 | r1 | s7 / r1 | - | r1 | - | - | - | - | r1 |
| 10 | r3 | r3 | r3 | - | - | - | - | - | - | r3 |
| 11 | r5 | r5 | r5 | - | r5 | - | - | - | - | r5 |
The discarded states (item sets) are summarized in this table:
| Discarded (Duplicate and Merged) States | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| State | $end | '+' | '*' | '(' | ')' | id | Expr | Term | Factor | Default |
| x9 » 2 | r2 | r2 | s? / r2 | - | r2 | - | - | - | - | r2 |
| x24 » 2 | r2 | r2 | s? / r2 | - | r2 | - | - | - | - | r2 |
| x10 » 3 | r4 | r4 | r4 | - | r4 | - | - | - | - | r4 |
| x14 » 3 | r4 | r4 | r4 | - | - | - | - | - | - | r4 |
| x25 » 3 | r4 | r4 | r4 | - | r4 | - | - | - | - | r4 |
| x30 » 3 | r4 | r4 | r4 | - | r4 | - | - | - | - | r4 |
| x11 » 4 | - | - | - | s? | - | s? | s? | s? | s? | - |
| x15 » 4 | - | - | - | - | - | - | s? | - | - | - |
| x18 » 4 | - | - | - | s? | - | s? | s? | s? | s? | - |
| x26 » 4 | - | - | - | s? | - | s? | s? | s? | s? | - |
| x31 » 4 | - | - | - | s? | - | s? | s? | s? | s? | - |
| x34 » 4 | - | - | - | s? | - | s? | s? | s? | s? | - |
| x12 » 5 | r6 | r6 | r6 | - | r6 | - | - | - | - | r6 |
| x16 » 5 | r6 | r6 | r6 | - | - | - | - | - | - | r6 |
| x19 » 5 | r6 | r6 | r6 | - | - | - | - | - | - | r6 |
| x27 » 5 | r6 | r6 | r6 | - | r6 | - | - | - | - | r6 |
| x32 » 5 | r6 | r6 | r6 | - | r6 | - | - | - | - | r6 |
| x35 » 5 | r6 | r6 | r6 | - | r6 | - | - | - | - | r6 |
| x21 » 6 | - | - | - | s? | - | s? | - | s? | s? | - |
| x37 » 6 | - | - | - | s? | - | s? | - | s? | s? | - |
| x22 » 7 | - | - | - | s? | - | s? | - | - | s? | - |
| x28 » 7 | - | - | - | s? | - | s? | - | - | s? | - |
| x38 » 7 | - | - | - | s? | - | s? | - | - | s? | - |
| x23 » 8 | - | s? | - | - | s? | - | - | - | - | - |
| x29 » 9 | r1 | r1 | s? / r1 | - | r1 | - | - | - | - | r1 |
| x33 » 10 | r3 | r3 | r3 | - | r3 | - | - | - | - | r3 |
| x36 » 11 | r5 | r5 | r5 | - | r5 | - | - | - | - | r5 |
The Honalee LR Algorithm is discussed further at:
honalee.html.
Next example:
honalee_ex2.html.
Author's home page: david.tribble.com
Copyright ©2004-2005 by David R. Tribble, all rights reserved.
Permission is granted to reproduce this document in whole or in part provided
that proper credit is given to the original author.