Perl & Parsing: A Metapost

This series of blog posts on "Perl and Parsing", which is evolving into a mini-history of parsing theory, started as an offshoot of my own attempt at a contribution to parsing. I wanted to do a couple of blog posts aimed at those trying to decide whether it was better to take a chance with my new parser (Marpa), or to stick with the terrors of the known. There's a large literature on parsing, but much of it is difficult or dryasdust, and I thought I could contribute a helpful overview. "An informed consumer is our best customer" and all that.

Like other offshoots of the Marpa project before it, while the "Perl & Parsing" was originally intended to draw attention to Marpa, it's been better at drawing attention to itself. I've received some positive comments, and some helpful criticism. I'm grateful for both, and I plan to continue the series.

The history is not being told in order. This is not because I am attempting to ape "Pulp Fiction". It's because the series was originally planned as perhaps two or three blog posts and has grown in scope. I'm stuck now with telling the tale using flashbacks and fast-forwards, but I'll make the process as easy as possible.

Parsing is an extremely important topic. It's technical no doubt -- math and technology play an important role in the rise and fall of parsing algorithms. But so does personality and history.

In much of what we programmers do, we are following fashion (though it does sound more professional when we call it "best practices"). In fields like parsing and search algorithms, even the top minds have to guess. Most everybody else is not even guessing -- they are simply playing follow the leader. Not that that's a bad idea. Pick leaders like Torvalds, Ritchie, Wall, Stallman and Thompson, and "follow the leader" becomes a pretty good heuristic.

Since personalities are important here, so is the history. Historians can divided into two types -- the Braudel's and the Churchill's. Fernand Braudel insisted on accumulation of detail, and avoided broad sweeping statements, especially those of the kind that are hard to back up with facts. Winston Churchill thought the important thing was the broad sense, and that historians should awaken the reader to what really mattered, not deaden him with forgettable detail.

In general, the quiet diligence of a Braudel contributes more than the flashy grandeur of a Churchill. But the history of parsing has been in the hands of the Braudel's. A Churchill would liven things up. In this series I will take Winston's road, although I hope I will avoid Winston's detours through the odd fib.

Leave a comment

About Jeffrey Kegler

user-pic I blog about Marpa, my parsing algorithm, and other things of interest to techies.