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

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?

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.

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.