The Marpa parser
I hope Marpa will become the standard for parsing languages that are too complex for regular expressions to handle.
Marpa's current release is
What Marpa Does
Marpa parses anything you can write in BNF, including ambiguous and even infinitely ambiguous grammars.
Marpa easily and efficiently handles both left- and right-recursion.
If a grammar is in one of the classes in practical use today, Marpa parses it in O(n) (linear) time.
Marpa never goes exponential. Worst case, even for wildly ambiguous grammars, is
O(n3) (cubic) time.
Marpa's run-time error detection is revolutionary. Marpa has complete situational awareness. It knows at all times which rules it is attempting to apply, how far it has progressed in them, and exactly which tokens it can accept. And Marpa can communicate its situational awareness back to the application.
Marpa allows the application to efficiently retry rejected input. This, combined with its situational awareness, allows "Ruby Slippers" parsing: When an application has a token rejected, it can ask the parse engine which tokens would be acceptable. It can then create a virtual token that allows the parse to continue -- the application can make the parse engine's "wishes" come true. The Ruby Slippers are easy to use and surprisingly wide in their application.
What Marpa is
Marpa is a new parsing
algorithm with a decades-long heritage. Its lineage starts
with the algorithm invented by Jay Earley. Marpa is the first
algorithm to combine the improvements to Earley's algorithm made by Joop
Leo with those discovered by John Aycock and R. Nigel Horspool. Marpa's
"situational awareness", and Ruby Slippers parsing, are a new feature.
Learning more about Marpa
The best places to learn about Marpa
are 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.