Re: parent pointers in AST nodes

"eliben" <eliben@gmail.com> wrote in message
> 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've looked at my own code and AST nodes don't use a parent pointer,
presumably because I never do anything exciting with the AST other than just
traverse it top-down and left-right.


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


I don't think the space is an issue, assuming it's running on reasonable
hardware. (How many AST nodes will exist at any one time? 100,000 max?
That's less than 1MB extra. It's even possible the AST node might have
padding bytes that can absorb the pointer)


Just put in the pointer if you think it might be useful. (Although, if a
subtree is shared between different parents, you might have to choose which
one you like best...)


--
Bartc

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