TU Darmstadt / ULB / tuprints

Church-Rosser Languages and Their Application to Parsing Problems

Woinowski, Jens Robert :
Church-Rosser Languages and Their Application to Parsing Problems.
[Online-Edition]
TU Darmstadt
[Ph.D. Thesis], (2001)

[img]
Preview
PDF
DissWoinowski.pdf
Available under Simple publication rights for ULB.

Download (1382Kb) | Preview
Item Type: Ph.D. Thesis
Title: Church-Rosser Languages and Their Application to Parsing Problems
Language: English
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.

Alternative Abstract:
Alternative AbstractLanguage
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.German
Uncontrolled Keywords: Church-Rosser-Sprachen, Wortersetzung, schrumpfende Zweikeller-Automaten, Syntaxanalyse
Alternative keywords:
Alternative keywordsLanguage
Church-Rosser-Sprachen, Wortersetzung, schrumpfende Zweikeller-Automaten, SyntaxanalyseGerman
Church-Rosser languages, string rewriting systems, shrinking two pushdown automata, growing context-sensitive languages, parsingEnglish
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Divisions: Fachbereich Informatik
Date Deposited: 17 Oct 2008 09:21
Last Modified: 07 Dec 2012 11:47
Official URL: http://elib.tu-darmstadt.de/diss/000173
URN: urn:nbn:de:tuda-tuprints-1739
License: Simple publication rights for ULB
Referees: Walter, Prof. Dr. Hermann and Otto, Prof. Dr. Friedrich
Advisors: Walter, Prof. Dr. Hermann
Refereed: 22 October 2001
URI: http://tuprints.ulb.tu-darmstadt.de/id/eprint/173
Export:

Actions (login required)

View Item View Item