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ł.
źródło
Odpowiedzi:
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.
(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:
kod, który napisałem, wytworzyłby ten AST:
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”.
źródło
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
ASTNode
klasy. Dla każdego konstruktu składniowego w przetwarzanym języku będzie klasa reprezentująca ten konstrukt w AST, taka jakConstantNode
(dla stałych, takich jak0x10
lub42
),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.
ConstantNode
Zazwyczaj nie mają dzieci,AssignmentNode
będzie miał dwa iExpressionBlockNode
moż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
ASTNode
definiuje 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.źródło
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
bison
zflex
, 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.
źródło
--My comment #1 print("Hello, ".."world.")
przekształca się w `[{" type ":" - ", content": "My comment # 1"}, {"type": "call", "name": " print ”,„ argumenty ”: [[{„ type ”:„ str ”,„ action ”:„ .. ”,„ content ”:„ Hello, ”}, {„ type ”:„ str ”,„ content ”: "świat." }]]}] `Myślę, że w JS jest o wiele prostszy niż w jakimkolwiek innym języku!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 takTwoje 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:
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,
if
konstrukcję 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ęcelsestmt
pole może mieć wartość NULL, którą funkcja odwiedzającego rekurencyjnego może zignorować.z powrotem w nazwie funkcji drukowania odwiedzającego węzeł
AST_PrintNode
, możemy dostosować konstrukcjęif
instrukcji AST, dodając ten kod C:Tak proste jak to! Podsumowując, drzewo składniowe nie jest niczym więcej niż drzewem oznaczonego związku drzewa i jego danych!
źródło