使用具有 return 值的访问者模式实现 AST 的最佳方法是什么？

Question

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

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 都是二元运算符，但它们依赖于子级访问的 return 类型。

据我所知，只有 2 个选项：

accept 仍然可以 return 无效，将 return 值保存在传递给每个接受和访问函数的上下文对象中，并在访问函数中使用它们，我知道要使用什么类型。这应该可行，但感觉像是一个 hack。
使AstNode成为模板，并接受none虚拟函数，但return类型取决于模板参数T.But如果我这样做，我不再有一个共同的 AstNode* class 并且不能在子列表中保存任何 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.

的类型

Answer 2

template<class T> struct tag { using type=T; };
template<class...Ts> struct types { using type=types; }

template<class T>
struct AstVisitable {
  virtual boost::optional<T> accept( tag<T>, AstNodeVisitor&v ) = 0;
  virtual ~AstVisitable() {};
};
template<>
struct AstVisitable<void> {
  virtual void accept( tag<void>, AstNodeVisitor&v ) = 0;
  virtual ~AstVisitable() {};
};
template<class Types>
struct AstVisitables;
template<>
struct AstVisibables<types<>> {
  virtual ~AstVisitables() {};
};
template<class T0, class...Ts>
struct AstVisitables<types<T0, Ts...>>:
  virtual AstVisitable<T0>,
  AstVisitables<types<Ts...>>
{
  using AstVisitable<T0>::accept;
  using AstVisitables<types<Ts...>>::accept;
};

using supported_ast_return_types = types<int, bool, std::string, void>;

class AstNode:public AstVisitables<supported_ast_return_types> {
public:
  void addChild(AstNode* child);
  AstNode* left() { return m_left.get(); }
  AstNode* right() { return m_right.get(); }

private:
  std::unique_ptr<AstNode> m_left;
  std::unique_ptr<AstNode> m_right;
};

template<class types>
struct AstVisiablesFailAll;
template<>
struct AstVisiablesFailAll<> {
  virtual ~AstVisiablesFailAll() {};
};
template<class T>
struct AstVisitableFailure : virtual AstVisitable<T> {
  boost::optional<T> accept( tag<T>, AstNodeVisitor& ) override {
    return {};
  }
};
template<>
struct AstVisitableFailure<void> : virtual AstVisitable<void> {
  void accept( tag<void>, AstNodeVisitor& ) override {
    return;
  }
};
template<class T0, class...Ts>
struct AstVisitablesFailAll<types<T0, Ts...>>:
  AstVisitableFailure<T0>,
  AstVisitableFailAll<types<Ts...>>
{
  using AstVisitableFailure<T0>::accept;
  using AstVisitableFailAll<types<Ts...>>::accept;
};

所以现在你可以 boost::optional<bool> lhs = node.left()->accept( tag<bool>, *this );，并且从 lhs 的状态知道左节点是否可以在 bool 上下文中计算。

SumNode 看起来像这样：

class SumNode :
  public AstNode,
  AstVisiablesFailAll<supported_ast_return_types>
{
public:
  void accept(tag<void>, AstNodeVisitor& v) override
  {
    accept(tag<int>, v );
  }
  boost::optional<int> accept(tag<int>, AstNodeVisitor& v) override
  {
    return v->visitSumNode(this);
  }
  int eval(int lhs, int rhs) const {
    return lhs + rhs;
  }
};

和visitSumNode:

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

以上假定在 void 上下文中访问 a+b 是可以接受的（就像在 C/C++ 中一样）。如果不是，那么您需要一种方法 void 访问 "fail to produce a void".

简而言之，接受需要上下文，这也决定了你期望的类型。失败是一个空的可选。

以上使用boost::optional——std::experimental::optional也可以，或者你可以自己滚，或者你可以定义一个穷人的可选：

template<class T>
struct poor_optional {
  bool empty = true;
  T t;
  explicit operator bool() const { return !empty; }
  bool operator!() const { return !*this; }
  T& operator*() { return t; }
  T const& operator*() const { return t; }
  // 9 default special member functions:
  poor_optional() = default;
  poor_optional(poor_optional const&)=default;
  poor_optional(poor_optional const&&)=default;
  poor_optional(poor_optional &&)=default;
  poor_optional(poor_optional &)=default;
  poor_optional& operator=(poor_optional const&)=default;
  poor_optional& operator=(poor_optional const&&)=default;
  poor_optional& operator=(poor_optional &&)=default;
  poor_optional& operator=(poor_optional &)=default;
  template<class...Ts>
  void emplace(Ts&&...ts) {
    t = {std::forward<Ts>(ts)...};
    empty = false;
  }
  template<class...Ts>
  poor_optional( Ts&&... ts ):empty(false), t(std::forward<Ts>(ts)...) {}
};

这很糟糕，因为它构建了一个 T 即使不需要，但它应该可以工作。

Answer 3

为了完成，我 post OP

提到的模板版本

#include <string>
#include <iostream>

namespace bodhi
{
    template<typename T> class Beignet;
    template<typename T> class Cruller;

    template<typename T> class IPastryVisitor
    {
    public:
        virtual T visitBeignet(Beignet<T>& beignet) = 0;
        virtual T visitCruller(Cruller<T>& cruller) = 0;
    };

    template<typename T> class Pastry
    {
    public:
        virtual T accept(IPastryVisitor<T>& visitor) = 0;
    };

    template<typename T> class Beignet : public Pastry<T>
    {
    public:
        T accept(IPastryVisitor<T>& visitor)
        {
            return visitor.visitBeignet(*this);
        }

        std::string name = "Beignet";
    };

    template<typename T> class Cruller : public Pastry<T>
    {
    public:
        T accept(IPastryVisitor<T>& visitor)
        {
            return visitor.visitCruller(*this);
        }

        std::string name = "Cruller";
    };


    class Confectioner : public IPastryVisitor<std::string>
    {
    public:
        virtual std::string visitBeignet(Beignet<std::string>& beignet) override
        {
            return "I just visited: " + beignet.name;
        }

        virtual std::string visitCruller(Cruller<std::string>& cruller) override
        {
            return "I just visited: " + cruller.name;
        }
    };
}

int main()
{
    bodhi::Confectioner pastryChef;

    bodhi::Beignet<std::string> beignet;
    std::cout << beignet.accept(pastryChef) << "\n";

    bodhi::Cruller<std::string> cruller;
    std::cout << cruller.accept(pastryChef) << "\n";
    return 0;
}

每个糕点都是一个节点，每个访问者都可以实现其接受的 return 类型。多个访客可以访问同一个糕点。

使用具有 return 值的访问者模式实现 AST 的最佳方法是什么？

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

c++

abstract-syntax-tree

visitor-pattern