Bidirectional Parsing for Context Free Languages
Andrei, Stefan ; Kudlek, Manfred
| URL | http://edoc.sub.uni-hamburg.de/informatik/volltexte/2009/42/ |
|---|---|
| Dokumentart: | Report (Bericht) |
| Schriftenreihe: | Berichte des Fachbereichs Informatik der Universität Hamburg |
| Bandnummer: | 219 |
| Sprache: | Englisch |
| Erstellungsjahr: | 1999 |
| Publikationsdatum: | 25.08.2009 |
| SWD-Schlagwörter: | Kontextfreie Grammatik |
| Freie Schlagwörter (Deutsch): | Unterklassen |
| Freie Schlagwörter (Englisch): | subclasses , context-free grammars |
| DDC-Sachgruppe: | Informatik |
| BK - Klassifikation: | 54.10 |
Kurzfassung auf Englisch:
In this paper, we describe some subclasses of context-free grammars for which a parallel approach useful for solving the membership problem will be defined. More precisely, we will combine the classical type of parser attached to a grammar $G$ with a “mirror" process for $G$. They analyse the input word from both sides using two processors. In the first section, we present the (general) left and right bidirectional parsers which use a nondeterministic device for any context free language. In the second section, a general SIMD model for describing bidirectional parsing is introduced. It contains two algorithms which use a backtracking method to describe the nondeterministic behaviour of the (general) left and right bidirectional model. The third section treats some deterministic subclasses of context free grammars, such as $RR(k)$, $RL(k)$ and $SIP$ grammars. The idea is to put in a reverse view" the classical deterministic subclasses of context free grammars. The fourth section points out the application of the (general) left and right bidirectional parser to the deterministic subclasses described in the previous section. Ten new classes of grammars obtained by combining the previous ones are defined, using descendant and ascendant strategies. The membership problem for all these type of grammars can be solved with a parallel algorithm in linear time.
Kurzfassung auf Deutsch:
In diesem Artikel beschreiben wir einige Teilklassen kontextfreier Sprachen. für welche ein paralleler Ansatz zur Lösung des Wortproblems existiert. Im ersten Teil untersuchen wir allgemeine nicht deterministische links- und rechts-bidirektionale Parser ein, welche jede kontextfreie Sprache analysieren. Im zweiten Teil untersuchen wir ein allgemeines SIMD-Modell zur Beschreibung bidirektionalen Parsens. Es enthält zwei Algorithmen mit backtracking um das nichtdeterministische Verhalten des allgemeinen links-(und recht-) bidirektionalen Modells zu beschreiben. Der dritte Teil behandelt einige deterministische Teilklassen der kontextfreien Grammatiken, wie RR(k)-, RL(k) und SIP-Grammatiken. Der vierte Teil betrachtet die Anwendung der im Teil 3 beschriebenen deterministischen Teilklassen auf allgemeine links- (und rechts-) bidirektionale Parser. Wir erhalten 10 Kombinationen von Grammatiken mit auf- und absteigenden Strategien. Das Wortproblem für diese Grammatiktypen kann mit einem parallelen Algorithmus in linearer Zeitkomplexität gelöst werden. Im letzten Teil geben wir einige Folgerungen und offene Probleme an.
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.