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

Question

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()$.

Answer 1

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}$$

Answer 2

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