c++ - 使用具有返回值的访问者模式实现 AST 的最佳方法是什么？

Question

我正在尝试使用访问者模式在 C++ 中实现一个简单的抽象语法树 (AST)。通常访问者模式不处理返回值。但是在我的 AST 中有表达式节点关心其子节点的返回类型和值。例如，我有一个这样的节点结构:

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);
    }
};

在这种情况下，CompareNode 和 SumNode 都是二元运算符，但它们依赖于其子节点访问的返回类型。

据我所知，只有两种选择:

1. accept 仍然可以返回 void，将返回值保存在传递给每个 accept 和 visit 函数的上下文对象中，并在 visit 函数中使用它们，我知道要使用什么类型。这应该可行，但感觉像是黑客攻击。

2. 使 AstNode 成为模板，并接受一个非虚拟函数，但返回类型取决于模板参数 T。但是如果我这样做，我不再有一个通用的 AstNode* 类并且无法保存任何 AstNode*在子列表中。

例如:

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

那么有没有更优雅的方式来做到这一点？对于实现 AST 步行的人来说，这应该是一个相当普遍的问题，所以我想知道什么是最佳实践。

谢谢。

Answer 1

访问者可以拥有可用于存储结果的成员，例如:

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;
};

您可能还想保存最后结果的类型或使用类似 boost::variant 的东西。