Title
Sekvenční a paralelní syntaktická analýza, překlad a sémantika
Code
GA201/02/0125
Summary
Parsing and translation algorithms of context-free languages belong to the fundamental algorithms of the theory of formal languages. Recently we have discovered speed-up in sequential generalized LR (GLR) parsing by removing reduce operations for the cas of context-free grammars without right recursion. We have combined that speed-up with another improvement presented at the CC '99 conference by our colleagues from Canada. The first implementations of the resultant sequential LR parser are significantly faster than the standard (Tomita) GLR parser. This result is to appear in Acta Informatica. Parallel version of our GLR parsing is optimal for certain class of grammars, which includes expression grammar for example. It might be useful to also consider L parsing from a similar approach and mutual relationship between LL and LR parsing.
Start year
2002
End year
2004
Provider
Grantová agentura ČR
Category
Obecná forma
Type
Standardní projekty
Solver
Information system of research, development and innovation (in Czech)