Implementowanie wzorca gościa dla abstrakcyjnego drzewa składni

Jestem w trakcie tworzenia własnego języka programowania, który robię do celów edukacyjnych. Napisałem już leksyk i parser rekurencyjnego zapisu dla podzbioru mojego języka (obecnie obsługuję wyrażenia matematyczne, takie jak + - * /i nawiasy). Analizator składni oddaje mi Streszczenie Drzewo Składni, w którym wywołuję Evaluatemetodę, aby uzyskać wynik wyrażenia. Wszystko dziala. Oto w przybliżeniu moja obecna sytuacja (przykłady kodu w języku C #, chociaż jest to w dużej mierze niezależne od języka):

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

Chciałbym jednak oddzielić algorytm od węzłów drzewa, ponieważ chcę zastosować zasadę otwartej / zamkniętej, aby nie musieć ponownie otwierać każdej klasy węzła, gdy chcę na przykład zaimplementować generowanie kodu. Czytam, że Wzorzec Odwiedzających jest do tego odpowiedni. Dobrze rozumiem, w jaki sposób działa wzór, i że korzystam z podwójnej wysyłki. Ale ze względu na rekurencyjną naturę drzewa nie jestem pewien, jak mam do niego podejść. Oto jak wyglądałby mój gość:

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
}

To jest mój problem. Chcę rozwiązać ten problem natychmiast, podczas gdy mój język nie obsługuje wielu funkcji, aby uniknąć później większego problemu.

Nie wysłałem tego do StackOverflow, ponieważ nie chcę, abyś dostarczył implementację. Chcę tylko, abyś podzielił się pomysłami i koncepcjami, które mogłem przegapić, i tym, jak powinienem do tego podejść.

Od implementacji użytkownika zależy decyzja, czy odwiedzić węzły potomne iw jakiej kolejności. To jest sedno wzoru odwiedzin.

Aby dostosować gościa do większej liczby sytuacji, pomocne (i dość powszechne) jest użycie takich ogólnych (to Java):

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

Oraz acceptmetoda będzie wyglądać następująco:

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

Pozwala to przekazać dodatkowe parametry odwiedzającemu i pobrać z niego wynik. Tak więc ocenę wyrażenia można zaimplementować w następujący sposób:

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

acceptParametr metoda nie jest stosowana w powyższym przykładzie, ale po prostu mi wierzyć: to jest bardzo przydatne mieć jeden. Na przykład może to być instancja rejestratora, w której można zgłaszać błędy.

Wcześniej zaimplementowałem wzór gościa na rekurencyjnym drzewie.

Moja szczególna struktura danych rekurencyjnych była niezwykle prosta - tylko trzy typy węzłów: węzeł ogólny, węzeł wewnętrzny, który ma dzieci i węzeł liścia, który ma dane. Jest to o wiele prostsze, niż się spodziewam, ale być może pomysły mogą się skalować.

W moim przypadku celowo nie pozwoliłem, aby węzeł z dziećmi wywoływał polecenie Akceptuj u swoich dzieci lub odwiedzającego. Odwiedzaj (dziecko) z poziomu Akceptuj. Odpowiedzialność za prawidłowe wdrożenie członka odwiedzającego użytkownika „Wizyta” w celu delegowania Akceptuje dzieci odwiedzanego węzła. Wybrałem ten sposób, ponieważ chciałem umożliwić różnym implementacjom Odwiedzającym możliwość decydowania o kolejności odwiedzin niezależnie od reprezentacji drzewa.

Druga korzyść polega na tym, że w moich węzłach drzewnych prawie nie ma artefaktów wzoru gościa - każde „Akceptuj” po prostu wywołuje „Odwiedziny” na odwiedzającym z właściwym typem betonu. Ułatwia to zlokalizowanie i zrozumienie logiki odwiedzin, wszystko jest w ramach implementacji odwiedzającego.

Dla jasności dodałem pseudokod C ++. Najpierw węzły:

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

A gość:

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

};

Wzorzec odwiedzin wokół struktury rekurencyjnej działa w ten sam sposób, co w przypadku struktury rekurencyjnej, robiąc cokolwiek innego: odwiedzając rekursywnie węzły w strukturze.

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