Eine Rekonstruktion der LR-Theorie zur Elimination von Redundanz mit Anwendung auf den Bau von ELR-Parsern

dc.contributor.advisorEggers, Bleickeen
dc.contributor.authorKannapinn, Sönkeen
dc.contributor.grantorTechnische Universität Berlin, Fakultät IV - Elektrotechnik und Informatiken
dc.date.accepted2001-07-06
dc.date.accessioned2015-11-20T14:38:09Z
dc.date.available2001-07-12T12:00:00Z
dc.date.issued2001-07-12
dc.date.submitted2001-07-12
dc.description.abstractIn 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 <i>allgemeine LR(k)-Parser</i> 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 <i>allgemeine SLR(k)- und LALR(k)-Parser</i> und analysieren im Zuge dessen die neue Klasse der <i>ILALR(k)-Grammatiken,</i> 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 <i>regular right part grammars</i> 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.de
dc.description.abstractIn 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 <i>general LR(k) parsers.</i> 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 <i>general SLR(k) and LALR(k) parsers,</i> and introduce the class of <i>ILALR(k) grammars.</i> 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.en
dc.identifier.uriurn:nbn:de:kobv:83-opus-1782
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/573
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-276
dc.languageGermanen
dc.language.isodeen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc004 Datenverarbeitung; Informatiken
dc.subject.otherSyntaxanalysede
dc.subject.otherLR-Parserde
dc.subject.othererweiterte kontextfreie Grammatikde
dc.subject.otherregulärer Ausdruckde
dc.subject.otherSyntax analysisen
dc.subject.otherLR parseren
dc.subject.otherextended context-free grammaren
dc.subject.otherregular expressionen
dc.titleEine Rekonstruktion der LR-Theorie zur Elimination von Redundanz mit Anwendung auf den Bau von ELR-Parsernde
dc.title.translatedReconstructing LR Theory to eliminate redundance, with an application to the construction of ELR parsersen
dc.typeDoctoral Thesisen
dc.type.versionpublishedVersionen
tub.accessrights.dnbfree*
tub.affiliationFak. 4 Elektrotechnik und Informatikde
tub.affiliation.facultyFak. 4 Elektrotechnik und Informatikde
tub.identifier.opus3178
tub.identifier.opus4183
tub.publisher.universityorinstitutionTechnische Universität Berlinen

Files

Original bundle
Now showing 1 - 1 of 1
Loading…
Thumbnail Image
Name:
Dokument_33.pdf
Size:
1.27 MB
Format:
Adobe Portable Document Format

Collections