Best design for generating code from an AST?

Question

I'm working on a pretty complex DSL that I want to compile down into a few high level languages. The whole process has been a learning experience. The compiler is written in java.

I was wondering if anyone knew a best practice for the design of the code generator portion. I currently have everything parsed into an abstract syntax tree.

I was thinking of using a template system, but I haven't researched that direction too far yet as I would like to hear some wisdom first from stack overflow.

Thanks!

Answer 1

When I was doing this back in my programming languages class, we ended up using emitters based on following the Visitor pattern. It worked pretty well - makes retargeting it to new output languages pretty easy, as long as your AST matches what you're printing fairly well.

Answer 2

DSL is a nice thing. And writing them is a good practice.

But I am not sure that implementing your own YACC and similar is a good choice in 2010, unless it is just for fun or educational.

When you will finish your educational process and will start looking for a nice way of implementing your DSLs, you can consider using dynamic languages.

By using Groovy for instance you can implement your small and big DSLs very easy and in enjoyable way.
BTW Groovy has built in AST manipulation api.

Answer 3

What you really want is a program transformation system, that maps syntax structures in one language (your DSL) into syntax patterns in other langauges. Such a tool can carry out arbitrary transformations (tree-rewrites generalize string-rewrites which are Post systems which are full Turing capable) during the code generation project, which means that what you generate and how sophisticated your generation process is determined only by your ambition, not by "code generator framework" properties.

Sophtisticated program transformation systems combine various types of scoping, flow analysis and/or custom analyzers to enable the tranformations. This doesn't add any theoretical power, but it adds a lot of practical power: most real languages (even DSLs) have namespaces, control and data flow, need type inference, etc. etc.

Our DMS Software Reengineering Toolkit is this type of transformation system. It has been used to analyze/transform both conventional languages and DSLs, for simple and complex languages, and for small, large and even huge software systems.

Related to comments by OP about "turning the AST into other languages", that is accomplished by DMS by writing transformations that map surface syntax for the DSL (implemented behind the scenes his DSL's AST) to surface syntax for the target language (implemented using target language ASTs). The resulting target langauge AST is then prettyprinted automatically by DMS to provide actual source code in the target language, that corresponds to the target AST.

Answer 4

If you are already using ANTLR and have your AST ready you might want to take a look at StringTemplate: http://www.antlr.org/wiki/display/ST/StringTemplate+Documentation

Also Section 9.6 of The Definitive ANTLR Reference: Building Domain-Specific Languages explains this: http://www.pragprog.com/titles/tpantlr/the-definitive-antlr-reference

The free code samples are available at http://media.pragprog.com/titles/tpantlr/code/tpantlr-code.tgz. In the subfolder code\templates\generator\2pass\ you'll find an example converting mathematical expressions to java bytecode.