How to write Visitor Pattern for a Abstract Syntax

Question

I have to write a visitor pattern to navigate the AST. Can anyone tell me more how would I start writing it? As far as I understand, each Node in AST would have visit() method (?) that would somehow get called (from where?). That about concludes my understanding. To simplify everything, suppose I have nodes Root, Expression, Number, Op and the tree looks like this:

      Root
        |
       Op(+)
      /   \
     /     \
 Number(5)  \
             Op(*)
             /   \
            /     \
           /       \
       Number(2)   Number(444)

Answer 1

Pattern visitor is a design pattern that allows you to implement arbitrary operations (implemented as visitors) on the parse tree( eg. Type-checking ) without having to modify the implementation of the nodes of the parse tree.

It can be implemented in the following way (i am using pseudocode):

First you need to define the base-class of the tree's nodes that all nodes have to implement.

abstract class VisitableNode {
   abstract void accept( Visitor v );
}

The only method that node classes must implement is the accept method.

Then you should define the base-class of a visitor node of your parse-tree.

abstract class Visitor {
   abstract void visit( Root rootNode );
   abstract void visit( Op opNode );
   abstract void visit( Number number );
}

Note that visitor's base-class is made for your parse tree only, and should have one visit method for every node type you define in your parse tree.

Then, you should let your node classes implementation extend the VisitableNode class in the following way:

class Root : VisitableNode {
   [...]
   void accept( Visitor v ) {
      v.visit(this);
   }
}

class Op : VisitableNode {
   [...]
   void accept( Visitor v ) {
      v.visit(this);
   }
}

class Number : VisitableNode {
   [...]
   void accept( Visitor v ) {
      v.visit(this);
   }
}

Now you have your parse-tree structure that should not change, and you are free to implement as many visitors (operations) as you like.

In order to do type checking, you will have to store a type inside the Number class together with your value, or otherwise have a Number class for every type you support: NumberFloat, NumberInteger, NumberDouble, etc.

As an example, let's assume that you have a way to infer the static type of the value from your Number class.

I will also assume that you can access to node's children by method getChild(int childIndex).

Finally, i will use a class Type that trivially represents a static Type you intend to support (like Float, Integer, etc...).

class TypeCheckVisitor : Visitor {

   // Field used to save resulting type of a visit
   Type resultType;


   void visit( Root rootNode )
   {
      rootNode.getChild(0).accept( this );
   }

   void visit( Op opNode )
   {
      opNode.getChild(0).accept( this );
      Type type1 = resultType;

      opNode.getChild(1).accept( this );
      Type type2 = resultType;

      // Type check
      if( !type1.isCompatible( type2 ) ){
         // Produce type error
      }

      // Saves the return type of this OP (ex. Int + Int would return Int)
      resultType = typeTableLookup( opNode.getOperator(), type1, type2 );
   }

   void visit( Number number )
   {
      // Saves the type of this number as result
      resultType = number.getType();
   }
}

Then, you would implement the Type class probably as an enum in a way similar to:

enum Type {
   Double,
   Float,
   Integer;

   boolean isCompatible(Type type1, Type type2){
      // Lookup some type table to determine types compatibility
   }
}

And finally you only need to implement your type tables and operator tables.

EDIT: In the visit recursion, it is actually correct to recur using the accept method of the nodes on which you want to recur.

As for the usage, you can perform type checking on the root node of the parse tree (and simultaneously determine the expression's type) by:

TypeCheckVisitor v = new TypeCheckVisitor();
rootNode.accept( v );
print( "Root type is: " + v.resultType );

You can also type-check an arbitrary node of the parse tree different from the root in the same way.