[Haskell] [ANNOUNCE] Frisby: composable, linear time parser for arbitrary PEG grammers

[John Meacham]

Frisby is an implementation of the 'packrat' parsing algorithm, which
parse PEG grammars and have a number of very useful qualities, they are
a generalization of regexes in a sense that can parse everything in
LL(k), LR(k), and more, including things that require unlimited
lookahead, all in guarenteed linear time. There is no need for a
separate lexing pass when using a packrat parser due to the subsumpion
of regular expressions, and the unlimited lookahead obviating the need
to tokenize the input.

The work is still alpha, but has had some very promising test results,
parsing (subsuming lexing) megabytes of test input in seconds that
traditional backtracking parsers completely fail at.

Although the basic mechanism works, the API is still in flux, at the
moment, parsers are specified almost exactly in their native grammar
form. here is an example of a simple parser and evaluator for numeric
expressions.

additive = mdo
     additive  <- mkRule $ multitive <> char '+' ->> additive ## uncurry (+)
                           // multitive
     multitive <- mkRule $ primary <> char '*' ->> multitive ## uncurry (*)
                           // primary
     primary   <- mkRule $ char '(' ->> additive <<- char ')'
                           // decimal
     decimal   <- mkRule $ many1 (oneOf ['0' .. '9']) ## read
     return additive

// is choice, it attempts its left argument, and if it fails, it trys
 its right one.

<> is concatination
<<- and ->> are concatination that discard the results of one side or
the other

and ## is jus a fancy way of writing 'fmap' to process the results.

notice the use of 'mdo' to implement monadic recursion.


the home page and more information is here:

http://repetae.net/computer/frisby/


I would greatly welcome feedback on the API.

I have included routines that take standard regular expression syntax
and translate them into an equivalent frisby parser.


        John

--
John Meacham - ⑆repetae.net⑆john⑈