1
$\begingroup$

Some particularly degenerate CFGs can produce a single string in infinitely many ways: for a dumb example, $S \to SS \mid \epsilon$ can produce the empty string as $S \to \epsilon$ or $S \to SS \to S \to \epsilon$, etc.

I'm writing a general CFG parser which can produce all the different parses for a given string, but obviously it chokes on examples like the above. I'd like to be able to detect when there may be infinitely many parses for a string, rather than just looping forever. Can I, and, if so, how?

My intuition is that a grammar has this property if and only if there is some non-useless nonterminal A (ie, A is used in the production of some string in the language of the CFG) which can produce itself via some chain of productions such that all of the other symbols produced by following that chain are nullable nonterminals of A itself. But I don't know if this is correct, and I'm not sure how to detect it.

(A nonterminal B is nullable if $B \to^* \epsilon$, ie, some series of productions replaces the symbol with the empty string.)

Improve this question
$\endgroup$
6
  • $\begingroup$ The answer you accepted is good. However, this is not needed to produce a general CF parser. It is perfectly possible to parse any string, even when it has infinitely many parses, and to describe in a finite form the set of parses (even when infinite). You can then easily list parts of that infinite set if you choose to. $\endgroup$
    – babou
    Commented Apr 2, 2015 at 8:36
  • $\begingroup$ @babou : I might add that at some point, but I can't think of a better way of doing it than checking to see when a nonterminal may derive itself per below, cutting it off, and making a note that the parse may be extended indefinitely by adding iterations of the loop. Is there a better and/or more standard way of doing it? (For reference, I'm writing an Earley parser.) $\endgroup$
    – Bakkot
    Commented Apr 2, 2015 at 15:20
  • $\begingroup$ Yes, there is a better way, unless you are actually trying to enumerate all the parses, which is the very thing you should avoid doing. Earley build a linked structure representing all the parses, and all you need is to add a loop (appropriately) in that linked structure which is otherwise a DAG. This structure is always finite, but can be used to enumerate parses, even when there are infinitely many parses. This may be useful when you intend further processing of all the parse-trees. Earley parsers are not the simplest, and use a somewhat complicated structure for parses. $\endgroup$
    – babou
    Commented Apr 2, 2015 at 15:34
  • $\begingroup$ I am in fact trying to enumerate all parses, when that's possible. The tool is intended for students who are just being introduced to CFGs, and I think it's more useful to see "here are all of the ways the grammar you have given can derive the string you have given" than "here is a graph representing all parses". $\endgroup$
    – Bakkot
    Commented Apr 2, 2015 at 15:40
  • $\begingroup$ Even with your goal. Earley's algorithm will not naturally enumerate parses. It is best to first build the graph, and then to use it to enumerate the parses. Earley's graph is a bit messy, too much for students imho. But there are simpler forms that actually show the structure of ambiguity (provided there is not too much ambiguity turning it into a spaghetti dish). $\endgroup$
    – babou
    Commented Apr 2, 2015 at 16:01

1 Answer 1

Reset to default
2
$\begingroup$

If a nonterminal can derive itself ($A \to A$) then you can have an infinite number of derivations deriving whatever else that nonterminal can derive. There is no need for it or any other nonterminal to derive $\epsilon$ (unless you are only concerned with an infinite number of parses for the empty string.)

In other words,

$$A \to A \mid a$$

can produce infinitely many parses for the string $a$. By contrast,

$$A \to A A \mid a$$

can only produce exponentially many parses for the string $a^n$.

As far as I know, the existence of a useful nonterminal which can (possibly indirectly) derive itself is necessary and sufficient for the existence of an infinite number of possible parses.

It's easy to detect whether a nonterminal can derive itself. First, use the standard algorithm to find all nullable nonterminals. Then define the relation $$ R = \{ (A, B) \mid A \to \omega B \chi \wedge \omega \to \epsilon \wedge \chi \to \epsilon \}$$ which you can do in linear time by scanning all the productions keeping track of nullability.

Then construct $R^+$. If it contains $(A, A)$ for any nonterminal, you have a possibly indirect self-derivation.

Improve this answer
$\endgroup$
2
  • $\begingroup$ That make sense (though I'd love a cite), but I'm still not sure how to check if a terminal derives itself indirectly, as in the example I give. $\endgroup$
    – Bakkot
    Commented Apr 2, 2015 at 5:22
  • $\begingroup$ @Bakkot: I don't have a cite, but I think the proof is not difficult. It's clear that self-derivation is sufficient for an infinite number of derivations; the necessary part is absolutely clear if there are no nullable productions (without nullables, a derivation chain is monotonically non-shortening, and you can only have an infinite chain if there is some cycle). The same argument should work with nullables but the formalisation won't fit in a comment. I'll add the detection algorithm; it's not hard. $\endgroup$
    – rici
    Commented Apr 2, 2015 at 5:34

Your Answer

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

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