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.

  • $\begingroup$ 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. $\endgroup$
    – babou
    Nov 18, 2014 at 10:04

1 Answer 1


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.

  • $\begingroup$ 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. $\endgroup$
    – babou
    Nov 24, 2014 at 23:11
  • $\begingroup$ @babou I agree, thanks for pointing that out! $\endgroup$
    – InformedA
    Nov 25, 2014 at 6:54
  • $\begingroup$ @babou Could you elaborate in what way the Earley parser does not fit this model? Its not immediately obvious. $\endgroup$ Sep 24, 2019 at 23:14

Your Answer

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

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