Generating Sentences *Randomly* Given A CFG

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 utter

Solution 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).