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

New contributor
ChaseMedallion is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.

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

  • $\begingroup$ 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. $\endgroup$ – ChaseMedallion Jan 12 at 22:47
  • $\begingroup$ @chase: quite right, fixed. $\endgroup$ – rici Jan 12 at 23:08
  • $\begingroup$ @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$. $\endgroup$ – 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$.


Your Answer

ChaseMedallion is a new contributor. Be nice, and check out our Code of Conduct.

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.