[ANN] Transept 0.1.0: Generalised Parser Combinators

I’m happy to announce the first release of Transept an OCaml implementation of generalized parsers combinators.

This implementation has been inspired by a 19 years old paper - written by Daan Leijen and Erik Meijer - titled “Parsec: Direct Style Monadic Parser Combinators For The Real World” [1]. The current implementation provides basic combinators dedicated to char, chars recognition but also conjunction, sequence, repetition and more. Since the current design relies on the abstract definition of manipulated element most of the parsers are generic and can be used with streams of chars or something else.

Finally, with this library, I wanted to share my love of OCaml modules :hugs:

Opam: https://opam.ocaml.org/packages/transept/transept.0.1.0/

[1] https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/parsec-paper-letter.pdf

8 Likes

It good to see yet another parser combinator for OCaml, even if this makes more difficult the choice of one of them. I believe this highlights how well OCaml shines for this kind of applications where both high-level expressiveness and performance matter.

angstrom is one the alternatives and provides a comparison with others. It would be good to position transept here.

There is also a more recent article with a radically new approach: A Typed, Algebraic Approach to Parsing by Neelakantan R. Krishnaswami and Jeremy Yallop - PLDI 2019. This paper proposes a library of parser combinators for context-free expressions, an algebraic presentation of the context-free languages. The key points are

  • the use of types to statically reject any language which cannot be parsed unambiguously and linearly;
  • the use of staging, with OcamlBER, to produce parsers which performance are close to those of hand-written code.
5 Likes