Contributions to the syntactical analysis beyond context-freeness

Beiträge zur syntaktischen Analyse nicht-kontextfreier Sprachen

  • 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.

Download full text files

Export metadata

Additional Services

Search Google Scholar Statistics
Metadaten
Author details:Henning BordihnORCiD
URN:urn:nbn:de:kobv:517-opus-59719
Supervisor(s):Helmut Jürgensen
Publication type:Habilitation Thesis
Language:English
Publication year:2011
Publishing institution:Universität Potsdam
Date of final exam:2012/03/23
Release date:2012/06/19
Tag:Akzeptierende Grammatiken; Gesteuerte Ableitungen; Grammatiksysteme; Linksableitungen; Parsing
Accepting Grammars; Controlled Derivations; Grammar Systems; Leftmost Derivations; Parsing
RVK - Regensburg classification:ST 306
RVK - Regensburg classification:ES 940
Organizational units:Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik und Computational Science
DDC classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
License (German):License LogoKeine öffentliche Lizenz: Unter Urheberrechtsschutz
External remark:CCS-Klassifikation: F.4.2 Gram
Accept ✔
This website uses technically necessary session cookies. By continuing to use the website, you agree to this. You can find our privacy policy here.