<p>There is a paper that describes how to do it:</p>

<p><strong><a href="https://web.archive.org/web/20130508170633/http://thor.info.uaic.ro/~grigoras/diplome/5.pdf" rel="nofollow">SPPF-style parsing from Earley Recognisers</a></strong> by Elisabeth Scott</p>

<p>It describes how to build a binarized parse forest in cubic time.</p>

CC BY-SA 3.0
2013-06-14T06:45:09.400Z
That link seems to now be broken now.  Do you have a reference (paper title, where published, list of authors) and/or an updated link?
D.W.
CC BY-SA 3.0
2014-05-20T21:27:08.030Z
See https://web.archive.org/web/20130508170633/http://thor.info.uaic.ro/~grigoras/diplome/5.pdf: "SPPF-Style Parsing From Earley Recognisers", Elizabeth Scott. Another link: http://dinhe.net/~aredridel/.notmine/PDFs/SPPF-Style%20Parsing%20From%20Earley%20Recognizers.pdf.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2016-02-22T20:47:49.517Z
This is the correct answer to the question "how to get a parse forest from an Earley recogniser".
tjvr
CC BY-SA 3.0
2017-02-17T12:39:37.037Z
There's a nice implementation of this in JS here: https://joshuagrams.github.io/pep/
tjvr
CC BY-SA 4.0
2019-09-23T10:57:35.787Z
What is meant by binarized in this context?
Bruce Adams
CC BY-SA 4.0
2023-11-26T16:32:04.577Z
Each packed node (the nodes that represent multiple parses of the same non-terminal nodes) has exactly one or two children. If a non-terminal expands to more than two sub-trees, the right child is represented with an intermediate node (a representation of a partial parse using a slot and left and right extent), so each child of a non-terminal is added left-to-right individually, so you avoid a (potentially) exponential tree.
Todd O'Bryan
CC BY-SA 4.0
2023-11-26T16:34:52.063Z
What is interesting is that in a later paper by Scott, et al, they found that binarizing the tree was actually less efficient than not. The paper is GLL Parsing with Flexible Combinators, by Binsbergen, Scott, and Johnstone. https://ir.cwi.nl/pub/29666/29666.pdf
Todd O'Bryan
CC BY-SA 3.0
2011-10-27T09:08:24.823Z
2016-02-24T13:00:42.530Z
2016-02-24T13:00:42.530Z
Angelo Borsotti
<p>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.</p>

<p>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 ?</p>

<p>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.</p>

<p>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.</p>

<p>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). </p>

<hr>

<p><strong>Complement following a request in a comment</strong> (july 7, 2013)</p>

<p>This complement concnerns the existence of simpler algorithms than Earley's.</p>

<p>As I said, searching the web at "parsing intersection forest" should
quickly give you references, from which you can dig further.</p>

<p>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).</p>

<p>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).</p>

<p>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
the end.</p>

<p>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.</p>

<p>Top-down techniques (such as LR(k) based ones) will avoid unreachable
rules and non-terminals, but will create unproductive ones.</p>

<p>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.</p>

<p>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 ?</p>

<p>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.</p>

<p>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.</p>

<p>Then you can introduce bells and whistles, but that is mostly
technological details.</p>

<p>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.</p>

<p>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 :-).</p>

<p><a href="http://creativecommons.org/licenses/by-sa/3.0/" rel="noreferrer">License CC BY-SA 3.0 from the author</a></p>

CC BY-SA 3.0
2013-07-05T22:08:30.287Z
"Earley ... is far too complicated for teaching, and could be replaced by simpler algorithms ...". Could you provide an example of such a simpler algorithm?
wjl
CC BY-SA 3.0
2013-07-07T10:43:19.037Z
@wjl I reply to you in an addendum to the answer above. I do not point to
a specific algorithm though you may find some in the litterature if
you do some search as I recommend. I rather tried to explain why it is
very easy to make simpler, yet efficient algorithms. Earley's is
probably the most complex of them all. Explaining the Bar Hillel et
al. construction is about half a page of textbook, say a page with the
proof.
babou
CC BY-SA 3.0
2013-07-09T20:20:55.370Z
@wjl 
Answering your request did take me some time. Did it help you ?
. . . . . If you
wanted an actual algorithm, there is one in the [last link](http://www.aclweb.org/anthology-new/P/P89/P89-1018.pdf) of the
initial question.
babou
CC BY-SA 3.0
2013-07-09T21:02:46.587Z
Yes, thank you; I appreciate the extra detail. I am working on a generalized parser library for some work that I am doing and have been doing a ton of research into different algorithms. I am currently leaning towards an Early-style implementation since, to me, it seemed to be a very easy to understand algorithm, and it is easy to extend to conjunctive grammars and "black box" (possibly context sensitive) terminals. I skimmed and printed out some of the papers that you pointed to; but I have not read them in earnest yet.
wjl
CC BY-SA 3.0
2013-07-10T08:45:58.447Z
@wjl If that is what you are doing, you should look at the following
topics: mildly context sensitive languages, linear context-free
rewriting systems (LCFRS), and range concatenation grammars. Not sure
I understand what is a "black box" terminal. - -
email: babou at inbox.com . - -
babou
CC BY-SA 3.0
2013-07-10T22:59:03.017Z
Thanks for the pointers of other things to check out. I have read up on midly context sensitive grammars a bit, but not the other two topics specifically. I mean "black-box" terminals in the sense that they are terminals which are implemented in an unknown way using a method (e.g. native code) outside of the parsing algorithm's control, e.g. as described in "Semantics and Algorithms for Data-dependent Grammars" http://www.cs.princeton.edu/~dpw/papers/ddg-tr.pdf
wjl
CC BY-SA 3.0
2013-06-13T11:03:36.960Z
2013-07-07T10:41:58.970Z
2013-07-07T10:41:58.970Z
babou
<p>The paper that describes how to build a binarized parse forest in cubic time (mentioned in the post by Angelo Borsotti) is: "SPPF-Style Parsing From Earley Recognizers" by Elizabeth Scott. You can find it here: <a href="http://dx.doi.org/10.1016/j.entcs.2008.03.044" rel="noreferrer">http://dx.doi.org/10.1016/j.entcs.2008.03.044</a></p>

<p>In this paper the construction of a shared packed parse forest (SPPF) is described which represents all the possible parse trees. Sub trees are shared whenever possible, and nodes corresponding to different derivations of the same substring from the same nonterminal are combined.</p>

CC BY-SA 3.0
2014-02-22T00:05:37.393Z
Thanks for the pointer. Building binarized parse-forests in cubic time
is standard. Binarization is the only way to get cubic time, so that
the OP's remark on complexity w.r.t. grammar size is
irrelevant. Another issue is to understand in what way the
parse-forest is binarized. That may be algorithm dependent. Other
issues are the amount of sharing in the shared-forest, and practical
efficiency of the parsing strategy (Earley may be a bad idea). All
this is developped in the OP's last reference. A general formal view
of the issue is sketched in my answer.
babou
CC BY-SA 3.0
2014-02-12T17:33:22.403Z
2014-02-12T17:33:22.403Z
eider
<p>I'd like to echo the answers above by suggesting you read this paper:</p>
<blockquote>
<p><a href="http://dx.doi.org/10.1016/j.entcs.2008.03.044" rel="nofollow noreferrer">http://dx.doi.org/10.1016/j.entcs.2008.03.044</a></p>
</blockquote>
<p>I would like to qualify though by saying that I have implemented the algorithm in this paper and I believe there is an error. In particular, the first sentence of the second paragraph of section 4. The predecessor labels that you make for what Earley would calle the &quot;scanning&quot; phase should point from p to q and not the other way around.</p>
<p>In particular, the following line:</p>
<blockquote>
<p>Set E0 to be the items (S ::= ·α, 0). For i &gt; 0 initialise Ei by adding the item
p = (A ::= αai · β, j) for each q = (A ::= α · aiβ, j) ∈ Ei−1 and, if α = , creating a
predecessor pointer labelled i − 1 from q to p</p>
</blockquote>
<p>Should read &quot;from p to q&quot; and not &quot;from q to p&quot;</p>
<p>I implemented the algorithm as it is originally stated, which gave me errors on some hand-built test cases, which were fixed once I changed the direction of the pointer here.</p>
<p>EDIT Nov 2020: I ended up writing my undergraduate thesis on practical and efficient methods for extracting ranked parses from the Earley parser. It builds off the work I cited above.</p>
<p>You can read it at this link <a href="https://github.com/jcd2020/Thesis" rel="nofollow noreferrer">https://github.com/jcd2020/Thesis</a></p>

CC BY-SA 4.0
2018-06-12T18:10:07.797Z
2020-11-16T16:58:44.590Z
2020-11-16T16:58:44.590Z
Jeremy Dohmann
<p>Doing that would of course depend on the right representation for a "packed forest" that represents all parse trees for a given sentence.</p>

<p>I think the place you want to start looking is at Joshua Goodman's thesis (parsing inside out, Harvard, 1999). Basically, the idea is that you can define a parsing algorithm under a certain semiring. Depending on the semiring, you would be able to calculate all kind of quantities and structures instead of the bare parse tree (as a recognizer or as a parser). One semiring that you could define (which Goodman does in his thesis) is a semiring where the values are sets of parses. When you eventually finish parsing a sentence, you'd get all parse trees in the main parse node.</p>

<p>Again, you have to be careful about making it possible through the right representation.</p>

CC BY-SA 3.0
2011-07-15T05:22:23.753Z
Thanks for the reference!  This looks like a great resource and I'm going to spend some time looking over it.
templatetypedef
CC BY-SA 3.0
2011-07-14T06:39:33.910Z
2011-07-14T06:39:33.910Z
gmmodeler
<p>I was recently reading up on the <a href="http://en.wikipedia.org/wiki/Earley_parser">Earley parser</a> and think it's one of the most elegant algorithms I've seen to date.  However, the algorithm in its traditional sense is a <em>recognizer</em> and not a <em>parser,</em> meaning that it can detect whether a string matches a particular CFG but not produce a parse tree for it.  My question is how to recover not a parse <em>tree</em>, but rather the parse <em>forest</em> of all possible parses of the given input string.</p>

<p>In Grune and Jacob's "Parsing Techniques: A Practical Guide" they illustrate an algorithm that can be used to recover a parse forest from the result of the Earley recognizer, but it is based on Unger's parsing method, whose runtime is O(n<sup>k + 1</sup>), where k is the length of the longest production in the grammar.  This means that the runtime is not a polynomial in the size of the grammar.  Moreover, Earley's original paper on the algorithm, which suggests an algorithm for recovering parse forests, is incorrect (see, for example, page 762 of <a href="http://www.google.com/url?sa=t&amp;source=web&amp;cd=1&amp;ved=0CB0QFjAA&amp;url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.80.5070&amp;rep=rep1&amp;type=pdf&amp;rct=j&amp;q=tomita%20efficient%20parsing%20for%20natural%20language&amp;ei=PEIeTvORBIXmiAK_2uS0Aw&amp;usg=AFQjCNFdGbsgtPgMYS0KII9nCTfTq8_hFg&amp;sig2=71GyjE-ZqEXrWUJ6NV9HIQ&amp;cad=rja">this article</a> by Tomita), although many sources still cite it as the appropriate way to recover the parse forest.</p>

<p>My question is whether it is possible, in polynomial time, to recover a parse forest for a given input string.  I have found a paper <a href="http://www.aclweb.org/anthology-new/P/P89/P89-1018.pdf">here</a> that provides an algorithm for producing cubic-size parse forest representations for any parse using a simulation of a PDA, so this seems like it should be possible, but I have yet to find any way to do this.  Ideally, I'd like to do this without converting the input grammar to CNF (which would indeed solve the problem), since the resulting parse forest would be pretty messy.</p>

<p>Thanks for any help you can offer!</p>

CC BY-SA 3.0
2011-07-14T09:34:37.957Z
Does it have to be an algorithm based on Earley parsing, or would you not mind using a different general CFG parser?
Alex ten Brink
CC BY-SA 3.0
2011-07-14T17:18:34.700Z
I would prefer an algorithm based on the Earley parser.  I've been teaching a compilers course and spent a few days trying to track down an answer to this question, and it's really bugging me.
templatetypedef
CC BY-SA 3.0
2011-10-27T16:58:19.463Z
Exponential runtimes are not surprising as words can have exponentially many parse trees. In fact, they can even have infinitely many if you allow arbitrary CFGs.
Raphael
CC BY-SA 3.0
2013-06-13T11:10:22.423Z
@Raphael The role of parse forests is precisely to have a sharing mechanism that will allow representing all the trees, even infinitely many, with a finite structure, with small space complexity. Of course, this may leave some work for lumberjacks.
babou
CC BY-SA 3.0
2014-09-19T14:41:20.307Z
You might want to look at [Marpa](https://metacpan.org/pod/Marpa::R2). It's a Perl module and C library that implements an Earley parser and has full parse forest support.
hippietrail
CC BY-SA 3.0
2016-09-05T09:13:20.867Z
Note that the author was looking for something more refined than a simple understanding of the algorithm. Also, posting on 5 year old threads that have already been answered rarely holds any merit. For more guidelines on how you can contribute to the site, check the [help center](http://cstheory.stackexchange.com/help).
chazisop
CC BY-SA 3.0
2016-09-05T09:13:45.010Z
While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference.  Link-only answers can become invalid if the linked page changes. - [From Review](/review/low-quality-posts/16843)
chazisop
<fl.formal-languages><parsing>
Recovering a parse forest from an Earley parser?
templatetypedef
# Recovering a parse forest from an Earley parser?

(Asked by: username_0 on 2011-07-14)

I was recently reading up on the [Earley parser](http://en.wikipedia.org/wiki/Earley_parser) and think it's one of the most elegant algorithms I've seen to date. However, the algorithm in its traditional sense is a *recognizer* and not a *parser,* meaning that it can detect whether a string matches a particular CFG but not produce a parse tree for it. My question is how to recover not a parse *tree*, but rather the parse *forest* of all possible parses of the given input string.

In Grune and Jacob's "Parsing Techniques: A Practical Guide" they illustrate an algorithm that can be used to recover a parse forest from the result of the Earley recognizer, but it is based on Unger's parsing method, whose runtime is O(nk + 1), where k is the length of the longest production in the grammar. This means that the runtime is not a polynomial in the size of the grammar. Moreover, Earley's original paper on the algorithm, which suggests an algorithm for recovering parse forests, is incorrect (see, for example, page 762 of [this article](http://www.google.com/url?sa=t&source=web&cd=1&ved=0CB0QFjAA&url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.80.5070&rep=rep1&type=pdf&rct=j&q=tomita%20efficient%20parsing%20for%20natural%20language&ei=PEIeTvORBIXmiAK_2uS0Aw&usg=AFQjCNFdGbsgtPgMYS0KII9nCTfTq8_hFg&sig2=71GyjE-ZqEXrWUJ6NV9HIQ&cad=rja) by Tomita), although many sources still cite it as the appropriate way to recover the parse forest.

My question is whether it is possible, in polynomial time, to recover a parse forest for a given input string. I have found a paper [here](http://www.aclweb.org/anthology-new/P/P89/P89-1018.pdf) that provides an algorithm for producing cubic-size parse forest representations for any parse using a simulation of a PDA, so this seems like it should be possible, but I have yet to find any way to do this. Ideally, I'd like to do this without converting the input grammar to CNF (which would indeed solve the problem), since the resulting parse forest would be pretty messy.

Thanks for any help you can offer!

**Tags:** fl.formal-languages, parsing

> **Comments:**
> **username_1**: Does it have to be an algorithm based on Earley parsing, or would you not mind using a different general CFG parser?  
> **username_0**: I would prefer an algorithm based on the Earley parser.  I've been teaching a compilers course and spent a few days trying to track down an answer to this question, and it's really bugging me.  
> **username_2**: Exponential runtimes are not surprising as words can have exponentially many parse trees. In fact, they can even have infinitely many if you allow arbitrary CFGs.  
> **username_3**: @username_2 The role of parse forests is precisely to have a sharing mechanism that will allow representing all the trees, even infinitely many, with a finite structure, with small space complexity. Of course, this may leave some work for lumberjacks.  
> **username_4**: You might want to look at [Marpa](https://metacpan.org/pod/Marpa::R2). It's a Perl module and C library that implements an Earley parser and has full parse forest support.  
> **username_5**: Note that the author was looking for something more refined than a simple understanding of the algorithm. Also, posting on 5 year old threads that have already been answered rarely holds any merit. For more guidelines on how you can contribute to the site, check the [help center](http://cstheory.stackexchange.com/help).  
> **username_5**: While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference.  Link-only answers can become invalid if the linked page changes. - [From Review](/review/low-quality-posts/16843)  

---

## 5 answers

### Answer by username_15 on 2011-07-14. Score: 16 | Accepted answer

Doing that would of course depend on the right representation for a "packed forest" that represents all parse trees for a given sentence.

I think the place you want to start looking is at Joshua Goodman's thesis (parsing inside out, Harvard, 1999). Basically, the idea is that you can define a parsing algorithm under a certain semiring. Depending on the semiring, you would be able to calculate all kind of quantities and structures instead of the bare parse tree (as a recognizer or as a parser). One semiring that you could define (which Goodman does in his thesis) is a semiring where the values are sets of parses. When you eventually finish parsing a sentence, you'd get all parse trees in the main parse node.

Again, you have to be careful about making it possible through the right representation.

> **Comments:**
> **username_0**: Thanks for the reference!  This looks like a great resource and I'm going to spend some time looking over it.  

---

### Answer by username_6 on 2011-10-27. Score: 11

There is a paper that describes how to do it:

**[SPPF-style parsing from Earley Recognisers](https://web.archive.org/web/20130508170633/http://thor.info.uaic.ro/~grigoras/diplome/5.pdf)** by Elisabeth Scott

It describes how to build a binarized parse forest in cubic time.

> **Comments:**
> **username_7**: That link seems to now be broken now.  Do you have a reference (paper title, where published, list of authors) and/or an updated link?  
> **username_8**: See https://web.archive.org/web/20130508170633/http://thor.info.uaic.ro/~grigoras/diplome/5.pdf: "SPPF-Style Parsing From Earley Recognisers", Elizabeth Scott. Another link: http://dinhe.net/~aredridel/.notmine/PDFs/SPPF-Style%20Parsing%20From%20Earley%20Recognizers.pdf.  
> **username_9**: This is the correct answer to the question "how to get a parse forest from an Earley recogniser".  
> **username_9**: There's a nice implementation of this in JS here: https://joshuagrams.github.io/pep/  
> **username_10**: What is meant by binarized in this context?  
> **username_11**: Each packed node (the nodes that represent multiple parses of the same non-terminal nodes) has exactly one or two children. If a non-terminal expands to more than two sub-trees, the right child is represented with an intermediate node (a representation of a partial parse using a slot and left and right extent), so each child of a non-terminal is added left-to-right individually, so you avoid a (potentially) exponential tree.  
> **username_11**: What is interesting is that in a later paper by Scott, et al, they found that binarizing the tree was actually less efficient than not. The paper is GLL Parsing with Flexible Combinators, by Binsbergen, Scott, and Johnstone. https://ir.cwi.nl/pub/29666/29666.pdf  

---

### Answer by username_3 on 2013-06-13. Score: 7

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
the end.

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
technological details.

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](http://creativecommons.org/licenses/by-sa/3.0/)

> **Comments:**
> **username_12**: "Earley ... is far too complicated for teaching, and could be replaced by simpler algorithms ...". Could you provide an example of such a simpler algorithm?  
> **username_3**: @username_12 I reply to you in an addendum to the answer above. I do not point to a specific algorithm though you may find some in the litterature if you do some search as I recommend. I rather tried to explain why it is very easy to make simpler, yet efficient algorithms. Earley's is probably the most complex of them all. Explaining the Bar Hillel et al. construction is about half a page of textbook, say a page with the proof.  
> **username_3**: @username_12  Answering your request did take me some time. Did it help you ? . . . . . If you wanted an actual algorithm, there is one in the [last link](http://www.aclweb.org/anthology-new/P/P89/P89-1018.pdf) of the initial question.  
> **username_12**: Yes, thank you; I appreciate the extra detail. I am working on a generalized parser library for some work that I am doing and have been doing a ton of research into different algorithms. I am currently leaning towards an Early-style implementation since, to me, it seemed to be a very easy to understand algorithm, and it is easy to extend to conjunctive grammars and "black box" (possibly context sensitive) terminals. I skimmed and printed out some of the papers that you pointed to; but I have not read them in earnest yet.  
> **username_3**: @username_12 If that is what you are doing, you should look at the following topics: mildly context sensitive languages, linear context-free rewriting systems (LCFRS), and range concatenation grammars. Not sure I understand what is a "black box" terminal. - - email: username_3 at inbox.com . - -  
> **username_12**: Thanks for the pointers of other things to check out. I have read up on midly context sensitive grammars a bit, but not the other two topics specifically. I mean "black-box" terminals in the sense that they are terminals which are implemented in an unknown way using a method (e.g. native code) outside of the parsing algorithm's control, e.g. as described in "Semantics and Algorithms for Data-dependent Grammars" http://www.cs.princeton.edu/~dpw/papers/ddg-tr.pdf  

---

### Answer by username_13 on 2014-02-12. Score: 6

The paper that describes how to build a binarized parse forest in cubic time (mentioned in the post by username_6) is: "SPPF-Style Parsing From Earley Recognizers" by Elizabeth Scott. You can find it here: <http://dx.doi.org/10.1016/j.entcs.2008.03.044>

In this paper the construction of a shared packed parse forest (SPPF) is described which represents all the possible parse trees. Sub trees are shared whenever possible, and nodes corresponding to different derivations of the same substring from the same nonterminal are combined.

> **Comments:**
> **username_3**: Thanks for the pointer. Building binarized parse-forests in cubic time is standard. Binarization is the only way to get cubic time, so that the OP's remark on complexity w.r.t. grammar size is irrelevant. Another issue is to understand in what way the parse-forest is binarized. That may be algorithm dependent. Other issues are the amount of sharing in the shared-forest, and practical efficiency of the parsing strategy (Earley may be a bad idea). All this is developped in the OP's last reference. A general formal view of the issue is sketched in my answer.  

---

### Answer by username_14 on 2018-06-12. Score: 2

I'd like to echo the answers above by suggesting you read this paper:

> <http://dx.doi.org/10.1016/j.entcs.2008.03.044>

I would like to qualify though by saying that I have implemented the algorithm in this paper and I believe there is an error. In particular, the first sentence of the second paragraph of section 4. The predecessor labels that you make for what Earley would calle the "scanning" phase should point from p to q and not the other way around.

In particular, the following line:

> Set E0 to be the items (S ::= ·α, 0). For i > 0 initialise Ei by adding the item
> p = (A ::= αai · β, j) for each q = (A ::= α · aiβ, j) ∈ Ei−1 and, if α = , creating a
> predecessor pointer labelled i − 1 from q to p

Should read "from p to q" and not "from q to p"

I implemented the algorithm as it is originally stated, which gave me errors on some hand-built test cases, which were fixed once I changed the direction of the pointer here.

EDIT Nov 2020: I ended up writing my undergraduate thesis on practical and efficient methods for extracting ranked parses from the Earley parser. It builds off the work I cited above.

You can read it at this link <https://github.com/jcd2020/Thesis>


---

