Simulation of LLk Parsers with Wide Context by Automaton with One-Symbol Reading Head
Result description
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
anaalysisto 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 automatonLL(k) grammarscontext-free language parser
The result's identifiers
Result code in IS VaVaI
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Simulation of LLk Parsers with Wide Context by Automaton with One-Symbol Reading Head
Original language description
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
anaalysisto the one-symbol reading
head pushdown automaton. Thus, we can simulate a function of the former by
using much simpler constructs of the latter.Czech name
Simulace analyzátorů LLk jazyků automaty s jedním symbolem pod čtecí hlavou
Czech description
LL gramatiky hrají důležitou roli v programovacích jazycích, avšak konstrukce efektivních syntaktických analyzátorů (zásobníkových automatů) takových jazyků je omezena na jazyky LL(1). Popisná síla těchto jazyků je poměrně malá a analýza jazyků LL(k), k>=1, není jednoduchá. Tato práce ukazuje algoritmus, který umožňuje převod zásobníkového automatu pro analýzu LL(k), k>=1, jazyka na automat s jediným symbolem pod čtecí hlavou. Tak je možné simulovat činnost prvého prostředky druhého, mnohem jednodduššího automatu.
Classification
Type
D - Article in proceedings
CEP classification
JC - Computer hardware and software
OECD FORD branch
—
Result continuities
Project
GA201/04/0441: Optimally integrated models of modern information technologies
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2004
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of 38th International Conference MOSIS '04 - Modelling and Simulation of Systems
ISBN
80-85988-98-4
ISSN
—
e-ISSN
—
Number of pages
8
Pages from-to
347-354
Publisher name
NEUVEDEN
Place of publication
Ostrava
Event location
Rožnov pod Radhoštěm
Event date
Apr 19, 2004
Type of event by nationality
EUR - Evropská akce
UT code for WoS article
—
Basic information
Result type
D - Article in proceedings
CEP
JC - Computer hardware and software
Year of implementation
2004