Revision: 1.1, 2006-01-01
Author: David R. Tribble
(david@tribble.com)
This document depicts the various stages of the
Honalee LR parser generator algorithm
as it generates the item sets for a particular sample grammar.
Grammar
The following is an LR(2) grammar.
%token num id
%token '(' ')'
%token '*'
%token '+'
%token ','
%token ';'
r0. $accept : Expr...
r1. Expr... : %empty
r2. Expr... : Expr... Expr ';' %prec ';'
r3. Parm : Expr
r4. Parm... : Parm
r5. Parm... : Parm... ',' Expr %prec ','
r6. Opt.Parm... : %empty
r7. Opt.Parm... : Parm...
r8. Term : num %prec num
r9. Term : id %prec id
r11. Term : '(' Expr ')' %prec ')'
r10. Term : id '(' Opt.Parm... ')' %prec ')'
r12. Factor : Term
r13. Factor : Factor '*' Term %prec '*'
r14. Expr : Factor
r16. Expr : Expr '+' Factor %prec '+'
r15. Expr : '+' Factor %prec '+'
The following First sets (with one-symbol look-ahead) are generated from the grammar:
First($accept) = { $epsilon, num, id, '(', '+' }
First(Expr...) = { $epsilon, num, id, '(', '+' }
First(Parm) = { num, id, '(', '+' }
First(Parm...) = { num, id, '(', '+' }
First(Opt.Parm...) = { $epsilon, num, id, '(', '+' }
First(Term) = { num, id, '(' }
First(Factor) = { num, id, '(' }
First(Expr) = { num, id, '(', '+' }
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:
toDoList: - empty doneList: - empty incList: - empty comeFrom: - null
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 shown with a name of xN.)
x0. initial item set [$accept -> . S, $end]* (-, -)
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 now looks like this:
toDoList: x0 doneList: - incList: - comeFrom: -
The main loop of the algorithm then begins. Phase 1 of the first iteration pops the first item set from the to-do list, which is set x0.
Phase 1 generates all of the closure items for set x0, which looks like:
x0. initial item set [$accept -> . S, $end]* (-, -) +REDO [S -> . b B d, 'b' ] (-, -)
There are no reduction items to mark in phase 1, and there are no other sets in the done list 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 (completed) list. As an item set x0 is moved to the incomplete list, it is renamed to i0, and it becomes an official item set of the grammar. At this point, the state of the algorithm is:
toDoList: - doneList: - incList: i0 comeFrom: -
Next, phase 2 of the first iteration examines the first set in the incomplete list, which is again item set i0. New transition item sets are generated from this set, each set being composed of new kernel items created by shifting groups of the same transition symbol in the generating items:
+INCOMPLETE
The final state of the algorithm is:
+REDO toDoList: - doneList: i0 i1 i2 i3 i4 i5 i6 i7 i8 i9 i10 i11 i12 i13 incList: - comeFrom: i8
The following item sets are generated as the final results of the algorithm:
- - - ---NEW---
i0. initial item set
[$accept -> . Expr..., $end]* (Expr..., i1)
[Expr... -> ., $end] ($end, r1)
[Expr... -> ., num ] (num, r1)
[Expr... -> ., id ] (id, r1)
[Expr... -> ., '(' ] ('(', r1)
[Expr... -> ., '+' ] ('+', r1)
[Expr... -> . Expr... Expr ';', $end] (Expr..., i1)
[Expr... -> . Expr... Expr ';', num ] (Expr..., i1)
[Expr... -> . Expr... Expr ';', id ] (Expr..., i1)
[Expr... -> . Expr... Expr ';', '(' ] (Expr..., i1)
[Expr... -> . Expr... Expr ';', '+' ] (Expr..., i1)
i1. goto(Expr...), from i1
[$accept -> Expr... ., $end]* ($end, accept)
[Expr... -> Expr... . Expr ';', $end]* (Expr, i2)
[Expr... -> Expr... . Expr ';', num ]* (Expr, i2)
[Expr... -> Expr... . Expr ';', id ]* (Expr, i2)
[Expr... -> Expr... . Expr ';', '(' ]* (Expr, i2)
[Expr... -> Expr... . Expr ';', '+' ]* (Expr, i2)
[Term -> . num, '*' ] (num, i3)
[Term -> . num, '+' ] (num, i3)
[Term -> . num, ';' ] (num, i3)
[Term -> . id, '+' ] (id, i4)
[Term -> . id, '*' ] (id, i4)
[Term -> . id, ';' ] (id, i4)
[Term -> . id '(' Opt.Parm... ')', '*' ] (id, i4)
[Term -> . id '(' Opt.Parm... ')', '+' ] (id, i4)
[Term -> . id '(' Opt.Parm... ')', ';' ] (id, i4)
[Term -> . '(' Expr ')', '*' ] ('(', i5)
[Term -> . '(' Expr ')', '+' ] ('(', i5)
[Term -> . '(' Expr ')', ';' ] ('(', i5)
[Factor -> . Term, '*' ] (Term, i6)
[Factor -> . Term, '+' ] (Term, i6)
[Factor -> . Term, ';' ] (Term, i6)
[Factor -> . Factor '*' Term, '*' ] (Factor, i7)
[Factor -> . Factor '*' Term, '+' ] (Factor, i7)
[Factor -> . Factor '*' Term, ';' ] (Factor, i7)
[Expr -> . Factor, '+' ] (Factor, i7)
[Expr -> . Factor, ';' ] (Factor, i7)
[Expr -> . '+' Factor, '+' ] ('+', i8)
[Expr -> . '+' Factor, ';' ] ('+', i8)
[Expr -> . Expr '+' Factor, '+' ] (Expr, i2)
[Expr -> . Expr '+' Factor, ';' ] (Expr, i2)
i2. goto(Expr), from i1,?
[Expr... -> Expr... Expr . ';', $end]* (';', i9)
[Expr... -> Expr... Expr . ';', num ]* (';', i9)
[Expr... -> Expr... Expr . ';', id ]* (';', i9)
[Expr... -> Expr... Expr . ';', '(' ]* (';', i9)
[Expr... -> Expr... Expr . ';', '+' ]* (';', i9)
[Expr -> Expr . '+' Factor, '+' ]* ('+', i10)
[Expr -> Expr . '+' Factor, ';' ]* ('+', i10)
i3. goto(num), from i1,?
[Term -> num ., ')' (num)]* (')', r8)
[Term -> num ., '*' (num)]* ('*', r8)
[Term -> num ., '+' (num)]* ('+', r8)
[Term -> num ., ',' (num)]* (',', r8)
[Term -> num ., ';' (num)]* (';', r8)
i4. goto(id), from i1,?
[Term -> id ., ')' (id)]* (')', r9)
[Term -> id ., '*' (id)]* ('*', r9)
[Term -> id ., '+' (id)]* ('+', r9)
[Term -> id ., ',' (id)]* (',', r9)
[Term -> id ., ';' (id)]* (';', r9)
[Term -> id . '(' Opt.Parm... ')', ')' ]* (-, -)
[Term -> id . '(' Opt.Parm... ')', '*' ]* ('(', i11)
[Term -> id . '(' Opt.Parm... ')', '+' ]* ('(', i11)
[Term -> id . '(' Opt.Parm... ')', ',' ]* (-, -)
[Term -> id . '(' Opt.Parm... ')', ';' ]* ('(', i11)
i5. goto('('), from i1,?
[Term -> '(' . Expr ')', ')' ]* (-, -)
[Term -> '(' . Expr ')', '*' ]* (Expr, i12)
[Term -> '(' . Expr ')', '+' ]* (Expr, i12)
[Term -> '(' . Expr ')', ',' ]* (-, -)
[Term -> '(' . Expr ')', ';' ]* (Expr, i12)
[Term -> . num, ')' ] (num, i3)
[Term -> . num, '*' ] (num, i3)
[Term -> . num, '+' ] (num, i3)
[Term -> . id, ')' ] (id, i4)
[Term -> . id, '*' ] (id, i4)
[Term -> . id, '+' ] (id, i4)
[Term -> . id '(' Opt.Parm... ')', ')' ] (id, i4)
[Term -> . id '(' Opt.Parm... ')', '*' ] (id, i4)
[Term -> . id '(' Opt.Parm... ')', '+' ] (id, i4)
[Term -> . '(' Expr ')', ')' ] ('(', i5)
[Term -> . '(' Expr ')', '*' ] ('(', i5)
[Term -> . '(' Expr ')', '+' ] ('(', i5)
[Factor -> . Term, ')' ] (Term, i6)
[Factor -> . Term, '*' ] (Term, i6)
[Factor -> . Term, '+' ] (Term, i6)
[Factor -> . Factor '*' Term, ')' ] (Factor, i7)
[Factor -> . Factor '*' Term, '*' ] (Factor, i7)
[Factor -> . Factor '*' Term, '+' ] (Factor, i7)
[Expr -> . Factor, ')' ] (Factor, i7)
[Expr -> . Factor, '+' ] (Factor, i7)
[Expr -> . '+' Factor, ')' ] ('+', i8)
[Expr -> . '+' Factor, '+' ] ('+', i8)
[Expr -> . Expr '+' Factor, ')' ] (Expr, i12)
[Expr -> . Expr '+' Factor, '+' ] (Expr, i12)
i6. goto(Term), from i1,?
[Factor -> Term ., ')' ]* (')', r12)
[Factor -> Term ., '*' ]* ('*', r12)
[Factor -> Term ., '+' ]* ('+', r12)
[Factor -> Term ., ',' ]* (',', r12)
[Factor -> Term ., ';' ]* (';', r12)
i7. goto(Factor), from i1,?
[Factor -> Factor . '*' Term, ')' ]* ('*', i13)
[Factor -> Factor . '*' Term, '*' ]* ('*', i13)
[Factor -> Factor . '*' Term, '+' ]* ('*', i13)
[Factor -> Factor . '*' Term, ',' ]* (-, -)
[Factor -> Factor . '*' Term, ';' ]* ('*', i13)
[Expr -> Factor ., ')' ]* (')', r14)
[Expr -> Factor ., '+' ]* ('+', r14)
[Expr -> Factor ., ',' ]* (',', r14)
[Expr -> Factor ., ';' ]* (';', r14)
i8. goto('+'), from i1,?
[Expr -> '+' . Factor, ')' ]* (Factor, i14)
[Expr -> '+' . Factor, '+' ]* (Factor, i14)
[Expr -> '+' . Factor, ',' ]* (-, -)
[Expr -> '+' . Factor, ';' ]* (Factor, i14)
[Term -> . num, ')' ] (num, i3)
[Term -> . num, '*' ] (num, i3)
[Term -> . num, '+' ] (num, i3)
[Term -> . num, ',' ] (-, -)
[Term -> . num, ';' ] (num, i3)
[Term -> . id, ')' ] (id, i4)
[Term -> . id, '*' ] (id, i4)
[Term -> . id, '+' ] (id, i4)
[Term -> . id, ',' ] (-, -)
[Term -> . id, ';' ] (id, i4)
[Term -> . id '(' Opt.Parm... ')', ')' ] (id, i4)
[Term -> . id '(' Opt.Parm... ')', '*' ] (id, i4)
[Term -> . id '(' Opt.Parm... ')', '+' ] (id, i4)
[Term -> . id '(' Opt.Parm... ')', ',' ] (-, -)
[Term -> . id '(' Opt.Parm... ')', ';' ] (id, i4)
[Term -> . '(' Expr ')', ')' ] ('(', i5)
[Term -> . '(' Expr ')', '*' ] ('(', i5)
[Term -> . '(' Expr ')', '+' ] ('(', i5)
[Term -> . '(' Expr ')', ',' ] (-, -)
[Term -> . '(' Expr ')', ';' ] ('(', i5)
[Factor -> . Term, ')' ] (Term, i6)
[Factor -> . Term, '*' ] (Term, i6)
[Factor -> . Term, '+' ] (Term, i6)
[Factor -> . Term, ',' ] (-, -)
[Factor -> . Term, ';' ] (Term, i6)
[Factor -> . Factor '*' Term, ')' ] (Factor, i14)
[Factor -> . Factor '*' Term, '*' ] (Factor, i14)
[Factor -> . Factor '*' Term, '+' ] (Factor, i14)
[Factor -> . Factor '*' Term, ',' ] (-, -)
[Factor -> . Factor '*' Term, ';' ] (Factor, i14)
i9. goto(';'), from i2,?
[Expr... -> Expr... Expr ';' ., $end (';')]* ($end, r2)
[Expr... -> Expr... Expr ';' ., num (';')]* (num, r2)
[Expr... -> Expr... Expr ';' ., id (';')]* (id, r2)
[Expr... -> Expr... Expr ';' ., '(' (';')]* ('(', r2)
[Expr... -> Expr... Expr ';' ., '+' (';')]* ('+', r2)
i10. goto('+'), from i2,?
[Expr -> Expr '+' . Factor, ')' ]* (-, -)
[Expr -> Expr '+' . Factor, '+' ]* (Factor, i15)
[Expr -> Expr '+' . Factor, ',' ]* (-, -)
[Expr -> Expr '+' . Factor, ';' ]* (Factor, i15)
[Term -> . num, ')' ] (-, -)
[Term -> . num, '*' ] (num, i3)
[Term -> . num, '+' ] (num, i3)
[Term -> . num, ',' ] (-, -)
[Term -> . num, ';' ] (num, i3)
[Term -> . id, ')' ] (-, -)
[Term -> . id, '*' ] (id, i4)
[Term -> . id, '+' ] (id, i4)
[Term -> . id, ',' ] (-, -)
[Term -> . id, ';' ] (id, i4)
[Term -> . id '(' Opt.Parm... ')', ')' ] (-, -)
[Term -> . id '(' Opt.Parm... ')', '*' ] (id, i4)
[Term -> . id '(' Opt.Parm... ')', '+' ] (id, i4)
[Term -> . id '(' Opt.Parm... ')', ',' ] (-, -)
[Term -> . id '(' Opt.Parm... ')', ';' ] (id, i4)
[Term -> . '(' Expr ')', ')' ] (-, -)
[Term -> . '(' Expr ')', '*' ] ('(', i5)
[Term -> . '(' Expr ')', '+' ] ('(', i5)
[Term -> . '(' Expr ')', ',' ] (-, -)
[Term -> . '(' Expr ')', ';' ] ('(', i5)
[Factor -> . Term, ')' ] (-, -)
[Factor -> . Term, '*' ] (Term, i6)
[Factor -> . Term, '+' ] (Term, i6)
[Factor -> . Term, ',' ] (-, -)
[Factor -> . Term, ';' ] (Term, i6)
[Factor -> . Factor '*' Term, ')' ] (-, -)
[Factor -> . Factor '*' Term, '*' ] (Factor, i15)
[Factor -> . Factor '*' Term, '+' ] (Factor, i15)
[Factor -> . Factor '*' Term, ',' ] (-, -)
[Factor -> . Factor '*' Term, ';' ] (Factor, i15)
i11. goto('('), from ?
[Term -> id '(' . Opt.Parm... ')', '*' ]* (Opt.Parm..., i16)
[Term -> id '(' . Opt.Parm... ')', '+' ]* (Opt.Parm..., i16)
[Term -> id '(' . Opt.Parm... ')', ';' ]* (Opt.Parm..., i16)
[Parm -> . Expr, ')' ] (Expr, i17)
[Parm -> . Expr, ',' ] (Expr, i17)
[Parm... -> . Parm, ')' ] (Parm, i18)
[Parm... -> . Parm, ',' ] (Parm, i18)
[Parm... -> . Parm... ',' Expr, ')' ] (Parm..., i19)
[Parm... -> . Parm... ',' Expr, ',' ] (Parm..., i19)
[Opt.Parm... -> ., ')' ] (')', r6)
[Opt.Parm... -> . Parm..., ')' ] (Parm..., i19)
[Term -> . num, ')' ] (num, i3)
[Term -> . num, '*' ] (num, i3)
[Term -> . num, '+' ] (num, i3)
[Term -> . num, ',' ] (num, i3)
[Term -> . id, ')' ] (id, i4)
[Term -> . id, '*' ] (id, i4)
[Term -> . id, '+' ] (id, i4)
[Term -> . id, ',' ] (id, i4)
[Term -> . id '(' Opt.Parm... ')', ')' ] (id, i4)
[Term -> . id '(' Opt.Parm... ')', '*' ] (id, i4)
[Term -> . id '(' Opt.Parm... ')', '+' ] (id, i4)
[Term -> . id '(' Opt.Parm... ')', ',' ] (id, i4)
[Term -> . '(' Expr ')', ')' ] ('(', i5)
[Term -> . '(' Expr ')', '*' ] ('(', i5)
[Term -> . '(' Expr ')', '+' ] ('(', i5)
[Term -> . '(' Expr ')', ',' ] ('(', i5)
[Factor -> . Term, ')' ] (Term, i6)
[Factor -> . Term, '*' ] (Term, i6)
[Factor -> . Term, '+' ] (Term, i6)
[Factor -> . Term, ',' ] (Term, i6)
[Factor -> . Factor '*' Term, ')' ] (Factor, i7)
[Factor -> . Factor '*' Term, '*' ] (Factor, i7)
[Factor -> . Factor '*' Term, '+' ] (Factor, i7)
[Factor -> . Factor '*' Term, ',' ] (Factor, i7)
[Expr -> . Factor, ')' ] (Factor, i7)
[Expr -> . Factor, '+' ] (Factor, i7)
[Expr -> . Factor, ',' ] (Factor, i7)
[Expr -> . '+' Factor, ')' ] ('+', i8)
[Expr -> . '+' Factor, '+' ] ('+', i8)
[Expr -> . '+' Factor, ',' ] ('+', i8)
[Expr -> . Expr '+' Factor, ')' ] (Expr, i17)
[Expr -> . Expr '+' Factor, '+' ] (Expr, i17)
[Expr -> . Expr '+' Factor, ',' ] (Expr, i17)
i12. goto(Expr), from ?
[Term -> '(' Expr . ')', '*' ]* (')', i20)
[Term -> '(' Expr . ')', '+' ]* (')', i20)
[Term -> '(' Expr . ')', ';' ]* (')', i20)
[Expr -> Expr . '+' Factor, ')' ]* ('+', i10)
[Expr -> Expr . '+' Factor, '+' ]* ('+', i10)
i13. goto('*'), from ?
[Factor -> Factor '*' . Term, ')' ]* (Term, i21)
[Factor -> Factor '*' . Term, '*' ]* (Term, i21)
[Factor -> Factor '*' . Term, '+' ]* (Term, i21)
[Factor -> Factor '*' . Term, ';' ]* (Term, i21)
[Term -> . num, ')' ] (num, i3)
[Term -> . num, '*' ] (num, i3)
[Term -> . num, '+' ] (num, i3)
[Term -> . num, ';' ] (num, i3)
[Term -> . id, ')' ] (id, i4)
[Term -> . id, '*' ] (id, i4)
[Term -> . id, '+' ] (id, i4)
[Term -> . id, ';' ] (id, i4)
[Term -> . id '(' Opt.Parm... ')', ')' ] (id, i4)
[Term -> . id '(' Opt.Parm... ')', '*' ] (id, i4)
[Term -> . id '(' Opt.Parm... ')', '+' ] (id, i4)
[Term -> . id '(' Opt.Parm... ')', ';' ] (id, i4)
[Term -> . '(' Expr ')', ')' ] ('(', i5)
[Term -> . '(' Expr ')', '*' ] ('(', i5)
[Term -> . '(' Expr ')', '+' ] ('(', i5)
[Term -> . '(' Expr ')', ';' ] ('(', i5)
i14. goto(Factor), from ?
[Expr -> '+' Factor ., ')' ('+')]* (')', r15)
[Expr -> '+' Factor ., '+' ('+')]* ('+', r15)
[Expr -> '+' Factor ., ';' ('+')]* (';', r15)
[Factor -> Factor . '*' Term, ')' ]* ('*', i13)
[Factor -> Factor . '*' Term, '*' ]* ('*', i13)
[Factor -> Factor . '*' Term, '+' ]* ('*', i13)
[Factor -> Factor . '*' Term, ';' ]* ('*', i13)
i15. goto(Factor), from ?
[Expr -> Expr '+' Factor ., '+' ('+')]* ('+', r16)
[Expr -> Expr '+' Factor ., ';' ('+')]* (';', r16)
[Factor -> Factor . '*' Term, '*' ]* ('*', i13)
[Factor -> Factor . '*' Term, '+' ]* ('*', i13)
[Factor -> Factor . '*' Term, ';' ]* ('*', i13)
i16. goto(Opt.Parm...), from ?
[Term -> id '(' Opt.Parm... . ')', '*' ]* (')', i22)
[Term -> id '(' Opt.Parm... . ')', '+' ]* (')', i22)
[Term -> id '(' Opt.Parm... . ')', ';' ]* (')', i22)
i17. goto(Expr), from ?
[Parm -> Expr ., ')' ]* (')', r3)
[Parm -> Expr ., ',' ]* (',', r3)
[Expr -> Expr . '+' Factor, ')' ]* ('+', i10)
[Expr -> Expr . '+' Factor, '+' ]* ('+', i10)
[Expr -> Expr . '+' Factor, ',' ]* ('+', i10)
i18. goto(Parm), from ?
[Parm... -> Parm ., ')' ]* (')', r4)
[Parm... -> Parm ., ',' ]* (',', r4)
i19. goto(Parm...), from ?
[Parm... -> Parm... . ',' Expr, ')' ]* (',', i23)
[Parm... -> Parm... . ',' Expr, ',' ]* (',', i23)
[Opt.Parm... -> Parm... ., ')' ]* (')', r7)
i20. goto(')'), from ?
[Term -> '(' Expr ')' ., '*' (')')]* ('*', r11)
[Term -> '(' Expr ')' ., '+' (')')]* ('+', r11)
[Term -> '(' Expr ')' ., ';' (')')]* (';', r11)
i21. goto(Term), from ?
[Factor -> Factor '*' Term ., ')' ('*')]* (')', r13)
[Factor -> Factor '*' Term ., '*' ('*')]* ('*', r13)
[Factor -> Factor '*' Term ., '+' ('*')]* ('+', r13)
[Factor -> Factor '*' Term ., ';' ('*')]* (';', r13)
i22. goto(')'), from ?
[Term -> id '(' Opt.Parm... ')' ., '*' (')')]* ('*', r10)
[Term -> id '(' Opt.Parm... ')' ., '+' (')')]* ('+', r10)
[Term -> id '(' Opt.Parm... ')' ., ';' (')')]* (';', r10)
i23. goto(','), from ?
[Parm... -> Parm... ',' . Expr, ')' ]* (Expr, i24)
[Parm... -> Parm... ',' . Expr, ',' ]* (Expr, i24)
[Term -> . num, ')' ] (num, i3)
[Term -> . num, '*' ] (num, i3)
[Term -> . num, '+' ] (num, i3)
[Term -> . num, ',' ] (num, i3)
[Term -> . id, ')' ] (id, i4)
[Term -> . id, '*' ] (id, i4)
[Term -> . id, '+' ] (id, i4)
[Term -> . id, ',' ] (id, i4)
[Term -> . id '(' Opt.Parm... ')', ')' ] (id, i4)
[Term -> . id '(' Opt.Parm... ')', '*' ] (id, i4)
[Term -> . id '(' Opt.Parm... ')', '+' ] (id, i4)
[Term -> . id '(' Opt.Parm... ')', ',' ] (id, i4)
[Term -> . '(' Expr ')', ')' ] ('(', i5)
[Term -> . '(' Expr ')', '*' ] ('(', i5)
[Term -> . '(' Expr ')', '+' ] ('(', i5)
[Term -> . '(' Expr ')', ',' ] ('(', i5)
[Factor -> . Term, ')' ] (Term, i6)
[Factor -> . Term, '*' ] (Term, i6)
[Factor -> . Term, '+' ] (Term, i6)
[Factor -> . Term, ',' ] (Term, i6)
[Factor -> . Factor '*' Term, ')' ] (Factor, i7)
[Factor -> . Factor '*' Term, '*' ] (Factor, i7)
[Factor -> . Factor '*' Term, '+' ] (Factor, i7)
[Factor -> . Factor '*' Term, ',' ] (Factor, i7)
[Expr -> . Factor, ')' ] (Factor, i7)
[Expr -> . Factor, '+' ] (Factor, i7)
[Expr -> . Factor, ',' ] (Factor, i7)
[Expr -> . '+' Factor, ')' ] ('+', i8)
[Expr -> . '+' Factor, '+' ] ('+', i8)
[Expr -> . '+' Factor, ',' ] ('+', i8)
[Expr -> . Expr '+' Factor, ')' ] (Expr, i24)
[Expr -> . Expr '+' Factor, '+' ] (Expr, i24)
[Expr -> . Expr '+' Factor, ',' ] (Expr, i24)
i24. goto(Expr), from ?
[Parm... -> Parm... ',' Expr ., ')' (',')]* (')', r5)
[Parm... -> Parm... ',' Expr ., ',' (',')]* (',', r5)
[Expr -> Expr . '+' Factor, ')' ]* ('+', i10)
[Expr -> Expr . '+' Factor, '+' ]* ('+', i10)
[Expr -> Expr . '+' Factor, ',' ]* ('+', i10)
Summary:
Terminal/token symbols .: 8 (0 unused)
Nonterminal/LHS symbols : 7 (0 unused)
Grammar rules ..........: 16 (0 unused)
Parser states ..........: 25
Duplicated states ......: 20
Merged states ..........: 14
Unmerged states ........: 0
State kernel items .....: 245
State closure items ....: 488
Item sets ..............: 25; 28 reuses; 6 max cached
Kernel items ...........: 115; 100 reuses; 30 max cached
Items ..................: 696; 480 reuses; 25 max cached
State transitions ......: 75
Defaulted transitions ..: 52
Shift/reduce conflicts .: 0
Reduce/reduce conflicts : 0
- - - ---OLD---
|o0. initial set
| [$accept -> . Expr..., $end]* (Expr..., o1)
| [Expr... -> ., $end] ($end, r1)
| [Expr... -> ., num] (num, r1)
| [Expr... -> ., id ] (id, r1)
| [Expr... -> ., '('] ('(', r1)
| [Expr... -> ., '+'] ('+', r1)
| [Expr... -> . Expr... Expr ';', $end] (Expr..., o1)
|
|o1. goto(Expr...) from o0
| [$accept -> Expr... ., $end]* ($end, accept)
| [Expr... -> Expr... . Expr ';', $end]* (Expr, o8)
| [Expr... -> Expr... . Expr ';', num]* (Expr, o8)
| [Expr... -> Expr... . Expr ';', id ]* (Expr, o8)
| [Expr... -> Expr... . Expr ';', '(']* (Expr, o8)
| [Expr... -> Expr... . Expr ';', '+']* (Expr, o8)
| [Term -> . num, '*'] (num, o9)
| [Term -> . id, '*'] (id, o10)
| [Term -> . '(' Expr ')', '*'] ('(', o2)
| [Factor -> . Term, '*'] (Term, o11)
| [Factor -> . Factor '*' Term, '*'] (Factor, o12)
| [Expr -> . '+' Factor, '+'] ('+', o3)
| [Expr -> . Expr '+' Factor, '+'] (Expr, o8)
|
|o2. goto('(') from o1,o2,o3,o4,o5,o6,o7
| [Term -> '(' . Expr ')', ')']* (-, -)
| [Term -> '(' . Expr ')', '*']* (Expr, o14)
| [Term -> '(' . Expr ')', '+']* (Expr, o14)
| [Term -> '(' . Expr ')', ',']* (-, -)
| [Term -> '(' . Expr ')', ';']* (Expr, o14)
| [Term -> . num, ')'] (num, o9)
| [Term -> . id, ')'] (id, o10)
| [Term -> . '(' Expr ')', ')'] ('(', o2)
| [Factor -> . Term, ')'] (Term, o11)
| [Factor -> . Factor '*' Term, ')'] (Factor, o12)
| [Expr -> . '+' Factor, ')'] ('+', o3)
| [Expr -> . Expr '+' Factor, ')'] (Expr, o14)
|
|o3. goto('+') from o1,o2,o5,o7
| [Expr -> '+' . Factor, ')']* (Factor, o15)
| [Expr -> '+' . Factor, '+']* (Factor, o15)
| [Expr -> '+' . Factor, ',']* (-, -)
| [Expr -> '+' . Factor, ';']* (Factor, o15)
| [Term -> . num, ')'] (num, o9)
| [Term -> . id, ')'] (id, o10)
| [Term -> . '(' Expr ')', ')'] ('(', o2)
| [Factor -> . Term, ')'] (Term, o11)
| [Factor -> . Factor '*' Term, ')'] (Factor, o15)
|
|o4. goto('+') from o8,o14,o18,o24
| [Expr -> Expr '+' . Factor, ')']* (-, -)
| [Expr -> Expr '+' . Factor, '+']* (Factor, o16)
| [Expr -> Expr '+' . Factor, ',']* (-, -)
| [Expr -> Expr '+' . Factor, ';']* (Factor, o16)
| [Term -> . num, '*'] (num, o9)
| [Term -> . id, '*'] (id, o10)
| [Term -> . '(' Expr ')', '*'] ('(', o2)
| [Factor -> . Term, '*'] (Term, o11)
| [Factor -> . Factor '*' Term, '*'] (Factor, o16)
|
|o5. goto('(') from o10
| [Term -> id '(' . Opt.Parm... ')', '*']* (Opt.Parm..., o17)
| [Term -> id '(' . Opt.Parm... ')', '+']* (Opt.Parm..., o17)
| [Term -> id '(' . Opt.Parm... ')', ';']* (Opt.Parm..., o17)
| [Parm -> . Expr, ')'] (Expr, o18)
| [Parm... -> . Parm, ')'] (Parm, o19)
| [Parm... -> . Parm... ',' Expr, ')'] (Parm..., o20)
| [Opt.Parm... -> ., ')'] (')', r6)
| [Term -> . num, ')'] (num, o9)
| [Term -> . id, ')'] (id, o10)
| [Term -> . '(' Expr ')', ')'] ('(', o2)
| [Factor -> . Term, ')'] (Term, o11)
| [Factor -> . Factor '*' Term, ')'] (Factor, o12)
| [Expr -> . '+' Factor, ')'] ('+', o3)
|
|o6. goto('*') from o12,o15,o16
| [Factor -> Factor '*' . Term, ')']* (Term, o22)
| [Factor -> Factor '*' . Term, '*']* (Term, o22)
| [Factor -> Factor '*' . Term, '+']* (Term, o22)
| [Factor -> Factor '*' . Term, ';']* (Term, o22)
| [Term -> . num, ')'] (num, o9)
| [Term -> . id, ')'] (id, o10)
| [Term -> . '(' Expr ')', ')'] ('(', o2)
|
|o7. goto(',') from o20
| [Parm... -> Parm... ',' . Expr, ')']* (Expr, o24)
| [Parm... -> Parm... ',' . Expr, ',']* (Expr, o24)
| [Term -> . num, ')'] (num, o9)
| [Term -> . id, ')'] (id, o10)
| [Term -> . '(' Expr ')', ')'] ('(', o2)
| [Factor -> . Term, ')'] (Term, o11)
| [Factor -> . Factor '*' Term, ')'] (Factor, o12)
| [Expr -> . '+' Factor, ')'] ('+', o3)
| [Expr -> . Expr '+' Factor, ')'] (Expr, o24)
|
|o8. goto(Expr) from o1
| [Expr... -> Expr... Expr . ';', $end]* (';', o13)
| [Expr... -> Expr... Expr . ';', num]* (';', o13)
| [Expr... -> Expr... Expr . ';', id ]* (';', o13)
| [Expr... -> Expr... Expr . ';', '(']* (';', o13)
| [Expr... -> Expr... Expr . ';', '+']* (';', o13)
| [Expr -> Expr . '+' Factor, '+']* ('+', o4)
| [Expr -> Expr . '+' Factor, ';']* ('+', o4)
|
|o9. goto(num) from o1,o2,o3,o4,o5,o6,o7
| [Term -> num ., ')' (num)]* (')', r8)
| [Term -> num ., '*' (num)]* ('*', r8)
| [Term -> num ., '+' (num)]* ('+', r8)
| [Term -> num ., ',' (num)]* (',', r8)
| [Term -> num ., ';' (num)]* (';', r8)
|
|o10. goto(id) from o1,o2,o3,o4,o5,o6,o7
| [Term -> id ., ')' (id)]* (')', r9)
| [Term -> id ., '*' (id)]* ('*', r9)
| [Term -> id ., '+' (id)]* ('+', r9)
| [Term -> id ., ',' (id)]* (',', r9)
| [Term -> id ., ';' (id)]* (';', r9)
| [Term -> id . '(' Opt.Parm... ')', ')' ]* (-, -)
| [Term -> id . '(' Opt.Parm... ')', '*' ]* ('(', o5)
| [Term -> id . '(' Opt.Parm... ')', '+' ]* ('(', o5)
| [Term -> id . '(' Opt.Parm... ')', ',' ]* (-, -)
| [Term -> id . '(' Opt.Parm... ')', ';' ]* ('(', o5)
|
|o11. goto(Term) from o1,o2,o3,o4,o5,o7
| [Factor -> Term ., ')']* (')', r12)
| [Factor -> Term ., '*']* ('*', r12)
| [Factor -> Term ., '+']* ('+', r12)
| [Factor -> Term ., ',']* (',', r12)
| [Factor -> Term ., ';']* (';', r12)
|
|o12. goto(Factor) from o1,o2,o5,o7
| [Factor -> Factor . '*' Term, ')']* ('*', o6)
| [Factor -> Factor . '*' Term, '*']* ('*', o6)
| [Factor -> Factor . '*' Term, '+']* ('*', o6)
| [Factor -> Factor . '*' Term, ',']* (-, -)
| [Factor -> Factor . '*' Term, ';']* ('*', o6)
| [Expr -> Factor ., ')']* (')', r14)
| [Expr -> Factor ., '+']* ('+', r14)
| [Expr -> Factor ., ',']* (',', r14)
| [Expr -> Factor ., ';']* (';', r14)
|
|o13. goto(';') from o8
| [Expr... -> Expr... Expr ';' ., $end (';')]* ($end, r2)
| [Expr... -> Expr... Expr ';' ., num (';') ]* (num, r2)
| [Expr... -> Expr... Expr ';' ., id (';') ]* (id, r2)
| [Expr... -> Expr... Expr ';' ., '(' (';') ]* ('(', r2)
| [Expr... -> Expr... Expr ';' ., '+' (';') ]* ('+', r2)
|
|o14. goto(Expr) from o2
| [Term -> '(' Expr . ')', '*']* (')', o21)
| [Term -> '(' Expr . ')', '+']* (')', o21)
| [Term -> '(' Expr . ')', ';']* (')', o21)
| [Expr -> Expr . '+' Factor, ')']* ('+', o4)
| [Expr -> Expr . '+' Factor, '+']* ('+', o4)
|
|o15. goto(Factor) from o3
| [Expr -> '+' Factor ., ')' ('+')]* (')', r15)
| [Expr -> '+' Factor ., '+' ('+')]* ('+', r15)
| [Expr -> '+' Factor ., ';' ('+')]* (';', r15)
| [Factor -> Factor . '*' Term, ')' ]* ('*', o6)
| [Factor -> Factor . '*' Term, '*' ]* ('*', o6)
| [Factor -> Factor . '*' Term, '+' ]* ('*', o6)
| [Factor -> Factor . '*' Term, ';' ]* ('*', o6)
|
|o16. goto(Factor) from o4
| [Expr -> Expr '+' Factor ., '+' ('+')]* ('+', r16)
| [Expr -> Expr '+' Factor ., ';' ('+')]* (';', r16)
| [Factor -> Factor . '*' Term, '*' ]* ('*', o6)
| [Factor -> Factor . '*' Term, '+' ]* ('*', o6)
| [Factor -> Factor . '*' Term, ';' ]* ('*', o6)
|
|o17. goto(Opt.Parm...) from o5
| [Term -> id '(' Opt.Parm... . ')', '*']* (')', o23)
| [Term -> id '(' Opt.Parm... . ')', '+']* (')', o23)
| [Term -> id '(' Opt.Parm... . ')', ';']* (')', o23)
|
|o18. goto(Expr) from o5
| [Parm -> Expr ., ')']* (')', r3)
| [Parm -> Expr ., ',']* (',', r3)
| [Expr -> Expr . '+' Factor, ')']* ('+', o4)
| [Expr -> Expr . '+' Factor, '+']* ('+', o4)
| [Expr -> Expr . '+' Factor, ',']* ('+', o4)
|
|o19. goto(Parm) from o5
| [Parm... -> Parm ., ')']* (')', r4)
| [Parm... -> Parm ., ',']* (',', r4)
|
|o20. goto(Parm...) from o5
| [Parm... -> Parm... . ',' Expr, ')']* (',', o7)
| [Parm... -> Parm... . ',' Expr, ',']* (',', o7)
| [Opt.Parm... -> Parm... ., ')']* (')', r7)
|
|o21. goto(')') from o14
| [Term -> '(' Expr ')' ., '*' (')')]* ('*', r11)
| [Term -> '(' Expr ')' ., '+' (')')]* ('+', r11)
| [Term -> '(' Expr ')' ., ';' (')')]* (';', r11)
|
|o22. goto(Term) from o6
| [Factor -> Factor '*' Term ., ')' ('*')]* (')', r13)
| [Factor -> Factor '*' Term ., '*' ('*')]* ('*', r13)
| [Factor -> Factor '*' Term ., '+' ('*')]* ('+', r13)
| [Factor -> Factor '*' Term ., ';' ('*')]* (';', r13)
|
|o23. goto(')') from o17
| [Term -> id '(' Opt.Parm... ')' ., '*' (')')]* ('*', r10)
| [Term -> id '(' Opt.Parm... ')' ., '+' (')')]* ('+', r10)
| [Term -> id '(' Opt.Parm... ')' ., ';' (')')]* (';', r10)
|
|o24. goto(Expr) from o7
| [Parm... -> Parm... ',' Expr ., ')' (',')]* (')', r5)
| [Parm... -> Parm... ',' Expr ., ',' (',')]* (',', r5)
| [Expr -> Expr . '+' Factor, ')' ]* ('+', o4)
| [Expr -> Expr . '+' Factor, '+' ]* ('+', o4)
| [Expr -> Expr . '+' Factor, ',' ]* ('+', o4)
+REDO 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 (13 sets). 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, and thus are able to properly handle the LR(1) look-ahead context necessary to distinguish between the two reductions of those sets.
state 0
$accept : . Expr...
Expr... : . (r1)
$any reduce 1
Expr... goto 1
state 1
$accept : Expr... . (accept)
Expr... : Expr... . Expr ';'
$end accept
num shift 3
id shift 4
'(' shift 5
'+' shift 8
$other error
Expr goto 2
Term goto 6
Factor goto 7
state 2
Expr... : Expr... Expr . ';'
Expr : Expr . '+' Factor
'+' shift 10
';' shift 9
$other error
state 3
Term : num . (r8)
$any reduce 8
state 4
Term : id . (r9)
Term : id . '(' Opt.Parm... ')'
'(' shift 11
$other reduce 9
state 5
Term : '(' . Expr ')'
num shift 3
id shift 4
'(' shift 5
'+' shift 8
$other error
Expr goto 12
Term goto 6
Factor goto 7
state 6
Factor : Term . (r12)
$any reduce 12
state 7
Factor : Factor . '*' Term
Expr : Factor . (r14)
'*' shift 13
$other reduce 14
state 8
Expr : '+' . Factor
num shift 3
id shift 4
'(' shift 5
$other error
Term goto 6
Factor goto 14
state 9
Expr... : Expr... Expr ';' . (r2)
$any reduce 2
state 10
Expr : Expr '+' . Factor
num shift 3
id shift 4
'(' shift 5
$other error
Term goto 6
Factor goto 15
state 11
Term : id '(' . Opt.Parm... ')'
Opt.Parm... : . (r6)
num shift 3
id shift 4
'(' shift 5
'+' shift 8
$other reduce 6
Expr goto 17
Parm goto 18
Parm... goto 19
Opt.Parm... goto 16
Term goto 6
Factor goto 7
state 12
Term : '(' Expr . ')'
Expr : Expr . '+' Factor
')' shift 20
'+' shift 10
$other error
state 13
Factor : Factor '*' . Term
num shift 3
id shift 4
'(' shift 5
$other error
Term goto 21
state 14
Expr : '+' Factor . (r15)
Factor : Factor . '*' Term
'*' shift 13
$other reduce 15
state 15
Expr : Expr '+' Factor . (r16)
Factor : Factor . '*' Term
'*' shift 13
$other reduce 16
state 16
Term : id '(' Opt.Parm... . ')'
')' shift 22
$other error
state 17
Parm : Expr . (r3)
Expr : Expr . '+' Factor
'+' shift 10
$other reduce 3
state 18
Parm... : Parm . (r4)
$any reduce 4
state 19
Parm... : Parm... . ',' Expr
Opt.Parm... : Parm... . (r7)
',' shift 23
$other reduce 7
state 20
Term : '(' Expr ')' . (r11)
$any reduce 11
state 21
Factor : Factor '*' Term . (r13)
$any reduce 13
state 22
Term : id '(' Opt.Parm... ')' . (r10)
$any reduce 10
state 23
Parm... : Parm... ',' . Expr
num shift 3
id shift 4
'(' shift 5
'+' shift 8
$other error
Expr goto 24
Term goto 6
Factor goto 7
state 24
Parm... : Parm... ',' Expr . (r5)
Expr : Expr . '+' Factor
'+' shift 10
$other reduce 5
The Honalee LR Algorithm can be found at:
honalee.html.
Previous example:
honalee_ex2.html,
Next example:
honalee_ex4.html.
Author's home page: david.tribble.com
Copyright ©2006 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.