Implementazione del pattern Visitor per un Abstract Syntax Tree

Spetta all'implementazione del visitatore decidere se visitare i nodi figli e in quale ordine. Questo è il punto centrale del modello di visitatore.

Per adattare il visitatore a più situazioni è utile (e abbastanza comune) usare generici come questo (è Java):

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

E un metodo accept sarebbe simile a questo:

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

Ciò consente di passare parametri aggiuntivi al visitatore e recuperare un risultato da esso. Quindi, la valutazione dell'espressione può essere implementata in questo modo:

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

Il parametro metodo accept non è usato nell'esempio sopra, ma mi credi: è abbastanza utile averne uno. Ad esempio, può essere un'istanza di Logger per segnalare errori a

Ho implementato il modello visitatore su un albero ricorsivo prima.

La mia particolare struttura dati ricorsiva era estremamente semplice: solo tre tipi di nodi: il nodo generico, un nodo interno con figli e un nodo foglia contenente dati. Questo è molto più semplice di quanto mi aspetto che il tuo AST sia, ma forse le idee possono essere scalate.

Nel mio caso ho deliberatamente impedito che l'accettazione di un nodo con figli chiamasse Accept sui suoi figli, o per chiamare visitor.Visit (child) all'interno di Accept. È responsabilità della corretta implementazione del membro "Visita" del visitatore di delegare Accetta i bambini del nodo visitato. Ho scelto in questo modo perché volevo consentire a diverse implementazioni di Visitor di essere in grado di decidere l'ordine di visita indipendentemente dalla rappresentazione ad albero.

Un vantaggio secondario è che non ci sono quasi artefatti del pattern Visitor all'interno dei miei nodi dell'albero - ogni "Accetta" chiama semplicemente "Visita" sul visitatore con il tipo concreto corretto. Ciò semplifica l'individuazione e la comprensione della logica di visita, è tutto all'interno dell'implementazione dei visitatori.

Per chiarezza ho aggiunto qualche pseudocodice C ++-ish. Prima i nodi:

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

E il visitatore:

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

};

Lavori il pattern visitatore attorno a una struttura ricorsiva nello stesso modo in cui faresti qualsiasi altra cosa con la tua struttura ricorsiva: visitando i nodi della tua struttura in modo ricorsivo.

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

Per gestire la natura ricorsiva dell'albero, userei un iteratore per visitare i nodi nell'ordine appropriato (qualcosa come l'ordine postale in questo caso?) La formula "(1 + 2) * 3" diventa "1 2 + 3 * ".

Il visitatore della valutazione sposterà i numeri (dai nodi foglia) al suo stack e li riporterà indietro per l'utilizzo quando viene eseguito nei Nodi Operativi. Il risultato dell'operatore in un Nodo Operativo deve sempre essere spinto nello stack.

Questo stack è conservato all'interno dell'oggetto visitor.

push (1); // nodo nodo visitato

pressione (2); // ...

push (pop () + pop ()) // nodo dell'operatore, somma 1 e 2 e spinge i risultati nuovamente nello stack.

push (3) // leaf, ora 3 e 3 sono nello stack

push (operatore pop () * pop ()) //, ora 9 è in pila.

Alla fine, il risultato è in pila.

Non sono sicuro al 100% se funzionerà, ed è facile da quando non l'ho testato.

Come hai detto, potresti creare diversi tipi di visitatori a seconda di ciò che desideri ottenere senza dover modificare il codice del nodo esistente. Il visitatore non è mai responsabile di determinare direttamente quale nodo selezionare, ma l'iteratore lo fa. Tuttavia, alcuni visitatori potrebbero richiedere che vengano applicati ai nodi in un ordine particolare, altrimenti non funzionerà o darà risultati indesiderati.