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.
Asked By : bngschmnd
Answered By : InformedA
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/33227
0 comments:
Post a Comment
Let us know your responses and feedback