Jaka jest różnica między abstrakcyjnym drzewem składni a konkretnym drzewem składni?

Czytałem trochę o tym, jak działają interpretery / kompilatory, a jednym z obszarów, w których jestem zdezorientowany, jest różnica między AST a CST. Rozumiem, że parser tworzy CST, przekazuje go do analizatora semantycznego, który zamienia go w AST. Jednak rozumiem, że analizator semantyczny zapewnia po prostu przestrzeganie reguł. Naprawdę nie rozumiem, dlaczego faktycznie wprowadziłby jakieś zmiany, aby uczynić go abstrakcyjnym, a nie konkretnym.

Czy jest coś, czego mi brakuje w analizatorze semantycznym, czy też różnica między AST i CST jest nieco sztuczna?

Konkretne drzewo składni przedstawia tekst źródłowy dokładnie w formie przeanalizowanej. Ogólnie rzecz biorąc, jest to zgodne z gramatyką bezkontekstową definiującą język źródłowy.

Jednak konkretna gramatyka i drzewo mają wiele rzeczy, które są niezbędne, aby tekst źródłowy był jednoznacznie analizowalny, ale nie przyczyniają się do rzeczywistego znaczenia. Na przykład, aby zaimplementować pierwszeństwo operatorów, twój CFG ma zwykle kilka poziomów składników wyrażenia (termin, czynnik, itp.), A operatory łączą je na różnych poziomach (dodajesz terminy, aby uzyskać wyrażenia, terminy składają się z czynników opcjonalnie mnożonych itp.). Jednak aby faktycznie zinterpretować lub skompilować język, nie potrzebujesz tego; potrzebujesz tylko węzłów Expression, które mają operatory i operandy. Abstrakcyjne drzewo składni jest wynikiem uproszczenia konkretnego drzewa składni do rzeczy faktycznie potrzebnych do przedstawienia znaczenia programu. To drzewo ma znacznie prostszą definicję i dlatego jest łatwiejsze do przetworzenia na późniejszych etapach wykonywania.

Zwykle nie ma potrzeby tworzenia konkretnego drzewa składni. Procedury akcji w gramatyce YACC (lub Antlr, Menhir, czy cokolwiek ...) mogą bezpośrednio budować abstrakcyjne drzewo składni, więc konkretne drzewo składni istnieje tylko jako pojęciowy byt reprezentujący strukturę parsowania tekstu źródłowego.

Drzewo składni betonu odpowiada co gramatyka zasady powiedzieć to składnia. Celem abstrakcyjnego drzewa składni jest „prosta” reprezentacja tego, co jest istotne w „drzewie składni”.

Prawdziwą wartością w AST IMHO jest to, że jest mniejszy niż CST, a zatem jego przetwarzanie zajmuje mniej czasu. (Można powiedzieć, kogo to obchodzi? Ale pracuję z narzędziem, w którym mamy dziesiątki milionów węzłów na raz!).

Większość generatorów parserów, które mają jakiekolwiek wsparcie dla budowania drzew składni nalega, abyś osobiście określił sposób ich budowania przy założeniu, że twoje węzły drzewa będą "prostsze" niż CST (iw tym ogólnie mają rację, ponieważ programiści są ładni leniwy). Prawdopodobnie oznacza to, że musisz kodować mniej funkcji odwiedzających drzewo, a jest to również cenne, ponieważ minimalizuje energię inżynierską. Jeśli masz 3500 reguł (np. W języku COBOL), ma to znaczenie. I ta „prostsza” prostota prowadzi do dobrej właściwości „małości”.

Ale posiadanie takich AST stwarza problem, którego nie było: nie pasuje do gramatyki, a teraz musisz mentalnie śledzić oba z nich. A kiedy istnieje 1500 węzłów AST dla gramatyki 3500 reguł, ma to duże znaczenie. A jeśli gramatyka ewoluuje (zawsze tak jest!), Teraz masz dwa gigantyczne zestawy rzeczy do synchronizacji.

Innym rozwiązaniem jest pozwolić parserowi po prostu zbudować dla ciebie węzły CST i po prostu ich użyć. Jest to ogromna zaleta podczas tworzenia gramatyk: nie ma potrzeby wymyślania 1500 specjalnych węzłów AST, aby modelować 3500 reguł gramatycznych. Pomyśl tylko o tym, że drzewo jest izomorficzne z gramatyką. Z punktu widzenia inżyniera gramatyki jest to całkowicie bezmózgowe, co pozwala mu skupić się na poprawieniu gramatyki i hakowaniu jej do syta. Prawdopodobnie musisz napisać więcej reguł dotyczących odwiedzających węzeł, ale można nimi zarządzać. Więcej o tym później.

To, co robimy z DMS Software Reengineering Toolkit, to automatyczne tworzenie CST na podstawie wyników procesu analizy (GLR). Następnie DMS automatycznie konstruuje „skompresowany” CST ze względu na oszczędność miejsca, eliminując terminale nie przenoszące wartości (słowa kluczowe, znaki interpunkcyjne), semantycznie bezużyteczne produkcje jednoargumentowe i tworząc listy par reguł gramatycznych, które są listami takimi jak:

    L = e ;
    L = L e ;
    L2 = e2 ;
    L2 = L2  ','  e2 ;

oraz szeroką gamę odmian takich form. Myślisz w kategoriach reguł gramatycznych i wirtualnego CST; narzędzie działa na skompresowanej reprezentacji. Przyjazny dla mózgu, szybszy / mniejszy w czasie wykonywania.

Co ciekawe, skompresowany CST zbudowany w ten sposób wygląda na AST, który mógłbyś zaprojektować ręcznie (patrz link na końcu do przykładów). W szczególności skompresowany CST nie zawiera żadnych węzłów, które są po prostu konkretną składnią. Są to drobne kawałki niezręczności, na przykład: podczas gdy węzły betonowe dla „(” i „)” klasycznie znalezione w subgrammars wypowiedzi nie są w drzewie, „nawiasy węzła” ma pojawić się w sprężonym CST i musi być obsługiwane. Prawdziwy AST by tego nie miał. Wydaje się, że jest to dość niewielka cena za wygodę polegającą na tym, że nigdy nie trzeba określać konstrukcji AST. Dokumentacja drzewa jest zawsze dostępna i poprawna: gramatyka jest dokumentacją.

Jak uniknąć „dodatkowych gości”? Nie do końca, ale DMS zapewnia bibliotekę AST, która obsługuje AST i w przejrzysty sposób obsługuje różnice między CST i AST. DMS oferuje również ewaluator „gramatyki atrybutów” (AGE), który jest metodą przekazywania wartości obliczanych przez węzły w górę iw dół drzewa; AGE zajmuje się wszystkimi kwestiami związanymi z reprezentacją drzewa, więc inżynier narzędziowy martwi się tylko o efektywne pisanie obliczeń bezpośrednio na zasadach gramatycznych. Wreszcie, DMS zapewnia również wzorce „składni powierzchniowej”, które pozwalają fragmentom kodu od gramatyki do używanej do znajdowania określonych typów poddrzew, bez znajomości większości typów węzłów.

Jedna z pozostałych odpowiedzi mówi, że jeśli chcesz zbudować narzędzia, które mogą regenerować źródło, twoje AST będzie musiało pasować do CST. To nie do końca prawda, ale o wiele łatwiej jest zregenerować źródło, jeśli masz węzły CST. DMS generuje większość prettyprintera automatycznie, ponieważ ma dostęp do obu: -}

Konkluzja: AST są dobre dla małych, zarówno fizycznych, jak i koncepcyjnych. Zautomatyzowana konstrukcja AST z CST zapewnia jedno i drugie i pozwala uniknąć problemu śledzenia dwóch różnych zestawów.

EDYCJA Marzec 2015: Link do przykładów CST vs. „AST” zbudowanych w ten sposób

Jest to oparte na gramatyce Expression Evaluator autorstwa Terrence'a Parra.

Gramatyka dla tego przykładu:

grammar Expr002;

options 
{
    output=AST;
    ASTLabelType=CommonTree; // type of $stat.tree ref etc...
}

prog    :   ( stat )+ ;

stat    :   expr NEWLINE        -> expr
        |   ID '=' expr NEWLINE -> ^('=' ID expr)
        |   NEWLINE             ->
        ;

expr    :   multExpr (( '+'^ | '-'^ ) multExpr)*
        ; 

multExpr
        :   atom ('*'^ atom)*
        ; 

atom    :   INT 
        |   ID
        |   '('! expr ')'!
        ;

ID      : ('a'..'z' | 'A'..'Z' )+ ;
INT     : '0'..'9'+ ;
NEWLINE : '\r'? '\n' ;
WS      : ( ' ' | '\t' )+ { skip(); } ;

Wejście

x=1
y=2
3*(x+y)

Drzewo analizy

Drzewo analizy jest konkretną reprezentacją danych wejściowych. Drzewo analizy zachowuje wszystkie informacje wejściowe. Puste pola reprezentują białe znaki, czyli koniec linii.

AST

AST to abstrakcyjna reprezentacja danych wejściowych. Zauważ, że pareny nie są obecne w AST, ponieważ asocjacje można wyprowadzić ze struktury drzewa.

EDYTOWAĆ

Aby uzyskać więcej informacji, zobacz Kompilatory i generatory kompilatorów str. 23

Ten post na blogu może być pomocny.

