Publication Details

Parsing Based on n-Path Tree-Controlled Grammars

ČERMÁK, M.; KOUTNÝ, J.; MEDUNA, A. Parsing Based on n-Path Tree-Controlled Grammars. Theoretical and Applied Informatics, 2011, vol. 23, no. 3, p. 213-228. ISSN: 1896-5334.
Czech title
Syntaktická analýza stromem řízených gramatik s omezenými cestami
Type
journal article
Language
English
Authors
Čermák Martin, Ing., Ph.D.
Koutný Jiří, Ing., Ph.D.
Meduna Alexandr, prof. RNDr., CSc. (DIFS)
URL
Keywords

regulated rewriting, derivation tree, tree-controlled grammars, path-controlled
grammars, parsing, n-path tree-controlled grammars

Abstract

This paper discusses recently introduced kind of linguistically motivated
restriction placed on tree-controlled grammars-context-free grammars with some
root-to-leaf paths in their derivation trees restricted by a control language. We
deal with restrictions placed on n >= 1 paths controlled by a deterministic
context-free language, and we recall several basic properties of such a rewriting
system. Then, we study the possibilities of corresponding parsing methods working
in polynomial time and demonstrate that some non-context-free languages can be
generated by this regulated rewriting model. Furthermore, we illustrate the
syntax analysis of LL grammars with controlled paths. Finally, we briefly discuss
how to base parsing methods on bottom-up syntax-analysis.

Published
2011
Pages
213–228
Journal
Theoretical and Applied Informatics, vol. 23, no. 3, ISSN 1896-5334
DOI
10.2478/v10179-011-0015-7
BibTeX 
@article{BUT91443,
  author="Martin {Čermák} and Jiří {Koutný} and Alexandr {Meduna}",
  title="Parsing Based on n-Path Tree-Controlled Grammars",
  journal="Theoretical and Applied Informatics",
  year="2011",
  volume="23",
  number="3",
  pages="213--228",
  doi="10.2478/v10179-011-0015-7",
  issn="1896-5334",
  url="https://journals.pan.pl/tai/133102"
}
Files
Back to top