Optimizing Parser Combinators
| Autor: | Mohammad Ghafari, Jan Vraný, Jan Kurs, Mircea Lungu, Oscar Nierstrasz |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Programming language
Computer science Recursive descent parser computer.software_genre Top-down parsing Canonical LR parser Simple LR parser 510 Mathematics TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Parser combinator GLR parser LL parser Software_PROGRAMMINGLANGUAGES LALR parser computer 000 Computer science knowledge & systems |
| Zdroj: | IWST |
| DOI: | 10.1145/2991041.2991042 |
| Popis: | Parser combinators are a popular approach to parsing. Parser combinators follow the structure of an underlying grammar, are modular, well-structured, easy to maintain, and can recognize a large variety of languages including context-sensitive ones. However, their universality and flexibility introduces a noticeable performance overhead. Time-wise, parser combinators cannot compete with parsers generated by well-performing parser generators or optimized hand-written code. Techniques exist to achieve a linear asymptotic performance of parser combinators, yet there is still a significant constant multiplier. This can be further lowered using meta-programming techniques. In this work we present a more traditional approach to optimization —- a compiler —- applied to the domain of parser combinators. A parser combinator compiler (pc-compiler) analyzes a parser combinator, applies parser combinator-specific optimizations and, generates an equivalent high-performance top-down parser. Such a compiler preserves the advantages of parser combinators while complementing them with better performance. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|