Besuchermuster für AST

Question

Ich versuche, das Besuchermuster zu verwenden, um Operationen für den AST meines Compilers durchzuführen, aber ich kann nicht scheinen, eine Implementierung zu finden, die richtig funktioniert.

AST Klassen Auszug:

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

Visitor (teilweise Umsetzung):

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

Wie ich es bin mit:

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

Das Problem:

Die Methodenknoten enthält einen bo dy Mitglied des Typs Ausdruck - was eine Basisklasse ist. Wie werde ich es besuchen?

Ich dachte, vielleicht könnte ich einfach eine Annahme-Methode für jeden AST-Knoten schreiben und die Traversierung stattdessen tun. (z. B. statt visit() im Besucher anzurufen, accept() im visitable anzurufen, dann call visit (* this), damit die Aufrufe polymorph werden und die richtige visit() -Methode des Besuchers aufgerufen wird.

Aber wenn ich das tue, habe ich keine Möglichkeit, Top-Down (Operation, dann Rekurse) oder Bottom-Up (Rekurse und Operation) zu durchlaufen, da ich nur einen auswählen muss Top-Down-Traversal des AST, aber ein TypeCheck wird einen Bottom-Up-Ansatz benötigen

Gibt es einen Weg um das? Oder bin ich over-Engineering Dinge? Im Moment denke ich, der schnellste Weg ist, nur die Methoden zu implementieren in den Knoten selbst.

Answer 1

Lassen Sie sich mit einer kleinen Korrektur für das Handwerk eines Besuchers beginnen:

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

der Anruf visit(*cs)cs->accept(*this) sein sollte für virtuellen Versand, in dem allgemeinen Fall zu ermöglichen.

---

Und nun zur Hauptfrage: die Kontrolle der Traversierungsreihenfolge.

Ein Besucher kann nur wirklich einen Baum in einer Tiefe zuerst besuchen, Breite zuerst kann implementiert werden, ist aber skurril in einer einzigen Methode visit (Sie müssen Besuch von Iterationen auf Kinder grundsätzlich trennen).

Auf der anderen Seite, auch in einer Tiefe ersten Traversal, können Sie wählen, ob auf dem Elternteil handeln entweder vor oder nach die Kinder besucht haben.

Die typische Art und Weise, dies zu tun, eine Zwischenschicht zwischen der reinen Basisklasse und den realen Schauspielern zu schaffen wäre, zum Beispiel: ist

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

Die Übergehungseinrichtung kostenlos entweder vor oder nach der Rekursion auftritt handeln ... und kann natürlich auf beide wirken!

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