For a recent personal project, I started working on an interpreter for my own programming language. One of the ground rules I set for myself on this project is that I need to properly test as much of my code as is practical as I develop.
I have scoured the web searching for guides or discussions about testing a parser, but there have been scant few resources that deal with this topic head on. Indeed, the few resources I found essentially suggest a kind of "brute force" approach to testing parsing cases, which ultimately boiled down to the following:
- Produce the Abstract Syntax Tree from the Parser and verify it against a known good AST.
- Produce the Abstract Syntax Tree from the Parser, "serialize" it to something like S-Expressions, and verify the S-Expression against a known good value.
- Produce the Virtual Machine byte-code from the Abstract Syntax Tree and verify against the known good value.
Of the three options I listed, I most prefer the third since it decouples the testing code from the explicit AST structure and seems least prone to bugs in the testing code (testing the equality of arrays of opcodes and values seems less error prone than verifying the equality of nested AST elements).
Still, I am writing the interpreter in C and specifying literals for byte code is tedious and verbose. I was hoping that I might be able to find a more succinct but equally thorough method for specifying test and expected result.
I know a lot of testing frameworks come with builtin support for randomization in testing. I would love if I could somehow specify a few expression pieces and send them randomly into the Parser, rather than writing a few hundred or a few thousand deterministic examples by hand. However, with this strategy it is unclear how I could possibly verify the correctness of the compiler output without essentially rewriting the parser logic in the testing suite as well.
- Am I missing some obvious testing strategies for verifying parser output? Can I write a breadth of tests more succinctly or will I have to code out hundreds or thousands of tests by hand?
- Can I employ randomization for this problem? If so, how?
I know I could use something like a parser generator to generate a working parser. I started this project to learn how all of the different pieces work and work together, so I decided I would write everything by hand.