CYK算法

维基百科，自由的百科全书

CYK算法是由Cocke，Younger和Kasami共同研究出来大约发表于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 < j, ~\exists Y,Z,k : X \rarr YZ$ 是 $~G$ 中的一个规则且 $Y \in V_{i,k}, Z \in V_{k+1,j}$

[编辑] 伪代码

FOR i:= 1 TO n DO 
FOR l:= 1 TO n-1
    FOR i:= 1 TO n-l DO
        
        FOR k:= i TO i+l-1 DO
            
IF  THEN accept ELSE reject

[编辑] 扩展CYK算法

[编辑] 简介

对于上述CYK算法作一个小改动，也就是说记住每次的k，就可以自动产生一个由该上下文无关语言的推导树。

[编辑] 伪代码

FOR i:= 1 TO n DO 
FOR l:= 1 TO n-1
    FOR i:= 1 TO n-l DO
        
        FOR k:= i TO i+l-1 DO
            
IF  THEN accept ELSE reject

通过对下面的方法递归运行就可以生成推导树。

Tree(X,i,j):
   IF i=j THEN RETURN 
   选择一个 k 使 
    选择 Y 和 Z 使 
    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$ 。

i	1	2	3	4	5	6
a_i	b	b	a	b	a	a
j=1	{B}	{B}	{A,C}	{B}	{A,C}	{A,C}
j=2	-	{A,S}	{S,C}	{A,S}	{B}
j=3	{A}	{S,C}	{B}	-
j=4	{S,C}	{B}	{A,S}
j=5	{B}	{A,S}
j=6	{A,S}

如果在表格的最左下角一格中有文法的开始非终结符 S ，那么字符串 bbabaa 就能由上面给出文法 G 产生。

[编辑] 相关链接

Interaktives Java-Applet zur Demonstration

[编辑] 参考文献

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 n³. Information and Control 10(2): 189–208.

分类: 算法 | 形式语言

See also ebooksgratis.com: no banners, no cookies, totally FREE.

CYK算法

维基百科，自由的百科全书

目录

[编辑] 相关参数定义

[编辑] 算法描述

[编辑] 简介

[编辑] 伪代码

[编辑] 扩展CYK算法

[编辑] 简介

[编辑] 伪代码

[编辑] 例子

[编辑] 相关链接

[编辑] 参考文献

Views

导航

帮助

搜索

其他语言