什么是使用访问者模式与返回值来实现AST的最佳方式？(What's the best way

2019-10-21 17:26发布

站内文章 / 后端开发
47 0 0

我试图实现在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都是二元运算符，但他们依靠自己的孩子的访问的返回类型。

至于我可以看到，使其工作，只有2个选择：

  1. 接受仍然可以返回void，保存在其被传递到每个接受并访问功能的上下文对象的返回值，并在访问功能，在那里我知道使用什么类型的使用它们。 这应该工作，但感觉就像一个黑客攻击。

  2. 让AstNode模板，并接受功能没有虚拟的，但返回类型依赖于模板参数T.But如果我这样做，我不再有一个共同的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 。



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

上述假定来访a+b在void上下文是可接受的（如在C / C ++）。 如果不是，那么你需要的一种手段void ，以“不能产生一个访问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:

对于完成的缘故，我张贴由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;
}

每个糕点是一个节点，每一位参观者可以实现其接受的返回类型。 拥有多个访问者可以访问相同的糕点。



文章来源: What's the best way to implement AST using visitor pattern with return value?
标签： c++ abstract-syntax-tree visitor
举报

收藏的人(0)

Ta的文章 更多文章
登录 后发表评论
0条评论
还没有人评论过~