Marpa::R2 is beta
[ blogs.perl.org has been a wonderful home, but I have finally given in to the lure of static blogging. This is cross-posted from the new home of the Ocean of Awareness blog. ]
Marpa::R2 is now beta. Marpa is a new parsing algorithm, based on decades of prior art. It is a practical and efficient solution targeted at all parsing problems that are too complex for regular expressions.
The Marpa::R2 module is the most recent Marpa module. Marpa is also available as the Marpa::XS module, which is stable and bug-fix only. Both Marpa modules:
Parse everything you can write in BNF.
Parse all classes of grammar in practical use today in linear time.
Parse all BNF grammars in times considered theoretically optimal. For unambiguous grammars, Marpa is never worse than O(n2). For ambiguous grammars, Marpa is never worse than O(n3). Marpa never goes exponential.
Are fully aware, at every point in the parse, of all the rules they are parsing, how far into them they have proceeded, and of what tokens they expect next. Especially with Marpa::R2, this information is available to the application conveniently and efficiently.
Do not need to be handwritten. Marpa is available as a open-source library. It is written in C, and the C library can be used directly or via a Perl interface.
For general BNF parsing, do not require the user to craft a lookahead or backtracking strategy -- Marpa does not use lookahead and never backtracks.
Come with the traditional theoretical apparatus of proofs based on prior literature.
Marpa::R2 is a major rewrite of the Marpa internals. The most visible of these changes:
Marpa::R2 is faster.
Marpa::R2 is easier to install. In particular the dependency on Glib has been removed. Marpa::R2 now has no non-core CPAN dependencies.
Marpa::R2's internal symbols are now invisible to the user, even when tracing and debugging.
Libmarpa, the C library which is at the core of Marpa, is now documented and separately installable. (Libmarpa remains alpha at this point.)
Another new documented interface, Marpa::R2::Thin, is a "thin" interface to Libmarpa from Perl. (Marpa::R2::Thin remains alpha at this point.)
I blog about Perl, with a focus on parsing and Marpa, my parsing algorithm based on Jay Earley's.
Regarding the new blog, I could not find a RSS feed. Without it is very difficult to keep up with your awesome Marpa work :)
Thanks,
When you say O(n^2) what is n? The size of the input document or the size of the grammar?
@Ed: In O(n^2), n is the length of the input.
@Pedro: Thanks for your encouraging words. The RSS feed is http://jeffreykegler.github.com/Ocean-of-Awareness-blog/index.rss
The new site is coming up in stages. I need to add links to the feed.
Thanks for answering my query about the O-notation. I have an existing grammar for Parse::RecDescent and use that module's $RD_AUTOACTION hook to return the complete parse tree. Is there a tool to convert the grammar or a way to get the parse tree in the same format?
@Ed: If I understand $RD_AUTOACTION correctly, it's very roughly the equivalent of Marpa's default_action named argument. I don't know of a tool that converts Parse::RecDescent grammars automatically.
Btw, in general, it is often best to ask questions on the "marpa parser" google group: marpa-parser@googlegroups.com That creates a record of the Q&A in one place, and it allows other Marpa users to answer. Some of them may know far more about conversion from Parse::RecDescent than I do.
Hi,
I'm learning to use Marpa::R2. I see when the parse fails only it gives the below error
Problem in b->new(): No parse at /fs_user/saddanki/perl5.12.3/lib/site_perl/5.12.3/x86_64-linux/Marpa/R2/Value.pm line 645
Above information isn't much helpful. I don't why it's failed? so how to further debug to know.
I have uploaded my experimental code here
http://pastebin.com/ayiUtVsP
Please tell me what else I need to do to enable a better debugging messages!
For support there is a Marpa mailing list: marpa-parser@googlegroups.com. I follow this list as much as I can, and other experts in Marpa use help answer the questions.
As a start, the Marpa::R2 documentation has a page on tracing issues with grammars. In particular, Marpa's "progress reports" are extremely helpful -- I use them a lot.