Testing Parsec parsers by generating inputs with QuickCheck

Question

I'd like to write tests for a suite of Parsec parsers. Here's a simple example of a parser I want to test with QuickCheck:

identifier = do
  c <- letter
  cs <- many (alphaNum <|> oneOf identSymbols)
  skipSpaces
  return $ Ident $ c:cs

So, ideally, I'd want QuickCheck to generate valid identifiers and make sure I get the right results back, as well as generating invalid identifiers and making sure they return ParseError. Are there any utilities that would make this sort of thing easier? Is there a way I can "run my parser in reverse", so to speak, to generate such inputs?

In general, what would a good suite of QuickCheck tests for this parser look like? To some extent, it seems like I'd basically have to duplicate the logic of the parser in QuickCheck to achieve a thorough test. Is that really a good idea, or this perhaps a situation where a more traditional tool like HUnit is more suitable than QuickCheck?

Tenuis

Answer 1

In general, the reverse of a parser is a pretty printer, and the reverse of random input to a parser, is random pretty printing of an AST.

So, follow the usual approach and define an Arbitrary instance for your AST, which drives random well-formed syntax fragments. Mix in some erroneous characters as a wrapper to test for error handling.

See also:

• Automated Testing of Java ABNF Grammar Parsers with QuickCheck
• Automatic Testing of Higher Order Functions - parser testing in Clean with QC.

Gage

A particular property that i like to use is that parse = parse . pretty . parse. This serves as a decent way to model the quotienting of information by the parser, there is a nice adjunction to drive it from a theoretical perspective, and it captures the fact that pretty . parse is idempotent, if not the identity function. (Usually parsing discards some information) – Pegeen

last two links are dead – Crankpin

@AlexHirzel Fixed! (pending approval) – Antoniettaantonin