Ist dieses CYK-Parser-Ergebnis korrekt?

Question

Ich versuche das zu lernen CYK-Parsing-Algorithmus.

Sind die resultierenden Tabellen für diesen Satz von Grammatikregeln für die beiden angegebenen Sätze korrekt?

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']

Answer 1

Sie können zunächst versuchen, Ihre Grammatik zu minimieren, da es einige unnötige Regeln gibt und das auch der Grund dafür ist not in CNF.

Wenn Sie es genauer betrachten, haben Sie es zufällig getan None im ersten Beispiel, zweite Zeile, zweite Spalte.Dort ist es tatsächlich möglich, eine zu haben S, aber da die Logik in CYK keine weiteren Optimierungen durchführen kann, wie z NP->NN.Von dort S -> NP VP für das erwähnte None Zelle geht verloren.Da CYK nicht in der Lage ist, diese durchzuführen, Die Grammatik muss in CNF vorliegen.Im Grunde ist es also ungefähr so, als würden Sie versuchen, einen C-Compiler auf ein C++-Programm anzuwenden (ohne C++-Bibliotheken).Und du hast es geschafft glücklich um überhaupt an der Spitze das richtige Ergebnis zu erzielen.

Vor diesem Hintergrund werde ich mich nicht auf Ihr zweites Beispiel einlassen.

Zur Verdeutlichung ist eine Grammatik enthalten CNF wenn es Regeln hat nur dieser beiden Formen:

S -> AB
A -> a

also eindeutig so etwas wie NP -> NN ist nicht in CNF.