Generating n statements from context-free grammars

Question

So not to reinvent the wheel, I would like to know what has already been done about generating random statements from a context-free language (like those produced by yacc, etc.). These grammars are primarily for parsing, but maybe someone has done some generation for testing the parsers? Thanks

Answer 1

Check out this blog post. Basically, it randomizes the RHS chosen at each rule application.

Answer 2

There's an ancient but still interesting article here that shows why you need a few more constraints for effective generation of random sentences than you do for parsing -- it also suggests a simple way of providing those extra constraints and gives a complete example program (...in Fortran IV... but, hey, it is over 40 years old...!-).

Unfortunately I am not aware of any more recent work on this subject (or implementations in more modern languages -- but transcoding the Fortran dusty deck to whatever language you like best shouldn't be as hard as coming up with these concepts on one's own;-) -- this is just the kind of already-ancient stuff I perused in actual paper-based libraries back when I was in college, and I'm amazed that the ACM's online search facilities allowed me to locate the reference I vaguely remembered, so rapidly (kudos, ACM!-). I have never done any original research on this subject.