Abstract Syntax Tree (AST)

Aus Eclipse
Wechseln zu: Navigation, Suche

Ein abstrakter Syntaxbaum (abstract syntax tree, AST) beschreibt den Inhalt eines konkreten Programmtextes oder eines Teils davon als Baum von Konstruktionen der Programmiersprache. Er ist Grundlage für Analyse, Modifikation und Übersetzung des Quellcodes. Eine Programmierschnittstelle für dieses mächtige Werkzeug steht für Erweiterungen der Eclipse Java Development Tools (JDT) allgemein zur Verfügung.

Dieser Artikel führt in Aufbau und Anwendung des AST für Code-Analysen ein und zeigt, wie Eclipse-Plug-ins, die die Java-Entwicklungsumgebung erweitern, diese Programmierschnittstelle anwenden können.

Einleitung

Das Problem

Eine Integrierte Entwicklungsumgebung (IDE) ist ein Werkzeug zum Lesen, Erstellen, Testen, Verändern, Debuggen und Übersetzen von Programmen. Für Darstellung von Programmtext, für Navigieren im Programm und für eine Unterstützung beim Schreiben und Ändern des Codes benötigt jede Entwicklungsumgebung interne Programmierschnittstellen (API). Diese API modelliert Programme, ihre Elemente und Operationen darauf auf deutlich höherer Abstraktionsebene als der Ebene von Zeichen und Zeichenketten. Die Eclipse-Java-Development-Tools (JDT) enthalten zu diesem Zweck mehrere Modelle. Ein solches Modell ist das Java-Modell, das Programme bis zu Deklarations-Elementen auflöst. Diese Auflösung reicht jedoch für viele Anwendungen nicht aus: Referenzierte Typen aus einem Editor heraus per Mausklick öffnen, die zugehörige Java-Dokumentation öffnen, automatisches Vervollständigen von Code oder gar Refaktorisierungen.

In diesem Artikel geht es um ein Modell mit erheblich feinerer Auflösung und mächtigerem API: Es geht um den abstrakten Syntaxbaum (AST), der auch den Rumpf von Methoden bis hinunter zu Anweisungen, Ausdrücken und deren Bestandteile zerlegt. Das Modell des Syntaxbaums und seine Klassen sind das Arbeitspferd vieler eingebauter Funktionen der Java-Entwicklungsumgebung aber auch Grundlage vieler Plug-ins, die diese Werkzeuge ergänzen. Die Erweiterungen sind möglich, weil die Java-Development-Tools wesentliche Teile dieser Programmierschnittstelle für Anwenderinnen bereitstellen und als öffentliches Erweiterungs-API dokumentieren.

Worin besteht das Problem? Die Funktionsvielfalt der Entwicklungswerkzeuge lässt ahnen, dass die Programmierschnittstelle und die zugrunde liegenden Modelle nicht ganz einfach sein können. So bedarf es einiger Anstrengung, sich einen Überblick der Modelle zu erarbeiten, den Funktionsumfang der API zu verstehen und das zugehörige Vokabular zu erlernen. Eine Reihe von Artikeln und Lehrbüchern hilft beim Einstieg in verschiedene Aspekte der mit dem abstrakten Syntaxbaum verbundenen API. Dieser Artikel hat zum Ziel, einen lesbaren und dennoch einigermaßen tief gehenden Einstieg in die Anwendung der AST-API für Code-Analysen zu geben, die verstreute Information zusammenzutragen und den Weg zu spezifischerer Literatur zu zeigen.

