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?


I don't think it's common.


One compiler that keeps parent pointers in the tree is GNAT
(the gcc Ada compiler).


> 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 that code that follows parent pointers tends to be confusing.
Same reasons that global variables cause trouble. It's usually better
to pass information down the tree as parameters during the tree walk
-- as opposed to wandering off into totally unrelated parts of the
tree.


Parent pointers also raise the possibility of malformed trees -- what if
Parent(X) = Y, but Y has no child X?


If you need to keep track of where you are in a tree walk, you can
keep a stack of pointers. This gives you the parent of the current
node (and grandparent, and so on) -- but not the parent of some
arbitrary node.


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


The stack I mentioned above wastes less space.


- Bob

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