Contributions to the syntactical analysis beyond context-freeness

Autor:	Bordihn, Henning
Jazyk:	angličtina
Rok vydání:	2011
Předmět:	Parsing Akzeptierende Grammatiken Gesteuerte Ableitungen Grammatiksysteme Linksableitungen Accepting Grammars Controlled Derivations Grammar Systems Leftmost Derivations Data processing Computer science
Druh dokumentu:	Text.Thesis.Habilitation
Popis:	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.
Databáze:	Networked Digital Library of Theses & Dissertations
Externí odkaz:	http://opus.kobv.de/ubp/volltexte/2012/5971/ Zobrazit plný text záznamu