访问者模式为AST

Question

我想使用访问者模式来执行我的编译器的AST的操作，但我似乎无法弄清楚将正常工作的实现。

AST类摘录：

class AstNode 
{ 
public: 
    AstNode() {} 
}; 

class Program : public AstNode 
{ 
public: 
    std::vector<std::shared_ptr<Class>> classes; 

    Program(const std::vector<std::shared_ptr<Class>>&); 
    void accept(AstNodeVisitor& visitor) const { visitor.visit(*this); } 
}; 

class Expression : public AstNode 
{ 
public: 
    Expression() {} 
}; 

class Method : public Feature 
{ 
public: 
    Symbol name; 
    Symbol return_type; 
    std::vector<std::shared_ptr<Formal>> params; 
    std::shared_ptr<Expression> body; 

    Method(const Symbol&, const Symbol&, const std::vector<std::shared_ptr<Formal>>&, 
      const std::shared_ptr<Expression>&); 
    feature_type get_type() const; 
}; 

class Class : public AstNode 
{ 
public: 
    Symbol name; 
    Symbol parent; 
    Symbol filename; 
    std::vector<std::shared_ptr<Feature>> features; 

    Class(const Symbol&, const Symbol&, const Symbol&, 
      const std::vector<std::shared_ptr<Feature>>&); 
}; 

class Assign : public Expression 
{ 
public: 
    Symbol name; 
    std::shared_ptr<Expression> rhs; 

    Assign(const Symbol&, const std::shared_ptr<Expression>&); 
}; 

游客（部分实现）：

class AstNodeVisitor 
{ 
public: 
    virtual void visit(const Program&) = 0; 
    virtual void visit(const Class&) = 0; 
    virtual void visit(const Attribute&) = 0; 
    virtual void visit(const Formal&) = 0; 
    virtual void visit(const Method&) = 0; 
}; 

class AstNodePrintVisitor : public AstNodeVisitor 
{ 
private: 
    size_t depth; 

public: 
    void visit(const Program& node) { 
     for (auto cs : node.classes) 
      visit(*cs); 
    } 

    void visit(const Class&); 
    void visit(const Attribute&); 
    void visit(const Formal&); 
    void visit(const Method&); 
}; 

我如何使用它：

AstNodePrintVisitor print; 
ast_root->accept(print); // ast_root is a shared_ptr<Program> 

问题：

的方法节点包含一个bo类型Expression的dy成员 - 这是一个基类。我将如何访问它？

我想也许我可以简单地为每个AST节点编写一个接受方法，然后进行遍历。 （即，不是在访问者中调用visit（），而是在可访问的调用访问（* this）中调用accept（），以便调用将是多态的，访问者的正确访问方法将被调用。但是，如果我这样做，我将无法选择自顶向下（操作然后递归）或自下而上（递归操作），因为我必须仅选择一个。因此，我的意思是一个PrintVisitor例如需要一个AST自顶向下遍历，但TypeCheck需要自下而上的方法。

有没有办法解决这个问题？或者我过度设计了一些东西？现在我认为最快的方法就是实现方法在节点本身。

Answer 1

让我们从一个小的修正开始访问者的工艺：

void visit(const Program& node) { 
    for (auto cs : node.classes) 
     visit(*cs); 
} 

通话visit(*cs)应该cs->accept(*this)允许虚拟调度，在一般情况下。

---

而现在到了主要问题：控制遍历顺序。

访问者只能真正以深度第一种方式真正访问一棵树，首先可以实现广度，但在单个visit方法中很古怪（您基本上需要将访问与孩子的迭代分开）。

在另一方面，即使在深度优先遍历，你可以选择是否对父母要么或之前访问过的儿童行动后。

这样做将是提供纯的基类和真正的演员之间的中间层，例如典型的方式：

class RecursiveAstNodeVisitor: public AstNodeVisitor 
{ 
public: 
    // returns whether or not to stop recursion 
    virtual bool actBefore(Program const&) { return false; } 
    virtual void actAfter(Program const&) {} 

    virtual bool actBefore(Class const&) { return false; } 
    virtual void actAfter(Class const&) {} 

    // ... You get the idea 


    virtual void visit(Program const& p) { 
     if (actBefore(p)) { return; } 

     for (auto c: p.classes) { 
      c->accept(*this); 
     } 

     actAfter(p); 
    } 

    // ... You get the idea 
}; 

的超控器是自由之前或递归发生后采取行动...当然可以对两者都起作用！

class PrintAstNodeVisitor: public RecursiveAstNodeVisitor { 
public: 
    PrintAstNodeVisitor(std::ostream& out): _out(out), _prefix() {} 

    virtual bool actBefore(Program const& p) { 
     _out << "{\n"; 
     _out << " \"type\": \"Program\",\n"; 
     _out << " \"name\": \" << p.name << "\",\n"; 
     _out << " \"classes\": [\n"; 

     _prefix = " "; 

     return false; 
     } 

     virtual void actAfter(Program const& p) { 
     _out << " ]\n"; 
     _out << "}\n"; 
     } 

     virtual bool actBefore(Class const& c) { 
     _out << _prefix << "{\n"; 
     _out << _prefix << " \"type\": \"Class\",\n"; 
     // ... 
     } 

private: 
    std::ostream& _out; 
    std::string _prefix; 
};