深入解析cfg在自然语言处理中的核心作用与实现机制

1次阅读

共计 1631 个字符，预计需要花费 5 分钟才能阅读完成。

上下文无关文法 (Context-Free Grammar, CFG) 是形式文法的一种，由四元组 (N, Σ, P, S) 构成，其中：

N 为非终结符集合
Σ 为终结符集合
P 为产生式规则
S 为起始符号

在 NLP 中，CFG 最典型的应用是句法分析(syntactic parsing)。例如分析句子 ”The cat sat on the mat” 时：

S → NP VP
NP → Det N
VP → V PP
PP → P NP
Det → 'the'
N → 'cat' | 'mat'
V → 'sat'
P → 'on'

当语法规则超过 200 条时，传统递归下降解析器的时间复杂度会呈指数增长。实测数据显示：

规则数量	解析耗时(ms)
50	12
200	180
500	超时(>5000)

同一个句子可能对应多个语法树，例如 ”I saw the man with the telescope” 存在两种合法解释：

使用望远镜看到那个人
看到拿着望远镜的人

概率上下文无关文法 (Probabilistic CFG) 通过给规则附加概率值来解决歧义问题：

VP → V NP PP (0.7)
VP → V NP (0.3)

from typing import List, Dict, Tuple

class CFGParser:
    def __init__(self, grammar: Dict[str, List[List[str]]]):
        self.grammar = grammar

    def parse(self, tokens: List[str]) -> bool:
        """使用 CYK 算法进行解析"""
        n = len(tokens)
        # 初始化三角矩阵
        table = [[set() for _ in range(n)] for _ in range(n)]

        # 填充对角线
        for i in range(n):
            for lhs in self.grammar:
                for rhs in self.grammar[lhs]:
                    if len(rhs) == 1 and rhs[0] == tokens[i]:
                        table[i][i].add(lhs)

        # 自底向上填充
        for length in range(2, n+1):
            for i in range(n-length+1):
                j = i + length - 1
                for k in range(i, j):
                    for lhs in self.grammar:
                        for rhs in self.grammar[lhs]:
                            if len(rhs) == 2 and \
                               rhs[0] in table[i][k] and \
                               rhs[1] in table[k+1][j]:
                                table[i][j].add(lhs)

        return 'S' in table[0][n-1]

算法	时间复杂度	空间复杂度
CYK	O(n³)	O(n²)
Earley	O(n³)	O(n²)
递归下降	O(kⁿ)	O(n)

所有规则必须符合这两种形式之一：

A → BC（两个非终结符）
A → a（单个终结符）

转换示例：

原始规则：S → aSb
转换后：S → AX
X → SB
A → a
B → b

使用有向图检测循环依赖：

def detect_cycle(grammar):
    graph = {nt: set() for nt in grammar}
    for lhs in grammar:
        for rhs in grammar[lhs]:
            for symbol in rhs:
                if symbol in grammar:
                    graph[lhs].add(symbol)
    # 使用 DFS 检测环