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

Why does first of S contain c??

---

Can you please how will follow of Z contain c , since FO(Z) =(F(X) -€) U FO(Y) , which is equal to {b, $}.

---

follow(z) = { first(XY) }

              = { first(X), first(Y), follow(W) } // as X,Y are nullable

              = { b, c, $ }

 

Answer 2

variable is changed. But grammar is same

 

Answer 3

Its contain left recursive, that's why its not LL1