Generating Sentences *Randomly* Given a CFG

Question

I want to generate sentences randomly from a given context-free grammar.

Randomly is the important part because my grammar is quite large, and NLTK generates all the possible utterances which falls short on recursions (i.e. E -> A E) and takes too long to generate "interesting" utterances in short time (interesting being unlike the other utterances preceding the current one).

Are there any Python libraries for that? Thanks!

Answer 1

NLTK doesn't provide a method to generate random sentences from a grammar, although as indicated in this related SO question, How to use NLTK to generate sentences from an induced grammar?, it can generate random sentences from trigrams.

If you want to write your own Python function, you might be interested in this 1997 paper by Bruce Mackenzie, Generating Strings at Random from a Context Free Grammar. (I found the link in this answer to a different SO question.) The algorithm involves precomputing weights in an O(N²) preprocessing step, and requires that the grammar have no epsilon productions (productions that expand to the empty string).