Questo risultato del parrser cyk è corretto?

Question

Sto cercando di imparare il Cyk Parsing Algorithm .

Per questo set di regole grammaticali, sono le tabelle risultanti corrette per le due frasi fornite?

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

Puoi provare a minimizzare prima la tua grammatica, perché ci sono alcune regole non necessarie e inoltre è per questo che è not in CNF.

Guardandolo più conciso, ti capita di avere None sul primo esempio, seconda riga, seconda colonna. Lì è effettivamente possibile avere un S, ma poiché la logica in Cyk non può fare ulteriori ottimizzazioni come NP->NN. Da lì S -> NP VP per la cella None menzionata è mancata. A causa dell'incapacità di Cyk di eseguire quelle, La grammatica deve essere in CNF . Quindi, fondamentalmente è approssimativamente come stai cercando di applicare un compilatore C su un programma C ++ (con nessuna libreria C ++). E hai fortunato per ottenere anche il risultato giusto in alto.

Con questo detto, non ho intenzione di indulgere nel secondo tuo esempio.

Solo per chiarire, una grammatica è in CNF se ha regole solo di queste due forme:

.

S -> AB
A -> A

Così chiaramente qualcosa come NP -> NN non è in CNF.