Honalee LR Parsing Algorithm
LR(2) Example

Revision: 1.0, 2006-01-11
Author: David R. Tribble (david@tribble.com)

Grammar, LR(2)

%token	a
%token	s
%token	t
%token	x

r0. $accept : S
r1. S : A x s
r2. S : B x t
r3. A : a
r4. B : a

First Sets

First₂(S) = { a x }
First₂(A) = { a - }
First₂(B) = { a - }

Algorithm Execution

Initial Set-up

x0. initial item set
  [$accept -> . S,      $end -]*  (-, -)

doneList: -
incList:  -
toDoList: x0
comeFrom: -

Iteration 1

i0 x0. initial item set
  [$accept -> . S,      $end -]*  (-, -)
  [S       -> . A x s,  $end -]   (-, -)  closure
  [S       -> . B x t,  $end -]   (-, -)  closure
  [A       -> . a,      x s   ]   (-, -)  closure
  [B       -> . a,      x t   ]   (-, -)  closure

doneList: -
incList:  i0
toDoList: -
comeFrom: -

Iteration 2, Phase 1

i0 x0. initial item set  complete
  [$accept -> . S,      $end -]*  (S, x1)  shift
  [S       -> . A x s,  $end -]   (A, x2)  shift
  [S       -> . B x t,  $end -]   (B, x3)  shift
  [A       -> . a,      x s   ]   (a, x4)  shift
  [B       -> . a,      x t   ]   (a, x4)  shift

x1. goto(S) from i0
  [$accept -> S .,      $end -]*  (-, -)

x2. goto(A) from i0
  [S       -> A . x s,  $end -]*  (-, -)

x3. goto(B) from i0
  [S       -> B . x t,  $end -]*  (-, -)

x4. goto(a) from i0
  [A       -> a .,      x s   ]*  (-, -)
  [B       -> a .,      x t   ]*  (-, -)

doneList: i0
incList:  -
toDoList: x1 x2 x3 x4
comeFrom: i0

Iteration 2, Phase 2

i1 x1. goto(S) from i0  complete
  [$accept -> S .,      $end -]*  ($end -, r0)  reduce

i2 x2. goto(A) from i0
  [S       -> A . x s,  $end -]*  (-, -)

i3 x3. goto(B) from i0
  [S       -> B . x t,  $end -]*  (-, -)

i4 x4. goto(a) from i0
  [A       -> a .,      x s   ]*  (x s, r3)  reduce
  [B       -> a .,      x t   ]*  (x t, r4)  reduce

doneList: i0
incList:  i1 i2 i3 i4
toDoList: -
comeFrom: i0

Iteration 3

i1 x1. goto(S) from i0  complete
  [$accept -> S .,      $end -]*  ($end -, r0)

doneList: i0 i1
incList:  i2 i3 i4
toDoList: -
comeFrom: i1

Iteration 4, Phase 1

i2 x2. goto(A) from i0  complete
  [S       -> A . x s,  $end -]*  (x, x5)  shift

x5. goto(x) from i2
  [S       -> A x . s,  $end -]*  (-, -)

doneList: i0 i1 i2
incList:  i3 i4
toDoList: x5
comeFrom: i2

Iteration 4, Phase 2

i5 x5. goto(x) from i2
  [S       -> A x . s,  $end -]*  (-, -)

doneList: i0 i1 i2
incList:  i3 i4 i5
toDoList: -
comeFrom: i2

Iteration 5, Phase 1

i3 x3. goto(B) from i0  complete
  [S       -> B . x t,  $end -]*  (x, x6)  shift

x6. goto(x) from i3
  [S       -> B x . t,  $end -]*  (-, -)

doneList: i0 i1 i2 i3
incList:  i4 i5
toDoList: x6
comeFrom: i3

Iteration 5, Phase 2

i6 x6. goto(x) from i3
  [S       -> B x . t,  $end -]*  (-, -)

doneList: i0 i1 i2 i3
incList:  i4 i5 i6
toDoList: -
comeFrom: i3

Iteration 6

i4 x4. goto(a) from i0  complete
  [A       -> a .,      x s   ]*  (x s, r3)  reduce
  [B       -> a .,      x t   ]*  (x t, r4)  reduce

doneList: i0 i1 i2 i3 i4
incList:  i5 i6
toDoList: -
comeFrom: i4

Iteration 7, Phase 1

i5 x5. goto(x) from i2  complete
  [S       -> A x . s,  $end -]*  (s, x7)  shift

x7. goto(s) from i5
  [S       -> A x s .,  $end -]*  (-, -)

doneList: i0 i1 i2 i3 i4 i5
incList:  i6
toDoList: x7
comeFrom: i5

Iteration 7, Phase 2

i7 x7. goto(s) from i5
  [S       -> A x s .,  $end -]*  ($end -, r1)  reduce

doneList: i0 i1 i2 i3 i4 i5
incList:  i6 i7
toDoList: -
comeFrom: i5

