訪問者模式爲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; 
};