4

I'm writing a compiler for a C-like language, and I'm looking for an elegant way to traverse my abstract syntax tree. I'm trying to implement the Visitor pattern, although I'm not convinced that I'm doing it correctly.

struct Visitor { // Expressions virtual void visit(AsgnExpression&); virtual void visit(ConstantExpression&); ... virtual void visit(Statement&); ... virtual void finished(ASTNode&); protected: virtual void visit(ASTNode&) = 0; };

visit is overloaded for each type, and by default each overload will call visit(ASTNode&) which subclasses are forced to implement. This makes it easier to do quick and dirty things, although defining a visit for each type is tedious. Each subclass of ASTNode must implement an accept method which is used to traverse the tree structure.

class ASTNode { public: virtual ~ASTNode(); virtual void accept(Visitor& visitor) = 0; };

However, this design is quickly becoming tedious because the accept methods are often very similar.

Who should be responsible for traversing the structure, the nodes or the visitor? I'm leaning towards having ASTNode provide an iterator for accessing its children, and then having the visitor traverse the structure. If you have any experience designing Abstract Syntax Trees, please share your wisdom with me!

Improve this question
3
  • 2
    Unfortunately, implementing the Visitor pattern is always tedious. It's one of the most egregious examples of a design pattern that exists solely to work around a limitation introduced by features in certain OO languages (in this case access level). Commented Apr 28, 2014 at 17:15
  • 2
    Is access control really a problem for Visitor? It seems to me that it's a work-around for multiple dispatch. Commented Jan 12, 2015 at 22:18
  • FYI: clang::RecursiveASTVisitor has both VisitFoo functions and TraverseFoo functions, and even WalkUpFromFoo functions that can walk up the class hierarchy, to achieve quite good flexibility. Commented Jun 4, 2024 at 15:40

2 Answers 2

Reset to default
3

Who is responsible for the traversal depends for a large part on the analysis you want to do in your visitors, the details of the language structure and also a part personal preference.

In particular, if there are cases where the visitor to a parent node needs to take an action halfway through the processing of the children, then you must put the traversal logic in the visitor. For example, if your language has a construct where a newly introduced variable is available only in some of the child nodes of the node that introduces the variable.
Another case is when you need a mixture of pre-order and post-order traversal. With traversal in the nodes, each node must call the visitor twice, once before and once after the children. In that case, it might be easier to let the visitor do the traversal.

Otherwise, it is mostly a matter of preference. The traversal can be either in the nodes or in the visitor.

Improve this answer
1

Different problems need different traversal strategies. Therefore my suggestion would be to implement a separate Traverser using the strategy pattern.

The Visitor pattern can require alot of boilerplate code. Its actually well-suited to automated code-generation (see Java's jaxb-visitor). My suggestion is to implement a basic/default visitor that basically does nothing for every node type. Any visitors that are going to do anything interesting should extend the base boilerplate visitor. When a new node type is added to the visitor interface, you only have to provide the empty implementation in the base class. Otherwise, every time you add a new node type you have to hunt-down all the implementations and add the new method.

Improve this answer
1
  • 1
    ALOT Commented Jan 12, 2015 at 21:13

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.