Publication detail
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
conference paper
Language
en
Original 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.
English 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.
Keywords
pushdown automaton, LL(k) grammars, context-free language parser
RIV year
2004
Released
19.04.2004
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
Documents
BibTex
@inproceedings{BUT17112,
author="Dušan {Kolář}",
title="Simulation of LLk Parsers with Wide Context by Automaton with One-Symbol Reading Head",
annote="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.",
booktitle="Proceedings of 38th International Conference MOSIS '04 - Modelling and Simulation of Systems",
chapter="17112",
year="2004",
month="april",
pages="347--354",
type="conference paper"
}