Is this CYK parser result correct?

Question

I am trying to learn the CYK parsing algorithm.

For this set of grammar rules, are the resulting tables correct for the two given sentences?

S -> NP VP
VP -> VB NP
NP -> DT NN
PP -> IN NP
NP -> NP PP
NP -> NN
VP -> VP PP
IN -> with
NN -> dog
NN -> cat
VB -> ate
NN -> mouse
DT -> the


['S']
[None, None]
[None, None, 'VP']
['NP', None, None, 'NP']
['DT', 'NN', 'VB', 'DT', 'NN']
['the', 'cat', 'ate', 'the', 'dog']


['S']
['NP', None]
['NP', None, 'VP']
['NP', None, None, 'NP']
[None, None, 'VP', None, None]
[None, None, 'VP', None, None, 'PP']
['NP', None, None, 'NP', None, None, 'NP']
['DT', 'NN', 'VB', 'DT', 'NN', 'IN', 'DT', 'NN']
['the', 'cat', 'ate', 'the', 'dog', 'with', 'the', 'cat']

Dimitar · Accepted Answer · 2016-07-26T08:00:44.003

1

You can try to minimize your grammar first, because there are some unnecessary rules and furthermore that's why it is not in CNF.

Looking at it more concisely, you happen to have None on the first example, second row, second column. There it is actually possible to have a S, but since the logic in CYK cannot do further optimizations such as NP->NN. From there S -> NP VP for the mentioned None cell goes missing. Because of CYK's inability to perform those, the grammar must be in CNF. So, basically it is roughly like you are trying to apply a C-compiler on a C++ programm (with no C++ libraries). And you got lucky to even get the right result at the top.

With that being said, I am not going to indulge in the second example of yours.

Just to clarify, a grammar is in CNF if it has rules only of these two forms:

S -> AB
A -> a

so clearly something like NP -> NN is not in CNF.

edited Jul 26 '16 at 08:00

answered Jul 18 '16 at 10:19

Dimitar

4,402
4
31
47

...thanks for answering my question, it's been 4 years and I'm glad I finally got an answer to it, and cleared it up for me. I'm glad I asked that question because I read your answer and it just clicked... Why do you think it's not worth upvoting, could I have asked it better? – Eric Jul 26 '16 at 01:50
You have not transformed it in `CNF` and the algorithm can't do its job properly, that's why. But after all, this what questions are all about. I am really glad that it cleared itself to you, even though late. – Dimitar Jul 26 '16 at 07:54

Sandipan Dey · Answer 2 · 2021-12-10T12:11:32.337

Although the given grammar is not in Chomosky normal form, we can easily convert it to CNF like the following one (e.g., get rid of the illegal production NP -> NN and augment the grammar with additional rules):

S -> NP VP
S -> NN VP
VP -> VB NP
VP -> VB NN
NP -> DT NN
PP -> IN NP
PP -> IN NN
NP -> NP PP
NP -> NN PP
VP -> VP PP
IN -> with
NN -> dog
NN -> cat
VB -> ate
NN -> mouse
DT -> the

With the grammar modified to the above one the DP table with CYK algorithm (refer to the implementation here, although it assumes each symbol in the grammar to be a single character in length, but can easily be extended) will be like the following one, for the first sentence:

It will have the following parse tree:

with the 2nd sentence, the following animation shows the DP table generated,

with the following parse tree:

Is this CYK parser result correct?

2 Answers2