Is this CYK parser result correct?
source link: https://stackoverflow.com/questions/10700289/is-this-cyk-parser-result-correct/70297684
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Is this CYK parser result correct?
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']
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.
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:
Your Answer
Post as a guest
Required, but never shown
By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy
Not the answer you're looking for? Browse other questions tagged nlp compiler-construction dynamic-programming chomsky-normal-form cyk or ask your own question.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK