Wie man Besuchermuster für einen abstrakten Syntaxbaum in C# schreibt?

Question

Ich habe ein Besuchermuster zu schreiben, den AST zu navigieren. Kann mir jemand mehr sagen, wie würde ich anfangen, es zu schreiben? Soweit ich verstehe, würde jeder Knoten in AST hat Besuch() -Methode (?), Die irgendwie aufgerufen würden (von wo?). Das schließt mein Verständnis ab. alles zu vereinfachen, nehme ich Knoten Root, Ausdruck, Zahl, Op und der Baum wie folgt aussehen:

Besucher

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

Answer 1

Muster ist ein Design-Muster, das Sie beliebige Operationen implementieren kann (als Besucher implementiert) auf den Syntaxbaum (z. B. Typprüfung), ohne die Implementierung der Knoten des Syntaxbaums modifizieren zu müssen.

Es kann auf folgende Weise implementiert werden (ich bin mit Pseudo-Code):

Zuerst müssen Sie die Basis-Klasse des Baumes Knoten definieren, die alle Knoten zu implementieren.

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

Die einzige Methode, die Knotenklassen implementieren müssen, ist die Methode accept.

Dann sollten Sie die Basisklasse eines Besuchers Knoten des Parse-Baum definieren.

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

Beachten Sie, dass Besucher der Basisklasse für Ihren Parse-Baum nur gemacht wird, und sollte für jeden Knotentyp Sie definieren in Ihrem Parse-Baum einen Besuch Methode hat.

Dann sollten Sie Ihre Knotenklassen Implementierung erweitern die VisitableNode Klasse auf folgende Weise lassen:

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

Jetzt haben Sie Ihre Parse-Baumstruktur, die sich nicht ändern sollte, und Sie sind frei, so viele implementieren Besucher (Operationen) wie Sie möchten.

Um Typprüfung zu tun, werden Sie eine Art innerhalb der Number-Klasse zusammen mit dem Wert speichern müssen, oder auf andere Weise eine Anzahl Klasse, die Sie für jede Art haben unterstützen: NumberFloat, NumberInteger, NumberDouble usw.

Nehmen wir als Beispiel an, dass Sie den statischen Typ des Wertes aus Ihrer Number-Klasse ableiten können.

Ich werde auch an, dass Sie Knoten der Kinder durch Methode getChild zugreifen können (int child).

Schließlich werde ich einen Klasse-Typen verwenden, die trivialerweise einen statischen Typen repräsentieren Sie unterstützen möchten (wie Float, Integer, etc ...).

enum Type { 
    Double, 
    Float, 
    Integer; 

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

Und schließlich müssen Sie nur Ihre Art Tabellen und Operator-Tabellen implementieren:

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

Dann würden Sie die Typklasse wahrscheinlich als Enum in einer Art und Weise ähnlich implementieren.

EDIT: In dem Besuch Rekursion ist es eigentlich richtig zu wiederholen das Verfahren der Knoten akzeptieren verwenden, auf das Sie wiederholt werden sollen.

Wie für die Nutzung, können Sie Typüberprüfung auf dem Wurzelknoten des Parse-Baum (und gleichzeitig der Ausdruck des Typs bestimmen) durch ausführen:

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

Sie können auch einen beliebigen Knoten des Typs überprüfen den Baum auf die gleiche Weise von der Wurzel unterscheiden.