April 2013 Archives

Is Earley parsing fast enough?

done in production compilers for existing programming languages? The answer is, practically none." -- Jay Earley's Ph.D thesis, p. 122.

[ This is cross posted from its home at the Ocean of Awareness blog.

In the above quote, the inventor of the Earley parsing algorithm poses a question. Is his algorithm fast enough for a production compiler? His answer …

Marpa's SLIF now allows procedural parsing

[ This is cross-posted from the Ocean of Awareness blog. ]

Marpa's SLIF (scanless interface) allows an application to parse directly from any BNF grammar. Marpa parses vast classes of grammars in linear time, including all those classes currently in practical use. With its latest release, Marpa::R2's SLIF also allows an application to intermix its own custom lexing and parsing logic with Marpa's, and to switch back and forth between them. This means, among other things, that Marpa's SLIF can now do procedural parsing.

What is procedural parsing? Procedural parsing is parsing using ad hoc code in a procedural language. The opposite of procedural parsing is declarative parsing -- parsing driven by some kind of formal description of the grammar. Procedural parsing may be described as what you do when you've given up on your parsing algorithm. Dissatisfaction with parsing theory has left modern programmers accustomed to procedural parsing. And in fact some problems are best tackled with procedural parsing.

About Jeffrey Kegler

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