Ocean of Awareness

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

Jeffrey's personal website


Marpa resources

The Marpa website

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

Wed, 20 Jun 2012

Marpa & customizing the Ruby Slippers

The Marpa parser introduced Ruby Slippers parsing. But the Ruby Slippers were just part of a broader feature of Marpa -- its "situational awareness". With the latest release of Marpa::R2, applications now have efficient access to the broader awareness.

For those new to this blog Marpa is something new in parsing -- it parses anything you can write in BNF and, if your grammar is in one of the classes currently in practical use, parses it in linear time. Marpa::R2's parse engine is written in optimized C, so that Marpa::R2's speed is competitive with parsers of far less power.

Marpa knows at every point in the parse, which rules are possible, how far into those rules the parse has already gotten, and where those rules might start. This degree of situational awareness is unusual in a parser, and the more "production quality" the parser, the more unusual it is. This seems paradoxical. Situational awareness seems like a common sense thing to want in any parser, and certainly in one that you'd hope would be able to produce quality error messages. But the practice has been for parsers, as a way to achieve efficiency, to turn their grammar into an abstraction. This can be OK if all goes as planned, but if anything goes wrong it means these parsers don't really have a clue what it was.

In stable distribution, Marpa::XS, Marpa already made situational awareness available in a form that allowed Ruby Slippers parsing -- at any point in the parse, it could return a list of expected tokens. A full description of the parse was also available in Marpa::XS's progress reports, which gave this information in text form. This was wonderful for tracing parsing issues, but it was not a convenient form for post-processing.

As of its latest release, Marpa::R2 makes available the "raw" data behind the progress reports. This is ideal for post-processing. My hope is that users will use this to invent their own advanced parsing tricks -- customized versions of the Ruby Slippers.

The road is open. Marpa::R2 is fast, powerful and maneuverable. Floor it.

posted at: 14:57 | direct link to this entry

§         §         §