Parsing Expression Grammars Made Practical

Laurent, Nicolas;Mens, Kim
(2015) 2015 ACM SIGPLAN International Conference on Software Language Engineering (SLE 2015) — Location: Pittsburg, USA (25.October.2015)

Files

paper.pdf
  • Closed Access
  • Adobe PDF
  • 217.61 KB
Request a copy
sle2015_submission_23.pdf
  • Restricted Access
  • Adobe PDF
  • 217.61 KB
Request a copy
ParsingExpressionGrammarsMadePractical.pdf
  • Open Access
  • Adobe PDF
  • 100.65 KB
Download

Details

Authors
  • Laurent, Nicolasorcid-logoUCLouvain
    Author
  • Mens, Kimorcid-logoUCLouvain
    Author
Abstract
Parsing Expression Grammars (PEGs) define languages by specifying a recursive-descent parser that recognises them. The PEG formalism exhibits desirable properties, such as being closed under composition, built-in disambiguation, unification of syntactic and lexical concerns, and closely matching programmer intuition. Unfortunately, state of the art PEG parsers still lack features that are taken for granted in other parsing paradigms. In particular, many struggle with left-recursive grammar rules, which are not supported by the original definition of the formalism and can lead to infinite recursion under naive implementations. Likewise, support for associativity and precedence is spotty at best. To remedy these issues, we introduce Autumn, a new general purpose PEG library that supports left-recursion, left and right associativity and precedence rules, and does so efficiently. Furthermore, we identify infix and postfix expressions as a major source of inefficiency in left-recursive PEG parsers and show how to tackle this problem. We also explore the modular nature of PEGs by showing how one can easily introduce new parsing operators (sometimes called combinators) and how our parser accomodates custom memoization and error handling strategies. We compare our parser to both state of the art and battle-tested PEG and CFG parsers, such as Rats!, Parboiled and ANTLR.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Laurent, N., & Mens, K. (2015). Parsing Expression Grammars Made Practical. Proceedings of the International Conference on Software Language Engineering (SLE 2015), 167-172. https://doi.org/10.1145/2814251.2814265