Publication result detail

General Top-Down Parsers Based On Deep Pushdown Expansions

KŘIVKA, Z.; MEDUNA, A.

Original Title

General Top-Down Parsers Based On Deep Pushdown Expansions

English Title

General Top-Down Parsers Based On Deep Pushdown Expansions

Type

Paper in proceedings outside WoS and Scopus

Original Abstract

This paper  discusses a generalization of the classical general top-down
parsers formalized by pushdown automata.  This generalization consists in
allowing them to make expansions deeper in the pushdown.  Based on the
expansion depth, this paper establishes an infinite hierarchy of language
families between the families of context-free and context-sensitive
languages. The discussion about several modifications, their properties and open problems follows.

English abstract

This paper  discusses a generalization of the classical general top-down
parsers formalized by pushdown automata.  This generalization consists in
allowing them to make expansions deeper in the pushdown.  Based on the
expansion depth, this paper establishes an infinite hierarchy of language
families between the families of context-free and context-sensitive
languages. The discussion about several modifications, their properties and open problems follows.

Keywords

parsing, pushdown automata, state grammars, infinite hierarchy

Key words in English

parsing, pushdown automata, state grammars, infinite hierarchy

Authors

KŘIVKA, Z.; MEDUNA, A.

Released

25.04.2006

Publisher

Marq software s.r.o.

Location

Ostrava

ISBN

80-86840-20-4

Book

Proceedings of 1st International Workshop on Formal Models (WFM'06)

Pages from

11

Pages to

18

Pages count

8

BibTex

@inproceedings{BUT22190,
  author="Zbyněk {Křivka} and Alexandr {Meduna}",
  title="General Top-Down Parsers Based On Deep Pushdown Expansions",
  booktitle="Proceedings of 1st International Workshop on Formal Models (WFM'06)",
  year="2006",
  pages="11--18",
  publisher="Marq software s.r.o.",
  address="Ostrava",
  isbn="80-86840-20-4"
}