The Marpa parser
is a parsing algorithm.
It is new, but very much based
on the prior work of Jay Earley, Joop Leo, John Aycock and R. Nigel Horspool.
Marpa is intended to replace, and to go well beyond,
recursive descent and the yacc family of parsers.
Marpa is fast. It parses in linear time:
- All the grammars that recursive descent parses.
- All grammars that the yacc family parses.
In fact, all unambiguous grammars, as long as they are free of unmarked middle recursions.
All the ambiguous grammars that are unions of a finite set of any of the above grammars.
Marpa is powerful. Marpa will parse anything you can write in BNF,
including any mixture of left, right and middle recursion, as well as cycles.
Marpa is flexible. Like recursive descent, Marpa allows you to stop and
do your own custom processing. Unlike recursive descent, Marpa makes available
to you detailed information about the parse so far --
which rules and symbols have been recognized, with their locations,
and which rules and symbols are expected next.
Learning more about Marpa
This is Jeffrey Kegler's Marpa web site.
(I'm the author of Marpa.)
The official starting point for learning about Marpa is
Ron Savage's Marpa page.
Other good places to learn about Marpa
include the documentation of
its current release,
and my blog,
Ocean of Awareness.
Many of my blog posts are tutorials
and readers have found these especially helpful.
To get oriented in my blog,
start at its
annotated list of the most interesting Marpa posts.
Discussion of Marpa currently centers around
the "marpa parser" Google Group.
For those interested in the mathematics behind Marpa, there's
a paper with pseudocode, and proofs of correctness and of my complexity claims.
is a C library, and is the core of Marpa.
These are resources of interest only
to those working on the internals of Marpa itself --
"bleeding edge" documentation, etc.