Formal Translation Directed by Paralllel LLP Parsing
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F07%3A03127928" target="_blank" >RIV/68407700:21230/07:03127928 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Formal Translation Directed by Paralllel LLP Parsing
Original language description
Formal translation directed by parallel LLP parsing is presented here. The translator follows the traditional translation scheme - the input grammar is extended by output symbols that are added into appropriate right-hand sides of grammar rules. The translation algorithm is based on the intermediate results provided by the parallel LLP parser. The correct sequence of output symbols is obtained from the intermediate results using the parallel prefix sum, the segmented parallel prefix sum, and parallel sorting steps. The translation algorithm presented here is suitable for all translations with LLP(q,k) input grammars. The asymptotical parallel time of the translation algorithm is O(log^2(n)).
Czech name
Formální překlad řízený paralelním LLP syntaktickým analyzátorem
Czech description
V práci je popsán formální překladač řízený paralelním LLP syntaktickým analyzátorem. Vlastní překladač je postaven tradičním způsobem - vstupní gramatika je rozšířena o výstupní symboly, které jsou vloženy na odpovídající místa pravých stran pravidel gramatiky. Vlastní algoritmus překladu je založen na mezivýsledcích, které poskytuje paralelní LLP syntaktický analyzátor. Správná posloupnost výstupních symbolů je získána z mezivýsledků v krocích, které využívají algoritmy paralelního prefixového součtu,paralelního prefixového součtu v segmentech a paralelního řazení. Předkládaný algoritmus překladu je použitelný pro všechny formální překlady s LLP(q,k) vstupní gramatikou. Asymptotická časová složitost algoritmu je O(log^2(n)).
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
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)
Others
Publication year
2007
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
Lecture Notes in Computer Science 4362 - SOFSEM 2007: Theory and Practice of Computer Science
ISBN
978-3-540-69506-6
ISSN
—
e-ISSN
—
Number of pages
12
Pages from-to
532-543
Publisher name
Springer-Verlag
Place of publication
Berlin
Event location
Harrachov
Event date
Jan 20, 2007
Type of event by nationality
EUR - Evropská akce
UT code for WoS article
—