Parallel LL Parsing

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F07%3A03129407" target="_blank" >RIV/68407700:21230/07:03129407 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Parallel LL Parsing

Original language description

Deterministic parallel LL parsing algorithm is presented. The algorithm is based on a transformation from parsing problem to parallel reduction. Firstly, the nondeterministic version of parallel LL parser is introduced. Then, it is transformed into the deterministic version- the LLP parser. The deterministic LLP(q,k) parser uses two kinds of information to select the next operation - lookahead string of length up to k symbols and lookback string of length up to q symbols. The deterministic parsing is available for a subclass of LL grammars - the LLP grammars. Both presented deterministic and nondeterministic parallel parsers are based on the parallel reduction, thus are suitable for majority of parallel architectures.

Czech name

Paralelní LL syntaktická analýza

Czech description

V práci je popsán algoritmus pro deterministickou paralelní LL syntaktickou analýzu. Vlastní algoritmus je založen na převodu problému syntaktické analýzy na problém paralelní redukce. Nejprve je předvedena nedeterministická varianta paralelního LL syntaktického analyzátoru, která je pak upravena na deterministickou variantu - LLP analyzátor. Deterministický LLP(q,k) analyzátor využívá při rozhodování o následující operaci dva zdroje informací -- dopředu prohlížený řetězec o délce k symbolů a dozadu prohlížený řetězec o délce q symbolů. Deterministická syntaktická analýza je použitelná pouze pro LLP gramatiky, ty tvoří podmnožinu LL gramatik. Jak deterministická tak nedeterministická varianta prezentovaného paralelního LL syntaktického analyzátoru je založena na paralelní redukci, analyzátory jsou tedy použitelné na většině paralelních architektur.

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

IN - Informatics

OECD FORD branch

—

Project

<a href="/en/project/GA201%2F06%2F1039" target="_blank" >GA201/06/1039: Text processing and analysis</a><br>

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2007

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Acta Informatica

ISSN

0001-5903

e-ISSN

—

Volume of the periodical

44

Issue of the periodical within the volume

1

Country of publishing house

DE - GERMANY

Number of pages

21

Pages from-to

1-21

UT code for WoS article

—

EID of the result in the Scopus database

—