18,993 views
4 votes
4 votes

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

1 Answer

Best answer
8 votes
8 votes

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

Related questions

8 votes
8 votes
3 answers
2
Parshu gate asked Nov 13, 2017
15,198 views
Suppose we are given a grammar and asked to find the type of that grammar , what is the algorithm which needs to be followed for each of them? LL(1), OR LR(0) , OR CLR(1...
2 votes
2 votes
1 answer
4
sripo asked Nov 10, 2018
3,181 views
Can you give an example which is not LL(1) but is CLR(1)