Sequential and parallel parsing, translation and semantics
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 1 (SGA02002GA-ST)
Main participants
České vysoké učení technické v Praze / Fakulta elektrotechnická
Contest type
VS - Public tender
Contract ID
—
Alternative language
Project name in Czech
Sekvenční a paralelní syntaktická analýza, překlad a sémantika
Annotation in Czech
Algoritmy syntaktické analýzy a syntaxí řízeného překladu pro bezkontextové gramatiky patří k základním algoritmům teorie formálních jazyků. Poslední dobou jsme objevili zrychlení algoritmu sekvenční nedeterministické LR (GLR) analýzy pro případ bezkontextových gramatik bez pravé rekurze. Toto zrychlení jsme zkombinovali s jiným zlepšením, které bylo prezentováno zahraničními kolegy z Kanady na konferenci CC '99. První implementace výsledného GLR analyzátoru vykazují podstatné zrychlení analýzy ve srovnání se standardním (Tomitovým) GLR analyzátorem. Článek popisující tento výsledek byl přijat a poslán k vytištění do časopisu Acta Informatica. Paralelní verze našeho GLR analyzátoru je optimální pro jistou třídu gramatik, obsahující např. gramatiku generující aritmetické výrazy. Dále se domníváme, že je účelné uvažovat z podobného pohledu i o sekvenční a paralelní LL analýze a o vzájemných vztazích mezi LL a LR analýzou. V oblasti překladů jsme popsali překladač řízený LR analyzátorem pro
Scientific branches
R&D category
ZV - Basic research
CEP classification - main branch
JC - Computer hardware and software
CEP - secondary branch
—
CEP - another secondary branch
—
OECD FORD - equivalent branches <br>(according to the <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">converter</a>)
20206 - Computer hardware and architecture
Completed project evaluation
Provider evaluation
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Project results evaluation
In the area of our method of faster GLR parsing, where the number of stack operations are significantly reduced and certain operations are precomputed beforehand, we have described a new construction method. That method is based on the well known theory
Solution timeline
Realization period - beginning
Jan 1, 2002
Realization period - end
Jan 1, 2004
Project status
U - Finished project
Latest support payment
—
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP/2005/GA0/GA05GA/U/N/B:7
Data delivery date
Jun 2, 2008
Finance
Total approved costs
2,150 thou. CZK
Public financial support
1,098 thou. CZK
Other public sources
1,052 thou. CZK
Non public and foreign sources
0 thou. CZK