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)$?

  • 2
    $\begingroup$ Isn't it elementary to implement that algorithm in linear time? Might this be a homework problem? $\endgroup$ – Warren Schudy Oct 26 '10 at 17:25
  • $\begingroup$ Are you interested in a certain class of grammars or do you want to tackle arbitrary grammars? $\endgroup$ – Raphael Oct 26 '10 at 17:31
  • 1
    $\begingroup$ 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. $\endgroup$ – Alex ten Brink Oct 26 '10 at 23:16
  • $\begingroup$ Do you have a reason to keep such rules in any practical situation? $\endgroup$ – Raphael Oct 27 '10 at 20:07
  • 1
    $\begingroup$ 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. $\endgroup$ – Alex ten Brink Oct 27 '10 at 20:58

Can't one implement that algorithm in linear time as follows? (Warning I haven't proof-read this too carefully, so bugs are likely.)

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

  • $\begingroup$ Unless I'm missing something I think your algorithm should work. I just find it very odd that if I search the internet for an algorithm for this problem, I get over half a dozen hits on the first page describing some variation of the algorithm I described in my first post - why give a n-squared algorithm if a simple linear algorithm exists? $\endgroup$ – Alex ten Brink Oct 27 '10 at 0:05
  • $\begingroup$ One likely reason for giving the quadratic algorithm is that it's even simpler. If you just want to give people an understanding of nullability hiding implementation details makes sense. $\endgroup$ – Warren Schudy Oct 27 '10 at 14:46

Your Answer