Der Artikel skizziert zunächst das Konzept des abstrakten Syntaxbaums, geht dann genauer auf die AST-Programmierschnittstelle ein und erläutert die Klassenhierarchie der Knotentypen des Syntaxbaums. Es folgen die Interfaces der Bindungen und die Benutzung des Document-Object-Models (DOM). Praktischer wird es in den Abschnitten, die demonstrieren, wie man programmatisch einen AST bzw. seinen Wurzelknoten bezieht und auf welche Art und Weise ein Syntaxbaum traversiert werden kann. Gesichtspunkte des Managements von AST in einem Eclipse Plug-in schließen diesen Artikel ab. Wir setzen im Rest dieses Artikels Kenntnis der Grundzüge des Java-Modells voraus.

Fortgeschrittene Leserinnen wollen den Rest der Einleitung vermutlich überspringen und gleich mit dem Abschnitt #AST-Programmierschnittstelle beginnen, wenn sie nicht gleich den Schlüsselartikel von Kuhn und Thomann (2006) lesen, in dem es flotter zur Sache geht. Andere Arbeiten zum AST der Java-Development-Tools bespricht die Diskussionsseite dieses Artikels.

Konzept des Syntaxbaums

Lexen und Parsen

Eine maschinelle Analyse von Programmtexten beginnt im Allgemeinen mit Lexen (Aufteilen in atomare Symbole oder Tokens der Sprache wie Schlüsselworte, Bezeichner und Operatoren) und Parsen (Zerlegen der Symbolfolge in Elemente gemäß der Grammatik der Sprache). Das Ergebnis dieser Zerlegung ist eine Baumstruktur. Der Baum wird Parse-, Ableitungs- oder konkreter Syntaxbaum genannt, wenn er jedes Detail des ursprünglichen Programmtextes enthält. Eine Vereinfachung dieses Baums, die nur für das zu bearbeitende Problem entscheidende Elemente enthält, heißt abstrakter Syntaxbaum (AST), Strukturbaum oder einfach Syntaxbaum (Aho et al. 2007, S. 78). Ein abstrakter Syntaxbaum ist also das Ergebnis der Transformation eines konkreten Programmtextes in einen Baum, dessen Knoten für Sprachkonstruktionen wie Ausdrücke, Deklarationen und Anweisungen stehen und dessen Kanten die Zusammensetzung repräsentieren. Details wie geschweifte Klammern oder Semikolons enthält der AST nicht, da die Struktur des Baums die Position dieser Hilfssymbole impliziert.

Abstrakter Syntaxbaum der Übersetzungseinheit Life.java

Wie die Abbildung des abstrakten Syntaxbaums für die Übersetzungseinheit (Compilation-Unit) Life.java zeigt, erzeugt selbst die absolut nutzlose Klasse Life einen überraschend komplexen Syntaxbaum. Wir empfehlen, das Eclipse-Plug-in AST-View zu installieren, auszuprobieren und auch den Quellcode zu lesen.

Homogene und heterogene Syntaxbäume

Homogene AST bestehen aus einheitlichen Knotentypen, während heterogene AST für verschiedene Sprachkonstruktionen verschiedene Knotentypen verwenden. Der Syntaxbaum der Eclipse-Java-Development-Tools (JDT) ist zunächst ein heterogener AST, der für jede Java-Sprachkonstruktion einen eigenen Knotentyp bereitstellt. Bach (2007, S. 104) zählt 84 verschiedene Typen.

Ein anderes Beispiel eines heterogenen AST, auf das die JDT-Dokumentation wiederholt Bezug nimmt, ist das HTML/XML Document Object Model (DOM). Vom DOM haben die JDT teilweise das Vokabular übernommen (das in den Eclipse-FAQ noch genannte JDOM ist allerdings völlig obsolet und schon lange abgekündigt).

AST und DOM ähneln sich auch im Konzept, den Baum wie einen homogenen AST behandeln zu können. Möglich ist das durch einen gemeinsamen Supertypen aller Knotentypen. Beim AST heißt die Superklasse aller Knotentypen ASTNode, das DOM arbeitet mit dem gemeinsamen Interface Node. Während das DOM jedoch direkt Zugriff auf alle Kindknoten eines Node bietet (Fesler 2001), arbeiten die JDT mit dem Konzept der structural properties, das wir weiter unten erläutern.

