What's the best way to implement AST using visitor pattern with return value?

Question

I'm trying to implement a simple abstract syntax tree (AST) in C++ using the visitor pattern. Usually a visitor pattern does not handle return value. But in my AST there are expressions nodes which care about the return type and value of its children node. For example, I have a Node structure like this:

class AstNode
{
public:
    virtual void accept(AstNodeVisitor&) = 0;

    void addChild(AstNode* child);
    AstNode* left() { return m_left; }
    AstNode* right() { return m_right; }
...

private:
    AstNode* m_left;
    AstNode* m_right;
};

class CompareNode : public AstNode
{
public:
    virtual void accept(AstNodeVisitor& v)
    {
        v->visitCompareNode(this);
    }

    bool eval(bool lhs, bool rhs) const
    {
        return lhs && rhs;
    }
};

class SumNode : public AstNode
{
public:
    virtual void accept(AstNodeVisitor& v)
    {
        v->visitSumNode(this);
    }

    int eval(int lhs, int rhs) const
    {
        return lhs + rhs;
    }
};

class AstNodeVisitor
{
public:
    ...
    bool visitCompareNode(CompareNode& node)
    {
        // won't work, because accept return void!
        bool lhs = node.left()->accept(*this);
        bool rhs = node.right()->accept(*this);
        return node.eval(lhs, rhs);
    }

    int visitSumNode(Node& node)
    {
        // won't work, because accept return void!
        int lhs = node.left()->accept(*this);
        int rhs = node.right()->accept(*this);
        return node.eval(lhs, rhs);
    }
};

In this case both CompareNode and SumNode are binary operators but they rely on the return type of their children's visit.

As far as I can see to make it work, there are only 2 options:

1. accept can still return void, save the return value in a context object which is passed to each accept and visit function, and use them in the visit function, where I know what type to use. This should work but feels like a hack.

2. make AstNode a template, and accept function a none virtual, but return type depends on template parameter T.But if I do this, I no longer have a common AstNode* class and can't save any AstNode* in the children list.

for example:

template <typename T`>
class AstNode
{
public:
    T accept(AstNodeVisitor&);
    ...
};

So is there a more elegant way to do this? This should be a fairly common problem for people implementing AST walking so I'd like to know what's the best practice.

Thanks.

Answer 1

The Visitor can have member that it can use to store result, something like:

class AstNodeVisitor
{
public:
    void visitCompareNode(CompareNode& node)
    {
        node.left()->accept(*this); // modify b
        bool lhs = b;
        node.right()->accept(*this); // modify b
        bool rhs = b;
        b = node.eval(lhs, rhs);
    }

    void visitSumNode(Node& node)
    {
        node.left()->accept(*this); // modify n
        int lhs = n;
        node.right()->accept(*this);  // modify n
        int rhs = n;
        n = node.eval(lhs, rhs);
    }
private:
    bool b;
    int n;
};

You may also want to save the type of last result or use something like boost::variant.