April 2011 Archives

Announcing Marpa::XS

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 th…

Bovicide 5: Parse-time Error Reporting

a series prompted by an exchange of papers on the Internet. That exchange discussed what it would take to produce an acceptable replacement for yacc and the entire family of LALR-based parsers.

My first post concentrated on speed and power -- the ability to parse all context-free grammars in O(n**3) time, and the ability to parse just about every grammar in practical use, including all yacc-able grammars, in linear (…

About Jeffrey Kegler

user-pic I blog about Perl, with a focus on parsing and Marpa, my parsing algorithm based on Jay Earley's.