OK, so suppose you sit down and write a complicated string parser. Now how do you test that it works correctly? One way is to run the parser over a large corpus of "real world" samples. This has a number of problems: * If the parser is for a grammar you just invented yourself, presumably no "real world" corpus exists yet. * This tests that the most commonly used features work OK, but might not test whether more obscure features work right. * There's no really obvious way to check that what the parser returns is /correct/. You've got the input, but there's nothing to compare with. * This probably doesn't test whether the parser /fails/ for invalid input, since a real world corpus would presumably consist entirely of valid input. Most people's library of choice appears to be QuickCheck. But while it's not hard to have QuickCheck generate random strings and confirm that the returned parse tree (if any) doesn't violate any invariants, it's not so easy to check that the parse tree is actually what it should be. On top of that, depending on what the grammar is, the vast majority of random strings are probably just parse failures. Even if they aren't, there are probably specific constructs that are special-cased in the parser, which are very unlikely to appear by chance. (Things like keyword names, special combinations of punctuation, etc.) You can try to write your own text generator that constructs text more closely approximating what your parser is supposed to parse. But then how do you tell whether your generator is right? If you have a function that turns a parse tree back into text again, you can try verifying that a round-trip is the identity function. Except perhaps sometimes it isn't. Perhaps a given expression has more than one equivalent representation. A round-trip from string and back again is even less likely to be stable. So what's the best way to attack this problem?