• Monday Exam
• Wednesday Exam
• Friday Exam

Monday Exam

For each grammar below:

• (A) Classify each of the following grammars into the categories:
  • LR(0),
  • SLR(1),
  • LR(1),
  • LALR(1)
  by identifying the conflicts.
• (B) Construct appropriate parsing table.
• (C) Rewrite each grammar as LL(1) form.

• I. solution
  • S => a S a | a
• II. solution
  • S => ( S ) | a
• III. solution
  • S => a | V = E
  • V => a
  • E => V | n
• IV. solution
  • S => a R b | c T b | a T d | c R d
  • R => x
  • T => x

top

Wednesday Exam

• I. Remove Left Recursion solution
  • A => A a | a
  • B => B b | y
  • C => C c | epsilon
• II. Left Factor solution
  • A => B | C
  • B => a b a b | a b c
  • C => a c a c | a c b
• III. Remove Epsilon (epsilon) Productions solution
  • A => B C | C D
  • B => a | b
  • C => c | B C D | epsilon
  • D => n

top

Friday Exam

• I.Find First and Follow sets solution
  • A => B C D | C D
  • B => a | B | epsilon
  • C => c | D C B | epsilon
  • D => d
• II.Create LL(1) Grammar equivalent to solution
  • A => B C | C B
  • B => a b a | a b c | b b a | b a c
  • C => a c a | a c b | c a c | c b c
• III. Find all conflicts, classify and build parsing table if possible
  • E => E + F | F
  • F => ( E ) | a | a = E
  solution

top

Solution to I

I.	S => a S a 
	S => a

A. Not LR(1), shift reduce conflict.
	state (4) has shift reduce on LA(a)
	state (4)
		S => a *S a 	LA(a)
		S => a* 	LA(a)
		S => *a S a 	LA(a)
		S => *a 	LA(a)
		on S goto (6)
		if LA(a) reduce (S => a)
		if LA(a) shift (4) 
B. See below
C. LL form:
	LL => a [LL2]
	LL2 => a a [LL2]
	or 
	LL => a LL2
	LL2 => a a LL2 | (empty)




state (4) has shift reduce on LA(a)
TABLE	$	a	S
0		s2	g1
1	r0
2	r1	s4
3		s5
4		r2/s4	g6
5	r1
6		s7
7		r1
r0: S' => S (accept)
r1: S => a S a 
r2: S => a


state (0)
S' => *S 	LA($)
S => *a S a 	LA($)
S => *a 	LA($)
on S goto (1)
if LA(a) shift (2)


state (1)
S' => S* 	LA($)
if LA($) accept 


state (2)
S => a *S a 	LA($)
S => a*		LA($)
S => *a S a 	LA(a)
S => *a 	LA(a)
on S goto (3)
if LA($) reduce (S => a)
if LA(a) shift (4)


state (3)
S => a S* a 	LA($)
if LA(a) shift (5)


state (4)
S => a *S a 	LA(a)
S => a* 	LA(a)
S => *a S a 	LA(a)
S => *a 	LA(a)
on S goto (6)
if LA(a) reduce (S => a)
if LA(a) shift (4) 


state (5)
S => a S a* 	LA($)
if LA($) reduce (S => a S a)

state (6)
S => a S* a 	LA(a)
if LA(a) shift (7)

state (7)
S => a S a* 	LA(a)
if LA(a) reduce (S => a S a)

top

Solution to II

II.	S => ( S ) 
	S => a
A. LR(0)
B. See below
C. LL form. Already in LL form.

r0 = S' => S = accept
r1 = S => ( S ) 
r2 = S => a


LR(1) 	$	(	)	a	S
0		s2		s3	g1
1	r0
2		s5		s6	g4
3	r2	
4			s7
5(2)		s5		s6	g8
6(3)			r2
7	r1
8(4)			s9
9(7)			r1


LALR	$	(	)	a	S
0		s2		s3	g1
1	r0
2		s2		s3	g4
3	r2		r2
4			s5
5	r1		r1
state 5 was state 7

SLR	$	(	)	a	S	action 
0		s2		s3	g1	shift
1	r0					reduce
2		s2		s3	g4	shift
3	r2		r2			reduce
4			s5			shift
5	r1		r1			reduce



state (0)
S' => *S 	LA($)
S => *( S ) 	LA($)
S => *a 	LA($)
on S goto (1)
if LA(() shift (2)
if LA(a) shift (3)

state (1)
S' => S* 	LA($)
if LA($) accept


state (2)
S => ( *S ) 	LA($)
S => *( S ) 	LA())
S => *a 	LA())
on S goto (4)
if LA(() shift (5)
if LA(a) shift (6)

state (3)
S => a* 	LA($)
if LA($) reduce (S => a)

state (4)
S => ( S* ) 	LA($)
if LA()) shift (7)


state (5) (LALR MERGES WITH 2)
S => ( *S ) 	LA())
S => *( S ) 	LA())
S => *a 	LA())
on S goto (8)
if LA(() shift (5)
if LA(a) shift (6)


state (6) (LALR MERGES WITH 3)
S => a* 	LA())
if LA()) reduce (S => a)

