Jaki jest najprostszy przykład wyjaśniający różnicę między drzewami parsowania a drzewami abstrakcyjnej składni?

14

O ile mi wiadomo, analizator składni tworzy drzewo analizujące, a następnie odrzuca je. Może jednak wyskoczyć z abstrakcyjnego drzewa składni, z którego podobno korzysta kompilator.

Mam wrażenie, że zarówno parsowanie, jak i abstrakcyjne drzewo składniowe są tworzone pod etapem analizy. Czy ktoś mógłby wyjaśnić, dlaczego są one różne?

Logika kombinatora
źródło
3
Dlaczego muszą być inni? Czy nie mogą być tym samym z dwóch nieco odmiennych punktów widzenia?
S.Lott,
1
Nie jestem pewien, czy rozumiem te dwa „nieco inne punkty widzenia” :-(
Logika kombinatora
O to chodzi. Są tym samym, stąd zamieszanie. Po prostu masz różne słowa w zależności od twojego punktu widzenia: Parsowanie vs. Generowanie kodu (lub Wykonanie, w przypadku interpretera).
S.Lott,
Nie ma różnicy. Przy odrobinie wyobraźni można wymyślić reprezentację składni dla dowolnego możliwego abstrakcyjnego drzewa składni. Przy braku wyobraźni wyrażenia S Lispa byłyby domyślną składnią odpowiednią do wszystkiego.
SK-logic
1
Wszyscy powinniście przeczytać odpowiedź przed komentowaniem. Jest różnica, ale oddzielenie ich lub połączenie to problem z implementacją.
Paul

Odpowiedzi:

20

Drzewo analizy jest również znane jako konkretne drzewo składniowe.

Zasadniczo drzewo abstrakcyjne ma mniej informacji niż drzewo betonowe. Betonowe drzewo zawiera każdy element w języku, podczas gdy drzewo abstrakcyjne odrzuciło nieciekawe elementy.

Na przykład wyrażenie: (2 + 5) * 8

Beton wygląda tak

  ( 2  + 5 )  * 8
  |  \ | / |  | |
  |   \|/  |  | |
   \___|__/   | |
       \______|/

Natomiast abstrakcyjne drzewo ma:

2  5 
 \/   
  +  8
   \/
   *

W konkretnych przypadkach nawiasy i wszystkie części języka zostały włączone do drzewa. W przypadku abstrakcyjnym nawiasy zniknęły, ponieważ ich informacje zostały włączone do struktury drzewa.

Winston Ewert
źródło
Zapomniałeś wspomnieć, w którym kompilatorze dla jakiego języka jest to zaimplementowane w ten sposób. Ponieważ, wiesz, nie musisz ... parser mógłby równie dobrze odrzucić nawias.
Ingo
1
@Ingo, nic w mojej odpowiedzi nie ma nic do powiedzenia, gdy kompilator wyrzuca nawiasy. Pyta, jaka jest różnica między konkretnym drzewem analizy a abstrakcyjnym drzewem analizy.
Winston Ewert
Na pewno możesz podać źródło swojego roszczenia? Czy to tylko twoja prywatna definicja?
Ingo
1
@ingo, docs.google.com/document/d/…
Winston Ewert
0

Pierwszą rzeczą, którą musisz zrozumieć, jest to, że nikt nie zmusza Cię do napisania parsera lub kompilatora w określony sposób. W szczególności niekoniecznie jest tak, że wynikiem analizatora składni musi być drzewo. Może to być dowolna struktura danych odpowiednia do reprezentowania danych wejściowych.

Na przykład następujący język:

prog:
      definition 
    | definition ';' prog
    ;

definition: .....

może być reprezentowany jako lista definicji. (Nitpickers wskaże, że lista jest zdegenerowanym drzewem, ale i tak.)

Po drugie, nie ma potrzeby trzymania się drzewa parsowania (lub jakiejkolwiek struktury danych zwróconej przez parser). Przeciwnie, kompilatory są zwykle konstruowane jako sekwencja przebiegów, które przekształcają wyniki poprzedniego przejścia. Stąd ogólny układ kompilatora mógłby wyglądać następująco:

parser :: String             -> Maybe [Definitions]      -- parser
pass1  :: [Definitions]      -> Maybe DesugaredProg      -- desugarer
pass2  :: DesugaredProg      -> Maybe TypedProg          -- type checker
pass3  :: TypedProg          -> Maybe AbstractTargetLang -- code generation
pass4  :: AbstractTargetLang -> Maybe String             -- pretty printer

compiler :: String           -> Maybe String    -- transform source code to target code
compiler source = do
   defs  <- parser source
   desug <- pass1 defs
   typed <- pass2 desug
   targt <- pass3 typed
   pass4 targt

Konkluzja: Jeśli słyszysz, jak ludzie mówią o parsowaniu drzew , abstrakcyjnych drzewach syntak , betonowych drzewach składniowych itp., Zawsze zastępuj strukturę danych odpowiednią dla danego celu i wszystko jest w porządku.

Ingo
źródło
2
Jak to jest odpowiedź na pytanie?
Winston Ewert
@WinstonEwert Twierdzę, że „parsowanie drzewa” i „abstrakcyjne drzewo składniowe” są abstrakcjami i nie oznaczają nic więcej niż „odpowiednie struktury danych”. Tak więc odpowiedź jest taka, że ​​pytanie w ogólności nie ma sensu, chyba że poprosisz o różnicę między typem zwracanym parsera a typem zwrotnym jakiegoś innego przebiegu w kompilatorze XY języka L.
Ingo