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.
I blog about Perl, with a focus on parsing and Marpa, my parsing algorithm based on Jay Earley's.
Since the smoker didn't seem to want to upload a report, here's a failure on windows proper:
https://gist.github.com/924872
@Mithaldu: Thanks! cpantesters would call this a "NA" (not applicable), I think. Marpa:::XS requires CPAN's Glib as a prerequisite and in this test the GLib install failed, apparently because the GNU libraries it needs are not on the system.
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.
@George: I have an experimental Perl parser, which is fully featured enough to parse the output of Data::Dumper. Nonetheless it's missing a lot of important syntax, such as floating point. And because I've no intention of extending it to deal with Perl's semantics, which are closely tied into Perl's parsing, Marpa::Perl may forever remain an experiment.
A number of my previous posts have talked about aspects of Perl parsing, sometimes using the results from parsing Perl snippets using my experimental parser.
@education_foo:
1.) Marpa and Marpa::XS both allow rules to be speciifed as hashes or arrays. The alternative syntax you are looking for seems very much like the rule descriptor arrays,
which are already part of both Marpa and Marpa::XS. The ability to specify rules as hashes is necessary to allow rules to have a variety of properties, most of them optional.
2.) If you use Marpa instead of Marpa::XS, neither Glib or Cweb is needed, and you get almost all of the features, but minus the XS speed-up. You can install Marpa::XS without Cweb -- you won't be able to hack the non-XS C code, but you probably do not want to do so anyway. All of the Marpa::XS interface is in Perl or the XS, neither of which requires Cweb to hack.
3.) The non-XS C code implements the core algorithm. If you look at my PDF, you'll see that I am using Cweb not because it is "nice to have", but because I desperately need it if I or anyone else is ever going to make sense of this heavily mathematical code.
4.) My long-term dream is to get out of the interface business -- just hack the core algorithm, and let others figure out which interface is best for harnessing all the cool stuff it offers.
5.) Marpa does not require Glib. For Marpa::XS, the alternative to Glib is my own attempt at a portable implementation of what it does. Trust me, you prefer Glib.