The Marpa parser

Jeffrey Kegler's website for Marpa, his new parsing algorithm

Resources

Jeffrey Kegler's website

Follow @jeffreykegler

The Ocean of Awareness blog: home page, chronological index, and annotated index.

Marpa::R2 (active distribution): CPAN | MetaCPAN

Marpa::XS (stable distribution): CPAN | MetaCPAN

Mailing List (quite active): marpa-parser@googlegroups.com

Repository of stable code: github Experimental repository: github

I hope Marpa will become the standard for parsing languages that are too complex for regular expressions to handle. Marpa's current release is Marpa::R2.

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(n³) (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 Marpa::R2, 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.

Theory

For those interested in the mathematics behind Marpa, there's a paper with pseudocode, and proofs of correctness and of my complexity claims.

Examples

Here are some simple & elegant examples of Marpa parsers that others have done:

• A CSS parser by Wolfgang Kinkeldei
• A Graph::Easy parser by Ron Savage
• A Marpa parser that converts a grammar into another Marpa parser by Peter Stuifzand

Here is a more ambitious one:

• Graphviz2::Marpa by Ron Savage. This article describes the writing process, and has tips for using Marpa.

Other resources

Libmarpa is a C library, and is the core of Marpa.

Marpa internals: These are resources of interest only to those working on the internals of Marpa itself -- "bleeding edge" documentation, etc.