Übersetzerbau-Praktikum
Priv.-Doz. Dr. Lothar Schmitz
Wintertrimester 2006
[Ziel des Praktikums] [Termine und Ort] [Aufgaben und Ergebnisse] [Scheinerwerb]
[Links & Literatur zum Compilerbau] [Links & Literatur zu Ruby] [Software und Installation]
Ziel des Praktikums
Ziel des Praktikums ist es, Einblicke in das Innere von Werkzeugen zur Syntaxverarbeitung zu geben. Die Teilnehmer sollen damit in die Lage versetzt werden, angebotene Syntaxwerkzeuge einschätzen und sinnvoll einsetzen zu können. Dazu ist neben eigenen praktischen Erfahrungen auch ein Grundwissen über Analyse- und Generierungs- mechanismen erforderlich. Das Praktikum beginnt daher mit drei Vorlesungsblöcken, in denen kurz die wesentlichen theoretischen Grundlagen dargestellt werden zu:
- Lexikalischer Analyse mit regulären Mustern
- Kontextfreie Grammatiken und Syntaxanalyse
- Attributierte Grammatiken und Attributauswertung
Danach sollen einige zentrale Komponenten eines Compiler-Compilers praktisch selbst entwickelt und ausprogrammiert werden. Als Programmiersprache wird Ruby verwendet, das sich wegen folgender Eigenschaften besonders zur prototypischen Implementierung von Compiler-Compiler-Komponenten eignet:
- direkte Unterstützung regulärer Muster
- objektorientierte Programmstruktur
- funktionale Konzepte (closures) für flexible Verarbeitung
- flexible Datenstrukturen: erweiterbare Arrays und Hash-Tabellen
- Reflection und direkte Ausführung generierter Programme
- Typfreiheit (!!!)
Termine und Ort
Es handelt sich um ein dreistündiges Praktikum; davon sind zwei Wochenstunden Kontaktzeit, in denen Vorlesungen und Präsentationen stattfinden. Eine Wochenstunde dient individueller Aufgabenstellung und Beratung.
Wir treffen uns jeweils
- freitags 08:15 Uhr bis 10:00 Uhr im Electronic Classroom.
Die Implementierung findet in Gruppen von drei bis fünf Personen statt. Die Gruppeneinteilung wechselt zwischen den drei Phasen (Einarbeitung, Analyse und Generierung).
Aufgaben und Ergebnisse
Die Bearbeitung ist gegliedert in drei Phasen:
-
Die Einarbeitungsphase mit der Aufgabenbeschreibung und den Ergebnissen (zip-File). Hier ging es darum, sich in die Programmiersprache Ruby einzuarbeiten, einzelne Syntaxtools von Hand zu entwickeln und Basiskomponenten (Mengen, Relationen, Grammatiken) bereitzustellen.
-
Die Entwicklungsphase mit der Aufgabenbeschreibung und den Ergebnissen (zip-File). In dieser Phase wurden ein Scannergenerator und ein Parsergenerator mit graphischer Oberfläche prototypisch entwickelt.
-
Die Konsolidierungsphase mit der Aufgabenbeschreibung. Ziel dieser Phase ist es, die Ergebnisse der beiden vorangegangenen Phasen weiter auszubauen, ausführlich zu dokumentieren und vor allem die Codequalität zu verbessern (Laufzeit, Lesbarkeit). Dadurch soll eine Basis entstehen, auf der eine weitere Toolentwicklung möglich ist.
Insgesamt sollen die folgenden Teilaufgaben von den ursprünglichen Bearbeitern "poliert", gut dokumentiert und an aussagekräftigen Beispielen präsentiert werden:
- Plotter-Fenster: zum Anzeigen von Funktionsgraphen (Funktionen werden vom Benutzer als Ruby-Ausdrücke in x eingegeben).
- Markov-Fenster: zum Erzeugen von Markov-Interpretern in Ruby und zum Anzeigen von Traces dieser Interpreter.
- Warshall: Mengen und Relationen mit nützlichen Operationen wie transitive Hülle nach Warshall. Kompakte Mengendarstellung: Binäre Zahldarstellung als charakteristische Funktion verwenden.
- Grammatik: die der Parsererzeugung zugrundeliegende Darstellung von Grammatiken. aktuelle Fassung
- Syntaxbaum: die dazu passende Darstellung von Syntaxbäumen, wie sie von den Parsern erzeugt werden.
- First und Follow: zwei Relationen, die die Basis aller Parserkonstruktionen bilden.
- LR-Automaten: Automaten der Typen LR(0), SLR(1), LR(1) und LALR(1) werden berechnet. In der Überarbeitung soll die textbasierte durch eine effizient codierte Interndarstellung ersetzt werden.
- Parser-Tabellen: aus den verschiedenen LR-Automaten werden die Parsing-Tabellen abgeleitet und dabei Konfliktfreiheit geprüft.
- Parser-Rahmen: der allen Parsern gemeinsame Rahmen, der die Analyse mit Hilfe der Parser-Tabellen durchführt und den Syntaxbaum erzeugt.
- Grammatik-Editor: das gemeinsame Frontend des gesamten Projekts erlaubt es Grammatiken zu erstellen, speichern und laden. Abgeleitete Informationen (first und follow, LR-Automaten, Parsertabellen), der Syntaxanalysevorgang sowie Spezialfunktionen sind hier in eine graphische Oberfläche eingebettet.
- Grammatik-Funktionen: zum Erzeugen von Ausdrucksgrammatiken aus kompakten Beschreibungen, zum Erstellen abstrakter Syntaxbäume aus konkreten (auch für Ausdrücke) und die Erstellung von Recursive-Descent-Parsern (LL(1)).
- Scanner: Erstellung von Scannern aus Jaccie-artigen Scannerbeschreibungen. Ein generischer Scannerrahmen wird ergänzt um reguläre Ruby-Ausdrücke, die den Pattern und Token der Jaccie-artigen Beschreibungen entsprechen. Als Anwendungsbeispiele dienen die beiden Beispiele aus der Einarbeitung, der Scanner zu MiniDoc und der zur Analyse der Jaccie-artigen Beschreibung eingesetzte Scanner.
Scheinerwerb
Einen Schein erhält, wer
- sowohl die Einarbeitungsaufgabe (25 Prozent)
- als auch die Analyse- und Generierungsaufgabe (35 Prozent)
- als auch die Konsolidierungsaufgabe mit abschließender Präsentation (mündliche Abschlußprüfung) (zusammen 40 Prozent)
erfolgreich absolviert.
Literatur & Links zum Compilerbau
- Auf der Syntax-Seite finden Sie u.a. mein Buch (ausführliche Darstellung), Tutorials, Beispiele und unsere Werkzeuge SIC und Jaccie.
- Ebenfalls online verfügbar: Das Buch Parsing Techniques von Dick Grune eignet sich auch sehr gut für einen "vertieften Einstieg".
Software, Links und Literatur zu Ruby
- Das Standardbuch zu Ruby ist das "Spitzhacke-Buch" (so genannt wegen des Umschlagbilds) ist
Dave Thomas: Programming Ruby - The Pragmatic Programmer's Guide, Wiley 2005 (second edition). Die Online-Version dazu enthält leider nur den Text der ersten Auflage. Von Herrn Jede stammt der Hinweis auf eine deutsche Fassung vielen Dank! - Ein empfehlenswertes deutsches Buch ist
Armin Röhrl, Stefan Schmiedl, Clemens Wyss: Programmieren mit Ruby. dpunkt-verlag GmbH, März 2002. Auch hierzu gibt es eine Online-Version. - Die Wikipedia-Seite zu Ruby enthält neben einer Kurzbeschreibung von Ruby eine sehr nützliche Linksammung, über die Sie u.a. die folgenden Seiten erreichen.
- Die originale Ruby-Homepage
- Eine Ruby-Einstiegsseite mit vielen Tipps für Anfänger.
- Ein einfaches Einstiegs-Tutorial (deutsch)
- Eine liebevoll mit Comics illustrierte Einführung (sehr umfangreich!).
Software und Installation
Aus der Menge der angebotenen Tools seien zwei besonders leicht und angenehm zu benutzende hevorgehoben:
- Der freie One-click-Installer for Windows, Beschreibung siehe One-click-Installer Doku. Man erhält eine komplette Arbeitsumgebung mit Interpretern, Doku, Beispielen und Erweiterungspaketen.
- Hat man die Ruby-Basis Installation oben abgeschlossen, dann sollte man die freie Mondrian-IDE für angenehmeres Arbeiten daraufsetzen; herunterladbar von der Mondrian Homepage.