我正在尝试使用访问者模式来执行我的编译器的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 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>
问题：
方法节点包含Expression类型的主体成员 – 它是一个基类.我将如何访问它？
我想也许我可以简单地为每个AST节点编写一个accept方法,然后在那里进行遍历. (即,不是在访问者中调用visit(),而是在visitable中调用accept()然后调用visit(* this),这样调用将是多态的,并且调用访问者的right visit()方法.
但是,如果我这样做,我将无法选择自上而下(操作然后递归)或自下而上(递归然后操作),因为我必须只选择一个.我的意思是,例如PrintVisitor需要自上而下遍历AST,但TypeCheck需要自下而上的方法.
解决方法
让我们从对访客工艺的微小修正开始：
void visit(const Program& node) {
for (auto cs : node.classes)
visit(*cs);
}
在通用情况下,呼叫访问(* cs)应该是cs-> accept(* this)以允许虚拟调度.
现在主要问题是：遍历顺序的控制.
访问者只能以深度第一的方式真正访问树,首先可以实现广度,但在单一访问方法中是古怪的(您基本上需要将访问与儿童的迭代分开).
另一方面,即使在深度优先遍历中,您也可以选择是在访问孩子之前还是之后对父母采取行动.
这样做的典型方法是在纯基类和真实actor之间提供一个中间层,例如：
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;
};
