[Haskell] [ANNOUNCE] Frisby: composable,
linear time parser for arbitrary PEG grammers
john at repetae.net
Mon Aug 21 21:15:34 EDT 2006
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
additive = mdo
additive <- mkRule $ multitive <> char '+' ->> additive ## uncurry (+)
multitive <- mkRule $ primary <> char '*' ->> multitive ## uncurry (*)
primary <- mkRule $ char '(' ->> additive <<- char ')'
decimal <- mkRule $ many1 (oneOf ['0' .. '9']) ## read
// 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
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:
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 Meacham - ⑆repetae.net⑆john⑈
More information about the Haskell