CYK算法的Python实现

CYK算法（Cocke-Younger-Kasami算法）是一种用于解决文法的上下文无关语言的句法分析问题的算法。下面是CYK算法的Python实现，包含代码示例：

def cyk_parse(grammar, sentence):
    n = len(sentence)
    table = [[set() for _ in range(n-i)] for i in range(n)]
    
    # 填充表格的第一行，即填充终结符
    for i in range(n):
        for rule in grammar:
            if sentence[i] in grammar[rule]:
                table[0][i].add(rule)
    
    # 填充表格的剩余行
    for i in range(1, n):
        for j in range(n-i):
            for k in range(i):
                for rule in grammar:
                    for left in table[k][j]:
                        for right in table[i-k-1][j+k+1]:
                            if left + " " + right in grammar[rule]:
                                table[i][j].add(rule)
    
    # 判断是否可以由起始符推导出整个句子
    if "S" in table[n-1][0]:
        return True
    else:
        return False

# 示例文法和句子
grammar = {
    "S": ["NP VP"],
    "NP": ["Det N", "Det N PP"],
    "VP": ["V NP", "VP PP"],
    "PP": ["P NP"],
    "Det": ["a", "the"],
    "N": ["man", "ball", "woman", "table"],
    "V": ["hit", "took", "saw", "liked"],
    "P": ["on", "with"]
}

sentence = "the man saw a ball on the table"

# 执行CYK算法
result = cyk_parse(grammar, sentence.split())

# 输出结果
if result:
    print("句子可以由给定文法推导出")
else:
    print("句子无法由给定文法推导出")

上述代码实现了CYK算法，其中cyk_parse函数接受文法和句子作为输入，并返回一个布尔值，指示句子是否可以由给定文法推导出。

在示例中，我们使用了一个简单的文法和一个句子进行演示。可以根据实际需求修改grammar和sentence变量来进行测试。