Masterarbeit

Die im folgenden Vorgestellte Masterarbeit wurde im Rahmen meines Studiums an der Fachhochschule OÖ in Hagenberg erstellt. Dabei wurde ein Präprozessor namens BoB entwickelt, der die Vorteile der Bottom-Up Syntaxanalyse mit den Vorteilen Top-Down Semantikauswertung verknüpft. Nachfolgend die Kurzbeschreibung in Deutsch und Englisch. Am Ende dieses Artikels finden Sie die Masterarbeit, Präsentation zu Masterarbeit und die Quelltexte.

Kurzfassung

Diese Masterarbeit beschäftigt sich mit dem Problem, dass aktuelle Compiler entweder Top-down- oder Bottom-up-Syntaxanalyse verwenden. Beide Konzepte haben Nachteile. Die Bottom-up-Analyse, für die mächtigen LR(k)-Grammatiken, unterstützt nur S- oder LR-attributierte Grammatiken. Im Gegensatz dazu unterstützt die Top-down-Analyse, für die LL(k)-Grammatiken, die mächtigeren L-attributierten Grammatiken.

Das Ziel dieser Masterarbeit ist, die Vorteile der Bottom-up-Syntaxanalyse mit den Vorteilen der Top-down-Semantikauswertung zu kombinieren. Hierfür wird ein Präprozessor namens BoB (Best of Both) für flex und bison entwickelt.

BoB verarbeitet Compiler-Beschreibungen – geschrieben in Cocol4BoB – und erlaubt die Verarbeitung von L-attributierten LALR(1)-Grammatiken. Die durch die neue BoB-flex-bison-Werkzeugkette erzeugten Compiler verwenden Bottom-up-Syntaxanalyse und Top-down-Semantikauswertung.

Die Stärke von BoB ist die einfache und leistungsfähige Compiler-Beschreibungssprache Cocol4BoB. Entwickler müssen sich nicht um LL(1)-Konflikte kümmern und können in den semantischen Aktionen Eingangs-, Ausgangs- und Übergangsattribute verwenden. Deshalb ist der Einstieg für Anfänger bei BoB besonders einfach möglich. Mit diesen Vorteilen ist leider ein Nachteil verbunden: Compiler die durch BoB erzeugt werden haben eine längere Laufzeit.

In dieser Arbeit wird gezeigt, dass die Konzepte von BoB Vorteile in Bezug auf die Benutzerfreundlichkeit und Mächtigkeit der Eingabesprache haben. Trotzdem sollten die offenen Fragen bezüglich der Performance nicht vergessen und in zukünftigen Arbeiten behandelt werden.

Abstract

This master thesis deals with the problem, that current compilers use either top-down or bottom-up syntax analysis. Both concepts have their disadvantages. Bottom-up analysis for the powerful LR(k) grammars only supports S- or LR-attributed grammars. On the other hand, top-down analysis for the less powerful LL(k) grammars supports the powerful L-attributed grammars.

The goal of this master thesis is to combine the advantages of syntax analysis and semantic evaluation. Therefore, a preprocessor called BoB (Best of Both) for flex and bison is implemented.

BoB process a compiler description written in Cocol4BoB and allows L-attributed LALR(1) grammars. Compilers generated by the new BoB-flex-bison toolchain use bottom-up syntax analysis and top-down semantic evaluation.

The strength of BoB is the simple and powerful compiler description language Cocol4BoB. Developers do not have to handle LL(1) conflicts. Moreover, they can use inherited and synthesized attributes in semantic actions. Therefore, the usage for beginners is less difficult than in other compiler generators. However, these advantages came with a drawback: compilers generated by BoB have a longer compile-time.

This thesis shows, that the concepts of BoB have advantages in terms of usability and capability of the input language. Nevertheless, the open performance issues should be addressed in further projects.