Jaka jest różnica między drzewem parsowania a AST?

94

Czy są generowane na różnych etapach procesu kompilacji? A może są to po prostu różne nazwy dla tej samej rzeczy?

compiler-construction terminology compiler-theory abstract-syntax-tree parse-tree Thomson
źródło
Drzewo parsowania jest wynikiem twojej gramatyki z jej artefaktami (możesz napisać nieskończoną liczbę gramatyk dla tego samego języka), AST redukuje drzewo parsowania jak najbliżej języka. Kilka gramatyk dla tego samego języka da różne drzewa parsowania, ale powinno skutkować tym samym AST. (można również zredukować różne skrypty (różne drzewa parsowania z tej samej gramatyki) do tego samego AST)
Guillaume86.
1
Ta odpowiedź SO szczegółowo omawia różnicę: stackoverflow.com/a/1916687/120163
Ira Baxter
1
Możliwy duplikat. Jaka jest różnica między drzewami analizy a abstrakcyjnymi drzewami składni?
curiousdannii

Odpowiedzi:

98

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.

Drzewo analizy

AST

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

AST

Aby uzyskać więcej informacji, zobacz Kompilatory i generatory kompilatorów str. 23
lub abstrakcyjne drzewa składniowe na str. 21 w składni i semantyce języków programowania

Guy Coder
źródło
5
Jak uzyskać AST z drzewa parsowania? Jaka jest metoda uproszczenia drzewa parsowania do AST?
CMCDragonkai
3
Nie ma określonego algorytmu do wyprowadzenia AST z drzewa parsowania. To, co trafia do AST, to raczej osobiste preferencje, ale musi zawierać wystarczającą ilość informacji, aby wykonać zadanie. Wykluczyłem pareny z AST za pomocą ANTLR ! operator w gramatyce, ponieważ nie są one potrzebne, ale domyślnie ANTLR uwzględniłby je. Myślę, że drzewo parsowania daje ci wszystko, czy tego potrzebujesz, czy nie, a AST daje ci absolutne minimum. Pamiętaj, że będziesz dużo przemierzać drzewa, więc rozmiar ma znaczenie.
Guy Coder,
2
Masz na myśli jak CST (konkretne drzewo składniowe) kontra AST (abstrakcyjne drzewo składniowe)?
CMCDragonkai
Działania / reguły semantyczne osadzone w plikach składni parsera lub generatora parserów są zwykłym sposobem analizy semantycznej i tworzenia AST, podczas gdy drzewo parsowania jest rzadko, jeśli w ogóle kiedykolwiek tworzone lub używane przez kod użytkownika, z wyjątkiem być może weryfikacji poprawności parsera.
Interesujące: Abstrakcyjny wykres semantyczny
Guy Coder,
16

Z tego, co rozumiem, AST skupia się bardziej na abstrakcyjnych związkach między komponentami kodu źródłowego, podczas gdy drzewo parsowania koncentruje się na rzeczywistej implementacji gramatyki używanej przez język, w tym na szczegółach. Z pewnością nie są tym samym, ponieważ innym terminem określającym „drzewo parsowania” jest „konkretne drzewo składniowe”.

Znalazłem tę stronę, która próbuje rozwiązać dokładnie to pytanie.

Ken Wayne Vander Linde
źródło
11

Książka DSL od Martin Fowler wyjaśnia to ładnie. AST zawiera tylko wszystkie `` przydatne '' elementy, które zostaną użyte do dalszego przetwarzania, podczas gdy drzewo analizy zawiera wszystkie artefakty (spacje, nawiasy, ...) z oryginalnego dokumentu, który analizujesz

Wim Deblauwe
źródło
4

Weź przypisanie paskalowe Wiek: = 42;

Drzewo składni wyglądałoby tak samo jak kod źródłowy. Poniżej umieszczam nawiasy wokół węzłów. [Wiek] [: =] [42] [;]

Abstrakcyjne drzewo wyglądałoby tak [=] [Wiek] [42]

Przypisanie staje się węzłem z 2 elementami, Wiek i 42. Pomysł polega na tym, że możesz wykonać przypisanie.

Zwróć także uwagę, że składnia pascala znika. W ten sposób można mieć więcej niż jeden język generujący ten sam AST. Jest to przydatne w przypadku silników skryptów obsługujących wiele języków.

William Egge
źródło
1

W drzewie parsowania węzły wewnętrzne są nieterminalne, liście są terminalami. W drzewie składni węzły wewnętrzne są operatorami, liście są operandami.

Roshani Patel
źródło