Embedded Parser Generators

Jonas Duregård and Patrik Jansson (in the Chalmers FP group)

Abstract

We present a novel method of embedding context-free grammars in Haskell, and to automatically generate parsers and pretty-printers from them. We have implemented this method in a library called BNFC-meta (from the BNF Converter, which it is built on). The library builds compiler front ends using metaprogramming instead of conventional code generation. Parsers are built from labelled BNF grammars that are defined directly in Haskell modules. Our solution combines features of parser generators (static grammar checks, a highly specialised grammar DSL) and adds several features that are otherwise exclusive to combinatory libraries such as the ability to reuse, parameterise and generate grammars inside Haskell.

To allow writing grammars in concrete syntax, BNFC-meta provides a quasi-quoter that can parse grammars (embedded in Haskell files) at compile time and use metaprogramming to replace them with their abstract syntax. We also generate quasi-quoters so that the languages we define with BNFC-meta can be embedded in the same way. With a minimal change to the grammar, we support adding anti-quotation to the generated quasi-quoters, which allows users of the defined language to mix concrete and abstract syntax almost seamlessly. Unlike previous methods of achieving anti-quotation, the method used by BNFC-meta is simple, efficient and avoids polluting the abstract syntax types.

Bibtex

@inproceedings{BNFC-meta-Haskell2011,
  author =	 {Dureg{\aa}rd, Jonas and Jansson, Patrik},
  title =	 {Embedded Parser Generators},
  booktitle =	 {Proceedings of the 4th {ACM} Symposium on {Haskell}},
  series =	 {Haskell '11},
  isbn =	 {978-1-4503-0860-1},
  location =	 {Tokyo, Japan},
  pages =	 {107--117},
  numpages =	 11,
  url =		 {http://doi.acm.org/10.1145/2034675.2034689},
  doi =		 {10.1145/2034675.2034689},
  acmid =	 2034689,
  publisher =	 {ACM},
  address =	 {New York, NY, USA},
  keywords =	 {domain specific languages, metaprogramming},
  year =	 2011
}

Publication status

2011-07-01: Accepted for Haskell Symposium 2011!
2011-03-24: Preprint (before reviewing) 2011-03-25

Links

Hackage packages for BNFC-meta, happy-meta and alex-meta.