Research Topics
[] Entwurf und Implementierung eines effizienten Lexer Generators (für den Babylon Compiler Generator)
Der Java basierte Compilergenerator „Babylon“ beinhaltet einen Generator für syntaktische Analysephase und einen Generator für die lexikalische Analysephase. Letzterer basiert auf der Generierung eines deterministischen endlichen Automaten (DEA) aus einer geordneten Menge von Tokendefinitionen. Jede Tokendefinition beinhaltet einen regulären Ausdruck, welcher ihren Definitionsbereich festlegt.
Der in Babylon integrierte Lexergenerator arbeitet nach dem Prinzip der Thompson-Konstruktion und verwendet zur internen Repräsentation der endlichen Automaten eine generische Graph Implementierung mit Einzelkanten. Diese Darstellung ist jedoch wegen des hohen Speicherverbrauchs für eine große Zahl von Zustandsübergängen, wie sie bei der Verwendung von Unicode Zeichenkodierungen auftreten können, ungeeignet. Um reguläre Ausdrücke zu parsen und zur Konstruktion entsprechender endlicher Automaten verwendet der Lexergenerator einen proprietären per Hand implementierten Parser, welcher sich nur umständlich ändern bzw. erweitern lässt. So ist es beispielsweise schwierig zusätzliche Operatoren in die Sprache einzuführen, da hierzu der Code des Parsers an den richtigen Stellen manuell modifiziert werden muss. Compilergeneratoren wie Babylon unterstützen dagegen eine deklarative Sprachbeschreibung und können eingesetzt werden, um eine bessere Erweiterbarkeit zu Gewährleisten.
Zur Lösung obiger Probleme befasst sich diese Arbeit mit dem Entwurf und der Implementierung eines effizienten Lexergenerators für den Babylon Compilergenerator unter Verwendung von Babylon. Die Implementierung sollte es ermöglichen, zu den Elementen im generierten DEA die ursprünglichen Tokendefinitionen festzustellen.
Betreuer: Sven Karol