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 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;
  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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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