Re: parent pointers in AST nodes

On Nov 27, 7:32 am, eliben <eli...@gmail.com> wrote:
> Hello,
>
> 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 have no idea in general (haven't looked at that many compiler source
codes in detail yet.)


> 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.
>
> Against:
> * Maintaining parent nodes makes the AST creation code more complex
> * Wastes space (another pointer for each node)


With good design the programmer-time cost for maintaining the parent
nodes is basically a one-off time cost. In that case, I don't find
"making the AST creation code more complex" something that would deter
me. If one has an actual AST transform that this helps and have no
specification issues preventing it, I'd proceed regardless of the
listed negatives.


What I don't know, is how common backtracking to parent nodes is in
actual implementations. (Yes, I'm lazy -- I haven't actually
inspected the source code for the obviously open source compilers like
GCC, CLang, and TCC.)


I know I have never had to do that so far in implementing my vaporware
compiler Z.C++ for C and C++. Z.C++'s AST nodes [
http://svn.berlios.de/wsvn/zcplusplus/trunk/ParseTree.hpp ] are
"flat": one or two signature tokens, and as many prefix, infix, and
postfix nodes as memory allows. As the "signature tokens" and
existence/absence of prefix/infix/postfix nodes define interesting
nodes, backtracking is designed out of this AST representation.

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