state (7) 
S => ( S )* 	LA($)
if LA($) reduce (S => ( S ) )

state (8) (LALR MERGES WITH 4)
S => ( S *) 	LA())
if LA()) shift (9)

state (9) (LALR MERGES WITH 7)
S => ( S )* 	LA())
if LA()) reduce (S => ( S ) )

top

Solution to III

III.	S => a | V = E
	V => a
	E => V | n

A. LALR 
	SLR reduce/reduce conflict on  
	S => a*		
	V => a*	
	since follow(S) and follow (V) contain $
B. See below
C. LL Form
	LL => V [A] 
	V => a
	A => = E
	E => V | n
	or
	LL => V A 
	V => a
	A => = E | (empty)
	E => V | n




LALR	$	a	=	n	S	V	E
0		s2			g1	g3
1	r0
2	r1		r3
3			s4
4		s8		s7		g6	g5
5	r2
6	r4
7	r5
8	r3

r0: S' => S
r1: S => a 
r2: S => V = E
r3: V => a
r4: E => V 
r5: E => n



(0)
S' => *S	LA($)
S => *a 	LA($)
S => *V = E	LA($)
V => *a		LA(=)
on S goto 1
on V goto 3
LA(a) shift 2

(1)
S' => S*	LA($)
LA($) reduce S' => S

(2)
S => a*		LA($)
V => a*		LA(=)
LA($) reduce S => a
LA(=) reduce V => a

(3)
S => V *= E 	LA($)
LA(=) shift 4

(4)
S => V = *E	LA($)
E => *V 	LA($)
E => *n		LA($)
V => *a		LA($)
on E goto 5
on V goto 6
LA(n) shift 7
LA(a) shift 8

(5)
S => V = E*	LA($)
LA($) reduce S => V = E

(6)
E => V* 	LA($)
LA($) reduce E => V

(7)
E => n*		LA($)
LA($) reduce E => n

(8)
V => a*		LA($)
LA($) reduce V => a

top

Solution to IV

IV.	S => a R b | c T b | a T d | c R d
	R => x
	T => x

A. LR(1), NOT LALR 
	reduce/reduce conflict 
	R => x [b,d]
	T => x [b.d]
B. See below
C. LL Form 
	LL => AXBD | CXBD
	AXBD => a x BD 
	CXBD => c x BD
	BD => b | d  



LR(1)	$	a	b	c	d	x	S	R	T
0		s2		s3			g1
1	r0
2						6		g4	g5
3						s9		g7	g8	
4			s10
5					s11
6			r5		r6
7			s/12
8					s13
9			r6		r5
10	r1
11	r2
12	r3
13	r4

r0: S'=> S
r1: S => a R b
r2: S => c T b
r3: S => a T d
r4: S => c R d
r5: R => x
r6: T => x


state (0)
S'=> *S 	LA($)
S => *a R b	LA($)
S => *c T b	LA($)
S => *a T d	LA($)
S => *c R d	LA($)
on S goto 1
LA(a) shift 2
LA(c) shift 3

state (1)
S'=> S* 	LA($)
LA($) accept

state (2)
S => a *R b	LA($)
S => a *T d	LA($)
R => *x		LA(b)
T => *x		LA(d)
on R goto 4
on T goto 5
LA(x) shift 6

state (3)
S => c *T b	LA($)
S => c *R d	LA($)
T => *x		LA(b)
R => *x		LA(d)
on T goto 7
on R goto 8
LA(x) shift 9

state (4)
S => a R *b	LA($)
LA(b) shift 10

state (5)
S => a T *d	LA($)
LA(d) shift 11

state (6)
R => x*		LA(b)
T => x*		LA(d)
LA(b) reduce R => x
LA(d) reduce T => x

state (7)
S => c T *b	LA($)
LA(b) shift 12

state (8)
S => c R *d	LA($)
LA(d) shift 13

state (9)
T => x*		LA(b)
R => x*		LA(d)
LA(b) reduce T => x
LA(d) reduce R => x

state (10)
S => a R b*	LA($)
LA($) reduce S => a R b

state (11)
S => a T d*	LA($)
LA($) reduce S => a T d

state (12)
S => c T b*	LA($)
LA($) reduce S => c T b

state (13)
S => c R d*	LA($)
LA($) reduce S => c R d

top

Solution to Wednesday I

I.Remove Left Recursion

A => A a | a
B => B b | y
C => C c | epsilon 

===========================
Solution
===========================
A  => a A | a
B  => y B'
B' =>  b B' | epsilon
C  => c C | epsilon 

top

Solution to Wednesday II

II. Left Factor

A => B | C
B => a b a b | a b c
C => a c a c | a c b

===========================
Solution
===========================
A  => a A'
A' => b B | c C
B  => a b | b c
C  => a c | b

top

Solution to Wednesday III

III. Remove Epsilon (epsilon) Productions

A => B C | C D
B => a | b
C => c | B C D | epsilon
D => n

