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.

6 Comments

Since the smoker didn't seem to want to upload a report, here's a failure on windows proper:

https://gist.github.com/924872

Any crazy ideas of experimenting with the perl parser using Marpa instead of yacc?

Or perhaps less crazy being PPI?

I thought I might download Marpa::XS to see how hard it would be to replace the unnecessary

rules => [{ lhs => STRING, rhs => ARRAY}, ...]

syntax with

rules => [STRING => ARRAY, ...]

but it seems like working on Marpa requires an absolutely insane pile of prereqs, including gilb and noweb. I think you'll be on your own here until you eliminate annoying-to-install prereqs.

Leave a comment

About Jeffrey Kegler

user-pic I blog about Marpa, my parsing algorithm, and other things of interest to techies.