Optimizing Parser Combinators
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F16%3A00302490" target="_blank" >RIV/68407700:21240/16:00302490 - isvavai.cz</a>
Výsledek na webu
<a href="http://www.esug.org/data/ESUG2016/IWST/Papers/IWST_2016_paper_3.pdf" target="_blank" >http://www.esug.org/data/ESUG2016/IWST/Papers/IWST_2016_paper_3.pdf</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1145/2991041.2991042" target="_blank" >10.1145/2991041.2991042</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Optimizing Parser Combinators
Popis výsledku v původním jazyce
Parser combinators are a popular approach to pars-ing. Parser combinators follow the structure of an un-derlying grammar, are modular, well-structured, easyto maintain, and can recognize a large variety of lan-guages including context-sensitive ones. However, theiruniversality and flexibility introduces a noticeable per-formance overhead. Time-wise, parser combinators can-not compete with parsers generated by well-performingparser generators or optimized hand-written code.Techniques exist to achieve a linear asymptotic per-formance of parser combinators, yet there is still a sig-nificant constant multiplier. This can be further loweredusing meta-programming techniques.In this work we present a more traditional approachto optimization — a compiler — applied to the do-main of parser combinators. A parser combinator com-piler (pc-compiler) analyzes a parser combinator, ap-plies parser combinator-specific optimizations and, gen-erates an equivalent high-performance top-down parser.Such a compiler preserves the advantages of parser com-binators while complementing them with better perfor-mance.
Název v anglickém jazyce
Optimizing Parser Combinators
Popis výsledku anglicky
Parser combinators are a popular approach to pars-ing. Parser combinators follow the structure of an un-derlying grammar, are modular, well-structured, easyto maintain, and can recognize a large variety of lan-guages including context-sensitive ones. However, theiruniversality and flexibility introduces a noticeable per-formance overhead. Time-wise, parser combinators can-not compete with parsers generated by well-performingparser generators or optimized hand-written code.Techniques exist to achieve a linear asymptotic per-formance of parser combinators, yet there is still a sig-nificant constant multiplier. This can be further loweredusing meta-programming techniques.In this work we present a more traditional approachto optimization — a compiler — applied to the do-main of parser combinators. A parser combinator com-piler (pc-compiler) analyzes a parser combinator, ap-plies parser combinator-specific optimizations and, gen-erates an equivalent high-performance top-down parser.Such a compiler preserves the advantages of parser com-binators while complementing them with better perfor-mance.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
—
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2016
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
IWST'16 Proceedings of the 11th edition of the International Workshop on Smalltalk Technologies
ISBN
978-1-4503-4524-8
ISSN
—
e-ISSN
—
Počet stran výsledku
12
Strana od-do
—
Název nakladatele
ACM
Místo vydání
New York
Místo konání akce
Praha
Datum konání akce
22. 8. 2016
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
000390845100001