CYK算法（，縮寫為CYK algorithm）是由約翰·科克，Younger和共同研究出来大约发表于1965年的一个算法，它是一个用来判定任意给定的字符串~w \in \Sigma^* 是否属于一个上下文无关文法的算法。普通的回溯法（backtracking）在最坏的情况下需要指数时间才能解决这样的问题，而CYK算法只需要多项式时间就够了（~O(n^3) ， n 为字符串 w 的长度）。CYK算法采用了动态规划的思想。
对于一个任意给定的上下文无关文法，都可以使用CYK算法来计算上述问题，但首先要将该文法转换成乔姆斯基范式。
相关参数定义
- ~G =(V,\Sigma,S,P) 是一个上下文无关文法
- 对于任意字符串 w = \sigma_1...\sigma_n \in \Sigma^* ，定义 w[i,j] = \sigma_i...\sigma_j, ~1 \le i \le j \le n
- 对于任意选择的 ~i,j ，定义 V_{i,j} = \{ X \in V ~| ~X \Rightarrow^* w[i,j] \}
算法描述
简介
通过由下而上的方法计算 ~V_{i,j} 这个集合，如果 S \in V_{1,n} ，那么就说明 ~w 是被上下文无关文法 ~G 接受的字符串。
因为 ~G 是一个乔姆斯基范式，当且仅当有下面描述的情况时 X \in V_{i,j} ：
- i 是 ~G 中的一个规则且 Y \in V_{i,k}, Z \in V_{k+1,j}
伪代码
FOR i:= 1 TO n DO V_{i,i}:= \{ X \in V ~| ~X \rarr \sigma_i ~in ~P \}
FOR l:= 1 TO n-1
FOR i:= 1 TO n-l DO
~V_{i,i+l} := \varnothing
FOR k:= i TO i+l-1 DO
~V_{i,i+l} := V_{i,i+l} \cup \{X ~| ~X \rarr YZ, Y \in V_{i,k}, Z \in V_{k+1,i+l} \}
IF S \in V_{1,n} THEN accept ELSE reject
扩展CYK算法
简介
对于上述CYK算法作一个小改动，也就是说记住每次的k，就可以自动产生一个由该上下文无关语言的推导树。
伪代码
FOR i:= 1 TO n DO V_{i,i}:= \{ X \in V ~| ~X \rarr \sigma_i ~in ~P \}
FOR l:= 1 TO n-1
FOR i:= 1 TO n-l DO
~V_{i,i+l} := \varnothing
FOR k:= i TO i+l-1 DO
~V_{i,i+l} := V_{i,i+l} \cup \{ (X,k) ~| ~X \rarr YZ, Y \in V_{i,k}, Z \in V_{k+1,i+l} \}
IF \exists k : (S,k) \in V_{1,n} THEN accept ELSE reject
通过对下面的方法递归运行就可以生成推导树。
-{}-
Tree(X,i,j):
IF i=j THEN RETURN ~\sigma_i
选择一个 k 使 (X,k) \in V_{i,j}
选择 Y 和 Z 使 X \rarr YZ, Y \in V_{i,k}, Z \in V_{k+1,j}
RETURN Tree(X,Tree(Y,i,k),Tree(Z,k+1,j))
例子
给定一个乔姆斯基范式的上下文无关文法 ~G = (\lbrace S, A, B, C \rbrace, \lbrace a, b \rbrace, S, P) ，其中规则 P 如下：
:S \rightarrow AB \mid BC
:A \rightarrow BA \mid a
:B \rightarrow CC \mid b
:C \rightarrow AB \mid a
问：字符串 bbabaa 能不能通过该文法产生？
CYK算法可以通过一个表格来运算，表中 i 列 j 行表示由哪几个非终结符可以产生字字符串 \sigma_i \dots \sigma_j 。
例如：Table[1,3] = {A}，表示从非终结符 A 开始能够产生子串 bba。有如下推导：A \rightarrow BA \rightarrow bA \rightarrow bBA \rightarrow bbA \rightarrow bba
如果在表格的最左下角一格中有文法的开始非终结符 S ，那么字符串 bbabaa 就能由上面给出文法 G 产生。
参考文献
- John Cocke and Jacob T. Schwartz (1970). Programming languages and their compilers: Preliminary notes. Technical report, Courant Institute of Mathematical Sciences, New York University.
- T. Kasami (1965). An efficient recognition and syntax-analysis algorithm for context-free languages. Scientific report AFCRL-65-758, Air Force Cambridge Research Lab, Bedford, MA.
- Daniel H. Younger (1967). Recognition and parsing of context-free languages in time n3. Information and Control 10(2): 189–208.
外部链接
- [http://www.cs.iitm.ernet.in/tell/automata/Automata/final-cyk/app.html Interaktives Java-Applet zur Demonstration]
评论 (0)