The official Marpa starting page.
The Ocean of Awareness blog: home page, chronological index, and annotated index.
Marpa::R2 (active distribution): CPAN | MetaCPAN
Jeffrey Kegler's personal website
Donate to Marpa via patreon.comMarpa 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.
What you are looking at is the web site maintained by the author of Marpa (Jeffrey Kegler). It is NOT the best page for starting to learn about Marpa. Good places to do that are:
Discussion of Marpa currently centers around the "marpa parser" Google Group and the IRC channel: #marpa on irc.libera.chat.
Most of the posts on Ocean of Awareness, my blog, 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,
Marpa is supported by donations:
Donate to Marpa via patreon.com
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. |
For those interested in the mathematics behind Marpa, I have a paper on arxiv.org with pseudocode, and proofs of correctness and of my complexity claims.
Libmarpa is a C library, and is the core of Marpa.
I mentioned above that Marpa parses unambiguous grammars in linear time, with a couple of exceptions, and claimed that those were unlikely to be bothersome in practice. Here are the details.
For an unambiguous grammar to be parsed in linear time, it must
The marker of a middle recursion is anything that allows the parser to find the middle. It is possible to represent a halting Turing computation as a marker, so that the general problem of finding any possible marker is, in fact, undecidable. But that's not something you are likely to want to do in practice. For practical purposes, if you can spot the middle by eyeball, the middle recursion is "marked". If you can't, the middle recursion might be unmarked.
Right recursive symches are very easy to avoid. You just rewrite the rules so that they recurse on different symbols. Preserving the semantics is no problem in this case -- you simply make sure both of the new symbols have the same semantics as the original one.