Draft Tree

Intro

I like blogging about different design patterns, algorithms and approaches to solving different problems. This time I'll describe a problem I ran into some time ago and the approach I found to solve it. I always do not claim to have found a unique and absolutely perfect solution by myself. But I like the idea of keeping and reusing successful and interesting approaches to solving problems. Even if the code cannot be reused the idea itself is often very useful. This is not exactly a design pattern in the classical sense but it is more like a "design approach". But I'll describe it as a design pattern.

Motivation

If one wants to work with a DSL these days he or she usually has to use Antlr. This tool is free (BSD license) but is very useful. The grammars are simple enough. The code can be generated for Java, Javascript and other languages. In fact it is the tool of choice for anyone who wants to take on some DSL-related work.

When the grammar is complete and working well what the user has is the grammar tree. It looks like this:

This example is a logical expression from a simple grammar that parses logical expressions. The tree shows the grammar tree for 1 > 0 OR x < Y AND 10 > Z2. 

Antlr offers great tools to work with these trees: Listeners and Visitors. Listeners fire when a node is encountered and visitors visit nodes one by one. These tools are really great and help a lot. 

But what if the transformation one is trying to accomplish cannot be achieved with Antlr's listeners and visitors? This could be the case if the DSL structure is significantly different from the structure one is trying to achieve (we'll call it 'code structure' from now on. The implication is that the DSL is transformed into source code). 

Some people may try to modify the Antlr tree a little, some may add more complicated listeners/visitors. In this blog post I'll argue that there is a better solution.

Applicability

Use this pattern when you need to perform complicated transformations on the Antlr tree that are hard to accomplish directly with a listener or visitor.

Structure

There is a simple and elegant solution to this problem. We need to introduce an intermediate tree structure. In Java this can be accomplished with the class DefaultMutableTreeNode and other classes from javax.swing.tree. The API may look a bit old-fashioned with Enumeration and no generics but it works. The first tree instance is a copy of the Antlr tree with proper user objects in the nodes. Then we can slowly modify this tree step by step to make it look closer to the code structure. Usually if this structure is used there is no need to do it all in one step. Here is an example of the transformation:

This intermediate tree is like a draft that needs to be improved. After some steps it is ready to be transformed into the final code structure. 

Consequences

1. Simplicity. The process of transforming the DSL into the code structure can be defined as simple, concise operations on the draft tree. This makes the transformation code less complex. The implementation may even use a modified version of the Assembly Line pattern.
2. Loose coupling. All the operations on the draft tree are independent of the original DSL and the final code structure. If either the DSL or the code structure has to be modified the draft tree can be adapted to the new form by adding or removing steps. There is not tight coupling between the DSL and the code structure.

Final Thoughts

No sample code can be provided in this case because any code will be more specific than the design approach itself.