LR(1) Parser Generator

LR(1) grammar ('' is ε):

FIRST table
Nonterminal	FIRST
S'	{c,d}
S	{c,d}
C	{c,d}

LR(1) closure table
Goto	Kernel	State	Closure
	{[S' -> .S, $]}	0	{[S' -> .S, $]; [S -> .C C, $]; [C -> .c C, c/d]; [C -> .d, c/d]}
goto(0, S)	{[S' -> S., $]}	1	{[S' -> S., $]}
goto(0, C)	{[S -> C.C, $]}	2	{[S -> C.C, $]; [C -> .c C, $]; [C -> .d, $]}
goto(0, c)	{[C -> c.C, c/d]}	3	{[C -> c.C, c/d]; [C -> .c C, c/d]; [C -> .d, c/d]}
goto(0, d)	{[C -> d., c/d]}	4	{[C -> d., c/d]}
goto(2, C)	{[S -> C C., $]}	5	{[S -> C C., $]}
goto(2, c)	{[C -> c.C, $]}	6	{[C -> c.C, $]; [C -> .c C, $]; [C -> .d, $]}
goto(2, d)	{[C -> d., $]}	7	{[C -> d., $]}
goto(3, C)	{[C -> c C., c/d]}	8	{[C -> c C., c/d]}
goto(3, c)	{[C -> c.C, c/d]}	3
goto(3, d)	{[C -> d., c/d]}	4
goto(6, C)	{[C -> c C., $]}	9	{[C -> c C., $]}
goto(6, c)	{[C -> c.C, $]}	6
goto(6, d)	{[C -> d., $]}	7

LR table
State	ACTION			GOTO
State	c	d	$	S'	S	C
0	s3	s4			1	2
1			acc
2	s6	s7				5
3	s3	s4				8
4	r₃	r₃
5			r₁
6	s6	s7				9
7			r₃
8	r₂	r₂
9			r₂

Input (tokens):

Maximum number of steps:

Trace

Tree

Step

Stack

Input

Action

1

0

c d d $

s3

S

C

c

C
d

C
d

2

0 c 3

d d $

s4

3

0 c 3 d 4

d $

r₃

4

0 c 3 C

d $

8

5

0 c 3 C 8

d $

r₂

6

0 C

d $

2

7

0 C 2

d $

s7

8

0 C 2 d 7

$

r₃

9

0 C 2 C

$

5

10

0 C 2 C 5

$

r₁

11

0 S

$

1

12

0 S 1

$

acc