BNF grammar test case generation

Question

Does anyone have any experience with a tool that generates test strings from a BNF grammar that could then be fed into a unit test?

Answer 1

I don't have an answer to the tool question, but I will say it is fairly easy in any text processing language (perl/python/etc) to randomly generate sentences from a BNF grammar, and slightly more verbose in a bigger language (Java/C/etc), but it shouldn't be too hard to roll your own.

The problem with this, of course, is that it can only generate strings in the grammar, and unless your grammar is very simple, the test space is infinitely large.

Answer 2

I've done exactly as hazzen commented (using an embedded DSL in a scripting language). It was a mildly interesting exercise, but except for the most basic tests of e.g. parsing, it wasn't terribly useful. Most of my most interesting tests have to do with more sophisticated relationships than one can easily express in BNF (or any other context-free grammar).

Answer 3

If, say, you're developing a compiler, then you likely have an abstract syntax tree datatype. If so, then you could write a function to generate an random AST -- with that, you can print it to a string and feed that to your unit test. It's guaranteed to be a valid program this way, since you started with your AST.

If I were writing a compiler in Haskell or ML, this is what I would do, using QuickCheck.