===========================
Solution
===========================
A => B | B C | C D | D
B => a | b
C => c | B C D | B D
D => n

top

Solution to Friday I

I.Find First and Follow sets

A => B C D | C D
B => a | B | epsilon
C => c | D C B | epsilon
D => d

===========================
WORKING DETAILS
===========================

FIRST(A) = FIRST(B)+FIRST(C)+FIRST(D)	
FIRST(B) = {a,b}
FIRST(C) = {c}+FIRST(D)
FIRST(D) = {d}
FOLLOW(A) = {$}
FOLLOW(B) = FIRST(C) + FOLLOW(C)
FOLLOW(C) = FIRST(D)+FIRST(B)
FOLLOW(D) = FOLLOW(A)+FIRST(C)+FIRST(B)+FOLLOW(C)

===========================
Solution
===========================

	FIRST		FOLLOW
A 	{a b c d}	{$}	
B 	{a b}		{c d}
C 	{c d}		{a b d}
D 	{d}		{$ a b c d}

top

Solution to Friday II

II.Create LL(1) Grammar equivalent to

A => B C | C B
B => a b a | a b c | b b a | b a c
C => a c a | a c b | c a c | c b c

===========================
Solution
===========================

A => a A_PROD | b B_PROD | c C_PROD
B => a b AorC | b BA
C => a c AorB | c CA

A_PROD => b AorC C | c AorB B
B_PROD => BAorAC C
C_PROD => ACorBC B

AorC => a | c 
AorB => a | b 

BAorAC => b a | a c
ACorBC => a c | b c

top

Solution to Friday III

III. Find all conflicts, classify and build parsing table if possible
	E => E + F
	E => F
	F => ( E )
	F => a
	F => a = E

===========================
Solution
===========================
	LR(0)/SLR shift/reduce conflicts in state(4)
		F => a *= E
		F => a*
	unresolvable LALR shift reduce conflict in state(10)
		LA($,+) F => a = E*
		LA($,+)	E => E *+ F
		on($,+) reduce r5: F => a = E
		on(+) shift 5

LALR	$	+	(	)	a	=	S	E	F
0			s3		s4			g1	g2
1	r0	s5								
2	r2	r2								
3			s3		s4			g6	g7	
4	r4	r4				s8				
5			s3		s4				g9	
6		s5		s10						
7		r2		r2						
8			s3		s4			g10	g2	
9	r1	r1								
10	r5	s5(r5)								

shift/reduce conflict in state 10 resolved in favor of shift

r0: S => E
r1: E => E + F
r2: E => F
r3: F => ( E )
r4: F => a
r5: F => a = E


state(0)
	LA($) 	S => *E
	LA($) 	E => *E + F
	LA(+) 	E => *E + F
	LA($) 	E => *F
	LA(+) 	E => *F
	LA($) 	F => *( E )
	LA(+) 	F => *( E )
	LA($) 	F => *a = E
	LA(+) 	F => *a = E
	LA($) 	F => *a
	LA(+) 	F => *a
	on (E) goto 1
	on (F) goto 2
	on (() shift 3
	on (a) shift 4
state(1)
	LA($) 	S => E*
	LA($,+) E => E *+ F
	on ($) reduce r0: S => E (accept)
	on (+) shift 5
state(2)
	LA($,+) E => F*
	on ($,+) reduce r2: E => F
state(3)
	LA($,+) F => ( *E )
	LA()) 	E => *E + F
	LA(+) 	E => *E + F
	LA()) 	E => *F
	LA(+) 	E => *F
	LA()) 	F => *( E )
	LA(+) 	F => *( E )
	LA(+) 	F => *a = E
	LA()) 	F => *a = E
	LA(+) 	F => *a
	LA()) 	F => *a
	on (E) goto 6
	on (F) goto 7
	on (() shift 3
	on (a) shift 4
state(4)
	LA($,+) F => a *= E
	LA($,+) F => a*
	on($,+) reduce r4: F => a
	on(=) shift 8
state(5)
	LA($,+) E => E + *F
	LA($,+)	F => *( E )
	LA($,+)	F => *a = E
	LA($,+) F => *a
	on(F) goto 9
	on(() shift 3
	on(a) shift 4
state(6)
	LA($,+) F => ( E* )
	LA(),+)	E => E *+ F
	on()) shift 10
	on(+) shift 5
state(7)
	LA(),+)	E => F*
	on(),+) reduce r2: E => F
state(8)
	LA($,+) F => a =* E
	LA($,+)	E => *E + F
	LA($,+)	E => *F
	LA($,+)	F => *( E )
	LA($,+)	F => *a = E
	LA($,+)	F => *a
	on(E) goto 10
	on(F) goto 2
	on(() shift 3
	on(a) shift 4
state(9)
	LA($,+) E => E + F*
	on($,+) reduce r1: E => E + F
state(10)
	LA($,+) F => a = E*
	LA($,+)	E => E *+ F
	on($,+) reduce r5: F => a = E
	on(+) shift 5

top