Optimizing Parser Combinators

Kurs, Jan; Vraný, Jan; Ghafari, Mohammad; Lungu, Mircea; Nierstrasz, Oscar Marius (2016). Optimizing Parser Combinators. In: IWST'16 Proceedings of the 11th edition of the International Workshop on Smalltalk Technologies. Prague, Czech Republic. 23.-24.08.2016. 10.1145/2991041.2991042

[img] Text
a1-Kurs.pdf - Published Version
Restricted to registered users only
Available under License Publisher holds Copyright.

Download (1MB) | Request a copy

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.

Item Type: Conference or Workshop Item (Paper)
Division/Institute: 08 Faculty of Science > Institute of Computer Science (INF)
08 Faculty of Science > Institute of Computer Science (INF) > Software Composition Group (SCG)
UniBE Contributor: Kurs, Jan; Ghafari, Mohammad; Lungu, Mircea and Nierstrasz, Oscar Marius
Subjects: 000 Computer science, knowledge & systems
500 Science > 510 Mathematics
ISBN: 978-1-4503-4524-8
Language: English
Submitter: Oscar Marius Nierstrasz
Date Deposited: 20 Feb 2017 12:58
Last Modified: 26 Feb 2017 02:13
Publisher DOI: 10.1145/2991041.2991042
Uncontrolled Keywords: scg16 scg-pub jb17 snf-asa2 kursjan petitcompiler
BORIS DOI: 10.7892/boris.94641
URI: http://boris.unibe.ch/id/eprint/94641

Actions (login required)

Edit item Edit item
Provide Feedback