Was ist das einfachste Beispiel, um den Unterschied zwischen Parse Trees und Abstract Syntax Trees zu erklären?

Nach meinem Verständnis erstellt ein Parser einen Analysebaum und verwirft ihn anschließend. Es kann jedoch auch ein abstrakter Syntaxbaum eingeblendet werden, auf den der Compiler angeblich zurückgreifen soll.

Ich habe den Eindruck, dass sowohl der Analysebaum als auch der abstrakte Syntaxbaum während der Analysephase erstellt werden. Könnte dann jemand erklären, warum das anders ist?

Ein Analysebaum wird auch als konkreter Syntaxbaum bezeichnet.

Grundsätzlich hat der abstrakte Baum weniger Informationen als der konkrete Baum. Der konkrete Baum enthält jedes Element in der Sprache, während der abstrakte Baum die uninteressanten Teile weggeworfen hat.

Zum Beispiel der Ausdruck: (2 + 5) * 8

Der Beton sieht so aus

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

Während der abstrakte Baum hat:

2  5 
 \/   
  +  8
   \/
   *

In den konkreten Fällen wurden die Klammern und alle Teile der Sprache in den Baum aufgenommen. Im abstrakten Fall sind die Klammern weg, weil ihre Informationen in die Baumstruktur aufgenommen wurden.

Das Erste, was Sie verstehen müssen, ist, dass Sie niemand zwingt, einen Parser oder Compiler auf eine bestimmte Weise zu schreiben. Insbesondere muss das Ergebnis eines Parsers nicht unbedingt ein Baum sein. Es kann sich um eine beliebige Datenstruktur handeln, die zur Darstellung der Eingabe geeignet ist.

Zum Beispiel die folgende Sprache:

prog:
      definition 
    | definition ';' prog
    ;

definition: .....

kann als Liste von Definitionen dargestellt werden. (Nitpicker werden darauf hinweisen , dass eine Liste ist ein entarteter Baum, aber trotzdem.)

Zweitens ist es nicht erforderlich, den Analysebaum (oder die vom Parser zurückgegebene Datenstruktur) festzuhalten. Im Gegenteil, Compiler bestehen normalerweise aus einer Folge von Durchläufen, die die Ergebnisse des vorherigen Durchlaufs transformieren. Daher könnte das Gesamtlayout eines Compilers folgendermaßen aussehen:

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

Fazit: Wenn Sie hören , wie Leute darüber reden , Parse - Bäume , abstrakte Syntac Bäume , Beton Syntaxbäume usw., immer ersetzen durch Datenstruktur geeignet für den angegebenen Zweck , und du bist in Ordnung.