Linear Bidirectional Parsing for a Subclass of Linear Languages
Andrei, Stefan ; Kudlek, Manfred
| URN | urn:nbn:de:gbv:18-228-7-402 |
|---|---|
| URL | http://edoc.sub.uni-hamburg.de/informatik/volltexte/2009/40/ |
| Dokumentart: | Report (Bericht) |
| Schriftenreihe: | Berichte des Fachbereichs Informatik der Universität Hamburg |
| Bandnummer: | 215 |
| Sprache: | Englisch |
| Erstellungsjahr: | 1999 |
| Publikationsdatum: | 25.08.2009 |
| SWD-Schlagwörter: | LLk-Parser |
| Freie Schlagwörter (Deutsch): | lineare Grammatik |
| Freie Schlagwörter (Englisch): | linear grammars , LL(k) grammars , LLin(m,n) grammars |
| DDC-Sachgruppe: | Informatik |
| BK - Klassifikation: | 54.10 |
Kurzfassung auf Englisch:
In this paper, we consider a useful subclass of linear grammars, called LLin(m,n), which are similar to the class of LL(k) grammars. Intuitively, 'looking ahead' to the next m terminal symbols and 'looking back' to the previous n terminal symbols suffices to determine uniquely the production which was applied. The membership problem for such grammars can be solved using a linear time complexity algorithm. The paper contains results related to unambiguity, a hierarchy of languages, a comparison to LL(k) grammars, recursivity, and closure properties. We also show that there exist non-deterministic languages which can be generated by this new class of grammars. Finally, we present a characterization theorem for such grammars and describe a bidirectional parser for LLin(m,n) grammars. The case LLin(1,1) is presented in detail.
Kurzfassung auf Englisch:
In diesem Artikel betrachten wir eine nützliche Teilklasse LLin(m,n) der linearen Grammatiken, welche der Klasse der LL(k)-Grammatiken ähnelt. Intuitiv gesprochen reicht es aus, m Terminalsymbole voruas- und m Terminalsymbole zurückzuschauen, um die angewandte Regel eindeutig zu bestimmen. Das Wortproblem für solche Grammatiken hat eine lineare Zeitkomplexität. Der Artikel enthält Resultate zur Mehrdeutigkeit, eine Sprachhierarchie, eine Vergleich mit LL(k)-Grammatiken, Rekursivität, und Abschlusseigenschaften. Wir zeigen ausserdem, dass es nicht-deterministische Sprachen gibt, die mit dieser Grammatikklasse erzeugt werden können. Schließlich zeigen wir eine Charakterisierung solcher Grammatiken und beschreibe einen bidirektionalen Parser für LLin(m,n)-Grammatiken. Der Fall LLin(1,1) wird detailliert behandelt.
Hinweis zum Urherberrecht
Für Dokumente, die in elektronischer Form über Datenenetze angeboten werden, gilt uneingeschränkt das Urheberrechtsgesetz (UrhG). Insbesondere gilt:
Einzelne Vervielfältigungen, z.B. Kopien und Ausdrucke, dürfen nur zum privaten und sonstigen eigenen Gebrauch angefertigt werden (Paragraph 53 Urheberrecht). Die Herstellung und Verbreitung von weiteren Reproduktionen ist nur mit ausdrücklicher Genehmigung des Urhebers gestattet.
Der Benutzer ist für die Einhaltung der Rechtsvorschriften selbst verantwortlich und kann bei Mißbrauch haftbar gemacht werden.