Publication Details

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

KOLÁŘ, D. Simulation of LLk Parsers with Wide Context by Automaton with One-Symbol Reading Head. Proceedings of 38th International Conference MOSIS '04 - Modelling and Simulation of Systems. Ostrava: 2004. p. 347-354. ISBN: 80-85988-98-4.
Czech title
Simulace analyzátorů LLk jazyků automaty s jedním symbolem pod čtecí hlavou
Type
conference paper
Language
English
Authors
Keywords

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

Abstract

The LL grammars play important role in the programming languages description. 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.

Published
2004
Pages
347–354
Proceedings
Proceedings of 38th International Conference MOSIS '04 - Modelling and Simulation of Systems
ISBN
80-85988-98-4
Place
Ostrava
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",
  address="Ostrava",
  isbn="80-85988-98-4"
}
Back to top