gll: GLL parser with simple combinator interface

[ bsd3, compilers, library ] [ Propose Tags ]

GLL is a parser combinator library for writing generalised parsers. The parsers can correspond to arbitrary context-free grammar, accepting both non-determinism and (left-) recursion. The underlying parsing algorithm is GLL (Scott and Johnstone 2013).

The library provides an interface in Control.Applicative style (although no instance of Applicative is given). Users can add arbitrary semantic to the parser.

There are 4 top-level functions: parse, parseString, parseWithOptions and parseStringWithOptions. They all return a list of semantic results, one for each derivation. In the case that infinite derivations are possible only 'good parse trees' are accepted (Ridge 2014).

Function parse relies on a builtin Token datatype. User-defined token-types are currently not supported. parseString enables parsing character strings. The user is granted GLL.Combinators.Options to specify certain disambiguation rules.

GLL.Combinators.MemInterface is a memoised version of the library. Parsers are no longer pure functions and must be built inside the IO monad, providing fresh memo-tables to each memo'ed non-terminal.

See UnitTests and MemTests for examples of using both version of the library.

Versions [faq],,,,,,,,,,,,,,,,, (info)
Dependencies array, base (>=4.5 && <=, containers (>=0.4), TypeCompose [details]
License BSD-3-Clause
Author L. Thomas van Binsbergen
Category Compilers
Uploaded by ltvanbinsbergen at Thu Jun 4 16:43:59 UTC 2015
Distributions NixOS:
Downloads 5204 total (359 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs not available [build log]
Last success reported on 2015-06-09 [all 6 reports]


  • GLL
    • Combinators
      • GLL.Combinators.Interface
      • GLL.Combinators.MemInterface
      • GLL.Combinators.Memoisation
      • GLL.Combinators.Options
  • MemTests
  • UnitTests


Maintainer's Corner

For package maintainers and hackage trustees