A4 solution

Augmented grammar

Number	Production
0	S′ → S
1	S → X c Y
2	Y → X Y
3	Y → b X
4	X → a X
5	X → a

Words generated with this grammar are a sequence of one or more ‘a’s, followed by a ‘c’, followed by zero or more ‘a’s, followed by a ‘b’, followed by one or more ‘a’s.

The corresponding regular expression is a⁺ca^*ba⁺.

FIRST and FOLLOW sets

FIRST(S) = { a }

FIRST(X) = { a }

FIRST(Y) = { a, b }

FOLLOW(S) = { $ }

FOLLOW(X) = { a, b, c, $ }

FOLLOW(Y) = { $ }

Canonical collection of LR(0) items:

		I₀	=	{	S′ → ∙ S S → ∙ X c Y X → ∙ a X X → ∙ a }
GOTO(I₀, S)	=	I₁	=	{	S′ → S ∙ }
GOTO(I₀, X)	=	I₂	=	{	S → X ∙ c Y }
GOTO(I₀, a)	=	I₃	=	{	X → a ∙ X X → a ∙ X → ∙ a X X → ∙ a }
GOTO(I₂, c)	=	I₄	=	{	S → X c ∙ Y Y → ∙ X Y Y → ∙ b X X → ∙ a X X → ∙ a }
GOTO(I₃, X)	=	I₅	=	{	X → a X ∙ }
GOTO(I₃, a)	=	I₃
GOTO(I₄, X)	=	I₆	=	{	Y → X ∙ Y Y → ∙ X Y Y → ∙ b X X → ∙ a X X → ∙ a }
GOTO(I₄, Y)	=	I₇	=	{	S → X c Y ∙ }
GOTO(I₄, a)	=	I₃
GOTO(I₄, b)	=	I₈	=	{	Y → b ∙ X X → ∙ a X X → ∙ a }
GOTO(I₆, X)	=	I₆
GOTO(I₆, Y)	=	I₉	=	{	Y → X Y ∙ }
GOTO(I₆, a)	=	I₃
GOTO(I₆, b)	=	I₈
GOTO(I₈, X)	=	I₁₀	=	{	Y → b X ∙ }
GOTO(I₈, a)	=	I₃

SLR parsing table

STATE	ACTION				GOTO
STATE	a	b	c	$	S	X	Y
0	s3				1	2
1				acc
2			s4
3	s3/r5	r5	r5	r5		5
4	s3	s8				6	7
5	r4	r4	r4	r4
6	s3	s8				6	9
7				r1
8	s3					10
9				r2
10				r3

Parsing aacba

ACTION	STACK	INPUT
start	0	aacba$
s3	0 a 3	acba$
s3	0 a 3 a 3	cba$	...or...	r5	0 X 2	acba$
r5	0 a 3 X 5	cba$		err
r4	0 X 2	cba$
s4	0 X 2 c 4	ba$
s8	0 X 2 c 4 b 8	a$
s3	0 X 2 c 4 b 8 a 3	$
r5	0 X 2 c 4 b 8 X 10	$
r3	0 X 2 c 4 Y 7	$
r1	0 S 1	$
acc