|parent pointers in AST nodes email@example.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 firstname.lastname@example.org (Kenneth 'Bessarion' Boyd) (2009-11-27)|
|Re: parent pointers in AST nodes email@example.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 firstname.lastname@example.org (bartc) (2009-11-30)|
|Re: parent pointers in AST nodes email@example.com (2009-11-30)|
|Re: parent pointers in AST nodes firstname.lastname@example.org (Kaz Kylheku) (2009-12-01)|
|[2 later articles]|
|From:||Robert A Duff <bobduff@shell01.TheWorld.com>|
|Date:||Fri, 27 Nov 2009 12:26:32 -0500|
|Organization:||The World Public Access UNIX, Brookline, MA|
|Posted-Date:||27 Nov 2009 12:55:30 EST|
eliben <email@example.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
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
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
> * 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.
Return to the
Search the comp.compilers archives again.