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>

問題：

Method Node には、基本クラスである Expression 型の body メンバーが含まれています。どのように訪問しますか？

単純に AST ノードごとに accept メソッドを記述して、そこでトラバーサルを実行できるのではないかと考えました。(つまり、ビジターで visit() を呼び出す代わりに、visitable で accept() を呼び出してから、visit(*this) を呼び出して、呼び出しがポリモーフィックになり、ビジターの適切な visit() メソッドが呼び出されるようにします。

ただし、これを行うと、トップダウン (操作の後に再帰) またはボトムアップ (再帰の後に操作) を 1 つだけ選択する必要があるため、トラバースするオプションがなくなります。これにより、たとえば PrintVisitor では AST のトップダウン トラバーサルが必要になりますが、TypeCheck ではボトムアップ アプローチが必要になります。

これを回避する方法はありますか？それとも、私は物事を過剰に設計していますか？今のところ、最速の方法はノード自体にメソッドを実装することだと思います。

4

1 に答える 1

6

ビジターのクラフトを少し修正することから始めましょう。

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

the call visit(*cs) should be cs->accept(*this) to allow for virtual dispatch, in the generic case.

And now to the main question: the control of traversal order.

A visitor can only really visit a tree in a depth first way, breadth first may be implemented but is quirky in a single visit method (you basically need to separate visitation from iterations on children).

On the other hand, even in a depth first traversal, you may chose whether to act on the parent either before or after having visited the children.

The typical way to do so would be to provide an intermediate layer between the pure base class and the real actor, for example:

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

The overrider is free to act either before or after the recursion occurs... and of course may act on both!

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 に答える