Detail publikace

LL Leftmost k-Linear Scattered Context Grammars

ZEMEK, P. MEDUNA, A. VRÁBEL, L.

Originální název

LL Leftmost k-Linear Scattered Context Grammars

Anglický název

LL Leftmost k-Linear Scattered Context Grammars

Jazyk

en

Originální abstrakt

The present paper introduces a new variant of a scattered context grammar, called an LL leftmost k-linear scattered context grammar. It is an ordinary scattered context grammar without erasing rules, where (1) every scattered context rule is composed of k-linear rules, (2) if we take the first components of every rule, the resulting context-free grammar is an LL grammar, and (3) every rule is applied in a leftmost way. We study the generative power of this variant and its parsing properties, including time and space complexity. In the conclusion, several remarks regarding the achieved results are made.

Anglický abstrakt

The present paper introduces a new variant of a scattered context grammar, called an LL leftmost k-linear scattered context grammar. It is an ordinary scattered context grammar without erasing rules, where (1) every scattered context rule is composed of k-linear rules, (2) if we take the first components of every rule, the resulting context-free grammar is an LL grammar, and (3) every rule is applied in a leftmost way. We study the generative power of this variant and its parsing properties, including time and space complexity. In the conclusion, several remarks regarding the achieved results are made.

Dokumenty

BibTex 


@inproceedings{BUT76321,
  author="Petr {Zemek} and Alexandr {Meduna} and Lukáš {Vrábel}",
  title="LL Leftmost k-Linear Scattered Context Grammars",
  annote="The present paper introduces a new variant of a scattered context grammar, called
an LL leftmost k-linear scattered context grammar. It is an ordinary scattered
context grammar without erasing rules, where (1) every scattered context rule is
composed of k-linear rules, (2) if we take the first components of every rule,
the resulting context-free grammar is an LL grammar, and (3) every rule is
applied in a leftmost way. We study the generative power of this variant and its
parsing properties, including time and space complexity. In the conclusion,
several remarks regarding the achieved results are made.",
  address="American Institute of Physics",
  booktitle="AIP Conference Proceedings",
  chapter="76321",
  doi="10.1063/1.3636862",
  edition="NEUVEDEN",
  howpublished="electronic, physical medium",
  institution="American Institute of Physics",
  number="1",
  year="2011",
  month="september",
  pages="833--836",
  publisher="American Institute of Physics",
  type="conference paper"
}