Patrón de visitante para AST

Question

Estoy tratando de usar el patrón de visitante para realizar operaciones para el AST de mi compilador pero parece que no puedo encontrar una implementación que funcione correctamente.

clases AST extracto:

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

de Visitantes (aplicación parcial):

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

¿Cómo lo estoy usando:

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

El problema:

El El nodo de método contiene un bo dy miembro de tipo Expresión - que es una clase base. ¿Cómo lo voy a visitar?

Pensé que tal vez podría simplemente escribir un método de aceptación para cada nodo AST y hacer el recorrido allí en su lugar. (es decir, en lugar de llamar a visit() en el visitante, llame a accept() en la visita visitable (* this) para que las llamadas sean polimórficas y se llame al método de visita correcto() del visitante.

Sin embargo, si hago esto, no tendré opción para cruzar de arriba hacia abajo (operación luego recurrente) o de abajo hacia arriba (recurse luego operación) ya que tengo que elegir solo uno. Con esto quiero decir que PrintVisitor por ejemplo necesitará un cruce descendente del AST, pero un TypeCheck necesitará un enfoque de abajo hacia arriba.

¿Hay alguna forma de evitar esto? ¿O estoy sobreingeniería? En este momento, creo que la manera más rápida es simplemente implementar los métodos. en los nodos.

Answer 1

Vamos a empezar con una pequeña corrección a la nave de un Visitante:

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

la llamada visit(*cs) debería ser cs->accept(*this) para permitir la expedición virtual, en el caso genérico.

---

Y ahora a la pregunta principal: el control de la orden transversal.

Un visitante solo puede visitar un árbol en profundidad en primer lugar, la amplitud primero puede implementarse pero es peculiar en un solo método visit (básicamente necesita separar las visitas de las iteraciones en los niños).

Por otra parte, incluso en una profundidad primer recorrido, es posible elegir si actuar sobre los padres, ya sea antes o después de haber visitado a los hijos.

La forma típica de hacerlo sería para proporcionar una capa intermedia entre la clase base pura y el actor real, por ejemplo:

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

El overrider es libre de actuar ya sea antes o después de que ocurra la recursión ... ¡y por supuesto puede actuar en ambos!

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