10
$\begingroup$

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

$\endgroup$
5
  • 2
    $\begingroup$ Isn't it elementary to implement that algorithm in linear time? Might this be a homework problem? $\endgroup$ Oct 26, 2010 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, 2010 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$ Oct 26, 2010 at 23:16
  • $\begingroup$ Do you have a reason to keep such rules in any practical situation? $\endgroup$
    – Raphael
    Oct 27, 2010 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$ Oct 27, 2010 at 20:58

1 Answer 1

10
$\begingroup$

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

$\endgroup$
2
  • $\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$ Oct 27, 2010 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$ Oct 27, 2010 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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