[Haskell-cafe] How do you test a parser?

[Andrew Coppin]

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?