如何解析同步上下文无关文法？CYK算法双表关联实现求助

你的核心问题是要验证一对关联字符串是否符合带{1}/{2}标记的同步文法，单独解析每个字符串无法满足标记的关联约束，所以必须修改CYK算法，同步追踪两个字符串的推导过程。

核心方案：联合CYK表 #

放弃两个独立表的思路，直接构建联合CYK表，每个单元格存储「能同步推导出对应两个子串的非终结符」，关联标记会约束推导时的拆分规则。

1. 明确规则的同步含义 #

从你的文法来看，带标记的规则是描述两个字符串的同步推导逻辑：

• S -> A{1} B{2}：第一个字符串由A推导生成，第二个字符串由B推导生成
• S -> B{2} A{1}：第一个字符串由B推导生成，第二个字符串由A推导生成
• 二元规则如A -> A{1} A{2}：第一个字符串的A由A推导的子串拼接而成，第二个字符串的A也由A推导的子串拼接而成，两个推导过程同步

2. 联合CYK表定义 #

假设要验证的字符串对是w1（长度n）和w2（长度m），定义表T[i][j][k][l]：

• i,j：w1中子串的起始、结束索引（1-based）
• k,l：w2中子串的起始、结束索引
• 表项内容：所有能同步推导出w1[i..j]和w2[k..l]的非终结符集合

3. 算法步骤 #

初始化（子串长度为1或空串）

• 终结符匹配：遍历每个位置i（w1）和k（w2），如果非终结符X有规则X→w1[i]且X→w2[k]，则将X加入T[i][i][k][k]；如果X有空串规则X→e，则将X加入空区间表项T[i][i-1][k][k-1]（表示推导出空串）。
• 空串组合：若X能推导出空串，那么只要w1[i..j]和w2[k..l]都是空串，就将X加入T[i][j][k][l]。

递推阶段（子串长度≥2）

遍历所有可能的子串拆分方式：

1. 对于w1的子串w1[i..j]，拆分为w1[i..k] + w1[k+1..j]（k从i到j-1）
2. 对于w2的子串w2[p..q]，拆分为w2[p..r] + w2[r+1..q]（r从p到q-1）
3. 遍历所有二元规则：
   • 若规则是X → Y{1} Z{2}：如果Y在T[i][k][p][r]中，且Z在T[k+1][j][r+1][q]中，则将X加入T[i][j][p][q]
   • 若规则是X → Y{2} Z{1}：如果Y在T[i][k][r+1][q]中，且Z在T[k+1][j][p][r]中，则将X加入T[i][j][p][q]
   • 对于同标记规则如X → X{1} X{2}，按上述逻辑直接匹配即可

结果验证

检查T[1][n][1][m]中是否包含起始符号S，若包含则说明字符串对(w1,w2)符合文法规则。

优化技巧 #

1. 等长字符串优化：同步文法通常生成等长字符串（除非有空串），此时可将表简化为T[len][i][p]，其中len是子串长度，i是w1的起始位置，p是w2的起始位置，复杂度从O(n^6)降到O(n^4)。
2. 规则预分类：把规则按标记顺序（{1}{2}、{2}{1}）分类，递推时直接遍历对应类别，减少无效检查。
3. 空串快速处理：提前预处理所有能推导出空串的非终结符，初始化时批量加入对应表项，避免重复计算。

简单示例验证 #

验证字符串对("a", "b")：

1. 初始化时，A能推导出"a"，B能推导出"b"
2. 匹配规则S→A{1}B{2}：A对应w1[1..1]，B对应w2[1..1]，满足推导条件，因此S被加入T[1][1][1][1]
3. 最终检查T[1][1][1][1]包含S，验证通过

内容的提问来源于stack exchange，提问作者nic