Complex tree transformations using cascading tree rewriters

Owned by Anonymous
Last updated: May 05, 2009 by AnonymousVersion comment
2 min read

As you may know, since version 3.1 ANTLR supports rewriting of trees . This is especially useful when you have a very complex transformation from input to output. If so you can bring the input tree closer to the desired output tree with each tree transformation and finally spit out the desired textual output format using templates.

Bird's eye view cookbook

  1. Have a very clear idea what input should be translated to what output.
  2. Start with a lexer and a parser that parses the input and spits out a reasonable AST
  3. Think of reasonable templates for the output
  4. Analyse which data you would need for each template to fill it
  5. Informally make up an idea how a the ideal tree to feed your template would look like
  6. Write down a list of simple modification steps that would transform your initial AST into a tree that comes close to the ideal one you made up
  7. Write a new tree transformer that traverses the AST and spits it out again unmodified
  8. Adapt the new transformer to perform the next modification step
  9. Continue with (7) until you have a tree transformer for each modification step
  10. Add new transformations steps when more complex statements seem to justify this
  11. When you have a transformer for each step, write a tree parser that feeds our templates
  12. After you are functionall done completely, consider performance. Try combining tree transformations to one when performance is not acceptable. Do this thoughtfully as this will most likely make your code less obvious and less maintainable.

Hints

  • Do this in a depth-first manner - start by transforming a simple input to a valid output, then make it more complex and adapt the transformation steps
  • Do not add too many tree transformers as with every change in a transformer's output AST all subsequent transformers need adjustment
  • Tests are crucial. Compare expected transformation output with actual.
  • Consider doing this in a test first manner, as such a transformation task is really complex.

Add your Patterns for tree transformation.