Come scrivere il pattern Visitor per un Abstract Syntax Tree in C#?

Question

Devo scrivere un modello di visitatore per navigare nell'AST. Qualcuno può dirmi di più su come dovrei iniziare a scriverlo? Per quanto ho capito, ogni nodo in AST avrebbe un metodo visit() (?) Che sarebbe in qualche modo chiamato (da dove?). Quello di concludere la mia comprensione. Per semplificare tutto ciò, supponiamo di avere nodi principali, Espressione, Numero, Op e l'albero si presenta così:

 Root 
     | 
     Op(+) 
    / \ 
    / \ 
Number(5) \ 
      Op(*) 
      / \ 
      / \ 
     /  \ 
     Number(2) Number(444) 

Answer 1

modello visitatore è un modello di progettazione che consente di implementare operazioni arbitrarie (implementato come visitatori) su l'albero di analisi (ad esempio, controllo del tipo) senza dover modificare l'implementazione dei nodi dell'albero di analisi.

Può essere implementato nel seguente modo (sto usando pseudocodice):

In primo luogo è necessario definire la classe base dei nodi del albero che tutti i nodi devono implementare.

abstract class VisitableNode { 
    abstract void accept(Visitor v); 
} 

L'unico metodo che classi nodo devono implementare il metodo accettare.

Quindi è necessario definire la classe base di un nodo visitatore dell'albero di analisi.

abstract class Visitor { 
    abstract void visit(Root rootNode); 
    abstract void visit(Op opNode); 
    abstract void visit(Number number); 
} 

Nota che della classe base del visitatore è fatta solo per il vostro albero sintattico, e dovrebbe avere un metodo visita per ogni tipo di nodo si definisce nel vostro albero sintattico.

Poi, si dovrebbe lasciare l'implementazione classi nodo estendere la classe VisitableNode nel seguente modo:

class Root : VisitableNode { 
    [...] 
    void accept(Visitor v) { 
     v.visit(this); 
    } 
} 

class Op : VisitableNode { 
    [...] 
    void accept(Visitor v) { 
     v.visit(this); 
    } 
} 

class Number : VisitableNode { 
    [...] 
    void accept(Visitor v) { 
     v.visit(this); 
    } 
} 

Ora avete il vostro struttura parse-albero che non dovrebbe cambiare, e si è liberi di implementare come molti visitatori (operazioni) come ti piace.

Per fare controllo dei tipi, si dovrà memorizzare un tipo all'interno della classe Number insieme al vostro valore, o comunque avere una classe numero per ogni tipo sostenete: NumberFloat, NumberInteger, NumberDouble, ecc

Ad esempio, supponiamo di avere un modo per dedurre il tipo statico del valore dalla classe Number.

Suppongo anche che sia possibile accedere ai figli del nodo mediante il metodo getChild (int childIndex).

Infine, userò un tipo di classe che rappresenta banalmente un tipo statico che si intende supportare (come Float, Integer, ecc.).

class TypeCheckVisitor : Visitor { 

    // Field used to save resulting type of a visit 
    Type resultType; 


    void visit(Root rootNode) 
    { 
     rootNode.getChild(0).accept(this); 
    } 

    void visit(Op opNode) 
    { 
     opNode.getChild(0).accept(this); 
     Type type1 = resultType; 

     opNode.getChild(1).accept(this); 
     Type type2 = resultType; 

     // Type check 
     if(!type1.isCompatible(type2)){ 
     // Produce type error 
     } 

     // Saves the return type of this OP (ex. Int + Int would return Int) 
     resultType = typeTableLookup(opNode.getOperator(), type1, type2); 
    } 

    void visit(Number number) 
    { 
     // Saves the type of this number as result 
     resultType = number.getType(); 
    } 
} 

Poi, si dovrebbe implementare la classe Type probabilmente come un enum in un modo simile a:

enum Type { 
    Double, 
    Float, 
    Integer; 

    boolean isCompatible(Type type1, Type type2){ 
     // Lookup some type table to determine types compatibility 
    } 
} 

E, infine, solo il necessario per implementare le tabelle di tipo e tavoli operatori.

MODIFICA: Nella ricorsione di visita, è in realtà corretto ricorrere utilizzando il metodo di accettazione dei nodi su cui si desidera ripetere.

Per quanto riguarda l'utilizzo, è possibile eseguire il controllo del tipo sul nodo radice dell'albero parse (e contemporaneamente determinerà il tipo di espressione) da:

TypeCheckVisitor v = new TypeCheckVisitor(); 
rootNode.accept(v); 
print("Root type is: " + v.resultType); 

è anche possibile digitare controllare un nodo arbitrario della analizzare l'albero diverso dalla radice allo stesso modo.