gll: GLL parser with simple combinator interface

[ bsd3, compilers, library ] [ Propose Tags ]

GLL is a parser combinator library for writing generalised parsers. The user can write parsers for arbitrary context-free grammars, including both non-determinism and all forms of left and right-recursion. The underlying parsing algorithm is GLL (Scott and Johnstone 2013).

The library provides an interface in Control.Applicative style: it uses the combinators <*>, <|>, <$> and derivations. With <$> arbitrary semantic actions are added to the parser.

Four functions can be used to run a parser: parse, parseString, parseWithOptions and parseStringWithOptions. Function parse relies on the builtin Token datatype, receiving a list of Token as an input string. User-defined token-types are currently not supported. Function *parseString* enables parsing character-level parsing. The result of aparse is a list of semantic results, one result for each derivation. To avoid infinite recursion, only 'good parse trees' are considered (Ridge 2014). To limit the number of accepted derivation, and therefore avoiding potential exponential blow-up, GLL.Combinators.Options are available to specify certain disambiguation rules.

GLL.Combinators.MemInterface is a memoised version of the library. Memoisation is used to speed up the process of applying semantic actions, it is not necessary for generalised parsing: GLL.Combinators.Interface and GLL.Combinators.MemInterface are equally general. In the memoised version, parsers are no longer pure functions and must be developed inside the IO monad.

Examples can be found in the GLL.Combinators.Test directory.

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 Sat Jun 6 11:24:41 UTC 2015
Distributions NixOS:
Downloads 6184 total (186 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs available [build log]
Last success reported on 2015-06-09 [all 1 reports]




Maintainer's Corner

For package maintainers and hackage trustees