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 :


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!

  • $\begingroup$ FIRST(E) includes c and x, but not epsilon (why?) $\endgroup$ Dec 4 '16 at 18:42
  • $\begingroup$ 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! $\endgroup$
    – Raphael
    Jan 10 '18 at 11:10

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;
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 ++;
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
  • $\begingroup$ why we need to do - if ( ℇ ∈ first(α) ): write A -> α in T[A,x], ∀ x ∈ follow(A) $\endgroup$
    – darshan
    Jan 23 '20 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.