# How does the Earley Parser store possible parses of an ambiguous sentence?

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.

• What is a chart, according to you. Afaik chart parsing uses only a single chart, whatever the details of the algorithm. So how could the result, the parse trees, be stored in two charts. – babou Nov 18 '14 at 10:04

This is an example of what the graphical chart looks like when there are n tokens in the string:

$\begin{array}{} [1,1] & [1,2] & [1,3] & \cdots & [1,n] \\ & [2,2] & [2,3] & \cdots & [2,n] \\ & & [3,3] & \cdots & [3,n] \\ & & & \ddots & \vdots \\ & & & & [n,n] \end{array}$

Because $S$ is the root of the grammar, the two parses of $S$ will be stored in the $[1,n]$ cell of the chart. Here as you can already guess, $[i,j]$ stands for the position indices of the parses, in other word, the span.

In case of $S$, the positions span the whole string. If the positions do not span the whole string, what you have is a set of valid constituent parses in that span.

So the answer to your question is: Possible parses are stored in the same chart, they may be stored in different cells of the chart if their spans are different. If their spans are the same, they are stored in the same cell in the chart.

Btw, I think the first two rules in your grammar do not look right. Maybe you want

S -> NP VP and VP -> V NP instead.

• Would you agree that your answer is an abstract general answer that could apply to any chart parser? Actually you do not even mention the Earley parser in your answer. However, this presentation is not quite applicable to the Earley parser which is the only possible exception I know of. Earley parser does not quite fit that model as it does not exactly store valid constituents in these cells. – babou Nov 24 '14 at 23:11
• @babou I agree, thanks for pointing that out! – InformedA Nov 25 '14 at 6:54
• @babou Could you elaborate in what way the Earley parser does not fit this model? Its not immediately obvious. – Bruce Adams Sep 24 '19 at 23:14