Detail publikačního výsledku

Simulation of LLk Parsers with Wide Context by Automaton with One-Symbol Reading Head

KOLÁŘ, D.

Original Title

Simulation of LLk Parsers with Wide Context by Automaton with One-Symbol Reading Head

English Title

Simulation of LLk Parsers with Wide Context by Automaton with One-Symbol Reading Head

Type

Paper in proceedings outside WoS and Scopus

Original Abstract

The LL grammars play important role in the programming languagesdescription. The construction of their efficient and simple analyzers(pushdown
automata) is limited
to the LL(1) grammars, however. The descriptive power of these grammars
is quite low and, in addition, there are problems with analysis of the
LL(k+1), k>=1, grammars. This paper presents algorithm that allows transformation
from pushdown automaton with (k+1)-symbol reading head used for LL(k+1) language
analysis to the one-symbol reading
head pushdown automaton. Thus, we can simulate a function of the former by
using much simpler constructs of the latter.

English abstract

The LL grammars play important role in the programming languagesdescription. The construction of their efficient and simple analyzers(pushdown
automata) is limited
to the LL(1) grammars, however. The descriptive power of these grammars
is quite low and, in addition, there are problems with analysis of the
LL(k+1), k>=1, grammars. This paper presents algorithm that allows transformation
from pushdown automaton with (k+1)-symbol reading head used for LL(k+1) language
analysis to the one-symbol reading
head pushdown automaton. Thus, we can simulate a function of the former by
using much simpler constructs of the latter.

Keywords

pushdown automaton, LL(k) grammars, context-free language parser

Key words in English

pushdown automaton, LL(k) grammars, context-free language parser

Authors

KOLÁŘ, D.

Released

19.04.2004

Publisher

Marq software s.r.o.

Location

Ostrava

ISBN

80-85988-98-4

Book

Proceedings of 38th International Conference MOSIS '04 - Modelling and Simulation of Systems

Pages from

347

Pages to

354

Pages count

8

Full text in the Digital Library

http://hdl.handle.net/

BibTex

@inproceedings{BUT17112,
  author="Dušan {Kolář}",
  title="Simulation of LLk Parsers with Wide Context by Automaton with One-Symbol Reading Head",
  booktitle="Proceedings of 38th International Conference MOSIS '04 - Modelling and Simulation of Systems",
  year="2004",
  pages="347--354",
  publisher="Marq software s.r.o.",
  address="Ostrava",
  isbn="80-85988-98-4"
}