344 views

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) .

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).

??

selected by

Very Nice :)

Just a doubt ?

$X\rightarrow Xb$ won't go in $c$ and $? I don't think so.. X-> Xb would go only in the first of (Xb) right ?? And first of Xb = { b } ..right ?? Okk !! I am not sure but just thought that first of {Xb} = first of {X} And, First of {X} = {b,c,$} ?

First(X) = { b, $\epsilon$ }

Follow(X)={b, c, \$ }.
Yes, u r right .

1
+1 vote
2