# How to generate LL(1) parse table

Given the following grammar:

S -> A a
A -> B D
B -> b
B -> ε
D -> d
D -> ε


first would be:

B: {b,ε}
D: {d,ε}
A: {b,ε,d}
S: {b,ε,d,a}


S: {$} A: {a} B: {d,a} D: {a}  The LL(1) parse table should be easy to build. According to LL(1) parsing table construction I can simply follow this algorithm: foreach(A -> α in the grammar): write A -> α in T[A,b], ∀ b ∈ first(α); if ( ℇ ∈ first(α) ): write A -> α in T[A,x], ∀ x ∈ follow(A);  However, this would leave T[S,a] and T[A,d] blank, so "a" and "d a" could not be parsed: row S: column b -> S -> A a column d -> S -> A a column$ -> S -> A a
row A:
column  b -> A -> B D
column  a -> A -> B D
row B:
column  b -> B -> b
column  d -> B -> ε
column  a -> B -> ε
row D:
column  d -> D -> d
column  a -> D -> ε


When I use a tool like this: http://jsmachines.sourceforge.net/machines/ll1.html values for T[S,a] and T[A,d] are generated. Am I using a wrong algorithm for generating the parse table, is the grammar not LL1 or am I doing something else wrong?

• $a$ is in $first(S)$ and $d$ is in $first(A)$. Why would the corresponding entries be blank? – rici Aug 2 at 1:08
• @rici According to the formula from the linked SE page, only every $b$ in $first(α)$ should be added to $T[A,b]$, so $T[A,d]$ would be blank because $d$ is not in $first(B)$ – ikkentim Aug 2 at 10:15
• For the production $A\to BD$, $\alpha$ is $BD$, and $first(\alpha)$ is $first(BD)$, not $first(B)$. And $d$ most certainly is in $first(BD)$. – rici Aug 2 at 12:04
• @rici ah see, that's where I went wrong. Thank you! – ikkentim Aug 2 at 15:10