Draw the LL(1) parsing table of the given grammar ?

Question

Consider a Grammar G as follows :

$S\rightarrow W$

$W \rightarrow ZXY / XY$

$Y\rightarrow c/\epsilon$

$Z\rightarrow a/d$

$X\rightarrow Xb/\epsilon$

---

Draw the LL(1) parsing table for the given grammar ?

---

NOTE :- The above grammar is NOT LL(1) .

Comments

I think the above grammar is LL(1). There is left recursion in last production i.e. X -> Xb | ε....

If we remove left recursion from this production such as

X -> X'

X' -> bX' | ε

And then if we make LL(1) parsing table, then there will be only unit or single entries per cell of the table. There will be no multiple entries.

 

(Please comment on this...)

Answer 1

S→W

W→ZXY / XY

Y→c/ϵ

Z→a/d

X→Xb/ϵ

---

First(S) = { a, d, b, c, d, ϵ}  , Follow(S) = { $ }

First(W) = { a, d, b, c, d, ϵ} , Follow(W) = { $ }

First(X) = { b, ϵ}                  , Follow(X) = {b, c,$ }

First(Y) = { c, ϵ}                 , Follow(Y) = { $ }

First(Z) = { a, d}                 , Follow(Z) = { b, c, $ }

---

LL(1) Table-

---

Place A -> B in the first of B in row A.

If  A -> B , and first of A =ϵ or B = ϵ , then place A-> B, in the follow of A.

---

	a	b	c	d	$
S	S->W	S->W	S->W	S->W	S->W
W	W->ZXY	W->XY	W->XY	W->ZXY	W->XY
X		X->Xb X->$\epsilon$	X->$\epsilon$		X->$\epsilon$
Y			Y->c		Y->$\epsilon$
Z	Z->a			Z->d

Because of X-> Xb and X -> ϵ , going in same block, given grammar is not LL(1).

??

Comments

Can you tell why did you put first pproduction S->W in $ too ? I assume it is because when W = ϵ then  production becomes S-> ϵ and goes in Follow(S). Do I understand it correct ?

---

@ Amey Umarekar

S→W ::: W→XY::::X→ϵ,Y→ϵ:::::W→ϵ :::::S→ϵ

Follow of S=$

---

@  saxena0612

Ohh ok, so same goes with W->XY in Follow(W). Thanks !!