Menerapkan Pola Pengunjung untuk Pohon Sintaks Abstrak

Saya sedang dalam proses membuat bahasa pemrograman saya sendiri, yang saya lakukan untuk tujuan belajar. Saya sudah menulis lexer dan parser keturunan rekursif untuk subset dari bahasa saya (saya saat ini mendukung ekspresi matematika, seperti + - * /dan kurung). Pengurai memberikan saya kembali Pohon Sintaks Abstrak, di mana saya memanggil Evaluatemetode untuk mendapatkan hasil dari ekspresi. Semuanya bekerja dengan baik. Inilah kira-kira situasi saya saat ini (Contoh kode dalam C #, meskipun ini cukup banyak bahasa-agnostik):

public abstract class Node
{
    public abstract Double Evaluate();
}

public class OperationNode : Node
{
    public Node Left { get; set; }
    private String Operator { get; set; }
    private Node Right { get; set; }

    public Double Evaluate()
    {
        if (Operator == "+")
            return Left.Evaluate() + Right.Evaluate();

        //Same logic for the other operators
    }
}

public class NumberNode : Node
{
    public Double Value { get; set; }

    public Double Evaluate()
    {
        return Value;
    }
}

Namun, saya ingin memisahkan algoritma dari node pohon karena saya ingin menerapkan Prinsip Terbuka / Tertutup jadi saya tidak perlu membuka kembali setiap kelas simpul ketika saya ingin mengimplementasikan pembuatan kode misalnya. Saya membaca bahwa Pola Pengunjung baik untuk itu. Saya memiliki pemahaman yang baik tentang bagaimana pola bekerja dan menggunakan pengiriman ganda adalah cara untuk pergi. Tetapi karena sifat rekursif pohon itu, saya tidak yakin bagaimana saya harus mendekatinya. Di sini akan terlihat seperti apa Pengunjung saya:

public class AstEvaluationVisitor
{
    public void VisitOperation(OperationNode node)
    {
        // Here is where I operate on the operation node.
        // How do I implement this method?
        // OperationNode has two child nodes, which may have other children
        // How do I work the Visitor Pattern around a recursive structure?

        // Should I access children nodes here and call their Accept method so they get visited? 
        // Or should their Accept method be called from their parent's Accept?
    }

    // Other Visit implementation by Node type
}

Jadi ini masalah saya. Saya ingin segera mengatasinya sementara bahasa saya tidak mendukung banyak fungsi untuk menghindari masalah yang lebih besar nantinya.

Saya tidak memposting ini ke StackOverflow karena saya tidak ingin Anda memberikan implementasi. Saya hanya ingin Anda berbagi ide dan konsep yang mungkin saya lewatkan, dan bagaimana saya harus mendekati ini.

Terserah implementasi pengunjung untuk memutuskan apakah akan mengunjungi node anak dan dalam urutan apa. Itulah inti dari pola pengunjung.

Untuk menyesuaikan pengunjung dengan lebih banyak situasi, sangat membantu (dan sangat umum) untuk menggunakan obat generik seperti ini (ini Java):

public interface ExpressionNodeVisitor<R, P> {
    R visitNumber(NumberNode number, P p);
    R visitBinary(BinaryNode expression, P p);
    // ...
}

Dan sebuah acceptmetode akan terlihat seperti ini:

public interface ExpressionNode extends Node {
    <R, P> R accept(ExpressionNodeVisitor<R, P> visitor, P p);
    // ...
}

Ini memungkinkan untuk memberikan parameter tambahan kepada pengunjung dan mengambil hasil darinya. Jadi, evaluasi ekspresi dapat diimplementasikan seperti ini:

public class EvaluatingVisitor
    implements ExpressionNodeVisitor<Double, Void> {
    public Double visitNumber(NumberNode number, Void p) {
        // Parse the number and return it.
        return Double.valueOf(number.getText());
    }
    public Double visitBinary(BinaryNode binary, Void p) {
        switch (binary.getOperator()) {
        case '+':
            return binary.getLeftOperand().accept(this, p)
                + binary.getRightOperand().accept(this, p);
        // More cases for other operators here.
        }
    }
}

The acceptparameter metode tidak digunakan dalam contoh di atas, tetapi hanya percayalah: itu cukup berguna untuk memiliki satu. Misalnya, ini bisa menjadi contoh Logger untuk melaporkan kesalahan.

Saya telah menerapkan pola pengunjung pada pohon rekursif sebelumnya.

Struktur data rekursif khusus saya sangat sederhana - hanya tiga jenis simpul: simpul generik, simpul internal yang memiliki anak, dan simpul daun yang memiliki data. Ini jauh lebih sederhana dari yang saya perkirakan AST Anda, tetapi mungkin idenya dapat meningkat.

Dalam kasus saya, saya sengaja tidak membiarkan Terima node dengan anak-anak memanggil Terima pada anak-anaknya, atau untuk memanggil pengunjung. Kunjungi (anak) dari dalam Terima. Merupakan tanggung jawab implementasi anggota "Kunjungan" yang benar dari pengunjung untuk mendelegasikan Terima kepada anak-anak dari simpul yang dikunjungi. Saya memilih cara ini karena saya ingin mengizinkan implementasi Pengunjung yang berbeda untuk dapat memutuskan urutan kunjungan secara independen dari representasi pohon.

Manfaat kedua adalah hampir tidak ada artefak dari pola Pengunjung di dalam simpul pohon saya - masing-masing "Terima" hanya memanggil "Kunjungi" pada pengunjung dengan jenis beton yang benar. Ini membuatnya lebih mudah untuk menemukan dan memahami logika kunjungan, semuanya ada di dalam implementasi pengunjung.

Untuk lebih jelasnya saya telah menambahkan beberapa C ++ - pseudocode ish. Pertama node:

class INode {
  public:
    virtual void Accept(IVisitor& i_visitor) = 0;
};

class NodeWithChildren : public INode {
  public:
     virtual void Accept(IVisitor& i_visitor) override {
        i_visitor.Visit(*this);
     }
     // Plus interface for getting the children, exercise for the reader ;-)
 };

 class LeafNode : public INode {
   public:
     virtual void Accept(IVisitor& i_visitor) override {
       i_visitor.Visit(*this);
     }
 };

Dan pengunjung:

class IVisitor {
  public:
     virtual void Visit(NodeWithChildren& i_node) = 0;
     virtual void Visit(LeafNode& i_node) = 0;
};

class ConcreteVisitor : public IVisitor
  public:
     virtual void Visit(NodeWithChildren& i_node) override {
       // Do something useful, then...
       for(Node * p_child : i_node) {
         child->Accept(*this);
       }
     }

     virtual void Visit(LeafNode& i_node) override {
        // Just do something useful, there are no children.
     }

};

Anda mengerjakan pola pengunjung di sekitar struktur rekursif dengan cara yang sama Anda akan melakukan hal lain dengan struktur rekursif Anda: dengan mengunjungi node dalam struktur Anda secara rekursif.

public class OperationNode
{
    public int SomeProperty { get; set; }
    public List<OperationNode> Children { get; set; }
}

public static void VisitNode(OperationNode node)
{
    ... Visit this node

    foreach(var node in Children)
    {
         VisitNode(node);
    }
}

public static void VisitAllNodes()
{
    VisitNode(rootNode);
}