Jak dokładnie tworzone jest drzewo składni abstrakcyjnej?

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

Do Twojej wiadomości, tu Algorytm manewrowania na placu .

W tym przypadku użyję stosu operatorów i stosu wyrażeń. Ponieważ w większości języków liczby są uważane za wyrażenia, 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 z moim kodem. Wiem, że to nie jest solidny; to powinien być tylko pseudokod.)

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

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

kod, który napisałem, dałby takie AST:

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

A następnie, gdy chcesz wygenerować kod dla tego AST, wykonaj przemierzanie drzewa zamówienia końcowego . odwiedzasz węzeł liścia (z liczbą), generujesz stałą, ponieważ kompilator musi znać wartości argumentów. Gdy odwiedzasz węzeł z operatorem, generujesz odpowiednią instrukcję od operatora. Na przykład znak „+” operator daje instrukcję „dodaj”.

Komentarze

• Działa to dla r operatory, które mają asocjatywność od lewej do prawej, a nie od prawej do lewej.
• @Simon, dodanie możliwości dla operatorów od prawej do lewej byłoby niezwykle proste. Najprościej byłoby dodać tabelę przeglądową i jeśli operator jest operatorem od prawej do lewej, po prostu odwróć kolejność operandów.
• @Simon Jeśli chcesz obsługiwać oba, ' lepiej przyjrzeć się algorytmowi stacji manewrowej w pełnej okazałości. W miarę rozwoju algorytmów to ' jest absolutnym crackerem.

Istnieje znacząca różnica między sposobem, w jaki AST jest zazwyczaj przedstawiany 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 faktycznie implementowany.

Typowe implementacja AST (w języku OO) w dużym stopniu wykorzystuje polimorfizm. Węzły w AST są zwykle implementowane za pomocą różnych klas, z których wszystkie pochodzą ze wspólnej klasy ASTNode. Dla każdej konstrukcji składniowej w przetwarzanym języku będzie klasa reprezentująca tę konstrukcję w AST, na przykład ConstantNode (dla stałych, takich jak 0x10 lub 42), VariableNode (dla nazw zmiennych), AssignmentNode (dla operacji przypisania), ExpressionNode (dla wyrażeń ogólnych) itp.
Każdy konkretny typ węzła określa, czy ten węzeł ma dzieci, ile i ewentualnie jakiego typu. ConstantNode zazwyczaj nie będzie mieć elementów podrzędnych, AssignmentNode będzie miało dwa, a ExpressionBlockNode może mieć dowolną liczbę dzieci.

AST jest budowany przez parser, który wie, jaką konstrukcję właśnie przeanalizował, więc może skonstruować odpowiedni rodzaj węzła AST.

Podczas przechodzenia AST, polimorfizm węzłów naprawdę wchodzi w grę. Podstawowy ASTNode definiuje operacje, które mogą być wykonywane na węzłach, a każdy określony typ węzła implementuje te operacje w określony sposób dla tej konkretnej konstrukcji językowej.

Tworzenie AST na podstawie tekstu źródłowego jest ” po prostu ” parsowanie . To, jak dokładnie to się robi, zależy od przeanalizowanego języka formalnego i implementacji. Możesz użyć generatorów parsera, takich jak menhir (dla Ocaml) , GNU bison z flex lub ANTLR itd. itd. Często jest to wykonywane ” ręcznie ” przez kodowanie jakiegoś rekurencyjnego parsera zstępującego (patrz tę odpowiedź wyjaśniającą dlaczego). Kontekstowy aspekt parsowania jest często wykonywany gdzie indziej (tabele symboli, atrybuty, …).

Jednak w praktyce AST są znacznie bardziej złożone niż to, w co wierzysz. Na przykład w kompilatorze takim jak GCC AST przechowuje informacje o lokalizacji źródła i niektóre informacje o wpisywaniu. Przeczytaj o Drzewa ogólne i GIMPLE w GCC i zajrzyj do jego gcc / tree.def . Zastanów się, czy chcesz przetwarzać C, C ++, Fortran lub Adę, pisząc własną wtyczkę GCC . Swoją drogą, zajrzyj też do przestarzałego GCC MELT (które zaprojektowałem & zaimplementowanym), dotyczy pytanie. Przeczytaj Dragon book . Zobacz także tę wersję roboczą raportu w celu uzyskania referencji, a także projekt RefPerSys i kod źródłowy wielu inne projekty open source (w tym Ocaml lub Guile lub SBCL lub Jq ) na github lub gitlab jako przykłady.

Komentarze

• Ja ' robię interpreter Lua do analizowania tekstu źródłowego i przekształcania w tablicę w JS. Czy mogę to uznać za AST? Mam ' mam zrobić coś takiego: --My comment #1 print("Hello, ".."world.") przekształca się w „[{” wpisz „: ” – „, ” content „: ” Mój komentarz nr 1 „}, {” wpisz „: ” zadzwoń „, ” name „: ” print „, ” argumenty „: [[{” typ „: ” str „, ” akcja „: ” .. „, ” treść „: ” Witaj, „}, {” wpisz „: ” str „, ” content „: ” świat. „}]]}] `Myślę, że ' jest znacznie prostsze w JS niż w jakimkolwiek innym języku!
• @TheProHands To będzie traktowane jako tokeny, a nie AST.

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

Abstrakcyjne drzewa składniowe są tworzone nie inaczej niż inne drzewa; bardziej prawdziwe stwierdzenie w tym przypadku jest takie, że węzły drzewa składni mają różną liczbę węzłów, JAK POTRZEBUJESZ.

Przykładem są wyrażenia binarne, takie jak 1 + 2 Proste wyrażenie, takie jak co stworzyłoby pojedynczy węzeł główny zawierający prawy i lewy węzeł, który przechowuje 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 dotyczyło również sposobu przejścia? Trawers w tym przypadku nazywa się Węzły odwiedzające . Odwiedzenie każdego węzła wymaga użycia każdego typu węzła w celu określenia sposobu oceny danych każdego węzła składni.

Oto kolejny przykład tego w C, gdzie po prostu wypisuję 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; } } 

Zwróć uwagę, 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, konstrukcję instrukcji if! Przypomnijmy, że instrukcje if może mieć również opcjonalną klauzulę else. Dodajmy instrukcję if-else do naszej oryginalnej struktury węzłów. Pamiętaj, że same instrukcje if mogą również zawierać instrukcje if, więc może wystąpić pewnego rodzaju rekursja w naszym systemie węzłów. W przeciwnym razie instrukcje są opcjonalne, więc pole elsestmt może mieć wartość NULL, co rekursywna funkcja gościa może ignorować.

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

wstecz w naszej funkcji drukowania odwiedzających węzeł o nazwie AST_PrintNode, możemy uwzględnić konstrukcję AST instrukcji if, dodając następujący kod C:

div id = „94509e4238”>