Bindungen

Bezeichner in einem Programmtext entsprechen Sprachkonstruktionen wie Methoden oder Variablen. Nach dem Parsen liegen sie in Form von AST-Knoten vor. Unter Bindung (Binding) versteht man nun den Bezug von Variablen-, Methoden- oder Typbezeichnern an der Verwendungsstelle auf die Deklaration. Man spricht von Namensanalyse oder Auflösen der Bindungen, wenn man die Bindungen von Bezeichnern an Deklarationen und an deklarierte Typen ermittelt (siehe #Bindings). Wir unterscheiden Namensbindung etwa einer Variable von der Typbindung eines Ausdrucks. Weil eine Namensanalyse aufwändig ist, lösen die JDT Bindungen normalerweise nicht auf. Rückbezüge von der Deklaration zu allen vorkommenden Verwendungsstellen des Deklarationselements enthält der AST der JDT nicht.

Anwendungen des AST

Wir benennen im folgenden einige Anwendungen des AST der Java Development Tools. Das soll die Bedeutung des AST unterstreichen und zeigen, wo man praktische Beispiele der Anwendung des AST findet, von denen man lernen kann.

Erste Adresse für Anwendungsbeispiele des AST sind die Java-Development-Tools selbst (allerdings verwenden die Tools häufig nicht das öffentliche API des Packages org.eclipse.jdt.core.dom mit dessen ASTNode-Klasse und deren Subklassen, sondern eine zweite, interne Implementation org.eclipse.jdt.internal.compiler.ast.ASTNode -- also Vorsicht beim automatischen Importieren). Syntax-Highlighting und Code-Formatierung im Java-Editor benutzen die Strukturinformationen, die mit dem Syntaxbaum der geöffneten Übersetzungseinheit (.java-File) bereit steht. Die Tasten-Kombinationen Shift-F2 oder F3 bzw. Ctrl-Mouse-Hover (in Version 3.5 Galileo noch schöner mit einer Auswahlliste der überschriebenen Implementationen) zum Öffnen der mit einer Referenz assoziierten Deklaration benötigen die Bindungen des AST. Auch automatische Code-Vervollständigung (Ctrl-Leertaste) ist nur auf Grundlage detaillierter Code-Analyse mit dem AST möglich.

Viele Metrik- und Refactoring-Werkzeuge benutzen zur Code-Analyse einen AST und das damit verbundene API. Wir verweisen exemplarisch auf unsere Projekte Infer Type (IT) und Access Modifier Modifier (AMM).

Das Infer-Type-Refactoring berechnet aufgrund statischer Code-Analyse den Unterschied zwischen deklariertem und inferiertem Typ von Variablen, Methoden-Parametern und Rückgaben in Java-Programmen. Der inferierte Typ ist so generalisiert wie möglich und umfasst gerade die minimale Menge der im betrachteten Programmfragment tatsächlich aufgerufenen Methoden. Hannes Kegels Diplomarbeit (Kegel 2007, S. 58 ff.) beschreibt, wie die AST traversiert werden, um Constraints (Einschränkungen) für die Typinferenz zu ermitteln.

Das Refaktorisierungswerkzeug Access Modifier Modifier erlaubt auf einfache Art und Weise, die Sichtbarkeit von Methoden so weit wie möglich einzuschränken ohne die Semantik des Programms zu ändern. Die einzuhaltenden Regeln sind bei Java-Programmen recht komplex. Ihre Herleitung für ein Deklarationselement erfordert eine aufwändige Analyse des Programm-Codes, die nur auf Basis des abstrakten Syntaxbaums und dessen Bindungen möglich ist (Steimann und Thies 2009).

Weitere Anwendungen des AST behandeln unter der Kategorie AST verlinkte Wiki-Einträge.

Quellen

Siehe auch