Detail výsledku

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.
Typ
článek v časopise
Jazyk
anglicky
Autoři
Čermák Martin, Ing., Ph.D., UIFS (FIT)
Koutný Jiří, Ing., Ph.D., UIFS (FIT)
Meduna Alexandr, prof. RNDr., CSc., UIFS (FIT)
Abstrakt

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.

Klíčová slova

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

URL
Rok
2011
Strany
213–228
Časopis
Theoretical and Applied Informatics, roč. 23, č. 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"
}
Soubory
Projekty
Bezkontextové gramatiky a zásobníkové automaty, MŠMT, KONTAKT, MEB041003, zahájení: 2010-01-01, ukončení: 2011-12-31, ukončen
Matematické a inženýrské metody pro vývoj spolehlivých a bezpečných paralelních a distribuovaných počítačových systémů, GAČR, Doktorské granty, GD102/09/H042, zahájení: 2009-01-30, ukončení: 2012-12-31, ukončen
Pokročilé rozpoznávání a prezentace multimediálních dat, VUT, Vnitřní projekty VUT, FIT-S-11-2, zahájení: 2011-01-01, ukončení: 2013-12-31, ukončen
Výzkum informačních technologií z hlediska bezpečnosti, MŠMT, Institucionální prostředky SR ČR (např. VZ, VC), MSM0021630528, zahájení: 2007-01-01, ukončení: 2013-12-31, řešení
Výzkumné skupiny
Výzkumná skupina formálních modelů (VZ FM)
Pracoviště
Ústav informačních systémů (UIFS)
Nahoru