Analyse von Mehrdeutigkeiten in kontextfreien Grammatiken / Ambiguity Detection for Context-free Grammars in Eli

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.

Für die syntaktische Analyse haben wir Eli vor kurzem im Rahmen einer Bachelor-Arbeit um einen GLR-Parser-Generator erweitert. 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.  Im Falle von nicht-eindeutigen Grammatiken werden ebenfalls Parser erzeugt, die dann für mehrdeutige Eingabetexte Laufzeitfehler-Meldungen erzeugen.

Um diese - für klassische Parsing-Verfahren - ungewohnte Fehlerart zu vermeiden, soll eine Mehrdeutigkeitstest integriert werden, der auf Wunsch die Parser-Erzeugung nur für Grammatiken erlaubt, die er als eindeutig eingestuft.

Da das Problem der Mehrdeutigkeitsbestimmung für kontextfreie Grammatiken unentscheidbar ist, wurden dafür in der Literatur Näherungsverfahren  vorgestellt. Die jüngsten Arbeiten dazu sind von Sylvain Schmitz, 2007 und von Brabrand, Giegerich und Moeller, 2007.

Zu den Aufgaben dieser Bachelor-Arbeit gehören
  • Darstellung des Mehrdeutigkeitsproblems für kontext-freie Grammatiken
  • Erarbeitung und Darstellung der Näherungsverfahren aus der Literatur
  • Begründete Auswahl eines Testverfahrens, das  prototypisch implementiert werden soll.
  • Implementierung des Prototyps und Integration ins Eli-System
  • Erprobung und Evaluation des implementierten Mehrdeutigkeits-Tests

Ausarbeitung: Ambiguity Detection for Context-free Grammars in Eli

Bearbeiter: Michael Kruse

Betreuer: Peter Pfahler

Impressum | Webmaster | Letzte Änderungen am : 16.10.2013