parsley: A fast parser combinator library backed by Typed Template Haskell

[ bsd3, library, parsing ] [ Propose Tags ]

Parsley is a staged selective parser combinator library, which means it does not support monadic operations, and relies on Typed Template Haskell to generate very fast code. Currently there are no error messages but there are plans for this in the works.

Based on the work found in <em>Staged Selective Parser Combinators</em> (Willis et al. 2020)

While this library adheres to the Haskell PVP, it additionally enforces an additional constraint: the version M.I.m.p represents a breaking change to the user API M, a breaking change to the internal API I (which will not affect most users), an addition to either API m, and patches or performance improvements p. As such, users should feel free to bound themselves on the next M version of the library as opposed to the second I version if they do not make use of the Parsley.Internal package or any of its children.


[Skip to Readme]
Versions [RSS] [faq] 0.1.0.1, 0.1.1.0, 1.0.0.0
Change log ChangeLog.md
Dependencies array (>=0.5.2 && <0.6), base (>=4.10 && <4.16), bytestring (>=0.10.8 && <0.12), containers (==0.6.*), dependent-map (>=0.4.0 && <0.5), dependent-sum (>=0.7.1 && <0.8), ghc-prim (>=0.5.3 && <1), hashable (>=1.2.7.0 && <1.4), mtl (>=2.2.1 && <2.3), pretty-terminal (>=0.1.0 && <0.2), template-haskell (>=2.14 && <3), text (>=1.2.3 && <1.3), unordered-containers (>=0.2.13 && <0.3) [details]
License BSD-3-Clause
Author Jamie Willis, Parsley Contributors
Maintainer Jamie Willis <j.willis19@imperial.ac.uk>
Category Parsing
Home page https://github.com/j-mie6/ParsleyHaskell
Bug tracker https://github.com/j-mie6/ParsleyHaskell/issues
Source repo head: git clone https://github.com/j-mie6/HaskellParsley
Uploaded by j_mie6 at 2021-06-10T17:03:19Z
Distributions
Downloads 113 total (113 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs available [build log]
Last success reported on 2021-06-11 [all 1 reports]

Modules

[Index] [Quick Jump]

Downloads

Maintainer's Corner

For package maintainers and hackage trustees

Candidates


Readme for parsley-0.1.1.0

[back to package description]

Parsley GitHub Workflow Status GitHub release GitHub license GitHub commits since latest release (by SemVer)

What is Parsley?

Parsley is a very fast parser combinator library that outperforms the other libraries in both the parsec family, as well as Happy. To make this possible, it makes use of Typed Template Haskell to generate the code for the parsers.

How do I use it? Hackage Version Dependent repos (via libraries.io)

Parsley is distributed on Hackage, and can be added by depending on the package parsley.

The version policy adheres to the regular Haskell PVP, but the two major versions are distinguished in Parsley: the first is the User API major version, which represents backwards incompatible changes in the regular PVP sense that could affect any users of the library; the second version is the Internal API major version, which would only effect users who use part of the internal parsley modules. As such, for people that are not explicitly importing anything from Parsley.Internal, or its submodules, the second major version does not matter: 0.2.0.0 and 0.3.0.0 would be compatible, for instance.

To use it, you'll need to write you parsers in another file from where they will be used: this is due to Template Haskell.

How does Parsley being a Staged Selective library change its use?

By being a Selective Parser Combinator library, Parsley does not support monadic operations such as (>>=) or return. Instead, the most powerful operations are select or branch. Most monadic power can be recovered using the functionality provided by Parsley.Register, as well as the selectives.

The reason monads are not supported is because of the Staging: Parsley parsers are compiled ahead of time to produce fast code, but this means the entirety of the parser must be known before any input is provided, ruling out dynamic monadic operations. The use of staging (in this instance provided by Typed Template Haskell) means that the signatures of the combinators do not correspond to their counterparts in other libraries: they don't use raw values, they use code of values. A consequence of this is that Parsley does not implement instances of Functor, Applicative, Alternative, or indeed Selective; do-notation also cannot be used even with ApplicativeDo, except perhaps if RebindableSyntax is used.

Code is provided to the combinators by way of the datatype WQ (or Defunc if you're feeling fancy), which pairs a normal value with its Haskell code representation:

data WQ a = WQ a (Code a)

This gives us combinators like:

pure :: WQ a -> Parser a
satisfy :: WQ a -> Parser a

char :: Char -> Parser a
char c = satisfy (WQ (== c) [||(== c)||])

Using WQ explicitly like this can get annoying, which is what the parsley-garnish package is for! Currently, the garnish provides one plugin called OverloadedQuotes, which replaces the behaviour of the default Untyped Template Haskell quotes in a file so that they produce one of WQ or Defunc. See the Parsley.OverloadedQuotesPlugin module in the parsley-garnish package for more information.

How does it work?

In short, Parsley represents all parsers as Abstract Syntax Trees (ASTs). The representation of the parsers the users write is called the Combinator Tree, which is analysed and optimised by Parsley. This representation is then transformed into an Abstract Machine in CPS form, this is analysed further before being partially evaluated at compile-time to generate high quality Haskell code. For the long version, I'd recommend checking out the paper!

Bug Reports

If you encounter a bug when using Parsley, try and minimise the example of the parser (and the input) that triggers the bug. If possible, make a self contained example: this will help me to identify the issue without too much issue. It might be helpful to import Parsley.Internal.Verbose to provide a debug dump that I can check out.

References

Talks

For talks on how writing parsers changes when using Parsley see either of these:

For the technical overview of how Parsley works: