Revision: 2.0, 2005-12-31
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.
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 not LALR, the resulting collection of
LR(1) item sets contains one more set than
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 non-LALR item sets that cannot be merged.
%token a %token b %token c %token d %token e r0. $accept : S r1. S : a A d r2. S : a B e r3. S : b A e r4. S : b B d r5. A : c r6. B : c
This grammar is LR(1) but is not LALR(1), because combining the following two LR(1) item sets produces a reduce/reduce conflict:
i6. [A -> c ., d] (d, r5) [B -> c ., e] (e, r6) i9. [A -> c ., e] (e, r5) [B -> c ., d] (d, r6)
The first item set calls for reduction r5 for look-ahead
symbol d and reduction r6 for symbol e.
However, the second item set calls for reduction r6 for
symbol d and reduction r5 for symbol e.
An LALR(1) algorithm would attempt to merge these two sets because they have the
same core items, but such a merging creates a reduce/reduce conflict
on symbols d and e.
A pure LR(1) algorithm (such as the Honalee algorithm) does not merge these
two sets, and therefore does not introduce any reduce/reduce conflict.
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) = { a, b }
First(S) = { a, b }
First(A) = { c }
First(B) = { c }
The algorithm is started by first initializing all of the lists and counters. 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:
doneList: - (empty) incList: - (empty) toDoList: - (empty) comeFrom: - (empty)
Prior to entering the main loop of the algorithm, the initial item set x0 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 -> . S, $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 : S" and the marker is positioned immediately before the symbol "S". 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 is now (with new additions underlined):
doneList: - incList: - toDoList: x0 comeFrom: -
The main loop of the algorithm 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. Phase 2 generates all of the closure items for set x0, which now looks like:
x0. initial item set [$accept -> . S, $end]* (-, -) [S -> . a A d, $end] (-, -) closure [S -> . a B e, $end] (-, -) closure [S -> . b A e, $end] (-, -) closure [S -> . b B d, $end] (-, -) closure
Phase 2 also marks all of the reduction items of set x0, but there are none to mark.
Phase 2 then looks for another existing item set within the done and incomplete lists that could be merged with x0, but there are none (since x0 is currently the only item set in the lists).
Item set x0 is then moved to the end of the incomplete list, which is just the set of tail elements of the done (completed) list. As an item set xN is moved to the incomplete list, it is renamed to iM and becomes an official item set of the grammar. Thus set x0 it renamed to i0 as it is moved to the incomplete list:
i0x0. initial item set [$accept -> . S, $end]* (-, -) [S -> . a A d, $end] (-, -) [S -> . a B e, $end] (-, -) [S -> . b A e, $end] (-, -) [S -> . b B d, $end] (-, -)
At the point in phase 2, the comeFrom set would be updated to reflect the renaming of set x0, but since there is no comeFrom set established at this point by the algorithm, this is not done.
The state of the algorithm is now:
doneList: - incList: i0 toDoList: - comeFrom: -
Phase 2 is done at this point because the to-do list is now empty.
Next, phase 1 of the next iteration examines the first set in the incomplete list, which is again item set i0 (which is the only item set in any of the lists so far). New transition item sets are generated from this set, each being composed of new kernel items created by shifting groups of the same transition symbol in the generating items:
i0x0. initial item set [$accept -> . S, $end]* (S, x1) shift [S -> . a A d, $end] (a, x2) shift [S -> . a B e, $end] (a, x2) shift [S -> . b A e, $end] (b, x3) shift [S -> . b B d, $end] (b, x3) shift
The new transition item sets generated are:
x1. goto(S) from i0 [$accept -> S ., $end]* (-, -) x2. goto(a) from i0 [S -> a . A d, $end]* (-, -) [S -> a . B e, $end]* (-, -) x3. goto(b) from i0 [S -> b . A e, $end]* (-, -) [S -> b . B d, $end]* (-, -)
Item set x1 was created by shifting symbol S from set i0, and similarly set x2 is the transition from i0 by shifting symbol a, and set x3 is the transition from i0 by shifting symbol b.
These new transition sets are appended to the to-do list. Item set i0 becomes the comeFrom set, since it is the set from which the new transition sets are generated. All of the transition items of set i0 are then marked, and the set is marked as completed and moved to the done list. The state of the algorithm is now:
doneList: i0 incList: - toDoList: x1 x2 x3 comeFrom: i0
Phase 2 begins, which processes all of the item sets in the to-do list, starting with x1. All of its closure items (none) are generated, and all of its reduction actions are marked. It cannot be merged with any existing set in the done or incomplete lists (which presently contain only set i0), so x1 is renamed to i1 and moved to the incomplete list:
i1x1. goto(S) from i0 incomplete [$accept -> S ., $end]* ($end, accept) reduce
The items with shift actions in the comeFrom set i0 are updated to reflect the renaming of set x1 to i1:
i0x0. initial item set complete [$accept -> . S, $end]* (S, i1x1) updated [S -> . a A d, $end] (a, x2) [S -> . a B e, $end] (a, x2) [S -> . b A e, $end] (b, x3) [S -> . b B d, $end] (b, x3)
The state of the algorithm is now:
doneList: i0 incList: i1 toDoList: x2 x3 comeFrom: i0
Phase 2 continues, popping set x2 from the to-do list. All of its closure items are added and its reduction actions (none) are marked. As there are no existing item sets that it can be merged with, it is renamed to i2 and moved to the incomplete list:
i2x2. goto(a) from i0 incomplete [S -> a . A d, $end]* (-, -) [S -> a . B e, $end]* (-, -) [A -> . c, d ] (-, -) closure [B -> . c, e ] (-, -) closure
The comeFrom set i0 is updated to reflect the renaming of set x2:
i0x0. initial item set complete [$accept -> . S, $end]* (S, i1x1) [S -> . a A d, $end] (a, i2x2) updated [S -> . a B e, $end] (a, i2x2) updated [S -> . b A e, $end] (b, x3) [S -> . b B d, $end] (b, x3)
The state of the algorithm is now:
doneList: i0 incList: i1 i2 toDoList: x3 comeFrom: i0
Phase 2 continues, popping set x3 from the to-do list. All of its closure items are added and its reduction actions (none) are marked. As there are no existing item sets that it can be merged with, it is renamed to i3 and moved to the incomplete list:
i3x3. goto(b) from i0 incomplete [S -> b . A e, $end]* (-, -) [S -> b . B d, $end]* (-, -) [A -> . c, e ] (-, -) closure [B -> . c, d ] (-, -) closure
The comeFrom set i0 is updated to reflect the renaming:
i0x0. initial item set complete [$accept -> . S, $end]* (S, i1x1) [S -> . a A d, $end] (a, i2x2) [S -> . a B e, $end] (a, i2x2) [S -> . b A e, $end] (b, i3x3) updated [S -> . b B d, $end] (b, i3x3) updated
The state of the algorithm is now:
doneList: i0 incList: i1 i2 i3 toDoList: - comeFrom: i0
Phase 2 of this iteration stops because the to-do list is empty, and the next iteration starts.
Phase 1 of the next iteration begins, retrieving set i1 from the incomplete list and generating new transition sets from it, of which there are none. The set is then marked as completed and moved to the done list:
i1x1. goto(S) from i0 complete [$accept -> S ., $end]* ($end, accept)
The state of the algorithm is now:
doneList: i0 i1 incList: i2 i3 toDoList: - comeFrom: i1
Phase 2 of this iteration has no work to do because the to-do list is empty, so the next iteration begins.
Phase 1 of the next iteration pops item set i2 from the incomplete list, making it the comeFrom set and generating new transition sets from it:
i2x2. goto(a) from i0 [S -> a . A d, $end]* (A, x4) shift [S -> a . B e, $end]* (B, x5) shift [A -> . c, d ] (c, x6) shift [B -> . c, e ] (c, x6) shift
The new transition item sets are:
x4. goto(A) from i2 [S -> a A . d, $end]* (-, -) x5. goto(B) from i2 [S -> a B . e, $end]* (-, -) x6. goto(c) from i2 [A -> c ., d ]* (-, -) [B -> c ., e ]* (-, -)
Set i2 is marked as completed and moved to the done list. The state of the algorithm is now:
doneList: i0 i1 i2 incList: i3 toDoList: x4 x5 x6 comeFrom: i2
Phase 2 begins, retrieving item set x4 from the to-do list. Closure items (none) are added to it, and its reduction actions (none) are marked. No other item sets can be merged with x4, so it is renamed to i4 and moved to the incomplete list:
i4x4. goto(A) from i2 [S -> a A . d, $end]* (-, -)
The comeFrom set i2 is updated to reflect the renaming:
i2x2. goto(a) from i0 [S -> a . A d, $end]* (A, i4x4) updated [S -> a . B e, $end]* (B, x5) [A -> . c, d ] (c, x6) [B -> . c, e ] (c, x6)
The state of the algorithm is now:
doneList: i0 i1 i2 incList: i3 i4 toDoList: x5 x6 comeFrom: i2
Phase 2 continues, retrieving item set x5 from the to-do list. Closure items (none) are added to it, and its reduction actions (none) are marked. No other item sets can be merged with x5, so it is renamed to i5 and moved to the incomplete list:
i5x5. goto(B) from i2 [S -> a B . e, $end]* (-, -)
The comeFrom set i2 is updated to reflect the renaming:
i2x2. goto(a) from i0 [S -> a . A d, $end]* (A, i4x4) [S -> a . B e, $end]* (B, i5x5) updated [A -> . c, d ] (c, x6) [B -> . c, e ] (c, x6)
The state of the algorithm is now:
doneList: i0 i1 i2 incList: i3 i4 i5 toDoList: x6 comeFrom: i2
Phase 2 continues, retrieving item set x6 from the to-do list. Closure items (none) are added to it, and its reduction actions (none) are marked. No other item sets can be merged with x4, so it is renamed to i6 and moved to the incomplete list:
i6x6. goto(c) from i2 [A -> c ., d ]* (d, r5) reduce [B -> c ., e ]* (e, r6) reduce
The comeFrom set i2 is updated to reflect the renaming:
i2x2. goto(a) from i0 [S -> a . A d, $end]* (A, i4x4) [S -> a . B e, $end]* (B, i5x5) [A -> . c, d ] (c, i6x6) updated [B -> . c, e ] (c, i6x6) updated
The state of the algorithm is now:
doneList: i0 i1 i2 incList: i3 i4 i5 i6 toDoList: - comeFrom: i2
The to-do list is now empty, so this iteration is complete.
Phase 1 of the next iteration begins, popping item set i3 from the to-do list, making it the comeFrom set, and generating new shift transitions from it:
i3x3. goto(b) from i0 incomplete [S -> b . A e, $end]* (A, x7) shift [S -> b . B d, $end]* (B, x8) shift [A -> . c, e ] (c, x9) shift [B -> . c, d ] (c, x9) shift
The new transition item sets are:
x7. goto(A) from i3 [S -> b A . e, $end]* (-, -) x8. goto(B) from i3 [S -> b B . d, $end]* (-, -) x9. goto(c) from i3 [A -> c ., e ]* (-, -) [B -> c ., d ]* (-, -)
These new sets are added to the to-do list, and set i3 is marked as completed and moved to the done list. The state of the algorithm is now:
doneList: i0 i1 i2 i3 incList: i4 i5 i6 toDoList: x7 x8 x9 comeFrom: i3
Phase 2 then pops item set x7 from the to-do list. Closure items (none) are added to it, and its reduction actions (none) are marked. It cannot be merged with any existing set, so x7 is renamed to i7 and moved to the incomplete list:
i7x7. goto(A) from i3 [S -> b A . e, $end]* (-, -)
The comeFrom set i3 is updated:
i3x3. goto(b) from i0 incomplete [S -> b . A e, $end]* (A, i7x7) updated [S -> b . B d, $end]* (B, x8) [A -> . c, e ] (c, x9) [B -> . c, d ] (c, x9)
The state of the algorithm is now:
doneList: i0 i1 i2 i3 incList: i4 i5 i6 i7 toDoList: x8 x9 comeFrom: i3
Phase 2 then pops item set x8 from the to-do list. Closure items (none) are added to it, and its reduction actions (none) are marked. It cannot be merged with any existing set, so x8 is renamed to i8 and moved to the incomplete list:
i8x8. goto(B) from i3 [S -> b B . d, $end]* (-, -)
The comeFrom set i3 is updated:
i3x3. goto(b) from i0 incomplete [S -> b . A e, $end]* (A, i7x7) [S -> b . B d, $end]* (B, i8x8) updated [A -> . c, e ] (c, x9) [B -> . c, d ] (c, x9)
The state of the algorithm is now:
doneList: i0 i1 i2 i3 incList: i4 i5 i6 i7 i8 toDoList: x9 comeFrom: i3
Phase 2 continues, popping item set x9 from the to-do list. Closure items (none) are added to it, and its reduction actions (none) are marked.
x9. goto(c) from i3 [A -> c ., e ]* (e, r5) reduce [B -> c ., d ]* (d, r6) reduce
The next step in the algorithm determines if set x9 can be merged with any previously generated item set in the done or incomplete list. Item sets having identical kernel core items are candidates for item set merging. The kernel core items of set x9 are:
[A -> c . ]* core [B -> c . ]* core
Up to this point in the execution of the algorithm, no item sets have been merged. This time, however, item set i6 is found as a candidate for merging with set x9, having the same kernel core items:
i6x6. goto(c) from i2 [A -> c ., d ]* (d, r5) [B -> c ., e ]* (e, r6)
Unfortunately, merging these two item sets would create reduce/reduce conflicts:
merged i6+x9. goto(c) from i2,i3 [A -> c ., d ]* (d, r5) r/r conflict [A -> c ., e ]* (e, r5) r/r conflict [B -> c ., d ]* (d, r6) r/r conflict [B -> c ., e ]* (e, r6) r/r conflict
Given a look-ahead symbol of d, the merged item set calls for a reduction by rules r5 and r6; similarly, a look-ahead symbol of e also calls for a reduction by rules r5 and r6. So merging the two item sets would create two reduce/reduce conflicts.
If the sets could be merged, this would be an instance of the algorithm merging separate canonical LR item sets just like an LALR item set generator would do, resulting in fewer total sets for the grammar. But the creation of reduce/reduce conflicts from merging indicates that even though the grammar is LR, it is not LALR or SLR. In other words, more item sets are necessary for recognizing the LR grammar than would be if the grammar was only LALR.
Faced with the creation of a conflict, the algorithm chooses not to merge the two item sets, but instead to leave them as separate sets.
There are no other candidate sets for merging with set x9, so it is renamed to i9 and moved to the incomplete list:
i9x9. goto(c) from i3 [A -> c ., e ]* (e, r5) [B -> c ., d ]* (d, r6)
The comeFrom set i3 is updated:
i3x3. goto(b) from i0 incomplete [S -> b . A e, $end]* (A, i7x7) [S -> b . B d, $end]* (B, i8x8) [A -> . c, e ] (c, i9x9) updated [B -> . c, d ] (c, i9x9) updated
Phase 2 of this iteration stops because there are no more item sets left in the to-do list. The state of the algorithm is now:
doneList: i0 i1 i2 i3 incList: i4 i5 i6 i7 i8 i9 toDoList: - comeFrom: i3
Phase 1 of the next iteration pops set i4 from the incomplete list, makes it the comeFrom set, and generates its shift transitions:
i4x4. goto(A) from i2 [S -> a A . d, $end]* (d, x10) shift
A new transition item set is created and added to the to-do list:
x10. goto(d) from i4 [S -> a A d ., $end]* (-, -)
Set i4 is marked as completed and moved to the done list. The state of the algorithm is now:
doneList: i0 i1 i2 i3 i4 incList: i5 i6 i7 i8 i9 toDoList: x10 comeFrom: i4
Phase 2 then pops item set x10 from the to-do list. Closure items (none) are added to it, and its reduction actions are marked. It cannot be merged with any existing set, so x10 is renamed to i10 and moved to the incomplete list:
i10x10. goto(d) from i4 [S -> a A d ., $end]* ($end, r1) reduce
The comeFrom set i4 is updated:
i4x4. goto(A) from i2 [S -> a A . d, $end]* (d, i10x10) updated
The to-do list is now empty, so this iteration stops. The state of the algorithm is now:
doneList: i0 i1 i2 i3 i4 incList: i5 i6 i7 i8 i9 i10 toDoList: - comeFrom: i4
Phase 1 of the next iteration pops set i5 from the incomplete list, makes it the comeFrom set, and generates its shift transitions:
i5x5. goto(B) from i2 [S -> a B . e, $end]* (e, x11) shift
A new transition item set is created and added to the to-do list:
x11. goto(e) from i5 [S -> a B e ., $end]* (-, -)
Set i5 is marked as completed and moved to the done list. The state of the algorithm is now:
doneList: i0 i1 i2 i3 i4 i5 incList: i6 i7 i8 i9 i10 toDoList: x11 comeFrom: i5
Phase 2 then pops item set x11 from the to-do list. Closure items (none) are added to it, and its reduction actions are marked. It cannot be merged with any existing set, so x11 is renamed to i11 and moved to the incomplete list:
i11x11. goto(e) from i5 [S -> a B e ., $end]* ($end, r2) reduce
The comeFrom set i5 is updated:
i5x5. goto(B) from i2 [S -> a B . e, $end]* (e, i11x11) updated
No more sets remain in the to-do list. The state of the algorithm is now:
doneList: i0 i1 i2 i3 i4 i5 incList: i6 i7 i8 i9 i10 i11 toDoList: - comeFrom: i5
Phase 1 of the next iteration pops set i6 from the incomplete list, makes it the comeFrom set, and generates shift transitions from it. There are no transitions from i6, so it is simply marked as completed and moved to the done list:
i6x6. goto(c) from i2 complete [A -> c ., d ]* (d, r5) [B -> c ., e ]* (e, r6)
The state of the algorithm is now:
doneList: i0 i1 i2 i3 i4 i5 i6 incList: i7 i8 i9 i10 i11 toDoList: - comeFrom: i6
Phase 2 of this iteration has no work to do because the to-do list is empty, so the next iteration begins.
Phase 1 of the next iteration pops set i7 from the incomplete list, makes it the comeFrom set, and generates shift transitions from it:
i7x7. goto(A) from i3 [S -> b A . e, $end]* (e, x12) shift
A new transition item set is created and added to the to-do list:
x12. goto(e) from i7 [S -> b A e ., $end]* (-, -)
Set i7 is marked as completed and moved to the done list. The state of the algorithm is now:
doneList: i0 i1 i2 i3 i4 i5 i6 i7 incList: i8 i9 i10 i11 toDoList: x12 comeFrom: i7
Phase 2 then pops item set x12 from the to-do list. Closure items (none) are added to it, and its reduction actions are marked. It cannot be merged with any existing set, so x12 is renamed to i12 and moved to the incomplete list:
i12x12. goto(e) from i7 [S -> b A e ., $end]* ($end, r3) reduce
The comeFrom set i7 is updated:
i7x7. goto(A) from i3 [S -> b A . e, $end]* (e, i12x12) updated
The to-do is empty, so the state of the algorithm is now:
doneList: i0 i1 i2 i3 i4 i5 i6 i7 incList: i8 i9 i10 i11 i12 toDoList: - comeFrom: i7
Phase 1 of the next iteration pops set i8 from the incomplete list, makes it the comeFrom set, and generates shift transitions from it:
i8x8. goto(B) from i3 [S -> b B . d, $end]* (d, x13) shift
A new transition item set is created and added to the to-do list:
x13. goto(d) from i8 [S -> b B d ., $end]* (-, -)
Set i8 is marked as completed and moved to the done list. The state of the algorithm is now:
doneList: i0 i1 i2 i3 i4 i5 i6 i7 i8 incList: i9 i10 i11 i12 toDoList: x13 comeFrom: i8
Phase 2 then pops item set x13 from the to-do list. Closure items (none) are added to it, and its reduction actions are marked. It cannot be merged with any existing set, so x13 is renamed to i13 and moved to the incomplete list:
i13x13. goto(d) from i8 [S -> b B d ., $end]* ($end, r4) reduce
The comeFrom set i8 is updated:
i8x8. goto(B) from i3 [S -> b B . d, $end]* (d, i13x13) updated
The state of the algorithm is now:
doneList: i0 i1 i2 i3 i4 i5 i6 i7 i8 incList: i9 i10 i11 i12 i13 toDoList: - comeFrom: i8
Phase 1 of the next iteration pops set i9 from the incomplete list. No shift transitions can be generated from it, so it is just marked as completed and moved to the done list:
i9x9. goto(c) from i3 complete [A -> c ., e ]* (e, r5) [B -> c ., d ]* (d, r6)
The to-do list is empty, so Phase 2 has no work to so in this iteration. The state of the algorithm is now:
doneList: i0 i1 i2 i3 i4 i5 i6 i7 i8 i9 incList: i10 i11 i12 i13 toDoList: - comeFrom: i9
Phase 1 of the next iteration pops set i10 from the incomplete list. No shift transitions can be generated from it, so it is just marked as completed and moved to the done list:
i10x10. goto(d) from i4 complete [S -> a A d ., $end]* ($end, r1)
The to-do list is empty, so Phase 2 has no work to so in this iteration. The state of the algorithm is now:
doneList: i0 i1 i2 i3 i4 i5 i6 i7 i8 i9 i10 incList: i11 i12 i13 toDoList: - comeFrom: i10
Phase 1 of the next iteration pops set i11 from the incomplete list. No shift transitions can be generated from it, so it is just marked as completed and moved to the done list:
i11x11. goto(e) from i5 complete [S -> a B e ., $end]* ($end, r2)
The to-do list is empty, so Phase 2 has no work to so in this iteration. The state of the algorithm is now:
doneList: i0 i1 i2 i3 i4 i5 i6 i7 i8 i9 i10 i11 incList: i12 i13 toDoList: - comeFrom: i11
Phase 1 of the next iteration pops set i12 from the incomplete list. No shift transitions can be generated from it, so it is just marked as completed and moved to the done list:
i12x12. goto(e) from i7 complete [S -> b A e ., $end]* ($end, r3)
The to-do list is empty, so Phase 2 has no work to so in this iteration. The state of the algorithm is now:
doneList: i0 i1 i2 i3 i4 i5 i6 i7 i8 i9 i10 i11 i12 incList: i13 toDoList: - comeFrom: i12
Phase 1 of the next iteration pops set i13 from the incomplete list. No shift transitions can be generated from it, so it is just marked as completed and moved to the done list:
i13x13. goto(d) from i8 complete [S -> b B d ., $end]* ($end, r4)
The state of the algorithm is now:
doneList: i0 i1 i2 i3 i4 i5 i6 i7 i8 i9 i10 i11 i12 i13 incList: - toDoList: - comeFrom: i13
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 i2 i3 i4 i5 i6 i7 i8 i9 i10 i11 i12 i13 incList: - toDoList: - comeFrom: i13
A total of 14 item sets (originally named x0 through x13) were created during the iterations of the algorithm. None of those sets were merged or discarded, leaving all 14 of them (renamed i0 through i13) as the final canonical LR(1) item sets produced by the algorithm.
i0x0. initial item set [$accept -> . S, $end]* (S, i1x1) [S -> . a A d, $end] (a, i2x2) [S -> . a B e, $end] (a, i2x2) [S -> . b A e, $end] (b, i3x3) [S -> . b B d, $end] (b, i3x3) i1x1. goto(S) from i0 [$accept -> S ., $end]* ($end, accept) i2x2. goto(a) from i0 [S -> a . A d, $end]* (A, i4x4) [S -> a . B e, $end]* (B, i5x5) [A -> . c, d ] (c, i6x6) [B -> . c, e ] (c, i6x6) i3x3. goto(b) from i0 [S -> b . A e, $end]* (A, i7x7) [S -> b . B d, $end]* (B, i8x8) [A -> . c, e ] (c, i9x9) [B -> . c, d ] (c, i9x9) i4x4. goto(A) from i2 [S -> a A . d, $end]* (d, i10x10) i5x5. goto(B) from i2 [S -> a B . e, $end]* (e, i11x11) i6x6. goto(c) from i2 => not merged with x9 [A -> c ., d ]* (d, r5) [B -> c ., e ]* (e, r6) i7x7. goto(A) from i3 [S -> b A . e, $end]* (e, i12x12) i8x8. goto(B) from i3 [S -> b B . d, $end]* (d, i13x13) i9x9. goto(c) from i3 => not merged with i6 [A -> c ., e ]* (e, r5) [B -> c ., d ]* (d, r6) i10x10. goto(d) from i4 [S -> a A d ., $end]* ($end, r1) i11x11. goto(e) from i5 [S -> a B e ., $end]* ($end, r2) i12x12. goto(e) from i7 [S -> b A e ., $end]* ($end, r3) i13x13. goto(d) from i8 [S -> b B d ., $end]* ($end, r4)
There is exactly one more item set (i9) for this LR(1) grammar (a total of 14 item sets) than would have been produced by an LALR(1) algorithm. But unlike the LALR item sets, which would have a reduce/reduce conflict in the item set created by merging sets i6 and i9, the two sets are not merged here, and the resulting sets are able to properly handle the LR(1) look-ahead context necessary to distinguish between the two reduction actions in those sets.
The following LR parser states are derived from the item sets:
s0. initial item set $accept : . S a shift 2 b shift 3 S goto 1 s1. $accept : S . (r0) $end accept s2. S : a . A d S : a . B e c shift 6 A goto 4 B goto 5 s3. S : b . A e S : b . B d c shift 9 A goto 7 B goto 8 s4. S : a A . d d shift 10 s5. S : a B . e e shift 11 s6. A : c . (r5) B : c . (r6) d reduce 5 e reduce 6 s7. S : b A . e e shift 12 s8. S : b B . d d shift 13 s9. A : c . (r5) B : c . (r6) d reduce 6 e reduce 5 s10. S : a A d . (r1) $end reduce 1 s11. S : a B e . (r2) $end reduce 2 s12. S : b A e . (r3) $end reduce 3 s13. S : b B d . (r4) $end reduce 4
The parser states are summarized in the following table, with the two unmerged states highlighted:
| State | Terminals | Nonterminals | Default | |||||||
|---|---|---|---|---|---|---|---|---|---|---|
| $end | a | b | c | d | e | S | A | B | ||
| 0 | - | s2 | s3 | - | - | - | s1 | - | - | - |
| 1 | acc | - | - | - | - | - | - | - | - | - |
| 2 | - | - | - | s6 | - | - | - | s4 | s5 | - |
| 3 | - | - | - | s9 | - | - | - | s7 | s8 | - |
| 4 | - | - | - | - | s10 | - | - | - | - | - |
| 5 | - | - | - | - | - | s11 | - | - | - | - |
| 6 | - | - | - | - | r5 | r6 | - | - | - | - |
| 7 | - | - | - | - | - | s12 | - | - | - | - |
| 8 | - | - | - | - | s13 | - | - | - | - | - |
| 9 | - | - | - | - | r6 | r5 | - | - | - | - |
| 10 | r1 | - | - | - | - | - | - | - | - | r1 |
| 11 | r2 | - | - | - | - | - | - | - | - | r2 |
| 12 | r3 | - | - | - | - | - | - | - | - | r3 |
| 13 | r4 | - | - | - | - | - | - | - | - | r4 |
The Honalee LR Algorithm can be found at:
honalee.html.
Previous example:
honalee_ex1.html,
Next example:
honalee_ex3.html.
Author's home page: david.tribble.com
Copyright ©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.