Testing strategies for interpreter language parser

Question

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.

TL;DR?

1. 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?
2. Can I employ randomization for this problem? If so, how?

Note

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.

Answer 1

I would probably write at least two kinds of tests. I would write tests taking known text, and compare it to "AST or error". I would also write tests that take provided ASTs and validate execution, somehow (be that "validate that the right bytecode is generated", with the bytecode engine tested separately; or simply "execute in known state, verify consequent state").

Exactly how you test the AST isn't that critical, either structure comparison or serialisation should work just fine, as long as your serialisation is deterministic.

Answer 2

A pragmatic aproach would be to write an integrationtest with many Test-Examples

Create a big repository of examples for input with corresponding output (result or error message).

The automated test would iterate through the examples and verify that the interpreter output matches the expected output.

 example: valid math calculation
 source: "Sqrt(49)"
 expected errormessage: none
 expected output: "7"

 example: error in math calculation
 source: "sqrt(-1)" 
 expected errormessage: "Illegal Argument exception: Cannot calculate squareroot from negative number"
 expected java output: none

Not a duplicate but closly related: How to use BDD to unit test a compiler?