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}

and follow would be:

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?

  • 2
    $\begingroup$ $a$ is in $first(S)$ and $d$ is in $first(A)$. Why would the corresponding entries be blank? $\endgroup$
    – rici
    Aug 2 '19 at 1:08
  • $\begingroup$ @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)$ $\endgroup$
    – ikkentim
    Aug 2 '19 at 10:15
  • 1
    $\begingroup$ 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)$. $\endgroup$
    – rici
    Aug 2 '19 at 12:04
  • $\begingroup$ @rici ah see, that's where I went wrong. Thank you! $\endgroup$
    – ikkentim
    Aug 2 '19 at 15:10

Your Answer

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

Browse other questions tagged or ask your own question.