Re: parent pointers in AST nodes

Robert A Duff <bobduff@shell01.TheWorld.com>
Fri, 27 Nov 2009 12:26:32 -0500

          From comp.compilers

Related articles
parent pointers in AST nodes eliben@gmail.com (eliben) (2009-11-27)
Re: parent pointers in AST nodes bobduff@shell01.TheWorld.com (Robert A Duff) (2009-11-27)
Re: parent pointers in AST nodes zaimoni@zaimoni.com (Kenneth 'Bessarion' Boyd) (2009-11-27)
Re: parent pointers in AST nodes idbaxter@semdesigns.com (Ira Baxter) (2009-11-27)
Re: parent pointers in AST nodes DrDiettrich1@aol.com (Hans-Peter Diettrich) (2009-11-28)
Re: parent pointers in AST nodes bartc@freeuk.com (bartc) (2009-11-30)
Re: parent pointers in AST nodes torbenm@diku.dk (2009-11-30)
Re: parent pointers in AST nodes kkylheku@gmail.com (Kaz Kylheku) (2009-12-01)
[2 later articles]
| List of all articles for this month |

From: Robert A Duff <bobduff@shell01.TheWorld.com>
Newsgroups: comp.compilers
Date: Fri, 27 Nov 2009 12:26:32 -0500
Organization: The World Public Access UNIX, Brookline, MA
References: 09-11-060
Keywords: AST
Posted-Date: 27 Nov 2009 12:55:30 EST

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


Post a followup to this message

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