GLR Parsing für Eli

Studienarbeit / Bachelorarbeit

Eli ist ein Werkzeugsystem zum Entwurf und zur Implementierung von Programmiersprachen und anwendungsspezifischen Sprachen. Eli enthält zahlreiche generierende Werkzeuge und Bibliotheken, die die Lösung von Übersetzungsaufgaben systematisieren und den Herstellungsprozeß von Sprachimplementierungen automatisieren.

Zur Implementierung der syntaktischen Anaylyse kann ein Eli-Benutzer zwischen zwei Parser-Generatoren wählen. Beide erzeugen LALR(1)-Parser. Ziel dieser Arbeit ist es, in Eli einen GLR-Parser-Generator zu integrieren. GLR-Parsing ("generalized LR Parsing") ist eine Parsing-Technik, die im Konfliktfall (shift-reduce, reduce-reduce) mögliche Alternativen parallel verfolgt. Für eindeutige Grammatiken scheiden Alternativen bei der weiteren Eingabeverarbeitung aus bis wieder ein eindeutiger Parserzustand erreicht wird.

Vorteil des GLR-Parsing ist, dass der Grammatik-Entwurf erleichtert wird, da man nicht gezwungen ist, Nicht-LALR(1)-Grammatiken durch (oft unnatürliche) Transformationen in LALR(1)-Form zu bringen. Darüber hinaus sollte ein sorgfältig implementierter GLR-Parser keinen signifikaten Laufzeit-Nachteil verursachen.

Zu den Aufgaben dieser Arbeit gehören

• Ein existierender GLR-Parser-Generator (z.B. bison) soll in das Eli-System integriert werden. Das bedeutet, dass ein solcher Generator so gekapselt werden muss, dass er Schnittstellen-kompatibel zu den Eli-Generatoren ist.
• Erprobung des Generators mit verschiedenen Grammatiken, LALR(1), LR(1), LR(k).

Genauere Informationen finden Sie in der Ausarbeitung "Integrating a GLR Parser Generator in Eli".

Bearbeiter: Ulf Schwekendiek

Betreuer: Peter Pfahler