Design and Implementation of a Static Attribute Evaluator for Incomplete Syntax Trees

Student:Tom Kunze
Title:Design and Implementation of a Static Attribute Evaluator for Incomplete Syntax Trees
Type:bachelor thesis
Advisors:Kreutzer, P.; Philippsen, M.
State:submitted on May 17, 2019
Prerequisits:
Topic:

Hintergrund
Am Lehrstuhl für Informatik 2 wird derzeit ein Verfahren entwickelt, das semantisch korrekte (und damit übersetzbare) Programme in nahezu beliebigen Sprachen generieren kann, die beispielsweise zum Testen von Übersetzern verwendet werden können. Zur Spezifikation der Sprache dient dabei eine Art Attributgrammatik. Eine solche besteht im Wesentlichen aus zwei Komponenten: Zum einen beinhaltet die Grammatik kontextfreie Regeln, die die Syntax der Sprache beschreiben und aus denen sich zu einem gegebenen Programm ein abstrakter Syntaxbaum (AST) konstruieren lässt. Zum anderen definiert die Grammatik Attribute und Evaluationsregeln zur Berechnung der Attributwerte auf den AST-Knoten. Diese Regeln dienen der Beschreibung der kontextsensitiven Eigenschaften, die ein semantisch korrektes Programm erfüllen muss (z.B. dass eine Variable vor ihrer ersten Verwendung definiert werden muss oder dass der Typ auf der rechten Seite einer Zuweisung zum Typ der linken Seite passen muss).
Unser Verfahren baut während der Programmgenerierung schrittweise einen AST auf, der den kontextsensitiven Eigenschaften genügt. Mit Hilfe eines sogenannten Attributevaluators werden dabei wiederholt alle zum jeweiligen Zeitpunkt berechenbaren Attribute der AST-Knoten anhand der spezifizierten Evaluationsregeln ausgewertet, um fehlerhafte Teilbäume identifizieren und entfernen bzw. ersetzen zu können. Zum einen besteht die Aufgabe des Attributevaluators darin, die Abhängigkeiten zwischen den zu berechnenden Attributen einzuhalten: Ein Attribut darf erst dann berechnet werden, wenn die Werte aller Quellattribute berechnet wurden. Zum anderen sollte der Evaluator möglichst effizient arbeiten, da die Attributauswertung maßgeblichen Einfluss auf die Laufzeit des Gesamtverfahrens hat.
Derzeit verwendet unser Verfahren einen dynamischen Attributevaluator. Ein solcher ermittelt zur Laufzeit (also während der Attributauswertung und damit während der Programmgenerierung) die Abhängigkeiten zwischen den Attributen und entscheidet, welche Werte berechnet werden können. Demgegenüber stehen statische Attributevaluatoren, die die Auswertungsreihenfolge einmalig im Voraus bestimmen und daher keine dynamische Bestimmung berechenbarer Attribute benötigen, wodurch die Laufzeit i.A. reduziert werden kann.

Thema
In dem am Lehrstuhl entwickelten Verfahren zur Generierung von Programmen aus Attributgrammatiken wird derzeit ein dynamischer Attributevaluator verwendet, der die Attributabhängigkeiten zur Laufzeit bestimmt und darauf aufbauend die Attributwerte bis zu einem Fixpunkt berechnet. Im Rahmen dieser Arbeit soll dieses einfache Verfahren durch einen effizienteren statischen Evaluator ersetzt werden, um die Gesamtlaufzeit des Werkzeugs zu reduzieren.
In diesem Zusammenhang ist zunächst die Literatur nach geeigneten Verfahren zur effizienten Attributauswertung zu durchsuchen. Publizierte Verfahren gehen üblicherweise von einem vollständigen AST aus, jedoch müssen die Attribute in unserem Anwendungsfall bereits während der AST-Konstruktion (und damit auf unvollständigen ASTs) berechnet werden. Dieser Umstand muss bei der Bestimmung der Auswertungsreihenfolge Beachtung finden. In einem zweiten Schritt ist daher zu untersuchen, welche der Verfahren sich wie für unseren Kontext adaptieren lassen. Unter den geeignet erscheinenden Optionen soll ein Verfahren ausgewählt werden, das im Rahmen der Arbeit prototypisch zu implementieren ist.
Das implementierte Verfahren soll abschließend evaluiert und mit dem bisherigen Verfahren verglichen werden.

Meilensteine

  • Einarbeitung in Attributgrammatiken und das am Lehrstuhl entwickelte Werkzeug
  • Literaturrecherche nach effizienten statischen Attributevaluatoren
  • Prototypische Implementierung eines für unseren Anwendungsfall adaptierten Verfahrens
  • Evaluation des Verfahrens und Vergleich mit dem bisherigen Verfahren
  • Schriftliche Ausarbeitung (in Deutsch oder Englisch)

Zur Arbeit gehört außerdem ein Vortrag im Kolloquium des Lehrstuhls gegen Ende der Bearbeitungszeit.

Literatur

  • Grune, D. et al.: Modern Compiler Design. Springer Verlag New-York. 2012.
  • Alblas, H.: Attribute Evaluation Methods. In: Attribute Grammars, Applications and Systems. June 1991. pp. 48–113.
  • Kastens, U.: Ordered Attribute Grammars. In: Acta Informatica, 13(3). Mar. 1980. pp. 229–256.
watermark seal