Re: parent pointers in AST nodes

On 2009-11-27, eliben <eliben@gmail.com> wrote:
> When implementing an AST for some language, each AST node typically
> holds information about the language construct it represents and
> pointers to children nodes (such as a binary op node pointing to its
> left-hand and right-hand operands).
>
> Is it common / useful to supply a pointer to the node's parent as
> well?


It's a very poor idea.


> In favor:
> * This can simplify some AST processing tasks, especially when using
> the visitor pattern - we may get to an interesting node and then need
> to look at its ancestors to do the required analysis.


You can easily pass down a chain of parent link pointers during
traversal as an extra argument, which give you a path all the way
to the root.


> Against:
> * Maintaining parent nodes makes the AST creation code more complex
> * Wastes space (another pointer for each node)


* No easy functional programming:


Given a set of AST's, you can't construct a new AST which has those AST's as
its children, without destructively manipulating the parent pointers of these
children.


This is a non-starter if the children already have existing parents.


Which means that you can't functionally transform one AST into another, such
that the new one re-uses pieces of the original. You must do a full copy of
every AST, just so that it can have its own parent.


By the way, why would you manipulate AST's in a language that needs the visitor
pattern to emulate double dispatch? Don't tear your hair out; arm yourself with
a decent dynamic language.


If you have multiple dispatch, the visitor pattern pops out of a simple
functional traversal of the tree structure. The tree walker simply knows
how to walk the tree; it applies a caller-supplied function to every node.


That function can be a lambda function which invokes a generic function
on the node, plus some additional arguments. The generic function dispatches
on the run-time type of all generic arguments, and there goes the
visitor pattern.


    (walk-tree ast (lambda (node) (frobnicate node context-object)))


walk-tree visits every node of ast, invoking (lambda (node) ...) on it,
which invokes the function (frobnicate node context-object).
This may be a generic function which is dispatched based on the
class of node and the class of context-object.


Visitor Pattern disappears into one line of code.


So why would you even think about what kinds of compromises to make
in your data structure design for the sake of some pattern?

Return to the comp.compilers page.
Search the comp.compilers archives again.