August 2012 Archives

Domain-Specific Languages made simpler

[ This is cross-posted

Writing your own language

Creating your own language has been A Big Deal (tm). What if you could create a simple language in hours or minutes? There's been a serious obstacle up to now. No practical parser "just parsed" BNF. With Marpa, that restriction is lifted.

In this post, I will describe a small, sample …

Precedence parsing made simpler

This post describes a new approach to precedence parsing, more flexible. Many programmers find precedence is an intuitive way to look at problems. The traditional rules of arithmetic are a familiar example:

E ::= ( E )
E ::= n
E ::= E * E
E ::= E + E

Here, as in the rest of this post, the rules are ranked from tightest ("highest") precedence to loosest ("lowest"). The order in the above display indicates that multiplication takes precedence over addition, and parentheses take precedence over everything else.

The old way and the new w…

The solved problem that isn't, is

In the title of an excellent blog post, Laurence Tratt calls parsing, "the solved problem that isn't". I thought this phrase captured the current situation in parsing theory and practice very nicely. In stating that parsing is not a solved problem, Tratt realized he was taking on a consensus. But the consensus is fading -- for example, neither side in the interchange between Might/Darais and Russ Cox

Marpa v. Perl regexes: a rematch

Marpa::R2, the latest version of Marpa, has some significant speedups. Enough so, that it seems appropriate to revisit an old benchmark. (For those new to this blog Marpa is a new parser with a decades-long heritage. Marpa 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.)


About Jeffrey Kegler

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