Abstrakcyjne drzewa składniowe są strukturami danych szeroko stosowanymi w kompilatorach do reprezentowania struktury kodu programu. AST jest zwykle wynikiem fazy analizy składniowej kompilatora. Często służy jako pośrednia reprezentacja programu przez kilka etapów, których wymaga kompilator, i ma duży wpływ na końcowe wyjście kompilatora.
MotywacjaEdycja
An AST ma kilka właściwości, które pomagają w dalszych etapach procesu kompilacji:
- An AST może być edytowana i wzbogacana o informacje takie jak właściwości i adnotacje dla każdego elementu, który zawiera. Taka edycja i adnotacje są niemożliwe w przypadku kodu źródłowego programu, gdyż oznaczałyby jego zmianę.
- W porównaniu z kodem źródłowym, AST nie zawiera zbędnej interpunkcji i delimitatorów (nawiasów, średników, nawiasów itp.).
- An AST zawiera zwykle dodatkowe informacje o programie, wynikające z kolejnych etapów analizy przez kompilator. Na przykład, może przechowywać pozycję każdego elementu w kodzie źródłowym, pozwalając kompilatorowi na drukowanie użytecznych komunikatów o błędach.
AST-y są potrzebne ze względu na nieodłączną naturę języków programowania i ich dokumentacji. Języki są często wieloznaczne z natury. Aby uniknąć tej niejednoznaczności, języki programowania są często określane jako gramatyka bezkontekstowa (CFG). Jednakże, często istnieją aspekty języków programowania, których CFG nie może wyrazić, ale są częścią języka i są udokumentowane w jego specyfikacji. Są to szczegóły, które wymagają kontekstu, aby określić ich ważność i zachowanie. Na przykład, jeśli język pozwala na deklarowanie nowych typów, CFG nie może przewidzieć nazw tych typów ani sposobu, w jaki powinny być one używane. Nawet jeśli język posiada predefiniowany zestaw typów, wymuszenie ich prawidłowego użycia zwykle wymaga pewnego kontekstu. Innym przykładem jest duck typing, gdzie typ elementu może się zmieniać w zależności od kontekstu. Przeciążanie operatorów to kolejny przypadek, w którym poprawne użycie i funkcja końcowa są określane na podstawie kontekstu. Doskonałym przykładem jest Java, gdzie operator '+’ jest zarówno numerycznym dodawaniem, jak i konkatenacją łańcuchów znaków.
Chociaż istnieją inne struktury danych zaangażowane w wewnętrzne funkcjonowanie kompilatora, AST pełni unikalną funkcję. Podczas pierwszego etapu, etapu analizy składni, kompilator wytwarza drzewo parsowania. To drzewo parseków może być użyte do wykonania prawie wszystkich funkcji kompilatora za pomocą tłumaczenia ukierunkowanego na składnię. Chociaż ta metoda może prowadzić do stworzenia bardziej wydajnego kompilatora, jest ona sprzeczna z zasadami inżynierii oprogramowania dotyczącymi pisania i utrzymywania programów. Kolejną zaletą, jaką AST ma w porównaniu z drzewem parsującym, jest rozmiar, w szczególności mniejsza wysokość AST i mniejsza liczba elementów.
DesignEdit
Projekt AST jest często ściśle powiązany z projektem kompilatora i jego oczekiwanymi funkcjami.
Podstawowe wymagania obejmują następujące kwestie:
- Typy zmiennych muszą być zachowane, podobnie jak położenie każdej deklaracji w kodzie źródłowym.
- Porządek instrukcji wykonywalnych musi być jawnie reprezentowany i dobrze zdefiniowany.
- Lewe i prawe składowe operacji binarnych muszą być przechowywane i poprawnie identyfikowane.
- Identyfikatory i ich przypisane wartości muszą być przechowywane dla instrukcji przypisania.
Wymagania te mogą być użyte do zaprojektowania struktury danych dla AST.
Niektóre operacje zawsze będą wymagały dwóch elementów, takich jak dwa wyrażenia dla dodawania. Jednakże, niektóre konstrukcje językowe wymagają arbitralnie dużej liczby dzieci, takich jak listy argumentów przekazywane do programów z powłoki poleceń. W rezultacie, AST używany do reprezentacji kodu napisanego w takim języku musi być również wystarczająco elastyczny, aby umożliwić szybkie dodanie nieznanej ilości dzieci.
Aby wspomóc weryfikację kompilatora, powinno być możliwe rozszyfrowanie AST do postaci kodu źródłowego. Wyprodukowany kod źródłowy powinien być wystarczająco podobny do oryginału w wyglądzie i identyczny w wykonaniu, przy ponownej kompilacji.
UsageEdit
AST jest intensywnie wykorzystywana podczas analizy semantycznej, gdzie kompilator sprawdza poprawność użycia elementów programu i języka. Kompilator generuje również tablice symboli na podstawie AST podczas analizy semantycznej. Pełne przejście przez drzewo pozwala zweryfikować poprawność programu.
Po zweryfikowaniu poprawności, AST służy jako baza do generowania kodu. AST jest często używany do generowania reprezentacji pośredniej (IR), czasami nazywanej językiem pośrednim, do generowania kodu.
.