GSoC/GCI Archive
Google Summer of Code 2013 Scala Team

parboiled2: a macro-based PEG parser generator for Scala

by Alexander Myltsev for Scala Team

Grammar-based parsing of text data is a ubiquitous problem in real-world applications. One popular technique for implementing parsers is parser combinators. However, even though it's comparatively easy to build a parser with combinators the end-result is logic that essentially "interprets" the grammar rules against the input, which is rather slow. Hand-writing a parser can yield a much faster implementation but is tedious and error-prone. It is possible to implement a parser defined via an embedded DSL that is translated into runnable code by the host language compiler at compile time. The macro support introduced with Scala 2.10 provides the required and sufficient infrastructure for such an endeavor. The goal of this project is to use Scala 2.10 macros to implement a compile-time generator for highly efficient PEG parsers. Rule definition is based on the parboiled DSL embedded in Scala with a few extensions (such as shapeless' HLists for combining flexibility with strong type-safety).