Streszczenie Składnia Reprezentacja drzewa w C++

Question

Mam już interfejs tokenizera, który tworzy listę tokenów. Mam działający mechanizm dla analizatora składni. Jest naprawdę wyjątkowy i działa jak urok. Jedyne, czego mi brakuje, to podstawowa struktura AST. W jaki sposób drzewo, węzły i instrukcje powinny być reprezentowane na poziomie abstrakcji. Nie potrzebuję żadnej implementacji, tylko szybki pomysł, jak powinien wyglądać w hierarchii klasowej? Pracuję nad językiem obiektowym. Tak, już zdałem sobie sprawę, że będę potrzebował dwóch rodzajów stwierdzeń. Zwracająca pewną wartość instrukcja typu "expression" i nie powracająca instrukcja typu kontrolującego przepływ instrukcji. Dziękuję bardzo.

Answer 1

Jeśli Twój język jest imperatywem/c-like, wspólny scenariusz zaczyna się od najwyższej hierarchii rozdzielona na 2 supertypes:

• Ekspresji
• komunikat

Program jest lista oświadczenia, które jest samym oświadczeniem.

Prawdopodobnie będziesz chciał mieć jedną klasę dla typu instrukcji rozszerzającej klasę podstawową instrukcji.

Typowy scenariusz wygląda następująco:

• bloku instrukcji (wykaz sprawozdań)
• ite (jeśli wtedy jeszcze)
• dla (wyrażenie dla pętli z jej listy sprawozdania inicjalizacji, sprawdzenia, przyrost sprawozdań i zablokować
• czasu (podobnie, ale tylko sprawdzić wyrażenie
• deklaracji zmiennej
• zadanie (Łącznie + = - = ++ - można owijać wszystko w jednej klasie z pola operacyjnego, a lval i rval)
• wywołanie funkcji (void jeden)

Dla wyrażeń:

• Bop (operacja binarna, wszystko, co ma 2 operandy i 1 operator, tj. + - * /% | & & & || == <
• UOP (jednoskładnikowa operacja, wszystko co ma 1 operandu i 1 operator IE ~!)
• wywołanie funkcji (nie-void nich)
• wyrażenie warunkowe (exp prawdziwą val: fałszywy val)

Dobrą rzeczą posiadania tych 2 abstrakcji (wyrażeń i stwierdzeń) jest to, że we wszystkich twoich klasach będziesz miał abstrakcyjne typy i będziesz mógł odwiedzać AST, na przykład z wzorem gościa.

Na przykład, niektóre klasy będzie wyglądać następująco (Pseudokod):

class Ite extends Statement { 
    Expression condition; 
    Statement ifBranch; 
    Statement elseBranch; 
} 


class Bop extends Expression { 
    BOperator operator; // +, -. * or whatever 
    Expression left;  // Left operand 
    Expression right; // Right operand 
} 


class StatementBlock extends Statement { 
    List<Statement> statements; 
} 


class Assignment extends Statement { 
    AOperator assignOp; // = += -= etc. 
    LVal lvalue;   // The lvalue cannot be an arbitrary expression, you will usually have a specific type for it 
    Expression rvalue; // Right value 
} 

Ponadto, trzeba będzie w jakiś sposób do reprezentowania rodzajów (dla AST, zaledwie typy statyczne są wystarczające, jeśli wystają do implementacji niektórych back-endów, będziesz potrzebował również niektórych typów dynamicznych).

Typy statyczne można zwykle określić przy niektórych wyliczeniach, jeśli nie planuje się obsługiwać tablic o stałych rozmiarach, które wymagają informacji o rozmiarze. Jeśli chcesz mieć tablice o stałym rozmiarze z rozmiarem, możesz zaimplementować jedną klasę dla typu i mieć typ tablicy zawierający dodatkowe informacje o rozmiarze.

enum Type { 
    CHAR, 
    SHORT, 
    INT, 
    LONG, 
    FLOAT, 
    DOUBLE, 
    ARRAY 
} 

class Float extends StaticType { 
    final Type type = Type.FLOAT; 
} 

class Array extends StaticArray { 
    final Type type = Type.ARRAY; 

    int size; 
} 

Następnie wystąpienia jednej instancji StaticType dla każdego typu w AST, na przykład, gdy użytkownik deklaruje zmienną. Będziesz mógł korzystać z tej samej hierarchii, jeśli planujesz w przyszłości wykonywać statyczne sprawdzanie typów.

Jeśli chodzi o uruchamianie/interpretowanie kodu w formularzu AST, potrzebna będzie pamięć, w której będzie przechowywany stos/ster zawierający informacje o pamięci środowiska wykonawczego. W tym momencie będziesz musiał przechowywać wartości wraz z ich informacjami o typie.