Abstrakter Syntaxbaum (AST): Die reduzierte Struktur hinter jedem Code

Der Abstrakter Syntaxbaum (englisch Abstract Syntax Tree, kurz AST) ist eine Baumstruktur, die den Quellcode eines Programms so darstellt, dass nur die semantisch relevanten Informationen übrig bleiben. Er entsteht aus dem Syntaxbaum (Parse-Baum), indem alle Details entfernt werden, die nur für die Schreibweise des Codes wichtig sind.

Parse-Baum vs. AST

Der konkrete Syntaxbaum bildet die Regeln einer kontextfreien Grammatik eins zu eins ab: Jede Regel, jedes Klammerpaar und jede Einzel-Produktion erzeugt eigene Knoten. Der AST dagegen hält nur das, was für die weitere Verarbeitung zählt:

  • Keine Klammern: Die Operatoren-Priorität steckt in der Baumstruktur selbst (3 + 4 * 5 hat den *-Knoten tiefer als den +-Knoten).
  • Keine Einzel-Produktionen: Nichtterminale, die nur ein einziges Kind durchreichen (z.B. Expression → Term), verschwinden.
  • Kein syntaktischer Zucker: Schlüsselwörter wie then oder Semikolons werden nicht als eigene Knoten gespeichert.

Beispiel für 3 + 4 * 5: Im Parse-Baum stehen alle Regeln der Grammatik, der AST hat nur drei Knoten — + mit den Kindern 3 und * (4, 5).

Wie der AST entsteht

Der Parser erhält die Token aus der lexikalischen Analyse und baut daraus entweder erst den Parse-Baum und reduziert ihn dann, oder — wie beim Pratt-Parser — konstruiert den AST direkt während des Parsens. Die Reduktion heißt Restrukturierung oder AST-Bau.

Warum der AST zentral ist

Fast alle weiteren Compiler-Phasen arbeiten auf dem AST statt auf dem Quelltext:

  • Semantische Analyse: Typprüfung, Namensauflösung und Bereichsprüfungen laufen über die Baumknoten.
  • Optimierung: Konstantenfaltung, toter Code und Umformungen (z.B. x * 0 → 0) erkennen Muster im Baum.
  • Zwischendarstellung: Der AST wird in eine IR übersetzt, auf der dann die Codegenerierung aufsetzt — je nach Ziel entsteht Maschinencode, Assemblercode oder Bytecode.

Auch Werkzeuge außerhalb von Compilern arbeiten mit ASTs: Linter und Formatter analysieren den Baum, IDEs nutzen ihn für Refactoring, Autovervollständigung und Sprung zur Definition, und Transpiler wandeln einen AST der Quellsprache in einen AST der Zielsprache um, bevor sie neuen Code erzeugen.

Die Pipeline im Überblick

Quellcode
  → Lexer (Token)
  → Parser (Parse-Baum → AST)
  → Semantische Analyse
  → Zwischendarstellung (IR)
  → Codegenerierung
  → Maschinencode / Bytecode

Ein Compiler ohne AST muss alle Analysen direkt am Quelltext oder Parse-Baum durchführen — das ist langsamer und fehleranfälliger. Der AST ist deshalb die wichtigste Datenstruktur im Frontend fast aller modernen Compiler und Interpreter.