25
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Does it have to be an algorithm based on Earley parsing, or would you not mind using a different general CFG parser? $\endgroup$ – Alex ten Brink Jul 14 '11 at 9:34
  • 1
    $\begingroup$ 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. $\endgroup$ – templatetypedef Jul 14 '11 at 17:18
  • $\begingroup$ 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. $\endgroup$ – Raphael Oct 27 '11 at 16:58
  • 3
    $\begingroup$ @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. $\endgroup$ – babou Jun 13 '13 at 11:10
  • $\begingroup$ You might want to look at Marpa. It's a Perl module and C library that implements an Earley parser and has full parse forest support. $\endgroup$ – hippietrail Sep 19 '14 at 14:41
14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the reference! This looks like a great resource and I'm going to spend some time looking over it. $\endgroup$ – templatetypedef Jul 15 '11 at 5:22
8
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – D.W. Jun 14 '13 at 6:45
  • 1
    $\begingroup$ See web.archive.org/web/20130508170633/http://thor.info.uaic.ro/…: "SPPF-Style Parsing From Earley Recognisers", Elizabeth Scott. Another link: dinhe.net/~aredridel/.notmine/PDFs/…. $\endgroup$ – a3nm May 20 '14 at 21:27
  • $\begingroup$ This is the correct answer to the question "how to get a parse forest from an Earley recogniser". $\endgroup$ – tjvr Feb 22 '16 at 20:47
  • $\begingroup$ There's a nice implementation of this in JS here: joshuagrams.github.io/pep $\endgroup$ – tjvr Feb 17 '17 at 12:39
6
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ "Earley ... is far too complicated for teaching, and could be replaced by simpler algorithms ...". Could you provide an example of such a simpler algorithm? $\endgroup$ – wjl Jul 5 '13 at 22:08
  • $\begingroup$ @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. $\endgroup$ – babou Jul 7 '13 at 10:43
  • $\begingroup$ @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 of the initial question. $\endgroup$ – babou Jul 9 '13 at 20:20
  • $\begingroup$ 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. $\endgroup$ – wjl Jul 9 '13 at 21:02
  • $\begingroup$ @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 . - - $\endgroup$ – babou Jul 10 '13 at 8:45
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – babou Feb 22 '14 at 0:05
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.