# Quickly finding empty-string producing nonterminals in a CFG

For a given context free language G, we call a nonterminal $A_i$ nullable if $A_i \rightarrow^* \epsilon$, ie we can derive the empty string from $A_i$ after applying a finite number of productions.

There is a simple algorithm for determining which nonterminals of a grammar are nullable as can be found here:

We start by considering all nonterminals as not nullable. We mark all $A_i$ as nullable if there is a production $A_i \rightarrow \epsilon$. We then loop over all other productions $A_i \rightarrow B_1 B_2 \dots B_k$ excluding productions with a terminal in them, and mark $A_i$ as nullable if all $B_i$ are nullable. We keep doing this loop until we finish a loop without marking any nonterminals as nullable.

My problem with this algorithm is that it has a $O(n^2)$ running time: a worst case is for instance $A_1 \rightarrow A_2$, $A_2 \rightarrow A_3$, $A_3 \rightarrow A_4$, ..., $A_{n-1} \rightarrow A_n$, $A_n \rightarrow \epsilon$.

Is there an algorithm for this problem with a better running time than $O(n^2)$?

• Isn't it elementary to implement that algorithm in linear time? Might this be a homework problem? – Warren Schudy Oct 26 '10 at 17:25
• Are you interested in a certain class of grammars or do you want to tackle arbitrary grammars? – Raphael Oct 26 '10 at 17:31
• I'm interested in tackling arbitrary grammars: I'm implementing an Earley parser, for which it is useful to know if a nonterminal can derive the empty string. My initial reaction was that this should be trivially solvable in linear time, but grammars like $A \rightarrow B$, $B \rightarrow A$ complicate matters. – Alex ten Brink Oct 26 '10 at 23:16
• Do you have a reason to keep such rules in any practical situation? – Raphael Oct 27 '10 at 20:07
• I'm implementing an Earley parser in the manner described here: webhome.cs.uvic.ca/~nigelh/Publications/…. In the approach taken in that paper, at some point one needs to find the nullable nonterminals for a grammar: once these are known it's very easy to adapt the Earley algorithm to handle epsilon productions. – Alex ten Brink Oct 27 '10 at 20:58

In what follows whenever I say "production" I mean to include only those that include no terminals. Build a list, for each non-terminal, of the productions it appears in. For every production $i$ let $c_i$ count how many distinct non-terminals in the right hand side are currently marked non-nullable. Let $Q$ denote a queue of non-terminals that have been marked nullable but not yet processed. Initialize all $c_i$ to the number of distinct non-terminals in the right hand side of production $i$. Initialize all non-terminals to not nullable. For every non-terminal $Z$ generated by production $i$ with $c_i=0$ add $Z$ to $Q$ and mark $Z$ as nullable.
While $Q$ is non-empty, remove an arbitrary non-terminal $X$ from $Q$ and process it as follows. For every production $j$ that $X$ is in, decrement $c_j$. If a $c_j$ becomes zero, check to see if the corresponding non-terminal $Y$ has been marked nullable already. If not, mark $Y$ nullable and add $Y$ to $Q$.