एएसटी

Question

के लिए विज़िटर पैटर्न मैं अपने कंपाइलर के एएसटी के लिए संचालन करने के लिए विज़िटर पैटर्न का उपयोग करने की कोशिश कर रहा हूं लेकिन मुझे एक कार्यान्वयन का पता लगाना प्रतीत नहीं होता है जो ठीक से काम करेगा।

एएसटी कक्षाएं अंश:

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> 

मुद्दा:

विधि नोड में एक बो है प्रकार अभिव्यक्ति के डीई सदस्य - जो एक बेस क्लास है। मैं इसे कैसे देखूँगा?

मैंने सोचा कि शायद मैं प्रत्येक एएसटी नोड के लिए एक स्वीकार्य विधि लिख सकता हूं और इसके बजाय वहां ट्रैवर्सल कर सकता हूं। (यानी विज़िटर में विज़िट() को कॉल करने के बजाय, विज़िट करने योग्य() को कॉल करें() इस पर कॉल करें (* यह) कॉल करें ताकि कॉल पॉलिमॉर्फिक हो और विज़िटर की सही विज़िट() विधि को कॉल किया जा सके।

हालांकि, अगर मैं ऐसा करता हूं, तो मेरे पास टॉप-डाउन (ऑपरेशन फिर रिकर्स) या डाउन-अप (फिर ऑपरेशन की पुनर्संरचना) के लिए कोई विकल्प नहीं होगा क्योंकि मुझे केवल एक चुनना है। इसका मतलब है कि उदाहरण के लिए प्रिंटविजिटर की आवश्यकता होगी एएसटी के टॉप-डाउन ट्रैवर्सल लेकिन टाइपशेक को नीचे-अप दृष्टिकोण की आवश्यकता होगी।

क्या इसके आसपास कोई रास्ता है? या क्या मैं अधिक इंजीनियरिंग चीजें हूं? अभी मुझे लगता है कि सबसे तेज़ तरीका केवल तरीकों को लागू करना है नोड्स में स्वयं।

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

overrider पहले या प्रत्यावर्तन होने के बाद कार्य करने के लिए नि: शुल्क है ... और निश्चित रूप से दोनों पर कार्य कर सकते हैं!

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