Search code examples
compilationgrammarcontext-free-grammar

This LL(1) parse table is correct?

Given grammar:

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

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

Solution

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