Free Press

Abstrakte Syntaxbäume sind Datenstrukturen, die in Compilern häufig zur Darstellung der Struktur von Programmcode verwendet werden. Ein AST ist normalerweise das Ergebnis der Syntaxanalysephase eines Compilers. Er dient oft als Zwischendarstellung des Programms über mehrere Stufen, die der Compiler benötigt, und hat einen starken Einfluss auf die endgültige Ausgabe des Compilers.

MotivationBearbeiten

Ein AST hat mehrere Eigenschaften, die die weiteren Schritte des Compilierungsprozesses unterstützen:

• Ein AST kann bearbeitet und mit Informationen wie Eigenschaften und Anmerkungen für jedes darin enthaltene Element erweitert werden. Eine solche Bearbeitung und Kommentierung ist beim Quellcode eines Programms nicht möglich, da sie eine Änderung desselben bedeuten würde.
• Im Vergleich zum Quellcode enthält ein AST keine unwesentlichen Interpunktions- und Begrenzungszeichen (geschweifte Klammern, Semikolons, Klammern usw.).
• Ein AST enthält in der Regel zusätzliche Informationen über das Programm, die sich aus den aufeinanderfolgenden Stufen der Analyse durch den Compiler ergeben. Zum Beispiel kann es die Position jedes Elements im Quellcode speichern, so dass der Compiler nützliche Fehlermeldungen ausgeben kann.

ASTs werden aufgrund der inhärenten Natur von Programmiersprachen und ihrer Dokumentation benötigt. Sprachen sind von Natur aus oft mehrdeutig. Um diese Mehrdeutigkeit zu vermeiden, werden Programmiersprachen oft als kontextfreie Grammatik (CFG) spezifiziert. Es gibt jedoch häufig Aspekte von Programmiersprachen, die eine CFG nicht ausdrücken kann, die aber Teil der Sprache sind und in ihrer Spezifikation dokumentiert werden. Dabei handelt es sich um Details, die einen Kontext erfordern, um ihre Gültigkeit und ihr Verhalten zu bestimmen. Wenn eine Sprache beispielsweise die Deklaration neuer Typen erlaubt, kann ein CFG weder die Namen solcher Typen noch die Art ihrer Verwendung vorhersagen. Selbst wenn eine Sprache über einen vordefinierten Satz von Typen verfügt, erfordert die Durchsetzung der korrekten Verwendung in der Regel einen gewissen Kontext. Ein weiteres Beispiel ist die Typisierung von Enten, bei der sich der Typ eines Elements je nach Kontext ändern kann. Die Überladung von Operatoren ist ein weiterer Fall, bei dem die korrekte Verwendung und die endgültige Funktion vom Kontext abhängen. Java liefert ein hervorragendes Beispiel, bei dem der ‚+‘-Operator sowohl für die numerische Addition als auch für die Verkettung von Zeichenketten verwendet wird.

Obwohl auch andere Datenstrukturen in das Innenleben eines Compilers einbezogen sind, erfüllt der AST eine einzigartige Funktion. In der ersten Phase, der Syntaxanalyse, erzeugt ein Compiler einen Parse-Baum. Dieser Parse-Baum kann verwendet werden, um fast alle Funktionen eines Compilers durch syntaxgeleitete Übersetzung auszuführen. Obwohl diese Methode zu einem effizienteren Compiler führen kann, widerspricht sie den Grundsätzen des Software-Engineering beim Schreiben und Warten von Programmen. Ein weiterer Vorteil, den der AST gegenüber einem Parse-Baum hat, ist die Größe, insbesondere die geringere Höhe des AST und die geringere Anzahl von Elementen.

DesignEdit

Das Design eines AST ist oft eng mit dem Design eines Compilers und seinen erwarteten Funktionen verbunden.

Zu den Kernanforderungen gehören die folgenden:

• Variablentypen müssen erhalten bleiben, ebenso wie die Position jeder Deklaration im Quellcode.
• Die Reihenfolge der ausführbaren Anweisungen muss explizit dargestellt und genau definiert werden.
• Linke und rechte Komponenten von binären Operationen müssen gespeichert und korrekt identifiziert werden.
• Bezeichner und ihre zugewiesenen Werte müssen für Zuweisungsanweisungen gespeichert werden.

Diese Anforderungen können verwendet werden, um die Datenstruktur für den AST zu entwerfen.

Einige Operationen erfordern immer zwei Elemente, wie die beiden Terme für die Addition. Einige Sprachkonstrukte erfordern jedoch eine beliebig große Anzahl von Unterelementen, wie z.B. Argumentlisten, die von der Befehlsshell an Programme übergeben werden. Daher muss ein AST, das zur Darstellung von in einer solchen Sprache geschriebenem Code verwendet wird, auch flexibel genug sein, um eine schnelle Hinzufügung einer unbekannten Anzahl von Kindern zu ermöglichen.

Um die Compiler-Verifikation zu unterstützen, sollte es möglich sein, einen AST in Quellcodeform zu zerlegen. Der erzeugte Quellcode sollte dem Original im Aussehen hinreichend ähnlich und in der Ausführung identisch sein, wenn er neu kompiliert wird.

UsageEdit

Der AST wird intensiv während der semantischen Analyse verwendet, bei der der Compiler die korrekte Verwendung der Elemente des Programms und der Sprache überprüft. Während der semantischen Analyse erzeugt der Compiler auch Symboltabellen auf der Grundlage des AST. Eine vollständige Traversierung des Baums ermöglicht die Überprüfung der Korrektheit des Programms.

Nach der Überprüfung der Korrektheit dient der AST als Grundlage für die Codegenerierung. Der AST wird oft verwendet, um eine Zwischendarstellung (IR), manchmal auch als Zwischensprache bezeichnet, für die Codegenerierung zu erzeugen.