Uczę się na własną rękę o pisaniu tłumacza dla języka programowania, a ja czytałem o drzewach składni abstrakcyjnych. Mam pojęcie, czym one są, ale nie widzę ich użycia.Co to jest wykorzystanie abstrakcyjnych drzew składni?
Dlaczego AST są przydatne?
Reprezentują logikę/składnię kodu, który jest naturalnie drzewem, a nie listą wierszy, bez zagnieżdżania się w konkretnych kwestiach składniowych, takich jak: place your asterisk.
Logika może być następnie zmanipulowana w sposób bardziej spójny i wygodny z POV backendu, który może być (i jest dla wszystkiego oprócz Lisps) bardzo różny od tego, jak piszemy konkretną składnię.
Dlaczego więc miałbym używać AST zamiast po prostu tworzyć strumień rzeczy takich jak "IDENTIFIER blah ASTERISK NUMBER 4" i mieć FSM lub coś zejść i zjeść jeden żeton na raz? – RacecaR
@Rac: To, co opisujesz, jest krokiem pomiędzy nieprzetworzonym plikiem a generowaniem AST. Oznacza to: raw -> tokeny -> AST. BinaryOp (Multiply, Identifier ("blah"), Integer (4)) jest wygodniejsze dla backendu. –
@RacecaR twój FSM do parsowania zjadłby strumień do wyprodukowania AST; Twoje procedury generowania kodu i optymalizacji używają AST –
Ogólnie rzecz biorąc zamierzasz przeanalizować kod w jakiejś formie AST, może to być mniej więcej formalny model. Więc myślę o tym, co Kirk Woll osiągnął dzięki powyższemu komentarzowi, jest taki, że kiedy parsujesz ten język, bardzo często używasz parsera do stworzenia jakiegoś modelu danych surowej treści tego, co czytasz, ogólnie zorganizowanego w sposób drzewiasty. . Tak więc z tej definicji trudno jest uniknąć AST, chyba że robisz bardzo prostego tłumacza.
Często używam ANTLR do analizowania złożonych języków iw tym kontekście jest nieco bardziej konkretne znaczenie AST. ANTLR ma przydatny sposób generowania AST w gramatyce parsera za pomocą prostych czynności. Następnie należy napisać o wiele prostszy analizator składni dla tego AST, który można obsługiwać w znacznie prostszej wersji językiem, który przetwarza. To, czy dodatkowa praca polegająca na budowaniu dwóch parserów jest zyskiem netto, jest funkcją złożoności języka i tego, co planujesz z nim zrobić po przeanalizowaniu.
Dobra książka na ten temat, na którą możesz rzucić okiem, to "Wzorce implementacji języka" autorstwa Terrence'a Parra, autora ANTLR. Bardzo dokładnie zajmuje się tym tematem. Powiedział, że tak naprawdę nie dostałem AST, dopóki nie zacząłem ich używać, więc (jak zwykle) jest najlepszym sposobem na ich zrozumienie.
Główna korzyść przy użyciu metody AST polega na oddzieleniu logiki analizy i walidacji od elementu implementacji. Interpretatorzy zaimplementowani jako AST naprawdę są łatwiejsze do zrozumienia i utrzymania. Jeśli masz problem z analizą dziwnej składni, to spoglądasz na analizator AST, jeśli kiki kodu nie przynoszą oczekiwanych rezultatów, niż patrzysz na kod interpretujący AST.
Inną wielką zaletą jest to, że składnia wymaga "uprzedzenia", np. jeśli twoja składnia pozwala na użycie podprogramu przed jego zdefiniowaniem, to jest trywialne sprawdzanie istnienia podprogramu, gdy używasz AST - jego znacznie trudniejsze z parserem "w locie".
Dzięki. Właśnie pracowałem przy budowaniu parserów z Javą, który twierdzi, że budowanie AST jest dodatkowym kłopotem, niż jest to warte w prostych językach. Twój jest jedynym komentarzem na tej stronie, który nawet potwierdza, że można zrobić coś pożytecznego bez budowania AST. – kybernetikos
Potrzebne są "drzewa składniowe" do reprezentowania struktury większości programów językowych, w celu przeprowadzenia analizy lub przekształcenia dokumentów zawierających tekst w języku programowania. (Możesz zobaczyć kilka ciekawych przykładów tego poprzez mój bio).
To, czy drzewo jest abstrakcyjne (AST), czy betonowe (CST), to kwestia gustu, wygody i inżynieryjnego potu. Termin CST jest specjalnie używany do opisu drzewa wartości parse, gdy do dekonstrukcji kodu źródłowego użyta jest gramatyka; zwykle zawiera elementy drzewa dla wielu konkretnych składni, takich jak średniki terminatora instrukcji. AST ma na myśli "coś prostszego niż CST", np. Pomijając węzły drzewa średnika, ponieważ nie wpływają one znacząco na analizę programu, a zatem pisanie analizatorów, które przetwarzają AST, jest mniej wysiłkiem koncepcyjnym i inżynieryjnym niż pisanie tego samego analizatora na CST. Lepszym sposobem zrozumienia tego jest zrozumienie, że AST jest zwykle izomorficznym odpowiednikiem CST, to znaczy, że powinieneś być w stanie zregenerować CST.Jeśli chcesz przekształcić tekst źródłowy i zregenerować go, wówczas CST jest często lepszym wyborem, ponieważ traci mniej informacji z oryginalnego programu (a mój fantazyjny przykład używa tego podejścia).
Uważam, że dyskusja na temat SO na stronie abstract vs. concrete syntax trees jest bardzo pomocna.
W jaki sposób planujesz modelować składnię języka bez AST? tj. podczas pisania parser/kompilator/interpreter/etc. –