Jak dokładnie powstaje abstrakcyjne drzewo składniowe?

Myślę, że rozumiem cel AST i zbudowałem już kilka struktur drzewiastych, ale nigdy AST. Jestem w większości zdezorientowany, ponieważ węzły są tekstem, a nie liczbą, więc nie mogę wymyślić dobrego sposobu na wprowadzenie tokena / łańcucha, gdy parsuję jakiś kod.

Na przykład, kiedy patrzyłem na diagramy AST, zmienna i jej wartość były węzłami liścia do znaku równości. Ma to dla mnie idealny sens, ale jak miałbym to zrobić? Wydaje mi się, że mogę to zrobić indywidualnie dla każdego przypadku, więc kiedy natknę się na „=”, używam tego jako węzła i dodam wartość przeanalizowaną przed „=” jako liść. Wydaje się to po prostu złe, ponieważ prawdopodobnie musiałbym tworzyć przypadki dla wielu ton, w zależności od składni.

A potem natknąłem się na inny problem, w jaki sposób drzewo jest trawersowane? Czy schodzę na dół i wracam do węzła, gdy uderzę w dno, i robię to samo dla jego sąsiada?

Widziałem mnóstwo diagramów na AST, ale nie mogłem znaleźć dość prostego przykładu takiego w kodzie, który prawdopodobnie by pomógł.

Krótka odpowiedź brzmi: używasz stosów. To dobry przykład, ale zastosuję go do AST.

Do Twojej wiadomości, to jest algorytm manewrowania Edsger Dijkstra .

W takim przypadku użyję stosu operatora i stosu wyrażeń. Ponieważ liczby są uważane za wyrażenia w większości języków, użyję stosu wyrażeń do ich przechowywania.

class ExprNode:
    char c
    ExprNode operand1
    ExprNode operand2

    ExprNode(char num):
        c = num
        operand1 = operand2 = nil

    Expr(char op, ExprNode e1, ExprNode e2):
        c = op
        operand1 = e1
        operand2 = e2

# Parser
ExprNode parse(string input):
    char c
    while (c = input.getNextChar()):
        if (c == '('):
            operatorStack.push(c)

        else if (c.isDigit()):
            exprStack.push(ExprNode(c))

        else if (c.isOperator()):
            while(operatorStack.top().precedence >= c.precedence):
                operator = operatorStack.pop()
                # Careful! The second operand was pushed last.
                e2 = exprStack.pop()
                e1 = exprStack.pop()
                exprStack.push(ExprNode(operator, e1, e2))

            operatorStack.push(c)

        else if (c == ')'):
            while (operatorStack.top() != '('):
                operator = operatorStack.pop()
                # Careful! The second operand was pushed last.
                e2 = exprStack.pop()
                e1 = exprStack.pop()
                exprStack.push(ExprNode(operator, e1, e2))

            # Pop the '(' off the operator stack.
            operatorStack.pop()

        else:
            error()
            return nil

    # There should only be one item on exprStack.
    # It's the root node, so we return it.
    return exprStack.pop()

(Proszę, bądź miły w kwestii mojego kodu. Wiem, że nie jest solidny; powinien to być pseudokod.)

W każdym razie, jak widać z kodu, dowolne wyrażenia mogą być operandami innych wyrażeń. Jeśli masz następujące dane wejściowe:

5 * 3 + (4 + 2 % 2 * 8)

kod, który napisałem, wytworzyłby ten AST:

     +
    / \
   /   \
  *     +
 / \   / \
5   3 4   *
         / \
        %   8
       / \
      2   2

A następnie, gdy chcesz wygenerować kod dla tego AST, wykonujesz przejście drzewa zamówienia post . Kiedy odwiedzasz węzeł liścia (z liczbą), generujesz stałą, ponieważ kompilator musi znać wartości operandu. Gdy odwiedzasz węzeł z operatorem, generujesz odpowiednią instrukcję od operatora. Na przykład operator „+” podaje instrukcję „dodaj”.

Istnieje znacząca różnica między tym, jak AST jest zazwyczaj przedstawiana w teście (drzewo z liczbami / zmiennymi w węzłach liści i symbolami w węzłach wewnętrznych), a tym, jak jest ona faktycznie implementowana.

Typowa implementacja AST (w języku OO) często wykorzystuje polimorfizm. Węzły w AST są zazwyczaj implementowane z różnymi klasami, wszystkie pochodzące ze wspólnej ASTNodeklasy. Dla każdego konstruktu składniowego w przetwarzanym języku będzie klasa reprezentująca ten konstrukt w AST, taka jak ConstantNode(dla stałych, takich jak 0x10lub 42), VariableNode(dla nazw zmiennych), AssignmentNode(dla operacji przypisania), ExpressionNode(dla ogólnych wyrażenia) itp.
Każdy określony typ węzła określa, czy dany węzeł ma dzieci, ile i ewentualnie jakiego typu. ConstantNodeZazwyczaj nie mają dzieci, AssignmentNodebędzie miał dwa i ExpressionBlockNodemoże mieć dowolną liczbę dzieci.

AST jest budowany przez analizator składni, który wie, jaki konstrukt właśnie przeanalizował, aby mógł zbudować odpowiedni rodzaj węzła AST.

Podczas przemierzania AST bardzo ważny jest polimorfizm węzłów. Baza ASTNodedefiniuje operacje, które mogą być wykonywane na węzłach, a każdy konkretny typ węzła implementuje te operacje w określony sposób dla tej konstrukcji języka.

