Recovering a parse forest from an Earley parser? 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(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 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!
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.