Wydaje mi się, że AST „wyrzuca” wiele średniozaawansowanych informacji gramatycznych / strukturalnych, które nie miałyby wpływu na semantykę. Na przykład, nie obchodzi cię, że 3 jest atomem jest terminem jest współczynnikiem jest ... Po prostu obchodzi Cię, że jest to, 3gdy implementujesz wyrażenie potęgujące lub cokolwiek innego.

Drzewo składni betonu zgodnie z zasadami gramatyki języka. W gramatyce „listy wyrażeń” są zwykle definiowane za pomocą dwóch reguł

• lista_wyrażeń może być: wyrażenie
• lista_wyrażeń może być: wyrażenie, lista_wyrażeń

Następujące dosłownie, te dwie reguły nadają kształt grzebienia każdej liście wyrażeń, która pojawia się w programie.

Drzewo składniowe jest w formie, która jest wygodna dla dalszych manipulacji. Przedstawia rzeczy w sposób, który ma sens dla kogoś, kto rozumie znaczenie programów, a nie tylko sposób, w jaki są napisane. Powyższa lista wyrażeń, która może być listą argumentów funkcji, może być dogodnie reprezentowana jako wektor wyrażeń, ponieważ dla analizy statycznej lepiej jest mieć jawnie dostępną całkowitą liczbę wyrażeń i mieć dostęp do każdego wyrażenia za pomocą jego indeks.

Po prostu AST zawiera tylko semantykę kodu, drzewo parsowania / CST zawiera również informacje o tym, jak dokładnie kod został napisany.

Konkretne drzewo składni zawiera wszystkie informacje, takie jak zbędne nawiasy, spacje i komentarze, a abstrakcyjne drzewo składni oddziela te informacje.

Uwaga: to dość zabawne, kiedy zaimplementujesz silnik refaktoryzacji, twój AST będzie ponownie zawierał wszystkie konkretne informacje, ale będziesz dalej nazywać go AST, ponieważ stało się to standardowym terminem w tej dziedzinie (więc można powiedzieć, że ma już dawno temu stracił swoje pierwotne znaczenie).

To różnica, która nie robi różnicy.

AST jest zwykle wyjaśniany jako sposób przybliżenia semantyki wyrażenia języka programowania poprzez odrzucenie treści leksykalnej. Na przykład w gramatyce bezkontekstowej możesz napisać następującą regułę EBNF

term: atom (('*' | '/') term )*

podczas gdy w przypadku AST używasz tylko mul_rule i div_rule, które wyrażają właściwe operacje arytmetyczne.

Czy w ogóle nie można tych reguł wprowadzić do gramatyki? Oczywiście. Możesz przepisać powyższą zwięzłą i abstrakcyjną regułę, dzieląc ją na bardziej konkretne reguły używane do naśladowania wspomnianych węzłów AST:

term: mul_rule | div_rule
mul_rule: atom ('*' term)*
div_rule: atom ('/' term)*

Teraz, kiedy myślisz w kategoriach parsowania odgórnego, drugi termin wprowadza PIERWSZY / PIERWSZY konflikt między regułą mul_rule i div_rule, z którym parser LL (1) nie może sobie poradzić. Pierwsza forma reguły była lewostronną wersją drugiej, która skutecznie eliminowała strukturę. Za korzystanie z LL (1) musisz zapłacić tutaj jakąś nagrodę.

Tak więc AST są dodatkami ad hoc używanymi do naprawy braków gramatyki i parserów. Transformacja CST -> AST to ruch refaktoryzacyjny. Nikt nigdy nie przejmował się, gdy w drzewie składni przechowywany był dodatkowy przecinek lub dwukropek. Wręcz przeciwnie, niektórzy autorzy modernizują je w AST, ponieważ lubią używać AST do przeprowadzania refaktoryzacji, zamiast utrzymywać różne drzewa w tym samym czasie lub pisać dodatkowy silnik wnioskowania. Programiści są leniwi nie bez powodu. W rzeczywistości przechowują one równe informacje w wierszach i kolumnach zebrane przez analizę leksykalną w AST w celu raportowania błędów. Rzeczywiście bardzo abstrakcyjne.

CST (Concrete Syntax Tree) jest drzewem reprezentującym gramatykę (zasady pisania programu). W zależności od architektury kompilatora może być używany przez Parser do tworzenia AST.

AST (Abstract Syntax Tree) to drzewiasta reprezentacja Parsed źródła, tworzona przez część Parser kompilatora. Przechowuje informacje o tokenach + gramatyce.

W zależności od architektury kompilatora, CST może służyć do tworzenia AST. Można śmiało powiedzieć, że CST ewoluuje w AST. Lub AST jest bogatszym CST.

Więcej wyjaśnień można znaleźć pod tym linkiem: http://eli.thegreenplace.net/2009/02/16/abstract-vs-concrete-syntax-trees#id6