[Haskell-cafe] How do you test a parser?
andrewcoppin at btinternet.com
Sat Jun 11 15:10:51 CEST 2011
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
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?
More information about the Haskell-Cafe