|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)|
|Re: parent pointers in AST nodes email@example.com (Quinn Tyler Jackson) (2009-12-01)|
|Re: parent pointers in AST nodes firstname.lastname@example.org (Gary Oblock) (2009-12-14)|
|From:||email@example.com (Torben Ęgidius Mogensen)|
|Date:||Mon, 30 Nov 2009 16:11:36 +0100|
|Organization:||Department of Computer Science, University of Copenhagen|
|Posted-Date:||30 Nov 2009 23:52:43 EST|
eliben <firstname.lastname@example.org> 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
> 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
> * 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.
Return to the
Search the comp.compilers archives again.