Drzewo składni abstrakcyjnej - Abstract syntax tree

Abstrakcyjne drzewo składni dla następującego kodu dla algorytmu euklidesowego :
podczas gdy b ≠ 0 
jeśli a > b
a := a − b
inaczej
b := b − a
return a

W informatyce , drzewo składniowe ( AST ), lub po prostu składnia drzewo , to drzewo reprezentacją abstrakcyjnej syntaktycznej struktury tekstu (często kodu źródłowego ) napisany w języku formalnym . Każdy węzeł drzewa oznacza konstrukcję występującą w tekście.

Składnia jest „abstrakcyjna” w tym sensie, że nie reprezentuje wszystkich szczegółów występujących w rzeczywistej składni, ale raczej szczegóły strukturalne lub merytoryczne. Na przykład nawiasy grupujące są niejawne w strukturze drzewa, więc nie muszą być reprezentowane jako oddzielne węzły. Podobnie konstrukcja składniowa, taka jak instrukcja if-condition-then, może być oznaczona za pomocą pojedynczego węzła z trzema gałęziami.

Odróżnia to abstrakcyjne drzewa składni od konkretnych drzew składni, tradycyjnie określanych drzewami parsowania . Drzewa analizy są zazwyczaj budowane przez parser podczas procesu tłumaczenia i kompilacji kodu źródłowego . Po zbudowaniu, dodatkowe informacje są dodawane do AST za pomocą późniejszego przetwarzania, np . analizy kontekstowej .

Abstrakcyjne drzewa składni są również używane w systemach analizy programów i transformacji programów .

Aplikacja w kompilatorach

Abstrakcyjne drzewa składni to struktury danych szeroko stosowane w kompilatorach do reprezentowania struktury kodu programu. AST jest zwykle wynikiem fazy analizy składni kompilatora. Często służy jako pośrednia reprezentacja programu przez kilka etapów wymaganych przez kompilator i ma silny wpływ na końcowy wynik kompilatora.

Motywacja

AST ma kilka właściwości, które pomagają w dalszych etapach procesu kompilacji:

  • AST można edytować i wzbogacać o informacje, takie jak właściwości i adnotacje dla każdego zawartego w nim elementu. Taka edycja i adnotacja jest niemożliwa w kodzie źródłowym programu, ponieważ oznaczałoby to jego zmianę.
  • W porównaniu z kodem źródłowym AST nie zawiera nieistotnych znaków interpunkcyjnych i ograniczników (nawiasów klamrowych, średników, nawiasów itp.).
  • AST zwykle zawiera dodatkowe informacje o programie, ze względu na kolejne etapy analizy przez kompilator. Na przykład może przechowywać pozycję każdego elementu w kodzie źródłowym, umożliwiając kompilatorowi drukowanie przydatnych komunikatów o błędach.

AST są potrzebne ze względu na nieodłączną naturę języków programowania i ich dokumentacji. Języki są często z natury niejednoznaczne. Aby uniknąć tej niejednoznaczności, języki programowania są często określane jako gramatyka bezkontekstowa (CFG). Jednak 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 takich typów ani sposobu ich użycia. Nawet jeśli język ma predefiniowany zestaw typów, wymuszenie właściwego 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 ostateczna funkcja są określane na podstawie kontekstu. Doskonałym przykładem jest Java, gdzie operator „+” jest zarówno dodawaniem liczb, jak i łączeniem łańcuchów.

Chociaż istnieją inne struktury danych zaangażowane w wewnętrzne działanie kompilatora, AST pełni unikalną funkcję. Podczas pierwszego etapu, etapu analizy składni , kompilator tworzy drzewo analizy. To drzewo parsowania może być używane do wykonywania prawie wszystkich funkcji kompilatora za pomocą tłumaczenia ukierunkowanego na składnię. Chociaż ta metoda może prowadzić do wydajniejszego kompilatora, jest ona sprzeczna z zasadami inżynierii oprogramowania dotyczącymi pisania i utrzymywania programów. Kolejną zaletą, jaką AST ma nad drzewem parsowania, jest rozmiar, w szczególności mniejsza wysokość AST i mniejsza liczba elementów.

