Abstract Syntax Tree (AST): Unterschied zwischen den Versionen

Aus Eclipse
Wechseln zu: Navigation, Suche
(Entwurf von Gliederung und Einleitung)
 
(Quellen)
 
(Eine dazwischenliegende Version des gleichen Benutzers werden nicht angezeigt)
Zeile 1: Zeile 1:
<!-- Abstract Syntax Tree (AST) -->
 
 
 
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.
 
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. Das Thema ''Modifikation von Quellcode auf Grundlage des AST'' behandelt der separate Artikel [[AST-basierte Code-Modifikation]].
+
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 ==
 
== Einleitung ==
  
 
=== Das Problem ===
 
=== 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 [[Das Java-Modell|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.
 
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 [[Das Java-Modell|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.
  
Zeile 21: Zeile 15:
  
 
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 [http://www.eclipse.org/articles/Article-JavaCodeManipulation_AST/index.html Kuhn und Thomann (2006)] lesen, in dem es flotter zur Sache geht. Andere Arbeiten zum AST der Java-Development-Tools bespricht die [[{{TALKPAGENAME}}|Diskussionsseite]] dieses Artikels.
 
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 [http://www.eclipse.org/articles/Article-JavaCodeManipulation_AST/index.html Kuhn und Thomann (2006)] lesen, in dem es flotter zur Sache geht. Andere Arbeiten zum AST der Java-Development-Tools bespricht die [[{{TALKPAGENAME}}|Diskussionsseite]] dieses Artikels.
 
  
 
=== Konzept des Syntaxbaums ===
 
=== Konzept des Syntaxbaums ===
Zeile 32: Zeile 25:
  
 
Wie die Abbildung des abstrakten Syntaxbaums für die Übersetzungseinheit (Compilation-Unit) Life.java zeigt, erzeugt selbst die absolut nutzlose Klasse <code>Life</code> einen überraschend komplexen Syntaxbaum. Wir empfehlen, das Eclipse-Plug-in [http://www.eclipse.org/jdt/ui/astview/index.php AST-View] zu installieren, auszuprobieren und auch den Quellcode zu lesen.
 
Wie die Abbildung des abstrakten Syntaxbaums für die Übersetzungseinheit (Compilation-Unit) Life.java zeigt, erzeugt selbst die absolut nutzlose Klasse <code>Life</code> einen überraschend komplexen Syntaxbaum. Wir empfehlen, das Eclipse-Plug-in [http://www.eclipse.org/jdt/ui/astview/index.php AST-View] zu installieren, auszuprobieren und auch den Quellcode zu lesen.
 
  
 
''' Homogene und heterogene Syntaxbäume'''
 
''' Homogene und heterogene Syntaxbäume'''
Zeile 41: Zeile 33:
  
 
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 <code>ASTNode</code>, das DOM arbeitet mit dem gemeinsamen Interface <code>Node</code>.  Während das DOM jedoch direkt Zugriff auf alle Kindknoten eines <code>Node</code> bietet ([http://onjava.com/lpt/a/589 Fesler 2001)], arbeiten die JDT mit dem Konzept der ''structural properties'', das wir [[#Structural Properties|weiter unten]] erläutern.
 
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 <code>ASTNode</code>, das DOM arbeitet mit dem gemeinsamen Interface <code>Node</code>.  Während das DOM jedoch direkt Zugriff auf alle Kindknoten eines <code>Node</code> bietet ([http://onjava.com/lpt/a/589 Fesler 2001)], arbeiten die JDT mit dem Konzept der ''structural properties'', das wir [[#Structural Properties|weiter unten]] erläutern.
 
  
 
'''Bindungen'''
 
'''Bindungen'''
Zeile 47: Zeile 38:
 
Bezeichner in einem Programmtext entsprechen Sprachkonstruktionen wie Methoden oder Variablen. Nach dem Parsen liegen sie in Form von AST-Knoten vor.
 
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.
 
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 ===
 
=== 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.
 
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.
  
Zeile 61: Zeile 50:
 
Das Refaktorisierungswerkzeug [http://www.fernuni-hagen.de/ps/prjs/AMM2/ 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 ([http://deposit.fernuni-hagen.de/2190/ Steimann und Thies 2009]).
 
Das Refaktorisierungswerkzeug [http://www.fernuni-hagen.de/ps/prjs/AMM2/ 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 ([http://deposit.fernuni-hagen.de/2190/ Steimann und Thies 2009]).
  
Weitere Anwendungen des AST behandeln unser Artikel [[AST-basierte Code-Modifikation]] und andere unter der Kategorie [[:Category:AST|AST]] verlinkte Wiki-Einträge.
+
Weitere Anwendungen des AST behandeln unter der Kategorie [[:Category:AST|AST]] verlinkte Wiki-Einträge.
 
+
 
+
 
+
<!-- -------------------------------------------------------------------- -->
+
 
+
== Die AST-Programmierschnittstelle ==
+
 
+
=== AST-Kern-Klassen ===
+
 
+
''Dieser und die folgenden Abschnitte sind in Arbeit.''
+
 
+
=== AST-Struktur ===
+
 
+
=== Bindings ===
+
 
+
=== Structural Properties ===
+
 
+
 
+
 
+
<!-- -------------------------------------------------------------------- -->
+
 
+
== Beziehen eines AST ==
+
 
+
=== Existierenden Quellcode parsen ===
+
 
+
=== Neu aus Quelltext aufbauen ===
+
 
+
=== Von Grund auf generieren ===
+
 
+
 
+
 
+
<!-- -------------------------------------------------------------------- -->
+
 
+
== Traversieren ==
+
 
+
=== Visitor ===
+
 
+
=== Geschachtelter Visitor ===
+
 
+
=== Spezifisches Traversieren ===
+
 
+
=== Allgemeines Traversieren (DOM) ===
+
 
+
 
+
 
+
<!-- -------------------------------------------------------------------- -->
+
 
+
== AST-Management ==
+
 
+
=== Shared AST-Provider ===
+
 
+
=== Cache (IT) ===
+
 
+
=== Brute Force (AMM) ===
+
 
+
 
+
 
+
<!-- -------------------------------------------------------------------- -->
+
  
 
== Quellen ==
 
== Quellen ==
 
 
<!-- TODO: ausdünnen, ggf. ergänzen um die Abschlussarbeiten -->
 
<!-- TODO: ausdünnen, ggf. ergänzen um die Abschlussarbeiten -->
 
+
* Martin Aeschlimann, Dirk Bäumer und Jerome Lanneluc, 2005. Java Tool Smithing, Extending the Eclipse Java Development Tools. http://eclipsecon.org/2005/presentations/EclipseCON2005_Tutorial29.pdf <!-- Martin Aeschlimann, 2008. JDT fundamentals - Become a JDT tool smith. http://www.eclipsecon.org/2008/sub/attachments/JDT_fundamentals.ppt -->
Martin Aeschlimann, Dirk Bäumer und Jerome Lanneluc, 2005. Java Tool Smithing, Extending the Eclipse Java Development Tools. http://eclipsecon.org/2005/presentations/EclipseCON2005_Tutorial29.pdf
+
* Alfred V. Aho, Monica S. Lam, Ravi Sethi und Jeffrey D. Ullman, 2007. Compilers: Principles, Techniques, and Tools. 2. Aufl., Upper Saddle River, NJ, 1009 S.
 
+
* John Arthorne und Chris Laffra, 2004. Official Eclipse 3.0 FAQs. § 20 Java Development Tool API. Addison, Boston. 432 S., http://wiki.eclipse.org/index.php/Eclipse_FAQs#Java_Development_Tool_API
<!-- Martin Aeschlimann, 2008. JDT fundamentals - Become a JDT tool smith. http://www.eclipsecon.org/2008/sub/attachments/JDT_fundamentals.ppt -->
+
* Jim D'Anjou, Scott Fairbrother, Dan Kehn, John Kellerman und Pat McCarthy, 2005. The Java Developer's Guide to Eclipse. § 27 Extending the Java Development Tools. 2. Aufl., Addison, Boston, S. 651-688.
 
+
Alfred V. Aho, Monica S. Lam, Ravi Sethi und Jeffrey D. Ullman, 2007. Compilers: Principles, Techniques, and Tools. 2. Aufl., Upper Saddle River, NJ, 1009 S.
+
 
+
John Arthorne und Chris Laffra, 2004. Official Eclipse 3.0 FAQs. § 20 Java Development Tool API. Addison, Boston. 432 S., http://wiki.eclipse.org/index.php/Eclipse_FAQs#Java_Development_Tool_API
+
 
+
Jim D'Anjou, Scott Fairbrother, Dan Kehn, John Kellerman und Pat McCarthy, 2005. The Java Developer's Guide to Eclipse. § 27 Extending the Java Development Tools. 2. Aufl., Addison, Boston, S. 651-688.
+
 
+
 
<!-- Hannes Kegel und Friedrich Steimann, 2007. ITcore: A Type Inference Package for Refactoring Tools. 1st Workshop on Refactoring Tools WRT'07, S. 7-8 -->
 
<!-- Hannes Kegel und Friedrich Steimann, 2007. ITcore: A Type Inference Package for Refactoring Tools. 1st Workshop on Refactoring Tools WRT'07, S. 7-8 -->
 
+
* Thomas Kuhn und Oliver Thomann, 2006. Abstract Syntax Tree. http://www.eclipse.org/articles/Article-JavaCodeManipulation_AST/index.html (''dies ist der Schlüssel-Artikel zum AST der Eclipse-Java-Development-Tools.'')
Thomas Kuhn und Oliver Thomann, 2006. Abstract Syntax Tree. http://www.eclipse.org/articles/Article-JavaCodeManipulation_AST/index.html (''dies ist der Schlüssel-Artikel zum AST der Eclipse-Java-Development-Tools.'')
+
* aus der Abschlußarbeit von Markus Bach: [http://www.fernuni-hagen.de/ps/docs/Masterarbeit-Bach.pdf#page=104 Parsen des Abstract-Syntax-Tree (AST)]
 
+
*aus der Abschlußarbeit von Eric Großkinsky: [http://www.fernuni-hagen.de/ps/docs/Masterarbeit-Grosskinsky.pdf#page=18 Abstrakter Syntaxbaum (AST)]
Weitere Literaturhinweise gibt die [[{{TALKPAGENAME}}|Diskussionsseite]] dieses Artikels.
+
 
+
<!-- -------------------------------------------------------------------- -->
+
  
 
<h2> Siehe auch </h2>
 
<h2> Siehe auch </h2>
 
+
*[[Das Java-Modell]]
[[Das Java-Modell]]
+
 
+
[[AST-basierte Code-Modifikation]]
+
 
+
<!-- -------------------------------------------------------------------- -->
+
 
+
[[Category:AST]]
+
  
 
[[Kategorie:AST]]
 
[[Kategorie:AST]]

Aktuelle Version vom 15. Juli 2010, 15:06 Uhr

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