ISBN 9783868538618

978-3-86853-861-8, Reihe Informatik

Torben Wichers
Allgemeines Bottom-Up Parsing Modell

195 Seiten, Dissertation Universität Hannover (2011), Hardcover, A5

Zusammenfassung / Abstract

Die kontextfreien Grammatiken spielen eine entscheidende Rolle für die Entwicklung von Compilern einer existierenden oder neuen Programmiersprache. Sie bieten dem Entwickler die Möglichkeit die Programmiersprache auf eine sehr einfache Art und Weise zu beschreiben. Aus den Grammatiken können dann direkt die ersten Stufen eines Compilers generiert werden. Aber auch moderne Editoren, die speziell auf die Verwendung mit einer Programmiersprache ausgerichtet sind, können viele ihrer Erweiterungen, wie z.B. ausklappbare Regionen und Autovervollständigung, direkt aus der Grammatik heraus berechnen.

In vielen Fällen soll die Grammatik jedoch nicht nur genutzt werden um eine Eingabe zu prüfen, sondern für das weitere Vorgehen die Eingabe auch in eine interne Darstellung überführt werden, die die Struktur wiedergibt. Um eine solche Übersetzung in eine interne Darstellung auf Basis einer kontextfreien Grammatik möglichst automatisiert zu realisieren, müsste die Grammatik exakt entlang der gewünschten Strukturen konstruiert sein. Meistens ist es sogar recht einfach genau diese Grammatik zu schreiben, allerdings werden die Grammatiken oft nicht von den verwendeten Parser-Generatoren akzeptiert, da gängige Verfahren wie LL- oder LR-Parsing nicht ausreichen. Aus diesem Grund müssen die Grammatiken so umgeschrieben werden, dass sie zwar noch die gleiche Sprache beschreiben aber auch dem Parsing-Algorithmus genügen. Danach geben sie jedoch häufig die Struktur nicht mehr korrekt wieder, wodurch die interne Darstellung aufwendig per Hand rekonstruiert werden muss. Wird dann die Beschreibung der Programmiersprache noch modularisiert und auf mehrere unabhängige Grammatiken verteilt, ist eine solche Umformung eventuell gar nicht möglich.

Viele der Konflikte, die sich bei diesen Grammatiken ergeben, lassen sich mit Hilfe des nicht- kanonischen Bottom-Up Parsings in den Griff bekommen. Unter dieser Klasse des Parsings sind in der Vergangenheit eine Menge Verfahren wie NSLR- oder NLALR-Parsing entstanden. Das Problem jedoch ist, dass diese Grammatikklassen nicht formal sondern in großen Teilen nur verbal spezifiziert sind, da sie alle auf dem allgemeinen Bottom-Up Modell von T.G. Szymanski beruhen, das sich als nicht besonders flexibel erweist. Aus diesem Grund ist oft nicht klar, welche Grammatikklasse genau beschrieben wird und welche Möglichkeiten es gibt einen Parsing-Algorithmus zu konstruieren. Ein weiteres Problem an dem Modell ist, dass viele Fragen, wie z.B. ob das Parsen eines Wort, das nicht zur Sprache gehört, in eine Endlosschleife gerät oder ob sich genau der Ableitungsbaum ergibt, der erwartet wird, gar nicht geklärt werden. An vielen Stellen sind die formalen Spezifikationen sehr ungenau wodurch ein Beweis dieser Fragestellungen auch kaum möglich ist.

In der vorliegenden Arbeit wurde aus diesem Grund ein allgemeines Bottom-Up Parsing Modell vorgestellt, das zum einen die notwendige Flexibilität besitzt, um einen Großteil der vorhandenen Verfahren darauf zu reduzieren und zum anderen trotzdem durch die formale Abbildung die Sicherheit einer korrekten Arbeitsweise garantiert. Weiterhin werden durch das Modell auch für weitere neue Verfahren die Möglichkeiten und Parameter aufgezeigt, an denen gestellt und verändert werden kann. Hierfür wurde genau spezifiziert, was das kanonische und was das nicht-kanonische Parsing charakterisiert bzw. welche Unterschiede bestehen. Um die verschiedenen Grammatikklassen, die sich aus dem Modell ableiten lassen, auch nutzen zu können, wird weiterhin aufgezeigt, wie sich Erkenntnisse aus dem Modell in einen Algorithmus ableiten lassen.

Um diesen praktischen Anteil des Begreifens von Grammatiken zu unterstützen, wurde ein Eclipse-Plugin programmiert, das es auf sehr einfache Art und Weise erlaubt Grammatiken zu formulieren und mit verschiedenen Parsing-Verfahren zu erproben. Dazu erweitert das Plug-In beliebige Java-Projekte um die Fähigkeiten zur Bearbeitung von Parserbeschreibungen. Zusätzlich bietet es dem Entwickler eine Vielzahl an Möglichkeiten, eigene Grammatikklassen zu konfigurieren und an Hilfsinformationen, wie den Parsing- Automaten, die genaue Arbeitsweise eines Parsers begreifbar zu machen. Um auch spätere Ideen leicht integrieren zu können und weitere Informationen zu einer Grammatik mit anzuzeigen, wurde das Plugin sehr flexibel und erweiterbar gestaltet.