A parser library using monads and arrows. Supports both horizontal and vertical composition of parsers.
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
p2 in succession and gives the result of
(,) <$> p1 <*> p2 runs
p2 in succession and gives the results of
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
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
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
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.