title: Representing a multiple pass Abstract Syntax Tree (AST) in C++?
body: <p>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 <a href="http://llvm.org/">LLVM</a> 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 <a href="http://en.wikipedia.org/wiki/Operator-precedence_parser">operator precedence parsing</a>. Note that a pass may leave parts of the structure entirely unchanged.</p>
  
  <p>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.</p>
  
  <p>Note that I am currently using <a href="http://www.boost.org/libs/variant/">Boost Variant</a> instead of normal runtime polymorphism in my AST, and would like a solution to be compatible with it as well.</p>