GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
222 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) .

asked in Compiler Design by Veteran (47.4k points)   | 222 views

1 Answer

+6 votes
Best answer

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

??

answered by Veteran (24.9k points)  
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 .


Top Users Jun 2017
  1. Bikram

    3704 Points

  2. Hemant Parihar

    1502 Points

  3. junaid ahmad

    1432 Points

  4. Arnab Bhadra

    1416 Points

  5. Niraj Singh 2

    1391 Points

  6. Debashish Deka

    1246 Points

  7. Rupendra Choudhary

    1194 Points

  8. rahul sharma 5

    1158 Points

  9. Arjun

    956 Points

  10. srestha

    950 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 19 - 25
  1. Bikram

    1960 Points

  2. Niraj Singh 2

    1386 Points

  3. junaid ahmad

    502 Points

  4. Debashish Deka

    414 Points

  5. sudsho

    410 Points


23,373 questions
30,079 answers
67,405 comments
28,396 users