LParse: A continuation-based parser library

[ library, mit, parsing ] [ Propose Tags ]

A parser library using continuations with a possibility for failure to build parsers in a clear and concise manner.


[Skip to Readme]
Versions 0.1.1.1, 0.1.2.0, 0.1.3.0, 0.1.3.1, 0.2.1.0, 0.2.2.2
Change log CHANGELOG.md
Dependencies base (>=4.7 && <5) [details]
License MIT
Copyright (c) 2017 Marcus Völker
Author Marcus Völker
Maintainer marcus.voelker@rwth-aachen.de
Category Parsing
Home page https://github.com/MarcusVoelker/LParse#readme
Source repo head: git clone https://github.com/MarcusVoelker/LParse
Uploaded by Sacchan at Thu Nov 30 11:56:49 UTC 2017
Distributions NixOS:0.2.2.2
Downloads 1065 total (25 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2017-11-30 [all 1 reports]
Hackage Matrix CI

Modules

[Index]

Downloads

Maintainer's Corner

For package maintainers and hackage trustees


Readme for LParse-0.2.2.2

[back to package description]

╬╗Parse Travis-CI Hackage

A parser library using monads and arrows. Supports both horizontal and vertical composition of parsers.

Short Guide

Creating a parser

A parser is, at its heart, nothing more than a function that takes some input and either returns a result along with some residual, unconsumed input or that fails for some reason and returns an error message.

Since LParse is written in continuation-passing-style, this is modelled with a concept of DoubleContinuations - continuations that not only take one function to continue with, but one function to continue with in the case of a successful computation and one function to continue with in the case of a failure. This, of course, gives rise to classic parser semantics: To concatenate two parsers, the second one is put into the successful continuation of the first one, while for an alternative we put the second parser into the failure continuation of the first one.

These semantics are modelled with Monads and Alternatives, respectively, to make use of the familar syntax of these classes:

  • p1 >> p2 runs p1 and p2 in succession and gives the result of p2 only
  • (,) <$> p1 <*> p2 runs p1 and p2 in succession and gives the results of p1 and p2 as a pair
  • p1 <|> p2 runs p1. On a success, its result is returned, on a fail, p2 is run. On a success, its result is returned, on a failure, the whole parser fails

The parser can be built from scratch by constructing a parser object with the appropriate function, but a variety of common atomic parsers and parser transformers are provided in Text.LParse.Atomics and Text.LParse.Transformers, respectively.

The above construction is referred to as horizontal composition, i.e., running parsers successively on the same input. The dual concept to this we refer to as vertical composition, where the result of one parser is fed into the next one as an input. An application for this could be one parser lex that transforms a string into a list of tokens (a lexer) and a second parser par that transforms a list of tokens into a syntax tree. Then we could join these to create a parser that directly transforms a string into a syntax tree as lex >>> par

As the notation above implies, LParse realises vertical composition with arrows enabling all the other features of arrows, such as the proc notation, to be used with parsers.

Running a parser

Once you have obtained a parser object that represents your entire parser, you have two options

  1. You can supply a success and a failure function. When the parser is run, the appropriate function will be called, either with the result of the parse or an error message

  2. You can retrieve the double continuation from the parser and continue to build with it. This is appropriate if your program itself is written in CPS.