Visitor Pattern – Implementing for an Abstract Syntax Tree

parsingtreesvisitor-pattern

I'm in the process of creating my own programming language, which I do for learning purposes. I already wrote the lexer and a recursive descent parser for a subset of my language (I currently support mathematical expressions, such as + - * / and parenthesis). The parser hands me back an Abstract Syntax Tree, on which I call the Evaluate method to get the result of the expression. Everything works fine. Here is approximately my current situation (Code examples in C#, although this is pretty much language-agnostic):

public abstract class Node
{
    public abstract Double Evaluate();
}

public class OperationNode : Node
{
    public Node Left { get; set; }
    private String Operator { get; set; }
    private Node Right { get; set; }

    public Double Evaluate()
    {
        if (Operator == "+")
            return Left.Evaluate() + Right.Evaluate();

        //Same logic for the other operators
    }
}

public class NumberNode : Node
{
    public Double Value { get; set; }

    public Double Evaluate()
    {
        return Value;
    }
}

However, I would like to decouple the algorithm from the tree nodes because I want to apply Open/Closed Principle so I don't have to reopen every node class when I want to implement code generation for example. I read that the Visitor Pattern is good for that. I have a good understanding of how the pattern works and that using double dispatch is the way to go. But due to the recursive nature of the tree, I'm not sure how I should approach it. Here is what my Visitor would look like:

public class AstEvaluationVisitor
{
    public void VisitOperation(OperationNode node)
    {
        // Here is where I operate on the operation node.
        // How do I implement this method?
        // OperationNode has two child nodes, which may have other children
        // How do I work the Visitor Pattern around a recursive structure?

        // Should I access children nodes here and call their Accept method so they get visited? 
        // Or should their Accept method be called from their parent's Accept?
    }

    // Other Visit implementation by Node type
}

So this is my problem. I want to tackle it immediately while my language does not support a lot of functionnality to avoid having a bigger problem later.

I did not post this to StackOverflow because I don't want you to provide an implementation. I only want you to share ideas and concepts that I might have missed, and how I should approach this.

Best Answer

It is up to the visitor implementation to decide whether to visit child nodes and in which order. That's the whole point of the visitor pattern.

In order to adapt the visitor for more situations it is helpful (and quite common) to use generics like this (it's Java):

public interface ExpressionNodeVisitor<R, P> {
    R visitNumber(NumberNode number, P p);
    R visitBinary(BinaryNode expression, P p);
    // ...
}

And an accept method would look like this:

public interface ExpressionNode extends Node {
    <R, P> R accept(ExpressionNodeVisitor<R, P> visitor, P p);
    // ...
}

This allows to pass additional parameters to visitor and retrieve a result from it. So, the expression evaluation can be implemented like this:

public class EvaluatingVisitor
    implements ExpressionNodeVisitor<Double, Void> {
    public Double visitNumber(NumberNode number, Void p) {
        // Parse the number and return it.
        return Double.valueOf(number.getText());
    }
    public Double visitBinary(BinaryNode binary, Void p) {
        switch (binary.getOperator()) {
        case '+':
            return binary.getLeftOperand().accept(this, p)
                + binary.getRightOperand().accept(this, p);
        // More cases for other operators here.
        }
    }
}

The accept method parameter isn't used in the above example, but just believe me: it is quite useful to have one. For example, it can be a Logger instance to report errors to.

Related Topic