Implementación del patrón de visitante para un árbol de sintaxis abstracta

Estoy en el proceso de crear mi propio lenguaje de programación, lo cual hago para aprender. Ya escribí el lexer y un analizador de descenso recursivo para un subconjunto de mi lenguaje (actualmente soporto expresiones matemáticas, como + - * /y paréntesis). El analizador me devuelve un Árbol de sintaxis abstracta, en el que llamo al Evaluatemétodo para obtener el resultado de la expresión. Todo funciona bien Aquí está aproximadamente mi situación actual (ejemplos de código en C #, aunque esto es bastante independiente del lenguaje):

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

Sin embargo, me gustaría desacoplar el algoritmo de los nodos del árbol porque quiero aplicar el Principio Abierto / Cerrado para no tener que volver a abrir cada clase de nodo cuando quiero implementar la generación de código, por ejemplo. Leí que el patrón de visitante es bueno para eso. Tengo una buena comprensión de cómo funciona el patrón y que usar el envío doble es el camino a seguir. Pero debido a la naturaleza recursiva del árbol, no estoy seguro de cómo debería abordarlo. Así es como se vería mi visitante:

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
}

Entonces este es mi problema. Quiero abordarlo de inmediato mientras mi idioma no admite muchas funcionalidades para evitar tener un problema mayor más adelante.

No publiqué esto en StackOverflow porque no quiero que proporciones una implementación. Solo quiero que comparta ideas y conceptos que podría haber pasado por alto, y cómo debería abordar esto.

Depende de la implementación del visitante decidir si visitar nodos secundarios y en qué orden. Ese es el objetivo del patrón de visitante.

Para adaptar al visitante a más situaciones, es útil (y bastante común) usar genéricos como este (es Java):

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

Y un acceptmétodo se vería así:

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

Esto permite pasar parámetros adicionales al visitante y recuperar un resultado del mismo. Entonces, la evaluación de la expresión se puede implementar así:

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

El acceptparámetro método no se usa en el ejemplo anterior, pero solo créanme: es bastante útil tener uno. Por ejemplo, puede ser una instancia de Logger para informar errores.

He implementado el patrón de visitante en un árbol recursivo antes.

Mi estructura de datos recursiva particular era extremadamente simple: solo tres tipos de nodos: el nodo genérico, un nodo interno que tiene hijos y un nodo hoja que tiene datos. Esto es mucho más simple de lo que espero que sea su AST, pero tal vez las ideas puedan escalar.

En mi caso, deliberadamente no permití que Aceptar de un nodo con hijos llamara Aceptar a sus hijos, o llamar visitante. Visite (hijo) desde dentro de Aceptar. Es responsabilidad de la implementación correcta del miembro "Visita" del visitante delegar las Aceptaciones a los hijos del nodo que se está visitando. Elegí este camino porque quería permitir que diferentes implementaciones de Visitantes pudieran decidir el orden de visita independientemente de la representación del árbol.

Un beneficio secundario es que casi no hay artefactos del patrón Visitante dentro de los nodos de mi árbol: cada "Aceptar" solo llama "Visita" al visitante con el tipo concreto correcto. Esto facilita la localización y comprensión de la lógica de visitas, todo está dentro de la implementación del visitante.

Para mayor claridad, he agregado algunos pseudocódigos C ++ - ish. Primero los nodos:

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

Y el visitante:

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

};

Trabaja el patrón de visitante alrededor de una estructura recursiva de la misma manera que haría cualquier otra cosa con su estructura recursiva: visitando los nodos en su estructura recursivamente.

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