CYK算法的Python实现

Question

编辑:错误是此行if len(rhs) == 2 and rhs[0] in T[i][k] and rhs[1] in T[k + 1][j]:

我能够使用少量的规则、终端和非终端实现基于cky解析器wiki的cky算法。但是我扩展了它以包含更多的规则，单词，语法，现在它给了我IndexError: list index out of range，有人知道我在更大的语法集上做错了什么吗？

以下是前面的较小规模的语法，如果有帮助的话。

non_terminals = ["NP", "Nom", "Det", "AP",  
                  "Adv", "A"] 
terminals = ["book", "orange", "man",  
             "tall", "heavy",  
             "very", "muscular"] 
  
# Rules of the grammar 
R = { 
     "NP": [["Det", "Nom"]], 
     "Nom": [["AP", "Nom"], ["book"],  
             ["orange"], ["man"]], 
     "AP": [["Adv", "A"], ["heavy"],  
            ["orange"], ["tall"]], 
     "Det": [["a"]], 
     "Adv": [["very"], ["extremely"]], 
     "A": [["heavy"], ["orange"], ["tall"],  
           ["muscular"]] 
    } 

下面是我的函数

定义长度(W)：n=cykParse(W)

# Initialize the table 
T = [[set([]) for j in range(n)] for i in range(n)] 

# Filling in the table 
for j in range(0, n): 

    # Iterate over the rules 
    for lhs, rule in R.items(): 
        for rhs in rule: 
              
            # If a terminal is found 
            if len(rhs) == 1 and rhs[0] == w[j]: 
                T[j][j].add(lhs) 

    for i in range(j, -1, -1):    
           
        # Iterate over the range i to j + 1    
        for k in range(i, j + 1):      

            # Iterate over the rules 
            for lhs, rule in R.items(): 
                for rhs in rule: 
                      
                    # If a terminal is found 
                    if len(rhs) == 2 and rhs[0] in T[i][k] and rhs[1] in T[k + 1][j]: 
                        T[i][j].add(lhs) 

# If word can be formed by rules  
# of given grammar 
if len(T[0][n-1]) != 0: 
    print("True") 
else: 
    print("False") 

Answer 1

我猜测(因为您没有显示指示错误发生位置的实际错误)，它在下面这一行：

if len(rhs) == 2 and rhs[0] in T[i][k] and rhs[1] in T[k + 1][j]:

而那个k就是n-1。如果前两个条件为真，则第三个条件将执行并崩溃。

我怀疑k的迭代限制中存在off-by-one错误。一些代码注释可能会很有用，或者至少是对您的实现所基于的伪代码的引用。