TU Darmstadt / ULB / TUbiblio

Church-Rosser Languages and Their Application to Parsing Problems

Woinowski, Jens Robert (2001)
Church-Rosser Languages and Their Application to Parsing Problems.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

Kurzbeschreibung (Abstract)

Church-Rosser languages were defined by McNaughton, Narendran, and Otto in 1988. They are the deterministic variant of the growing context-sensitive languages. Their word problem is decidable in linear time and they are a propper superset of the deterministic context-free languages. Their definition is baes on confluent length-reducing string rewriting systems, enhanced by the possibility to mark word ends and to use variables (nonterminals). The thesis discusses the application of Church-Rosser languages to basic parsing problems, which, for example, appear in compiler construction. It is shown that it is possible to compute a description of each Church-Rosser language which has rewriting system fulfilling a special syntactical restriction. This restriction is similar to context-sensitive rules with swapped sides and ist called context-splittability. This result, which was not expected before, is a classification of the Church-Rosse languages which is also expandable to growing context-sensitive languages. For example, this normal form allows to compute syntax trees for accepted words of a Church-Rosser languages. Furthermore, it makes the proof easier that the Church-Rosser languages properly contain the deterministic context-free languages. Using this normal form a construction is introduced which can be used to describe certain the prefix languages of certain Church-Rosser languages again as Church-Rosser languages. Since in general this is not possible some decision problems arise. This are also discussed in the thesis, and at least paritally circumvented by test methods.

Typ des Eintrags: Dissertation
Erschienen: 2001
Autor(en): Woinowski, Jens Robert
Art des Eintrags: Erstveröffentlichung
Titel: Church-Rosser Languages and Their Application to Parsing Problems
Sprache: Englisch
Referenten: Walter, Prof. Dr. Hermann ; Otto, Prof. Dr. Friedrich
Berater: Walter, Prof. Dr. Hermann
Publikationsjahr: 27 November 2001
Ort: Darmstadt
Verlag: Technische Universität
Datum der mündlichen Prüfung: 22 Oktober 2001
URL / URN: urn:nbn:de:tuda-tuprints-1739
Kurzbeschreibung (Abstract):

Church-Rosser languages were defined by McNaughton, Narendran, and Otto in 1988. They are the deterministic variant of the growing context-sensitive languages. Their word problem is decidable in linear time and they are a propper superset of the deterministic context-free languages. Their definition is baes on confluent length-reducing string rewriting systems, enhanced by the possibility to mark word ends and to use variables (nonterminals). The thesis discusses the application of Church-Rosser languages to basic parsing problems, which, for example, appear in compiler construction. It is shown that it is possible to compute a description of each Church-Rosser language which has rewriting system fulfilling a special syntactical restriction. This restriction is similar to context-sensitive rules with swapped sides and ist called context-splittability. This result, which was not expected before, is a classification of the Church-Rosse languages which is also expandable to growing context-sensitive languages. For example, this normal form allows to compute syntax trees for accepted words of a Church-Rosser languages. Furthermore, it makes the proof easier that the Church-Rosser languages properly contain the deterministic context-free languages. Using this normal form a construction is introduced which can be used to describe certain the prefix languages of certain Church-Rosser languages again as Church-Rosser languages. Since in general this is not possible some decision problems arise. This are also discussed in the thesis, and at least paritally circumvented by test methods.

Alternatives oder übersetztes Abstract:
Alternatives AbstractSprache

Die Church-Rosser-Sprachen wurden 1988 von McNaughton, Narendran und Otto erstmals definiert. Sie sind die deterministische Variante der wachsend-kontextsensitiven Sprachen. Ihr Wortproblem ist in Linearzeit entscheidbar und sie sind eine echte Obermenge der deterministisch-kontextfreien Sprachen. Ihre Definition basiert auf konfluenten, längenreduzierenden Wortersetzungs-Systemen, erweitert um die Möglichkeit, Wortenden zu markieren und Hilfszeichen zu verwenden. Die vorliegende Arbeit beschäftigt sich mit der Anwendbarkeit der Church-Rosser-Sprachen für grundlegende Parsing-Probleme, wie sie zum Beispiel im Umfeld des Compilerbaus auftreten. Die Arbeit weist nach, dass es möglich ist, zu jeder Church-Rosser-Sprache eine Beschreibung zu berechnen, deren Wortersetzungssystem eine umgedrehten kontextsensitiven Regeln entsprechende syntaktische Restriktion erfüllt. Diese Restriktion wird Kontext-zerlegbarkeit genannt. Diese Normalform, die nicht vorher nicht erwartet worden war, ist eine Klassifikation der Church-Rosser-Sprachen und auch auf die wachsend kontextsensitiven Sprachen übertragbar. Mit Hilfe dieser kontext-zerlegbaren Systeme kann unter anderem zu einem akzeptierten Wort einer Church-Rosser-Sprache ein Syntaxbaum berechnet werden. Darübr hinaus erleichtert diese Normalform den Beweis, dass die deterministisch-kontextfreien Sprachen enthalten sind. Mit Hilfe dieser Normalform wird eine Konstruktion eingeführt, mit der es möglich ist, von bestimmten Church-Rosser-Sprachen die Prfäfixsprache als Church-Rosser-Sprache zu beschreiben. Da dies im allgemeinen nicht erreichbar ist, wirft diese Konstruktion auch einige Entscheidungsprobleme auf, die ebenfalls in der Arbeit diskutiert und zumindest teilweise durch einige Testmethoden umgangen werden.

Deutsch
Freie Schlagworte: Church-Rosser-Sprachen, Wortersetzung, schrumpfende Zweikeller-Automaten, Syntaxanalyse
Schlagworte:
Einzelne SchlagworteSprache
Church-Rosser languages, string rewriting systems, shrinking two pushdown automata, growing context-sensitive languages, parsingEnglisch
Sachgruppe der Dewey Dezimalklassifikatin (DDC): 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Fachbereich(e)/-gebiet(e): 20 Fachbereich Informatik
Hinterlegungsdatum: 17 Okt 2008 09:21
Letzte Änderung: 26 Aug 2018 21:24
PPN:
Referenten: Walter, Prof. Dr. Hermann ; Otto, Prof. Dr. Friedrich
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: 22 Oktober 2001
Schlagworte:
Einzelne SchlagworteSprache
Church-Rosser languages, string rewriting systems, shrinking two pushdown automata, growing context-sensitive languages, parsingEnglisch
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen