CYK算法实现

概述在计算机科学领域，CYK算法（也称为Cocke–Younger–Kasami算法）是一种用来对上下文无关文法（CFG，Context Free Grammar）进行语法分析（parsing）的算法。该算法最早由John Cocke, Daniel Younger and Tadao Kasami分别独立提出，其中John Cocke还是1987年度的图灵奖得主。CYK算法是基于动态规划思想设计的一种自底向上语法分析算法。乔姆斯基范式CNF(Chomsky Normal Form)是一种这样的语法标准： 如果一个CFG \(\epsilon-free\)，而且它的规则只有如下两种形式:\(A \rightarrow B C\)\(A \rightarrow a\)那么这个CFG就是CNF形式的，可见CNF语法都是二分叉的。任何语法都可以转化成一个弱等价的CNF形式，具体方法如下：Step 1: Convert \(A \rightarrow Bc\) to \(A\rightarrow BC, C\rightarrow c\)Step 2: Convert \(A \rightarr...