Iteration 8, Phase 1

i6 x6. goto(x) from i3  complete
  [S       -> B x . t,  $end -]*  (t, x8)  shift

x8. goto(t) from i6
  [S       -> B x t .,  $end -]*  (-, -)

doneList: i0 i1 i2 i3 i4 i5 i6
incList:  i7
toDoList: x8
comeFrom: i6

Iteration 8, Phase 2

i8 x8. goto(t) from i6
  [S       -> B x t .,  $end -]*  ($end -, r2)  reduce

doneList: i0 i1 i2 i3 i4 i5 i6
incList:  i7 i8
toDoList: -
comeFrom: i6

Iteration 9

i7 x7. goto(s) from i5  complete
  [S       -> A x s .,  $end -]*  ($end -, r1)

doneList: i0 i1 i2 i3 i4 i5 i6 i7
incList:  i8
toDoList: -
comeFrom: i7

Iteration 10 (last)

i8 x8. goto(t) from i6  complete
  [S       -> B x t .,  $end -]*  ($end -, r2)

doneList: i0 i1 i2 i3 i4 i5 i6 i7 i8
incList:  -
toDoList: -
comeFrom: i8

Final Results

i0 x0. initial item set
  [$accept -> . S,      $end -]*  (S, i1 x1)
  [S       -> . A x s,  $end -]   (A, i2 x2)
  [S       -> . B x t,  $end -]   (B, i3 x3)
  [A       -> . a,      x s   ]   (a, i4 x4)
  [B       -> . a,      x t   ]   (a, i4 x4)

i1 x1. goto(S) from i0
  [$accept -> S .,      $end -]*  ($end -, r0)

i2 x2. goto(A) from i0
  [S       -> A . x s,  $end -]*  (x, i5 x5)

i3 x3. goto(B) from i0
  [S       -> B . x t,  $end -]*  (x, i6 x6)

i4 x4. goto(a) from i0
  [A       -> a .,      x s   ]*  (x s, r3)
  [B       -> a .,      x t   ]*  (x t, r4)

i5 x5. goto(x) from i2
  [S       -> A x . s,  $end -]*  (s, i7 x7)

i6 x6. goto(x) from i3
  [S       -> B x . t,  $end -]*  (t, i8 x8)

i7 x7. goto(s) from i5
  [S       -> A x s .,  $end -]*  ($end -, r1)

i8 x8. goto(t) from i6
  [S       -> B x t .,  $end -]*  ($end -, r2)

Parser States

s0. initial state
  $accept : . S
  S       : . A x s
  S       : . B x t
  A       : . a
  B       : . a

  a -     shift  s4
  S       goto   s1
  A       goto   s2
  B       goto   s3

s1. goto(S) from s0
  $accept : S .        (r0)

  $end -  accept

s2. goto(A) from s0
  S       : A . x s

  x -     shift  s5

s3. goto(B) from s0
  S       : B . x t

  x -     shift  s6

s4. goto(a) from s0
  A       : a .        (r3)
  B       : a .        (r4)

  x s     reduce r3
  x t     reduce r4

s5. goto(x) from s2
  S       : A x . s

  s -     shift  s7

s6. goto(x) from s3
  S       : B x . t

  t -     shift  s8

s7. goto(s) from s5
  S       : A x s .    (r1)

  $end -  reduce r1

s8. goto(t) from s6
  S       : B x t .    (r2)

  $end -  reduce r2

Parser Table

State Terminal Lookaheads Nonterminals Default

$end - a - s - t - x - x s x t S A B

0 - s4 - - - - - s1 s2 s3 -

1 acc - - - - - - - - - -

2 - - - - s5 s5 s5 - - - -

3 - - - - s5 s5 s5 - - - -

4 - - - - - r3 r4 - - - -

5 - - s7 - - - - - - - -

6 - - - s8 - - - - - - -

7 r1 - - - - - - - - - r1

8 r2 - - - - - - - - - r2

State	Terminal Lookaheads	Nonterminals	Default
`$end -`	`a -`	`s -`	`t -`	`x -`	`x s`	`x t`	`S`	`A`	`B`
0	-	s4	-	-	-	-	-	s1	s2	s3	-
1	acc	-	-	-	-	-	-	-	-	-	-
2	-	-	-	-	s5	s5	s5	-	-	-	-
3	-	-	-	-	s5	s5	s5	-	-	-	-
4	-	-	-	-	-	r3	r4	-	-	-	-
5	-	-	s7	-	-	-	-	-	-	-	-
6	-	-	-	s8	-	-	-	-	-	-	-
7	r1	-	-	-	-	-	-	-	-	-	r1
8	r2	-	-	-	-	-	-	-	-	-	r2

The Honalee LR Algorithm is discussed further at: honalee.html.
Previous example: honalee_ex3.html.
Author's home page: david.tribble.com

Honalee LR Parsing Algorithm LR(2) Example