8

我正在尝试使用访问者模式为我的编译器的 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>

问题：

方法节点包含一个表达式类型的主体成员——它是一个基类。我将如何访问它？

我想也许我可以简单地为每个 AST 节点编写一个接受方法，然后在那里进行遍历。（即，不要在访问者中调用 visit()，而是在可访问者中调用 accept()，然后调用 visit(*this)，这样调用将是多态的，并且访问者的正确 visit() 方法被调用。

但是，如果我这样做，我将无法选择自上而下（操作然后递归）或自下而上（递归然后操作），因为我只能选择一个。我的意思是，例如 PrintVisitor 需要自上而下遍历 AST，但 TypeCheck 需要自下而上的方法。

有没有解决的办法？还是我过度设计了一些东西？现在我认为最快的方法是在节点本身中实现方法。

4

1 回答 1

6

让我们从对访客工艺的小修正开始：

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;
};
于 2012-07-13T07:09:06.010 回答