Abstract Syntax Tree with parent or not? [closed]

Question

Closed. This question is opinion-based. It is not currently accepting answers.

---

Want to improve this question? Update the question so it can be answered with facts and citations by editing this post.

Closed 5 years ago.

Improve this question

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.

Answer 1

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.

Answer 2

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.