Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Accelerating parser combinators with macros
 
conference paper

Accelerating parser combinators with macros

Béguet, Eric
•
Jonnalagedda, Manohar  
2014
Proceedings of the Fifth Anuual Scala Workshop on - SCALA '14
the Fifth Annual Scala Workshop (SCALA '14)

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.

  • Files
  • Details
  • Metrics
Type
conference paper
DOI
10.1145/2637647.2637653
Author(s)
Béguet, Eric
Jonnalagedda, Manohar  
Date Issued

2014

Publisher

ACM Press

Publisher place

New York, New York, USA

Published in
Proceedings of the Fifth Anuual Scala Workshop on - SCALA '14
Start page

7

End page

17

Subjects

Parser combinators

•

macros

•

Scala

•

optimization

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LAMP1  
Event nameEvent placeEvent date
the Fifth Annual Scala Workshop (SCALA '14)

Uppsala, Sweden

28-29 07 2014

Available on Infoscience
August 19, 2014
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/105919
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés