You never need CNF. It has the drawback of changing the grammar
structure. But you do need to introduce intermediate non-terminals so
that no right-hand-side is longer than 2 (2-form) since RHS length
determines the complexity. The best attempt at explaining that
intuitively is, if memory serves, a paper by Beau Shiel, "Observations
on Context Free Parsing", published in 1976 in a computational
lingistics conference. Earley's algorithm uses 2-form implicitly. It
is just hidden in the algorithm. Regarding recovery and handling of
parse forest, you should look the web at "parsing intersection
forest". It is actually very straightforward. Many papers are on the
web, if you get (from citations or tables of content) the titles or
authors to search them directly.
Actually, you can do a lot more than CF, and still get parse-forests
in polynomial time. The question is, sometimes: what can you do with it
once you have it ?
One purpose of the last article you mention is to show that complex
algorithms (such as GLR) are not necessarily buying anything in time
or in space, and may change your parse forest.
One remark about teaching. I think Earley, seminal as it was, is far
too complicated for teaching, and could be replaced by simpler
algorithms with essentially the same educational content. Teaching is
about concepts or technology. In Earley's algorithm, the essential
concepts are hidden in the complexity of details, and from a
technology point of view it is outdated. It was a great paper, but it
does not mean it is the best pedagogical approach.
There may be more information in the computational linguistics
literature than in the usual computer science channels.
I do not have the Ceriel-Grune-Jacobs book, but I would be surprised
if they did not have all the proper references (though I am not sure
about their selection criteria).
Complement following a request in a comment (july 7, 2013)
This complement concnerns the existence of simpler algorithms than Earley's.
As I said, searching the web at "parsing intersection forest" should
quickly give you references, from which you can dig further.
The basic idea is that all paths parsing with construction of a shared
forest is nothing but the old intersection construction of Bar Hillel,
Perles and Shamir for a regular language and a context-free language,
using a finite automaton and a context-free grammar. Given the CF
grammar, you apply the construction to a trivial automaton that
recognizes only your input string. That is all. The shared forest is
just the grammar for the intersection. It is related to the original
grammar through a homomorphism, recognizes only the given string, but
with all the parse-trees of the original grammar up to that
homomorphism (i.e., simple renaming of non-terminals).
The resulting grammar contains a lot of useless stuff, non-terminals
and rules, that are either unreachable from the axiom (not to be found
in a string derived from the initial symbol) or that are
non-productive (cannot be derived into a terminal string).
Then, either you have to clean it with a good brush at the end
(possibly long but algorithmically simple), or you can try to improve
the construction so that there is less useless fluff to be brushed in
For example, the CYK construction is exactly that, but organized so
that all rules and non-terminals created are productive, though many
can be unreachable. This is to be expected from a bottom-up technique.
Top-down techniques (such as LR(k) based ones) will avoid unreachable
rules and non-terminals, but will create unproductive ones.
A lot of the brushing can actually be achieved by adequate use of
pointers, I think, but I have not looked at this for a long time.
All existing algorithms actually follow essentially that model. So
that is really the heart of the matter, and it is very simple. Then
why bury it in complexity ?
Many "optimisations" are proposed in the litterature often based
on the LR(k), LL(k) family of parser construction, possibly with some
static factoring of these constructions (Earley has no static
factoring). It could actually be applied to all known techniques,
including the old precedence parsers. I put "optimization" between
quotes because it usually not clear what you are optimizing, or even
whether you are actually optimizing it, or whether the benefit of the
improvement is worth the added complexity of your parser. You will
find little objective data, formal or experimental, on this (there is
some), but many more claims. I am not saying that there is nothing of
interest. There are some smart ideas.
Now, once you know the basic idea, the "optimizations" or improvement
can often be introduced statically (possibly incrementally) by
constructing a push-down automaton from the grammar, following the
kind of parser construction technique you are interested in, and then
applying the cross-product construction for intersection to that
automaton (nearly the same thing as doing it to the grammar) or to a
grammar derived from that automaton.
Then you can introduce bells and whistles, but that is mostly
The Philosophiæ Naturalis Principia Mathematica of Isaac Newton is
reportedly a great piece of physics and mathematics. I do not think it
is on the reading list of many students. All other things being equal,
I do not think it is very useful to teach Earley's algorithm, though
it is an important historical piece. Students have enough to learn as
it is. At the risk of being shot down by many people, I think much the
same for the Knuth LR(k) paper. It is a superb piece of theoretical
analysis, and probably an important reading for a theoretician. I
strongly doubt that it is so essential for the building of parsers
given the current state of the technology, both hardware and
software. The times are past when parsing was a significant part of
compiling time, or when the speed of compilers was a critical issue (I
knew one corporation that died of compiling costs some 30 years
ago). The parsing specialist may want to learn that specialized
knowledge at some point, but the average student in computer science,
programming or engineering does not need it.
If students must spend more time on parsing, there are other
extensions that might be more useful and more formative, such as those
used in computational linguistics. The first role of teaching is to
extract the simple ideas that structure scientific knowledge, not to
force the students to suffer what the research scientists had to
suffer (doctoral students excepted: it is a rite of passage :-).
License CC BY-SA 3.0 from the author