Projekt

Projekt AST jest często ściśle powiązany z projektem kompilatora i jego oczekiwanymi funkcjami.

Podstawowe wymagania obejmują:

  • Należy zachować typy zmiennych, a także lokalizację każdej deklaracji w kodzie źródłowym.
  • Kolejność instrukcji wykonywalnych musi być wyraźnie przedstawiona i dobrze zdefiniowana.
  • Lewe i prawe składniki operacji binarnych muszą być przechowywane i poprawnie identyfikowane.
  • Identyfikatory i przypisane im wartości muszą być przechowywane dla instrukcji przypisania.

Wymagania te można wykorzystać do zaprojektowania struktury danych dla AST.

Niektóre operacje zawsze będą wymagały dwóch elementów, takich jak dwa terminy dodawania. Jednak niektóre konstrukcje językowe wymagają arbitralnie dużej liczby elementów potomnych, na przykład listy argumentów przekazywane do programów z powłoki poleceń . W rezultacie AST używany do reprezentowania kodu napisanego w takim języku musi być również na tyle elastyczny, aby umożliwić szybkie dodanie nieznanej ilości dzieci.

Aby wesprzeć weryfikację kompilatora, powinno być możliwe przetworzenie AST do postaci kodu źródłowego. Wytworzony kod źródłowy powinien być wystarczająco podobny do oryginalnego wyglądu i identyczny w wykonaniu po ponownej kompilacji.

Stosowanie

AST jest intensywnie wykorzystywany 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 drzewa pozwala na weryfikację poprawności 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.

Zobacz też

Bibliografia

  • Ten artykuł jest oparty na materiale zaczerpniętym z bezpłatnego słownika komputerowego on-line sprzed 1 listopada 2008 r. i włączonym na warunkach „ponownego licencjonowania” GFDL w wersji 1.3 lub nowszej.

Dalsza lektura

  • Jones, Joel. "Idiomy implementacji drzewa składni abstrakcyjnego" (PDF) . Cytowanie dziennika wymaga |journal=( pomoc ) (przegląd implementacji AST w różnych rodzinach językowych)
  • Neamtiu, Iulian; Foster, Jeffrey S.; Hicks, Michael (17 maja 2005). Zrozumienie ewolucji kodu źródłowego przy użyciu abstrakcyjnego dopasowania drzewa składni . MSR'05. Saint Louis, Missouri: ACM. CiteSeerX  10.1.1.88.5815 .
  • Baxter, Ira D.; Jahin, Andrzej; Moura, Leonardo; Sant'Anna, Marcelo; Bier, Lotaryngia (16-19 listopada 1998). Wykrywanie klonów za pomocą abstrakcyjnych drzew składni (PDF) . Postępowanie ICSM'98 . Bethesda, Maryland: IEEE .
  • Fluri, Beat; Würsch, Michael; Pinzgera, Marcina; Gall, Harald C. „Zmiana destylacji: różnicowanie drzewa dla drobnoziarnistego wyodrębniania zmian kodu źródłowego” (PDF) . Cytowanie dziennika wymaga |journal=( pomoc )( bezpośredni link do PDF )
  • Würsch, Michael. Poprawa wykrywania zmian kodu źródłowego w oparciu o drzewo składni abstrakcyjnej (praca dyplomowa).
  • Falleri, Jean-Remy; Morandat, Floréal; Blanc, Xavier; Martinez, Matias; Monperrus, Marcin. Drobnoziarniste i dokładne różnicowanie kodu źródłowego (PDF) . Postępowanie ASE 2014 . doi : 10.1145/2642937.2642982 .
  • Lucas, Jason. „Myśli o abstrakcyjnym drzewie składni języka Visual C++ (AST)” .

Zewnętrzne linki