Jeffrey Kegler's blog about Marpa, his new parsing algorithm, and other topics of interest
Marpa resources
The Ocean of Awareness blog: home page, chronological index, and annotated index.
Jeffrey Kegler's blog about Marpa, his new parsing algorithm, and other topics of interest
The Ocean of Awareness blog: home page, chronological index, and annotated index.
In other posts, I talked about improvements to Jay Earley's parsing algorithm -- some from Joop Leo, some from Aycock and Horspool, some of mine . Here I'd like to talk about Jay Earley's original algorithm. A common belief of great scientists is that, if an idea is basic and true, it is in essence also simple, and therefore it must have a simple explanation.
Finding the simple explanation might be far from simple. But a simple explanation there ought to be. I like to look for those simple explanations. Writing my mathematical novel, The God Proof, confirmed me in this habit. Whenever I am studying something, and it seems important and true, I look for the simple explanation.
The idea behind Earley's algorithm is that you can parse by building a table of rules and where you are in those rules. "Where" means two things: location in the rule relative to the rule's symbols, and location relative to the parse's input stream.
Let's look at an example of a rule in a context-free grammar. Here's the rule for assignment in perl's perly.y :
termbinop => term ASSIGNOP term
Within a rule, position relative to the symbols of the rule is traditionally indicated with a dot. In fact, the symbol-relative rule position is very often called the dot location. Taken as a pair, a rule and a dot location are called a dotted rule.
Here's our rule with dot location indicated:
termbinop => · term ASSIGNOP term
Here's another dotted rule:
termbinop => term · ASSIGNOP term
There's another special kind of dotted rule, a completion. Here's the completed version of the example we've been using:
termbinop => term ASSIGNOP term ·
In dotted rules, Earley's algorithm has all but one piece of the information it needs to track. The final piece is the second of the two "wheres": where in the input stream. To associate input stream location and dotted rules, Earley's algorithm uses what are now called Earley items. Earley items match input streams locations with dotted rules on a many-to-many basis.
A convenient way to think of an Earley item is as a triple, or 3-tuple, consisting of dotted rule, origin and current location. The origin is the location in the input stream where the dotted rule starts. The current location is the location in the input stream which corresponds to the dot position.
Two noteworthy consequences follow from the definitions in the previous paragraph. First, if a dotted rule is a prediction, origin and current location will always be the same. Second, the input stream location where a rule ends is not necessarily tracked, unless the dotted rule is a completion. In other cases, we don't necessarily know the location at which (or even if) the rule will be completed.
Readers familiar with the literature on Earley parsing will notice that what I call the origin is usually called the "parent". Parent" is a confusing and heavily overloaded term. I avoid it when I can.
The traditional representation of Earley items defines them as pairs of dotted rule and origin. Current location is represented by membership in an Earley set, with the Earley sets corresponding, one-to-one, with locations in the input stream. For me, the traditional representation tangles the basic idea up in implementation details. I find thinking in terms of the 3-tuple is cleaner.
Everything else about Earley's algorithm is about methods of creating the Earley items, about how to extract the parse from them, and about ways of speeding things up. It gets very complicated. In Marpa it gets so complicated it can be hard to remember that there is a basic idea. But there is, and it is Jay Earley's.
posted at: 03:41 | direct link to this entry