Recovering a parse forest from an Earley parser?

Question

I was recently reading up on the 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(n^{k + 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 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 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!

Answer 1

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.

Answer 2

There is a paper that describes how to do it:

SPPF-style parsing from Earley Recognisers by Elisabeth Scott

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

Answer 3

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

Answer 4

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: 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.

Answer 5

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