The Marpa parser
is a parsing algorithm.
It is new, but very much based
on earlier work by 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 grammar classes that recursive descent parses;
- the grammar class that the yacc family parses;
- in fact, all unambiguous grammars, as long as they are free of unmarked middle recursions;
ambiguous grammars that are unions of a finite set of any of the above grammars.
Marpa is powerful. Marpa will parse anything that can be
written in BNF.
This includes any mixture of left, right and middle recursions.
- Marpa is convenient.
Unlike recursive descent, you do not have to write a parser --
Marpa generates one from BNF.
Unlike PEG or yacc, parser generation is unrestricted and exact.
Marpa converts any grammar which can be written as BNF
into a parser which recognizes everything
in the language described by that BNF, and which rejects everything that is
not in that language.
The programmer is not forced to make arbitrary choices while parsing.
If a rule has several alternatives,
all of the alternatives are considered for as long as they might yield a valid parse.
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 about Marpa
What you are looking at is the web site maintained by the author of Marpa
the best page for starting to learn about Marpa.
Good places to do that are:
Other Marpa resources
Discussion of Marpa currently centers around
the "marpa parser" Google Group
and the IRC channel:
Most of the posts on
Ocean of Awareness,
are about Marpa.
To get oriented in my blog,
start at its
annotated list of the most interesting Marpa posts.
If you are interested in tutorials,
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.