[Hs-Generics] ANNOUNCE: grammar-combinators 0.1 (initial release): A parsing library of context-free grammar combinators

[Dominique Devriese]

Copying this announcement to generics at haskell.org. The
grammar-combinators library may interest some people here, because it
uses Multirec pattern functors throughout, to abstract a grammar from
its semantics. More details in the paper we are submitting to PADL
2011 [1].

Dominique

[1]: http://projects.haskell.org/grammar-combinators/#background

The grammar-combinators library is a parsing library employing a novel
grammar representation with explicit recursion. 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. Grammars and grammar algorithms are defined in a
functional style. The library currently has the following features:

* Grammar specified completely in Haskell using an elegant syntax
* Grammar algorithms implemented in a functional style (no fresh
 identifiers), with elegant and meaningful types.
* Multi-backend: use the same grammar with a Packrat, Parsec or
 UUParse parser
* Grammar transformations: use left-recursive grammars directly thanks
 to a powerful grammar transformation library, featuring the
 left-corner left-recursion removal transform, a uniform version of
 the classic Paull left-recursion removal, and various smaller
 transformations (dead-branch removal, dead non-terminal removal,
 consecutive epsilon combination, selective unfolding etc.).
* Grammar utility functions: printing of grammars, FIRST-set
 calculation, reachability analysis of non-terminals, etc.
* Compile-time transformations (using Template Haskell), given a
 suitable definition of the grammar. This is currently limited to a
 certain set of transformations.

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

We are submitting a paper about the ideas behind this library to PADL
2011. A draft is linked on the project's website.

More information:

* Project website: http://projects.haskell.org/grammar-combinators/
* Tutorial: http://projects.haskell.org/grammar-combinators/tutorial.html
* Hackage: http://hackage.haskell.org/package/grammar-combinators

All comments welcome!

Dominique

PS. The documentation on hackage currently doesn't build because of
(seemingly) a Hackage dependency problem during the build [1].
Compiling and generating the documentation locally should work fine. A
version of the docs is available on the project's webpage as a
temporary replacement [2].

Footnotes:
[1]  http://www.haskell.org/pipermail/libraries/2010-September/014168.html
[2]  http://projects.haskell.org/grammar-combinators/docs/index.html