This LL(1) parse table is correct?

1.4k views Asked by At

Given grammar:

S -> AB
A -> aA | b
B -> CA
C -> cC | ɛ

Is its LL(1) parsing table is this? enter image description here

2

There are 2 answers

1
Alexandra On BEST ANSWER

No, it is not entirely correct because of these calculations:

First(S) = First(A) = {a,b}
First(A) = {a,b}
First(B) = First(C) = {c,ε}
First(C) = {c,ε}

Considering that the Follow of each non-terminal symbol is the terminal symbol right after:

Follow(S) ={a,b} (if SAB --> AB then SaAB --> aAB or SbB --> bB)

Follow(A) = {a,c} (if AaA-->aA and Ab --> b then AaA --> aA or Ab --> b)

Follow(B) = Follow (A) = {a,c} (model production A --> aB, which a terminal, and a = ε, then Follow (A) = Follow (B))

Follow(C) = {a,b} (from B-->CA, B-->CaA or B-->Cb)

So the the difference with your parse table, and these calculations, is that in non-terminal B row in columns a and b the values are NULL.

0
Bhumika Patel On
Yes it is correct.
First(S) = First(A) = {a,b}
First(A) = {a,b}
First(B) = {a,b,c} 
B->CA and C->cC|ɛ
First(C) = {c,ε} 
so if we put ɛ as a replacement of C in B -> CA, we'll have B -> A, Thus First(B)= First(A) instead of ɛ.