Re: parent pointers in AST nodes

eliben <eliben@gmail.com> writes:


> 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?
>
> 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.


I find the visitor pattern non-intuitive for AST processing. A set of
mutually recursive functions (one for each syntactic category, i.e., one
for expressions, one for statements etc.) that each do case analysis
over the node type and calls recursively on children nodes is much more
intuitive.


> Against:
> * Maintaining parent nodes makes the AST creation code more complex


Even more of a problem is that rewriting the AST becomes more complex,
and you can't share subtrees between several parents (unless you use a
list of parent pointers).


> * Wastes space (another pointer for each node)


That is hardly an issue. Having to maintain an extra invariant is more
of an issue.


> What are your thoughts?


I can't really see any cases where it would be worth the effort.


Torben

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