The Marpa parser
The Marpa parser
This is Jeffrey Kegler's website for Marpa, a parsing algorithm
Resources
The official Marpa<br>starting page.
Follow @jeffreykegler
The Ocean of Awareness blog:
home page,
chronological index,<br>and
annotated index.
Marpa::R2 (active distribution):
CPAN
MetaCPAN
Mailing List
Github repository
Jeffrey Kegler's personal website
Donate to Marpa via patreon.com
-->
Marpa<br>is a parsing algorithm.<br>It is new, but very much based<br>on earlier work by Jay Earley, Joop Leo, John Aycock and R. Nigel Horspool.<br>Marpa is intended to replace, and to go well beyond,<br>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, any unambiguous grammars,<br>with a couple of exceptions that are not likely to<br>be an issue in practice (see quibbles); and
all<br>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<br>written in BNF.<br>This includes any mixture of left, right and middle recursions.
Marpa is convenient.<br>Unlike recursive descent, you do not have to write a parser --<br>Marpa generates one from BNF.<br>Unlike PEG or yacc, parser generation is unrestricted and exact.<br>Marpa converts any grammar which can be written as BNF<br>into a parser which recognizes everything<br>in the language described by that BNF, and which rejects everything that is<br>not in that language.<br>The programmer is not forced to make arbitrary choices while parsing.<br>If a rule has several alternatives,<br>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<br>do your own custom processing. Unlike recursive descent, Marpa makes available<br>to you detailed information about the parse so far --<br>which rules and symbols have been recognized, with their locations,<br>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<br>(Jeffrey Kegler).<br>It is<br>NOT<br>the best page for starting to learn about Marpa.<br>Good places to do that are:
Marpa's official starting page,<br>which is maintained by Ron Savage.
The documentation of
Marpa::R2,<br>Marpa's current stable release.
Other Marpa resources
Discussion of Marpa currently centers around
the "marpa parser" Google Group<br>and the IRC channel:<br>#marpa<br>on<br>irc.libera.chat.
Most of the posts on
Ocean of Awareness,<br>my blog,<br>are about Marpa.<br>To get oriented in my blog,<br>start at its
annotated list of the most interesting Marpa posts.
If you are interested in tutorials,
My blog contains
several tutorials.
Peter Stuifzand has written another as part of
the Marpa Guide.
And amon has written this
one for Stackoverflow.
Marpa is supported by donations:
Donate to Marpa via patreon.com
[nested comment] - ->
Donate to Marpa via paypal.me
This is the most convenient way to make a one-time donation.
The name of the paypal.me account is that of the next version of Marpa: Kollos .
("Marpa" and my own name were taken.)
Click through and you'll see the "Carmel, CA" address
and a picture of me in a hat.
--><br>Theory
For those interested in the mathematics behind Marpa, I have<br>a paper on arxiv.org<br>with pseudocode, and proofs of correctness and of my complexity claims.
Marpa internals
Libmarpa<br>is a C library, and is the core of Marpa.
Quibbles
I mentioned above that Marpa parses unambiguous grammars in linear time,<br>with a couple of exceptions,<br>and claimed that those were unlikely to be bothersome in practice.<br>Here are the details.
For an unambiguous grammar to be parsed in linear time,<br>it must
be free of unmarked middle recursions; and<br>be free of ambiguous right recursions.
Unmarked middle recursions?
Unmarked middle recursions are what they sound like:<br>recursions that are not left and right, but in the middle of<br>a rule, and for which there is no "marker".<br>What's a marker?<br>That gets tricky.<br>The marker of a middle recursion is anything that allows the parser to find the middle.<br>It is possible to represent a halting Turing computation as a marker,<br>so that the general problem of finding any possible marker is,<br>in fact, undecidable.<br>But that's not something you are likely to want to do in practice.<br>For practical purposes, if you can spot the middle by eyeball, the middle<br>recursion is "marked".<br>If you can't, the middle recursion might be unmarked.<br>Ambiguous right recursions
How does an unambiguous grammar manage to include an ambiguous right recursion?<br>The answer is not very easily, but you can sneak an ambiguous right recursion into<br>an unambigious grammar,<br>by having two different right recursive rules,<br>both of which recurse on the same symbol.<br>I call these ambiguities right recursive symches -- "symches"<br>because they are ambiguous due to a choice between symbols.<br>A right recursion can also be...