Änderungen

Wechseln zu: Navigation, Suche

Abstract Syntax Tree (AST)

1.593 Byte entfernt, 14:31, 15. Jul. 2010
leere Abschnitte und tote links entfernt
<!-- 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.
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]].   <!-- -------------------------------------------------------------------- -->
== 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 [[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.
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 ===
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'''
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'''
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.
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.   <!-- -------------------------------------------------------------------- --> == 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 ==
 
<!-- 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 --> * 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 -->
 * 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.'') Weitere Literaturhinweise gibt die [[{{TALKPAGENAME}}|Diskussionsseite]] dieses Artikels. <!-- -------------------------------------------------------------------- -->
<h2> Siehe auch </h2>
 *[[Das Java-Modell]] [[AST-basierte Code-Modifikation]] <!-- -------------------------------------------------------------------- --> [[Category:AST]]
[[Kategorie:AST]]
258
Bearbeitungen