My question is as simple as the title says -- should I implement AST with parent or not?

Currently I implemented it with parent -- the benefit of that approach is, that whatever I use, I can go up or down without any problem, all I need is some node. And modifications to the tree are also easy, because they are local to given branch.

However... when I look at the profiles, I see, that over 40% of the time is spent on cloning nodes. Clone is necessary, because with parent I cannot attach given node to multiple parents.

The opposite -- no parent -- would eliminate the need for cloning (at least such heavy usage), the tree would be more compact (actually it would be no tree no more, because of shared nodes), but would force me to use some kind navigator class to keep track of nodes when traversing them, and will add a little burden to modifying branches (first I would have to make a local clone :-) and then modify it).

It is hard for me to estimate which approach is better. Oh well, maybe there is some third way? Thank you in advance for help.

  • 1
    Why do you want to attach subtrees to multiple parents? Just to save memory via re-use? Are your parse trees really large enough to justify such a crass hack for efficiency? – Kilian Foth Nov 20 '15 at 16:14
  • @KilianFoth, yes, to save memory (or exactly speaking -- to avoid memory allocation). When I look at AST stats such nodes as "add", "if-control", "function", etc. looks normal, but typenames (and type parameter list for them) nodes simply explode in my AST (because for each expression node I have to compute its type, and with type I have a typename). – greenoldman Nov 20 '15 at 16:29
  • Why are you wanting to navigate up the AST? Most implementations I've seen don't. – Winston Ewert Nov 20 '15 at 17:03
  • @WinstonEwert, first thing that comes to my mind -- to modify the branch. For example I have compound assignment a += b, where a, and b as expression. I have to factor out a sub expressions, to avoid duplicated computation. To achieve this I need a parent of such assignment. – greenoldman Nov 20 '15 at 17:15
  • @greenoldman, where are the duplicated expressions? inside a and b? – Winston Ewert Nov 20 '15 at 17:54

Your immediate problem can be solved by not storing types of expressions as AST nodes. Create a separate type for types. This can be immutable and without parent references so you never have to clone it. There should be no reason to want to navigate from a type to its parent type. It also avoids having your expression types carry around information like token position which makes sense for AST nodes, but not for the type of an expression.

  • Thank you. As I wrote before I need some kind of parent (either provided by AST or by AST navigator). Removing the type from the expression does not change much, because I still have to compute the type, the only difference is I don't store that information. However it is just my prediction, so I will try this, because when cloning "type-less" nodes I will get some savings. In other words, there would be still cloning, but more lightweight. – greenoldman Nov 20 '15 at 17:19
  • 1
    @greenoldman, I'm not suggesting you remove the type from the expression. I'm suggesting that you store the type as something which isn't an AST node. – Winston Ewert Nov 20 '15 at 17:52
  • Btw. you wrote "Most implementations I've seen don't." -- do you remember some of them good for educational purposes, I tried with implementation in Ocaml, F#, and C but all of them are unreadable for me. – greenoldman Nov 20 '15 at 18:04
  • For the record, I am following your advice and despite the work is not finished I can see big improvements. Putting everything in AST may seem nice, but it is an overkill when it comes to memory. So once again thank you! – greenoldman Nov 21 '15 at 11:30

In general, trees should not know about their parents.

As you traverse the tree, you can see all children (and their children, and so on) to know if you need to do some work. Deciding once you get to the children that you need to go back is sloppy, and makes many algorithms more difficult/complex. And by keeping the knowledge in one direction, you reduce coupling, with all of the benefits that entails.

  • Thank you, however I asked about parents in context of making savings on node count. Removing parent in order to preprocessing child in its parent is something different and it would add more work. For example -- I detect compound assignment in assignment nodes, but if it should be preprocessed, it would mean I should detect it one level earlier, meaning I would have such detection in multiple nodes -- function calls, ifs, loops, you name it. – greenoldman Nov 21 '15 at 7:34

Not the answer you're looking for? Browse other questions tagged or ask your own question.