7

I've got a pretty basic question concerning the Earley parser: In case of syntactic ambiguity ( S -> NP VP(V NP(NP PP)) vs. S -> NP VP(VP((V NP) PP) ), are both parses stored in one chart or in two?

the grammar im talking about is the following: S -> VP NP VP -> V VP VP -> VP PP NP -> NP PP NP -> Det N PP -> P NP so you while parsing could either attach a PP to an NP or to an VP.

my question is detail is how the graphical chart would look like, meaning the positions of predict, scan and complete. I was assuming that both parses would be stored in one (big) chart. So S' will then be found in, let's say, s[0][8] and s[0][16] ? Is that right? An attached image or link with a graphical chart parsing through an ambigous sentence would help.

greetings

Improve this question
5
  • possible duplicate of linguistics.stackexchange.com/questions/4619/…?
    – prash ♦
    Nov 16, 2014 at 22:30
  • Can you draw somewhere the trees corresponding to your two examples of parse-tree?
    – babou
    Nov 17, 2014 at 14:59
  • the tree would look be similiar to this directupload.net/file/d/3804/8wr3dqog_png.htm
    – bngschmnd
    Nov 17, 2014 at 15:04
  • Thanks for the trees. BTW, you are not supposed to crosspost your questions. If you expect a better answer from CS, you should flag your question and ask to have it migrated to CS. There is also the risk that it will be considered duplicate on CS, as there was a prior question on this topic, which I refer to in my answer.
    – babou
    Nov 17, 2014 at 15:24
  • Your trees should be represented as: S(NP VP(V NP(NP PP))) and S(NP VP(VP(V NP) PP)) . Even assuming there is a reason for differentiating the top symbol S, you have one open parenthesis too many in the second example.
    – babou
    Nov 17, 2014 at 15:50

1 Answer 1

Reset to default
5

Earley parser is one example of chart parser, also called dynamic programming parser. There are many other kinds such as the CYK parser, the GLR and GLL parser, and more.

The whole point of chart parsing is to build a unique chart that will mimic all possible parsing computations, since there may be exponentially many (or even infinitely many in pathological cases). It is organized so that parts of computations that are common to distinct parses are somehow shared. This is so effective that the whole computation is done in cubic time at worst.

The basic chart parser is a recognizer. However the chart can incorporate a structure that also keep track of the corresponding parse trees, or more precisely of all parse-trees corresponding to these computations.

This structure for the parses trees tries to share common subparts (as the chart does for parsing computation), so that exponentially many parse trees can actually be represented in a unique structure that has a cubic size.

So, if I understand your question correctly, the answer is that the two parse-trees (or as many as there are) are all stored in the same structure associated to the unique chart.

Such a structure is often called a shared forest, but its organization can vary a bit, depending on the specific algorithm. The structure used by Earley's algorithms is not too easy to understand.

For more information, I suggest you look at the question: Is there a favoured data structure for storing ambiguous parse trees in Natural Language Processing?

For a detailed intuitive explanation of how sharing is organized to get an a possibly exponential (or even infinite) number of trees in a cubic structure, you may look at the first 6 pages of this 1991 paper by Lang. It does contain some simple examples. There are other papers on the web with such examples (I could copy some here, if really needed ... but since they are available with comments ...). One important point to keep in mind is that those diagram give you the a kind of purified version of the basic mechanism. It may be a lot more confused in actual parsers because this is encoded and interacting with the specific parsing process (This is the case for the Earley parser). But describing that is usually much too technical. I discuss a bit, about Earley's parser, in an answer to a question on another SE site: How do I reconstruct the forest of syntax trees from the Earley vector?

Getting an infinite number of trees in a cubic structure should not be too surprising. After all, CF grammar can be pretty small and still represent an infinite number of trees.

I would have tried to show sharing of subparts in your example, but I do not understand your notation. May be you can explain it: I could not draw trees from what you wrote. What is the + for? What does it mean to have an open parenthesis not preceded by a syntactic category?

Improve this answer
7
  • How exactly are the two parse trees stored in one chart? Can you maybe post an image of a chart with two parse trees integrated? I only found charts with one parse tree.
    – bngschmnd
    Nov 17, 2014 at 0:50
  • @bngschmnd I included a reference available on the web (you may have to register for free). It does contain examples. To understand how it is built by the parsing process, there are other papers.
    – babou
    Nov 17, 2014 at 12:20
  • @babobu: i edited my first post to make my question clearer.
    – bngschmnd
    Nov 17, 2014 at 13:37
  • @bngschmnd Your modified question is far too detailed in technicalities. First, Earley's parser is not presented graphically in the papers I read (those written by Earley himself). Another point is that these technical details do not matter very much. What is important is to understand the principles that make these techniques work. Teaching this algorithm is ill advised, because it is too much technical complexity for probably no benefit. Actually Earley himself does not say much about keeping the parse trees. Did you look at the references I gave you? Can you answer your question for CYK.
    – babou
    Nov 17, 2014 at 14:11
  • 1
    @bngschmnd Earley parser works pretty much the same as CKY. When a prefix part of a RHS has been recognized, it stores that in the chart, and keeps back-pointers in some form to the the subcomponents it used to do the completion. It is essentially the completer that builds the tree (as I remember). I say a bit more in the reference I added at the end of my answer. CKY is a chart parser, and they all more or less work on the same principes (up to details and optimizations). But most parsers use structures that less intricate than for Earley, because they use only binary grammars (CNF is binary)
    – babou
    Nov 18, 2014 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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