Loading…
Eine Rekonstruktion der LR-Theorie zur Elimination von Redundanz mit Anwendung auf den Bau von ELR-Parsern
Kannapinn, Sönke
In dieser Arbeit befassen wir uns mit zwei Problemen aus dem Themenfeld der Konstruktion sogenannter LR-Parser und damit dem Gebiet der Syntaxanalyse für kontextfreie Sprachen. Zum ersten zeigen wir auf, daß die herkömmliche LR-Parserkonstruktionstechnik Parser produziert, die erhebliche systematische Redundanzen aufweisen. Wir erarbeiten eine neue, theoretisch fundierte Methode, die sogenannte allgemeine LR(k)-Parser definiert. Zu einer gegebenen kontextfreien Grammatik charakterisiert die Definition eine ganze Familie von Kellertransduktoren, die alle die Form des entsprechenden kanonischen (und gleichzeitig "allgemeinen") LR(k)-Parsers haben, diesem im Verhalten völlig gleichwertig sind und dessen Schlüsseleigenschaften der linearen Laufzeit und des Determinismus bewahren. Dennoch ist die formale Größe allgemeiner LR(k)-Parser potentiell deutlich kleiner als die des kanonischen Pendants. Wir zeigen, wie wir durch die Anwendung von aus der Automatentheorie bekannter Minimierungstechnik zu minimal großen allgemeinen LR(k)-Parsern gelangen können und zu "ziemlich kleinen" auch durch eine direkte Konstruktion. In der Folge übertragen wir das Verfahren auch auf allgemeine SLR(k)- und LALR(k)-Parser und analysieren im Zuge dessen die neue Klasse der ILALR(k)-Grammatiken, für deren Mächtigkeit sich die Teilmengenbeziehung LALR(k) < ILALR(k) < LR(k) für k > 0 ergibt. Dabei ist ein kanonischer ILALR(k)-Parser sogar von kleinerer, höchstens gleicher Größe als der kanonische LALR(k)-Parser. Schließlich beschreiben wir auch einen Weg zur geschickten Implementierung der formal entworfenen Parser. Mit dem neuen Verfahren können wir klarstellen, daß die klassisch konstruierten LR-Parser Eigenschaften aufweisen, die für ihr korrektes Funktionieren im allgemeinen verzichtbar sind und mit Redundanz in der Konstruktion bezahlt werden. Wir arbeiten die in den traditionellen LR-Parsern unverzichtbaren Konstruktionsbestandteile und -eigenschaften heraus und tragen damit auch in didaktischer Hinsicht zum Verständnis der Konstruktion solcher Parser bei. Zum zweiten beleuchten wir in dieser Arbeit die Konstruktion von LR-Parsern für die sogenannten erweiterten kontextfreien Grammatiken, von denen Syntaxdiagramme und die Erweiterte Backus-Naur-Form sowie die regular right part grammars verschiedene Erscheinungsformen sind. Auf diesem Gebiet ist bis heute keine theoretisch gänzlich befriedigende Arbeit veröffentlicht worden. Wir analysieren und kritisieren die bekannten Veröffentlichungen zum Thema; hierbei bildet ein eigenes, fundiertes Verfahren eine wesentliche Grundlage, und wir greifen auf Ergebnisse des ersten Teils der Arbeit zurück. Nebenbei präzisieren wir die Rolle der epsilon-Normalform von Brüggemann-Klein im Zusammenhang mit der Eindeutigkeit regulärer Ausdrücke.
In this thesis, we present work on two problems from the field of LR parser construction, a family of syntax analysis techniques for context-free languages. In the first part, we show that the traditional LR parser construction technique produces parsers which are burdened with a substantial amount of systematic redundance. We develop a new and well-founded method which defines what we call general LR(k) parsers. For a given grammar, the definition characterizes a whole family of pushdown transducers the members of which all have the shape of the respective canonical LR(k) parser (which is also "general"), share its essential behaviour, and preserve its important linear-run-time and determinism properties. Yet, the formal size of general LR(k) parsers is potentially much smaller than the formal size of their canonical version. We demonstrate how to construct general LR(k) parsers of minimal size by applying minimization techniques from automata theory, and how to construct "nearly-minimal" general LR(k) parsers directly. We then adopt the method to the construction of general SLR(k) and LALR(k) parsers, and introduce the class of ILALR(k) grammars. Here, we show that, concerning grammar classes, the subset relation LALR(k) < ILALR(k) < LR(k) holds for k > 0 while at the same time the formal size of a canonical ILALR(k) parser is smaller than or equal to the formal size of a canonical LALR(k) parser. As a round-up of the first part, we sketch an apt implementation of the formally presented parsers. The new method distills those properties of LR parsers that are indispensable for their correctness; and it shows which ingredients of the traditional construction technique are responsible for guaranteeing correctness and which are responsible for nice-to-have yet dispensable properties that cause redundance. In the second part, we investigate the construction of LR parsers for the so-called extended context-free grammars of which syntax diagrams, Extended Backus-Naur Form, and regular right part grammars are different concrete versions. In that area of research, no work has been presented to the present day that is completely satisfying and theoretically deep. We analyze and criticize the relevant journal publications, and we develop, to that end, a theoretically well-founded method to construct such parsers profiting from results from the first part of this work. In the given context, we are also concerned with the concept of unambiguity of regular expressions, and we are able to state the role of Brüggemann-Klein s epsilon normal form of regular expressions more precisely.
