The grammar-combinators Parser Library

News

Introduction

The grammar-combinators library is an experimental next-generation parser library written in Haskell (LGPL license). The library features much of the power of a parser generator like Happy or ANTLR, but with the library approach and most of the benefits of a parser combinator library. Read the Tutorial to learn how the library works.

The library is currently not intended for mainstream use. Its API is relatively stable, but performance needs to be looked at further (see below).

Features

Download

Tutorial

The best way to learn more about this library is currently to read the Tutorial. After that, install the library and play with the code.

Limitations

Ideas for future work

We currently have several ideas for future work. People interested are very welcome to contact us.

Performance

The library's performance can currently be rather slow (parse time x50 for the grammar from our tutorial above compared against a manually transformed UUParse parser). However, we have done some initial experiments with the GHC compile flags proposed by Magalhaes, Holdermans and Jeuring where the factor of 50 was magically reduced to about 3. With the grammar transformation additionally performed at compile-time using Template Haskell, this factor was further reduced to slightly over 2.

Maybe further optimization is possible using more fine-grained inlining flags?

Background

The grammar-combinators library is fundamentally based on an abstract representation of context-free grammars with explicit recursion. The ideas behind this library are described in the following paper (being presented at PADL 2011). An accompanying technical report discusses the implementation of some important grammar algorithms.

Links

Authors