Python - Как реализовать детерминированный алгоритм CYK без NLTK

Question

ПРИМЕЧАНИЕ. Для этого вопроса я не могу использовать импорт, кроме io и sys.

Для задания НЛП я должен создать программу, которая принимает файл грамматики и файл высказываний в качестве системных аргументов, что я и сделал.

Проблема в том, что я так запутался, как реализовать детерминированный алгоритм CYK, который выводит строку в виде расширенной нормальной формы Хомского (eCNF).

Я пытался реализовать класс Node, но у меня было много проблем с получением правильной формы. Я также нашел реализации вероятностных версий алгоритма CYK, но они просто смутили меня больше. Я не хочу никаких оценок вероятности.

Я попытался создать матрицу P[i][j] успешно, но она не получилась треугольной, и когда я заполнил ее словами в строке произнесения, она заняла только последнее слово в строке.

Это псевдокод, которому я пытаюсь следовать:

Set P to a (n+1) x (n+1) matrix
for j = 1 to Length(words) do
    for i = j-1 downto 0 do
        for each non-terminal N in G do
        P[i][j].NT[N] = empty array
for j = 1 to Length(words) do
    for each rule N -> words[j] in G do
    append (j, N -> words[j]) to P[j-1][j].NT[N]
change = true
    while change do
    change = false
    for each non-terminal N in G do
        if P[j-1][j].NT[N] is not empty and
       there is a rule N' -> N in G and
           (j, N' -> N) is not in P[j-1][j].NT[N'] then
            append (j, N' -> N) to P[j-1][j].NT[N']
        change = true
for j = 2 to Length(words) do
    for i = j-2 downto 0 do
    for k = i+1 to j-1 do
        for each rule N -> A B in G such that
       P[i][k].NT[A] is nonempty and
       P[k][j].NT[B] is nonempty do
            append (k, N -> A B) to P[i][j].NT[N]
    change = true
        while change do
        change = false
        for each non-terminal N in G do
            if P[i][j].NT[N] is not empty and
           there is a rule N' -> N in G and
               (j, N' -> N) is not in P[i][j].NT[N'] then
                append (j, N' -> N) to P[i][j].NT[N']
            change = true
return P

Вот два примера входных файлов:

грамматика

S -> NP VP 
NP -> Det N
NP -> PN
Det -> "the"
N -> "dog"
N -> "rat"
N -> "elephant"
PN -> "Alice" 
PN -> "Bob"
VP -> V NP
V -> "admired" 
V -> "bit"
V -> "chased"

Высказывания

the aardvark bit the dog
the dog bit the man
Bob killed Alice

Моя программа до сих пор может сказать, когда предложение может быть проанализировано, а когда нет. Теперь мне нужно взять высказывания, которые можно проанализировать, и разобрать их.

Вывод должен выглядеть следующим образом:

[S [NP [Det "the"] [N "man"]] [VP [V "shot"] [NP [Det "the"] [N "elephant"]]]]

Вот моя программа со всем удаленным кодом, вызывающим ошибки:

import sys
import io

# usage = python CKYdet.py g#.ecfg u#L.utt

# Command Line Arguments - argv[0], argv[1], argv[2]
script = sys.argv[0]
grammarFile = open(sys.argv[1])
utteranceFile = open(sys.argv[2])

# Parsing algorithm
def CKYparse(uttline):
    with open(sys.argv[1]) as rules:
        # The following two lines throw index out of bound error. Not sure I need to select grammar rules this way.
        # rhs = [line.split("-> ", 1)[1].strip('\n ') for line in rules]
        # lhs = [line.split(None, 1)[0] for line in rules]

        # Here I want to assign the words to their repective grammar rules
        #Then I need to add each word to the matrix according to the grammar
        #Then outpit the matrix with priper formatting

    return "Valid parse goes here!" # Temporary return value until parse matrix P can be returned

# Initialize arrays from grammarFile
ruleArray = []
wordsInQuotes = []

for line in grammarFile:
    rule = line.rstrip('\n')
    start = line.find('"') + 1
    end = line.find('"', start)
    ruleArray.append(rule)
    wordsInQuotes.append(line[start:end])    #create a set of words from grammar file


# Print final output
# Check whether line in utteranceFile can be parsed.
# If so, parse it.
# If not, print "No valid parse"
n = 0
for line in utteranceFile:
    uttline = line
    n = n + 1
    uttString = "Utterance #{}: {}".format(n, line)
    notValidString = "No valid parse\n"
    if (all(x in wordsInQuotes for x in line.split())):        #if word is found in grammarFile
        print "".join((uttString, CKYparse(line)))
    else:
        print "".join((uttString, notValidString))

Я понимаю принципы алгоритма, но попытка написать его на Python без NLTK оказывается сложной задачей.