7-1-2013: Grammar-combinators v0.2.7 is released. Fixes v0.2.5 with GHC 7.4.
19-4-2011: Grammar-combinators v0.2.6 is released. Fixes v0.2.5 with GHC 7.
17-4-2011: Grammar-combinators v0.2.5 is released. Fixes incompatibility with UUParse 2.7.
17-2-2011: Grammar-combinators v0.2.4 is released. Home page back to projects.haskell.org.
10-2-2011: Grammar-combinators v0.2.3 is released. Changed home page because of unavailability of projects.haskell.org. Small fix for backward compatibility with GHC 6.
31-1-2011: Grammar-combinators v0.2.2 is released. This release makes the library work with GHC 7 (thanks to Doaitse Swierstra for reporting the problem).
5-1-2011: Grammar-combinators v0.2.1 was released. This release contains a new grammar combination primitive, the early start of a reusable grammar library, some experiments with bias introduction for Parsec and penalty-based error handling, more work on TH lifting of grammars etc. There is also an important bugfix in the uniform Paull transformation (thanks to Andries Verreydt).
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).
darcs get http://code.haskell.org/grammar-combinators/cabal update && cabal install grammar-combinatorsThe best way to learn more about this library is to read the Tutorial. After that, install the library and play with the code.
We currently have several ideas for future work. People interested are very welcome to contact us.
Heuristic-based modular error recovery
Penalty-based ambiguous parsing for highly interactive scenario's.
Automatic grammar transformation for use with penalty based ambiguous parsing.
Compositionality of grammars: add a facility for combining grammars.
Using compositional grammars: define a library of reusable non-terminals.
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?
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.