Accelerating parser combinators with macros

Parser combinators provide an elegant way of writing parsers: parser implementations closely follow the structure of the underlying grammar, while accommodating interleaved host language code for data processing. However, the host language features used for composition introduce substantial overhead, which leads to poor performance. In this paper, we present a technique to systematically eliminate this overhead. We use Scala macros to analyse the grammar specification at compile-time and remove composition, leaving behind an efficient top-down, recursive-descent parser. We compare our macro-based approach to a staging-based approach using the LMS framework, and provide an experience report in which we discuss the advantages and drawbacks of both methods. Our library outperforms Scala's standard parser combinators on a set of benchmarks by an order of magnitude, and is 2x faster than code generated by LMS.


Publié dans:
Proceedings of the Fifth Anuual Scala Workshop on - SCALA '14, 7-17
Présenté à:
the Fifth Annual Scala Workshop (SCALA '14), Uppsala, Sweden, 28-29 07 2014
Année
2014
Publisher:
New York, New York, USA, ACM Press
Mots-clefs:
Laboratoires:




 Notice créée le 2014-08-19, modifiée le 2019-03-16

Publisher's version:
Télécharger le document
PDF

Évaluer ce document:

Rate this document:
1
2
3
 
(Pas encore évalué)