Abstract | ||
---|---|---|
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 handwritten 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 combinatorspecific 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. |
Year | DOI | Venue |
---|---|---|
2016 | 10.1145/2991041.2991042 | IWST |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
9 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jan Kurs | 1 | 10 | 3.96 |
Jan Vraný | 2 | 11 | 4.47 |
Mohammad Ghafari | 3 | 2 | 1.06 |
Mircea Lungu | 4 | 545 | 39.17 |
Oscar Nierstrasz | 5 | 2404 | 346.86 |