Publication detail

Parsing Based on n-Path Tree-Controlled Grammars

ČERMÁK, M. KOUTNÝ, J. MEDUNA, A.

Original Title

Parsing Based on n-Path Tree-Controlled Grammars

English Title

Parsing Based on n-Path Tree-Controlled Grammars

Type

journal article - other

Language

en

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

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

Keywords

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

RIV year

2012

Released

31.01.2012

Publisher

NEUVEDEN

Location

NEUVEDEN

ISBN

1896-5334

Periodical

Theoretical and Applied Informatics

Year of study

2011

Number

23

State

PL

Pages from

213

Pages to

228

Pages count

16

URL

Documents

BibTex


@article{BUT91443,
  author="Martin {Čermák} and Jiří {Koutný} and Alexandr {Meduna}",
  title="Parsing Based on n-Path Tree-Controlled Grammars",
  annote="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.",
  address="NEUVEDEN",
  chapter="91443",
  doi="10.2478/v10179-011-0015-7",
  edition="NEUVEDEN",
  howpublished="print",
  institution="NEUVEDEN",
  number="23",
  volume="2011",
  year="2012",
  month="january",
  pages="213--228",
  publisher="NEUVEDEN",
  type="journal article - other"
}