Ocean of Awareness

Jeffrey Kegler's blog about Marpa, his new parsing algorithm, and other topics of interest

Jeffrey's personal website

Follow @jeffreykegler

Marpa resources

The Marpa website

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

Sun, 17 Apr 2011

Announcing Marpa::XS

I have released the first non-developer's version of Marpa::XS: 0.002000. Marpa::XS is the XS-accelerated version of Marpa. Marpa is a parser generator -- it parses from any grammar that you can write in BNF. If that grammar is one of the kinds in practical use (yacc, LALR, recursive descent, LR(k), LL(k), regular expressions, etc.), Marpa and Marpa::XS parse from it in linear (O(n)) time.

• The parts of Marpa::XS that were rewritten in C run 100 times faster than the original Pure Perl.
• Typical applications run approximately 10 times faster.
• There is a new, simplified, interface for reading input.
• The documentation has been improved.
• Error reporting and tracing of grammars with right recursion has been simplified and is much improved.

Users should keep in mind the following:

• Marpa::XS is alpha software.
• Use of Marpa::XS for production, or anything mission-critical, would be unwise.
• The interface, while I hope it is rapidly stabilizing, remains subject to change.
• The previous interface for reading input, based on the tokens() method, is now strongly deprecated. It is no longer documented and will be eliminated.
• Marpa::XS does not install on a minority of Unix platforms. The failures all involve either Freebsd's 8.0-release (though Marpa::XS does install on Freebsd's 8.1-release) or Linux for the i686-linux architecture (though Marpa::XS does install on i686-linux-gnu-thread-multi, as well as every other Linux tested). Where Marpa does not install, the problem lies in dynamically linking with the two Marpa::XS shared libraries.

In a future post, I'll talk about my roadmap for Marpa and Marpa::XS. So far I have converted Marpa's grammar pre-processing and parsing to C. The only part that remains is Marpa's evaluator. While an afterthought for the theories, the evaluator is very important in practical use, and for getting the full benefit of the other speedups. Conversion of Marpa's evaluator to C will probably be my next focus.

Notes

Note 1: Marpa::XS comes with two shared libraries: an XS library, which contains Marpa-to-Perl glue, and libmarpa.a, which contains Marpa's core algorithm. libmarpa.a is a standalone shared library, suitable for linking with other environments besides Perl XS.

For Marpa::XS to be dynamically linked, three things must happen:

• First, the Marpa::XS dynamic library must be loaded. This seems to work just fine everywhere.
• Second, to resolve symbols in Marpa::XS, libmarpa.a must be found and linked in. This also seems to work just fine everywhere.
• Third, libmarpa.a uses GNU's glib, so that to resolve symbols in libmarpa.a the glib library must be found and linked in. In fact, because Marpa::XS uses CPAN's Glib, GNU's glib should already have been loaded, so that it is simply a matter of ensuring that it is used to resolve references in libmarpa.a. It is this step that is failing on a minority of platforms.

With regard to Windows, I believe there is no major obstacle to porting Marpa::XS to any of the various Perl's for Windows. The GNU glib that I mentioned is NOT glibc -- nothing about Marpa::XS requires a POSIX environment. However, I know of only one attempt to install Marpa::XS on Windows and no successes.

posted at: 21:26 | direct link to this entry

This is Ocean of Awareness's new home. This blog has been hosted at blogs.perl.org but I have succumbed to the lure of static blogging.