Jak napisać wzór użytkownika dla drzewa składni abstrakcyjnej w języku C#?

Question

Muszę napisać wzór gościa, aby nawigować po AST. Czy ktoś może mi powiedzieć, jak bym zaczął go pisać? O ile rozumiem, każdy węzeł w AST miałby metodę visit() (?), Która w jakiś sposób zostanie wywołana (skąd?). To kończy się moim zrozumieniem. Aby uprościć wszystko, załóżmy, że mam węzły korzeni, Expression, Ilość op i drzewo wygląda następująco:

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

Answer 1

odwiedzający to wzorzec projektowy, który pozwala na wdrożenie dowolne operacje (zaimplementowane jako goście) na drzewo analizy (np. sprawdzanie typu) bez konieczności modyfikacji implementacji węzłów drzewa analizy.

Może być realizowany w następujący sposób (używam Pseudokod):

Najpierw trzeba zdefiniować klasy base węzłów drzewa, że ​​wszystkie węzły mają do wykonania.

Jedyną metodą, którą muszą implementować klasy węzłów, jest metoda akceptowania.

Następnie powinieneś zdefiniować klasę podstawową węzła odwiedzającego twojego drzewa parse.

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

Zauważ, że baza klasy odwiedzającego jest wykonany tylko drzewa parsowania i powinien mieć jedną metodę odwiedzenia dla każdego typu węzła można zdefiniować w drzewie parsowania.

Następnie należy pozwolić realizacja zajęcia węzłów rozszerzyć klasę VisitableNode w następujący sposób:

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

teraz masz swoją strukturę parse-drzewo, które nie powinny się zmieniać, i jesteś wolny, aby realizować jak najwięcej odwiedzających (operacje), jak chcesz.

W tym celu wpisz sprawdzanie, trzeba będzie przechowywać typ wewnątrz klasy Number wraz z wartości, lub w inny sposób mają klasy Number dla każdego typu wspierasz: NumberFloat, NumberInteger, NumberDouble itp

Jako przykład załóżmy, że masz sposób, aby wywnioskować statyczny typ wartości z klasy Numer.

Przyjmę również, że można uzyskać dostęp do dzieci węzła za pomocą metody getChild (int childIndex).

Na koniec użyję klasy Type, która trywialnie reprezentuje typ statyczny, który zamierzasz obsługiwać (jak Float, Integer itd.).

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

Następnie można zaimplementować klasę Type prawdopodobnie jako wyliczenia w sposób podobny do:

enum Type { 
    Double, 
    Float, 
    Integer; 

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

I wreszcie trzeba tylko realizować swoje stoły i stoliki typu operatora.

EDYCJA: W rekurencji odwiedzin, jest właściwie poprawne powtarzanie za pomocą metody akceptowania węzłów, które chcesz powtórzyć.

Co do użycia, można wykonać typ kontroli na węźle głównym drzewie parse (i jednocześnie określić rodzaj ekspresji za) przez:

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

Można również wpisać sprawdzić dowolny węzeł parsować drzewo inne niż root w ten sam sposób.