Return to search

Contributions to the syntactical analysis beyond context-freeness

Parsability approaches of several grammar formalisms generating also non-context-free languages are explored. Chomsky grammars, Lindenmayer systems, grammars with controlled derivations, and grammar systems are treated. Formal properties of these mechanisms are investigated, when they are used as language acceptors. Furthermore, cooperating distributed grammar systems are restricted so that efficient deterministic parsing without backtracking becomes possible. For this class of grammar systems, the parsing algorithm is presented and the feature of leftmost derivations is investigated in detail. / Ansätze zum Parsing verschiedener Grammatikformalismen, die auch nicht-kontextfreie Sprachen erzeugen können, werden diskutiert. Chomsky-Grammatiken, Lindenmayer-Systeme, Grammatiken mit gesteuerten Ersetzungen und Grammatiksysteme werden behandelt. Formale Eigenschaften dieser Mechanismen als Akzeptoren von Sprachen werden untersucht. Weiterhin werden kooperierende verteilte (CD) Grammatiksysteme derart beschränkt, dass effizientes deterministisches Parsing ohne Backtracking möglich ist. Für diese Klasse von Grammatiksystemen wird der Parsingalgorithmus vorgestellt und die Rolle von Linksableitungen wird detailliert betrachtet.

Identiferoai:union.ndltd.org:Potsdam/oai:kobv.de-opus-ubp:5971
Date January 2011
CreatorsBordihn, Henning
PublisherUniversität Potsdam, Mathematisch-Naturwissenschaftliche Fakultät. Institut für Informatik
Source SetsPotsdam University
LanguageEnglish
Detected LanguageEnglish
TypeText.Thesis.Habilitation
Formatapplication/pdf
Rightshttp://opus.kobv.de/ubp/doku/urheberrecht.php

Page generated in 0.0018 seconds