How to use BDD to unit test a compiler?

Question

My team is writing a compiler for a domain-specific language (DSL) which will be integrated into an IDE. Right now, we are focused on the analysis phase of the compiler. We are not using any existing parser-generators (such as ANTLR) because we need real-time performance and highly detailed error/warning/message information. We have

1. classes, each of which represents a node in the concrete syntax tree for the language, as well as
2. classes which act as annotations for each node (i.e., for errors and additional information), as well as
3. internal classes which build and manipulate the concrete syntax tree (i.e., lexer, parser, cache for strings, syntax visitors).

We are trying to decide on an overall strategy for organizing our tests. Our company is pushing behavior-driven development (BDD) and domain-driven design (DDD). Although we are building a DSL for our company’s domain, the domain of the compiler is a programming language.

We are still in the process of building the compiler and have some tests already. We are aiming to have 100% statement coverage.

We currently have tests in which we input source code to the syntax tree builder, and then run a verification on each property of every node of the resultant syntax tree to make sure that the expected information (line number, relevant error(s), child/parent tokens, width of token, type of token, etc.). Now, since each node is its own class, and certain annotations and errors attached to a node are separate classes, this test ends up referencing many classes.

We currently have tests for certain classes such as the lexer in which we can isolate the input (a string) and the output (a list of tokens) from other classes (e.g., the classes for the nodes of the syntax tree). These tests are more granular.

Now, the tests in the paragraph immediately above can be put in correspondence with the class under test (e.g., lexer, string cache). However, the tests from the second paragraph above really test the whole analysis phase of the compiler; that is, each test can have well over 300 assertions for the syntax tree, given the input source code. The tests are for the behavior of the analysis phase.

Is this an appropriate testing strategy? If not, what should we be doing differently? What organization strategy should we use for our tests?

Answer 1

  > Is this an appropriate testing strategy?

No, because the your subdomain is a DSL (a kind of programming language) and your compiler is part of an implementation detail for the use case that allows to automate actions/workflows in this domain using the DSL.

Since I do not know how your DSL looks like I assume that you have concepts like loop, condition, statement, variable using the example

 for(int i=1;i =< 10;i++) {subtask();}

Using a bdd-gherkin like language you could write something like

as a automation user
i want to have a for loop with startvalue, endvalue, loopincrement
so that i can repeat subtasks several times.

given startvalue=1
and endvalue = 10
and loopinclrement = 1
when i execute for(int i=%startvalue%;i =< %endvalue %;i+=%loopinclrement%)
then the subtask should have been executet 10 times.

This is quite a lot of work to prove that your compiler works as expected.

  > If not, what should we be doing differently? 
  > What organization strategy should we use for our tests?

I would create a big repository of examples for input with corresponding output.

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

Example: if your invoice/order-related dsl compiles to java a repository entry would look like:

 example: loop over orderentries
 dsl-source: foreach orderitem in orders do calculateTaxes(orderitem)
 expected errormessage: none
 expected java output: for(OrderItemType orderitem : orders) 
                          {calculateTaxes(orderitem);}

 example: loop with syntax errors
 dsl-source: foreach orderitem in orders 
 expected errormessage: missing "do"-keyword in line 1
 expected java output: none

So instead of writing a lot of code to fit bdd you simply have to add examples of hardcoded input/output values.