# LL(1) parsing table construction

i have the following CFG

E -> ABC
A-> a|Cb|epsilon
B-> c|xA|epsilon
C-> y|z


and the First of the Non-Terminal :

First(E) = {a,y,z,epsilon}
Frist(A) = { a,y,z,epsilon}
First(B) = { c,x,epsilon }
First(C) = {y,z}


the follow of Non-Terminal :

follow(E)={$} follow(A)={c,x,y,z} follow(B)={y,z} follow(C)={b,$}


my problem is how to construct the parsing table , i constructed the table and i got the following , but i think there is something missing/mistake in the table

    x    a    b    c    y    z    $------------------------------------ E ABC ABC ABC epsilon A eps. a eps. Cb Cb B xA c eps. eps. C y z  i hope the table is clear , Note : in the row A i got epsilon with both Cb in y And Cb in z , but i did not write it in the table , is that mean the grammer is not LL(1) ?? thank you! • FIRST(E) includes c and x, but not epsilon (why?) – André Souza Lemos Dec 4 '16 at 18:42 • The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Jan 10 '18 at 11:10 ## 1 Answer Let's start with the general case. Given a production of a grammar, let's say A -> α where α is a general string, to compute the LL(1) parsing table T the algorithm says: foreach(A -> α in the grammar): write A -> α in T[A,b], ∀ b ∈ first(α); if ( ℇ ∈ first(α) ): write A -> α in T[A,x], ∀ x ∈ follow(A);  If at the end of the algorithm you have any cell in the table T with more than one entry then the grammar is not LL(1), as in your case. To run this algorithm you need to compute the set of firsts and follow of a symbol. I see you did right the follows sets, but you mistake in the firsts set of E. So here is the algorithm to compute the firsts set of a symbol X: if(X is a terminal symbol): first(X) = X; break; if (X -> ℇ ∈ productions of the grammar): first(X).add({ ℇ }); foreach(X -> Y1....Yn ∈ productions of the grammar): j = 1; while (j <= n): first(X).add({ b }), ∀ b ∈ first(Yj) ; if ( ℇ ∈ first(Yj)): j ++; else: break; if(j = n+1): first(X).add({ ℇ });  So going back to your example: First(E) = {a,y,z,c,x}  and in the table: T[E,$] = E -> ABC