Budowanie AST z tekstu źródłowego to „po prostu” parsowanie . Dokładne wykonanie tego zależy od przeanalizowanego języka formalnego i implementacji. Możesz użyć generatorów parsera, takich jak menhir (dla Ocaml) , GNU bisonz flex, ANTLR itp. Często wykonuje się to „ręcznie”, kodując jakiś parser rekurencyjnego zapisu (patrz odpowiedź wyjaśniająca dlaczego). Kontekstowy aspekt parsowania jest często wykonywany gdzie indziej (tabele symboli, atrybuty, ...).

Jednak w praktyce AST są o wiele bardziej złożone niż myślisz. Na przykład w kompilatorze takim jak GCC AST przechowuje informacje o lokalizacji źródła i niektóre informacje o pisaniu. Przeczytaj o Generic Trees w GCC i zajrzyj do jego gcc / tree.def . BTW, zajrzyj również do GCC MELT (które zaprojektowałem i wdrożyłem), to jest istotne dla twojego pytania.

Wiem, że to pytanie ma ponad 4 lata, ale uważam, że powinienem dodać bardziej szczegółową odpowiedź.

Streszczenie Składnia Drzewa nie są tworzone inaczej niż inne drzewa; bardziej prawdziwe stwierdzenie w tym przypadku jest takie, że węzły drzewa składni mają różnorodną liczbę węzłów, JAK POTRZEBUJĄ.

Przykładem są wyrażenia binarne, takie jak 1 + 2 Proste wyrażenie, takie jak to, tworzyłoby pojedynczy węzeł główny z prawym i lewym węzłem, który przechowywałby dane o liczbach. W języku C wyglądałoby to mniej więcej tak

struct ASTNode;
union SyntaxNode {
    int64_t         llVal;
    uint64_t        ullVal;
    struct {
        struct ASTNode *left, *right;
    } BinaryExpr;
};

enum SyntaxNodeType {
    AST_IntVal, AST_Add, AST_Sub, AST_Mul, AST_Div, AST_Mod,
};

struct ASTNode {
    union SyntaxNode *Data;
    enum SyntaxNodeType Type;
};

Twoje pytanie brzmiało także, jak przejść. W tym przypadku przemierzanie nazywa się węzłami odwiedzającymi . Odwiedzanie każdego węzła wymaga użycia każdego typu węzła w celu ustalenia sposobu oceny danych każdego węzła składni.

Oto kolejny przykład tego w C, w którym po prostu drukuję zawartość każdego węzła:

void AST_PrintNode(const ASTNode *node)
{
    if( !node )
        return;

    char *opername = NULL;
    switch( node->Type ) {
        case AST_IntVal:
            printf("AST Integer Literal - %lli\n", node->Data->llVal);
            break;
        case AST_Add:
            if( !opername )
                opername = "+";
        case AST_Sub:
            if( !opername )
                opername = "-";
        case AST_Mul:
            if( !opername )
                opername = "*";
        case AST_Div:
            if( !opername )
                opername = "/";
        case AST_Mod:
            if( !opername )
                opername = "%";
            printf("AST Binary Expr - Oper: \'%s\' Left:\'%p\' | Right:\'%p\'\n", opername, node->Data->BinaryExpr.left, node->Data->BinaryExpr.right);
            AST_PrintNode(node->Data->BinaryExpr.left); // NOTE: Recursively Visit each node.
            AST_PrintNode(node->Data->BinaryExpr.right);
            break;
    }
}

Zauważ, jak funkcja rekurencyjnie odwiedza każdy węzeł zgodnie z typem węzła, z którym mamy do czynienia.

Dodajmy bardziej złożony przykład, ifkonstrukcję instrukcji! Przypomnij sobie, że jeśli instrukcje mogą mieć również opcjonalną klauzulę else. Dodajmy instrukcję if-else do naszej oryginalnej struktury węzła. Pamiętaj, że jeśli same instrukcje mogą również zawierać instrukcje if, może wystąpić pewnego rodzaju rekurencja w naszym systemie węzłów. Inne instrukcje są opcjonalne, więc elsestmtpole może mieć wartość NULL, którą funkcja odwiedzającego rekurencyjnego może zignorować.

struct ASTNode;
union SyntaxNode {
    int64_t         llVal;
    uint64_t        ullVal;
    struct {
        struct ASTNode *left, *right;
    } BinaryExpr;
    struct {
        struct ASTNode *expr, *stmt, *elsestmt;
    } IfStmt;
};

enum SyntaxNodeType {
    AST_IntVal, AST_Add, AST_Sub, AST_Mul, AST_Div, AST_Mod, AST_IfStmt, AST_ElseStmt, AST_Stmt
};

struct ASTNode {
    union SyntaxNode *Data;
    enum SyntaxNodeType Type;
};

z powrotem w nazwie funkcji drukowania odwiedzającego węzeł AST_PrintNode, możemy dostosować konstrukcję ifinstrukcji AST, dodając ten kod C:

case AST_IfStmt:
    puts("AST If Statement\n");
    AST_PrintNode(node->Data->IfStmt.expr);
    AST_PrintNode(node->Data->IfStmt.stmt);
    AST_PrintNode(node->Data->IfStmt.elsestmt);
    break;

Tak proste jak to! Podsumowując, drzewo składniowe nie jest niczym więcej niż drzewem oznaczonego związku drzewa i jego danych!