Automatisierte Vervollständigung von Programmskeletten zum Zwecke der Testfallgenerierung für Übersetzer

Student:Sara Kretschmer
Title:Automatisierte Vervollständigung von Programmskeletten zum Zwecke der Testfallgenerierung für Übersetzer
Type:bachelor thesis
Advisors:Kreutzer, P.; Philippsen, M.
State:submitted on May 7, 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).
Insbesondere bei der Generierung von Testfällen für Übersetzer kann es nützlich sein, das Grundgerüst des generierten Programms vorgeben zu können, um Programme mit einer bestimmten Struktur zu erzeugen. Dadurch ist es beispielsweise möglich, gezielt die Übersetzung eines bestimmten Programmkonstrukts zu testen oder Varianten eines zuvor generierten Testprogramms zu erzeugen. Die Aufgabe des Programmgenerierungsverfahrens ist es dann, die fehlenden Teile eines solchen Programmskeletts so zu erzeugen, dass das resultierende Programm den semantischen Regeln der Sprache genügt.
Das bisher von uns entwickelte Verfahren konstruiert das gesamte Programm in jedem Lauf zufällig, angefangen beim Wurzelknoten im AST. Dadurch hat der Anwender bislang (außer durch die Anpassung der Attributgrammatik sowie die Wahl einer Gewichtung der Regeln) keinerlei Möglichkeiten, Einfluss auf die Generierung des Programms zu nehmen.

Thema
Im Rahmen dieser Arbeit soll das am Lehrstuhl entwickelte Verfahren zur Generierung von Programmen aus Attributgrammatiken so erweitert werden, dass es semantisch korrekte Programme erzeugen kann, die einem vorher definiertem Grundgerüst genügen. Insbesondere soll das Verfahren dabei Programmskelette mit Platzhaltern an beliebigen Stellen (und damit auch inneren AST-Knoten) erlauben. Vereinfacht soll es beispielsweise (unter Verwendung einer Attributgrammatik für C) möglich sein, ein Grundgerüst für C-Programme mit mindestens einer while-Schleife zu spezifizieren.
Zunächst ist dazu ein Mechanismus zu implementieren, mit dem Anwender ein Programmskelett spezifizieren können, beispielsweise über eine einfache grafische Oberfläche. Bereits während der Definition des Grundgerüsts sollen unerfüllbare Programmskelette (soweit möglich) erkannt und verworfen werden.
Im Anschluss daran ist zu untersuchen, wie das bisherige Verfahren zur Programmgenerierung erweitert werden muss, damit nur Programme erzeugt werden, die dem spezifizierten Grundgerüst genügen. Das erarbeitete Verfahren soll im Rahmen der Arbeit prototypisch implementiert werden. Außerdem ist die Effizienz des implementierten Verfahrens zu evaluieren, insbesondere im Vergleich zu einer naiven Umsetzung, bei der Programme zufällig generiert und ggf. verworfen werden.

Meilensteine

  • Einarbeitung in Attributgrammatiken und das am Lehrstuhl entwickelte Werkzeug
  • Implementierung eines Mechanismus zur Spezifikation von Programmskeletten
  • Erweiterung des Programmgenerierungsverfahrens
  • Evaluation des implementierten Verfahrens
  • 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.
  • Zhang, Q. et al.: Skeletal Program Enumeration for Rigorous Compiler Testing. In: Programming Language Design and Implementation. June 2017. pp. 347–361.
watermark seal