# What's the right way to think about a CFG symbol with an infinite null derivation?

I'm curious about the right way to characterize symbol $$A$$ in a CFG like this one:

\begin{align*} A &\to A B\\ A &\to x\\ B &\to y\\ B &\to \varepsilon \end{align*}

$$B$$ is certainly nullable. However, should $$A$$ be considered nullable? It feels like the answer is probably "no" (and most first-follow implementations I've seen either agree or crash on this). However, you can derive an infinitely large parse tree for the null symbol sequence like $$A \to A(A(A(...) B()) B()$$.

The infinitely large parse tree you propose does not represent the parse of any sentence, because its leaves are not all terminals.

A more precise statement would be that $$A$$ cannot derive the empty sentence. You can produce an arbitrarily long derivation of $$A$$ by repeatedly using the rules $$A \to A B$$ and $$B \to \epsilon$$ but none of those derivations is empty. Since the precise definition of "nullable" is "a non-terminal which can derive the empty sentence", $$A$$ is not nullable.

If a FIRST/FOLLOW implementation crashes on that input, then the implementation is buggy. The correct computations are:

\begin{align} FIRST(A) &= \{x\} \\ FIRST(B) &= \{y, \epsilon\} \\ FOLLOW(A) &= \{y, \epsilon\} \\ FOLLOW(B) &= \{y, \epsilon\} \end{align}

• Why is FOLLOW(B) just ϵ? I would have thought that since A(A(B(y))B(y)) is a valid parse tree that FOLLOW(B) should include y. – ChaseMedallion Jan 12 at 22:47
• @chase: quite right, fixed. – rici Jan 12 at 23:08
• @chase: by the way, it's usually easier to think in terms of derivations (which is how all the concepts are defined) than parse trees. The derivation I missed was $A\to AB\to ABB\to ABy$. – rici Jan 13 at 0:09

A variable is nullable if you can derive the empty word from it. Hence, in your example, $$A$$ is not nullable. However, if you add a rule as, for example,

$$A \to B$$ then it is, as $$A\Rightarrow B\Rightarrow \varepsilon$$.