Representing a multiple pass Abstract Syntax Tree (AST) in C++?
abstract-syntax-tree, c++, compiler-construction, parse-tree
Solution
AST nodes by themselves don't need huge amounts of complexity. I think all this AST node machinery is just overkill.
The problem with ASTs isn't node type safety; its tree shape safety. An AST represents (presumably) some valid instance of some language L. What you ideally want is for transformations on the AST to produce other valid ASTs (instances of the language L). You're not going to guarantee that by guaranteeing that any one node has a valid type; you can only do it by guaranteeing that any tree patch produces a valid tree. And this is very difficult to do if the tree operations are atomic (e.g., "change node that", "replace child", "replace parent") and applied seperately; after several such steps, what precisely can you say about the tree?
This is better done using a kind of tree-rewrite transaction, e.g., source-to-source transformations whose grammatical structure is valid for language L, and which are applied in places that are valid for that transformation.
Most standard program transformation systems do this. They achieve this by holding a model of grammar for L, and checking that the proposed transforms are well-typed. This ensures that transformations of language L to language L stay well-formed.
This is harder to get right if the transformations map from one language A to another language B; if some such transformations are applied, you usually get a tree with mixed types that is not legal in either language. With care, one can define a set of transforms that map all subtrees of language A to language B, and apply them exhaustively; then you want the resulting tree to be well formed for B. You can ensure that by insisting whenever a B-patch is inserted in a mixed tree, if it is adjacent to another B-patch, that the resulting compound B-patch is well formed. This you can do using the same style of grammar checks.
Using these ideas, you can build a system that maps an AST through a series of "representations" (langauges A, B, C, ....) and have some faith that the result tree is well-shaped. This idea generalizes to graph rewrites.
Problem
I am currently exploring designing a compiler that transforms its AST in multiple stages. The idea is that starting from the parse tree, each pass transforms the tree until the resulting AST is optimised and contains all of the required information in each node of the tree required to generate the intermediate code (in this case LLVM IR). A pass over the tree may considerably change its structure, for example changing a list of operators and operands into a hierarchy of ordered operations via operator precedence parsing. Note that a pass may leave parts of the structure entirely unchanged. So, my question is how do I best (read: most easily, with as little repetition as possible) represent an AST that has multiple intermediate representations in C++? I would like node types from each phase's version of the AST to respect their incompatibility at compile time. I believe that the key issue is how should I represent parts of the structure that do not change between passes while avoiding repetitive code? I imagine that this is a problem solved many times in the past by compiler authors. Note that I am currently using Boost Variant instead of normal runtime polymorphism in my AST, and would like a solution to be compatible with it as well.