Mô hình khách truy cập cho AST

Question

Tôi đang cố gắng sử dụng mẫu khách truy cập để thực hiện các hoạt động cho AST của trình biên dịch của tôi nhưng tôi dường như không thể tìm ra một triển khai sẽ hoạt động đúng.

lớp AST trích đoạn:

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

khách (thực hiện một phần):

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

Làm thế nào tôi đang sử dụng nó:

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

Vấn đề:

Các Phương thức Node chứa một bo dy thành viên của loại Expression - đó là một lớp cơ sở. Làm thế nào tôi sẽ ghé thăm nó?

Tôi nghĩ có lẽ tôi chỉ đơn giản có thể viết một phương thức chấp nhận cho mỗi nút AST và thực hiện chuyển đổi ở đó. (ví dụ: thay vì gọi số lượt truy cập() trong khách truy cập, hãy gọi chấp nhận() trong lượt truy cập, sau đó gọi đến (* this) để các cuộc gọi sẽ được đa hình và phương thức truy cập() của khách truy cập được gọi là

Tuy nhiên, nếu tôi làm điều này, tôi sẽ không có tùy chọn để đi qua từ trên xuống (hoạt động sau đó recurse) hoặc từ dưới lên (recurse sau đó hoạt động) vì tôi phải chọn chỉ một.Vì điều này tôi có nghĩa là một PrintVisitor ví dụ sẽ cần một từ trên xuống dưới của AST nhưng một TypeCheck sẽ cần một phương pháp tiếp cận từ dưới lên

Có cách nào khác không? Hay tôi là kỹ thuật quá mức? Bây giờ tôi nghĩ cách nhanh nhất là thực hiện các phương pháp trong các nút của chính mình.

Answer 1

Hãy bắt đầu với một sự điều chỉnh nhỏ cho nghề của một khách:

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

cuộc gọi visit(*cs) nên cs->accept(*this) để cho phép công văn ảo, trong trường hợp tổng quát.

---

Và bây giờ đến câu hỏi chính: kiểm soát trật tự truyền tải.

Một khách truy cập chỉ có thể ghé thăm một cây theo chiều sâu, chiều rộng đầu tiên có thể được triển khai nhưng rất kỳ quặc trong một phương thức visit (về cơ bản bạn cần phải tách biệt lượt truy cập khỏi các lần lặp lại đối với trẻ em).

Mặt khác, ngay cả trong một chiều sâu traversal đầu tiên, bạn có thể chọn xem có nên hành động phụ huynh hoặc trước hoặc sau đã đến thăm trẻ em.

Cách điển hình để làm như vậy sẽ được cung cấp thêm một lớp trung gian giữa các lớp cơ sở trong sạch và các diễn viên thực thụ, ví dụ:

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

Các overrider là tự do hành động trước hoặc sau khi đệ quy xảy ra ... và tất nhiên có thể hành động trên cả hai!

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