CYK算法(英语:Cocke–Younger–Kasami algorithm,缩写为CYK algorithm)是由约翰·科克,Younger和嵩忠雄共同研究出来大约发表于1965年的一个算法,它是一个用来判定任意给定的字符串
是否属于一个上下文无关文法的算法。普通的回溯法(backtracking)在最坏的情况下需要指数时间才能解决这样的问题,而CYK算法只需要多项式时间就够了(
, n 为字符串 w 的长度)。CYK算法采用了动态规划的思想。
对于一个任意给定的上下文无关文法,都可以使用CYK算法来计算上述问题,但首先要将该文法转换成乔姆斯基范式。
是一个上下文无关文法
- 对于任意字符串
,定义 ![{\displaystyle w[i,j]=\sigma _{i}...\sigma _{j},~1\leq i\leq j\leq n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6b388a8829ea4a3fba00c0f5fbe59601eeea0b00)
- 对于任意选择的
,定义 ![{\displaystyle V_{i,j}=\{X\in V~|~X\Rightarrow ^{*}w[i,j]\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e77a4aaaa2148bf2c94b11722750693d3b748dfd)
通过自底向上的方法计算
这个集合,如果
,那么就说明
是被上下文无关文法
接受的字符串。
因为
是一个乔姆斯基范式,当且仅当有下面描述的情况时
:
是
中的一个规则且 ![{\displaystyle Y\in V_{i,k},Z\in V_{k+1,j}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3fb90d29685d46ad0c9643e6da4d0ed33b5d1411)
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算法作一个小改动,也就是说记住每次的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))
给定一个乔姆斯基范式的上下文无关文法
,其中规则 P 如下:
![{\displaystyle S\rightarrow AB\mid BC}](https://wikimedia.org/api/rest_v1/media/math/render/svg/be9eb71d1a6f5f2c73a8eaadba275d487dfa1a4b)
![{\displaystyle A\rightarrow BA\mid a}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b939fcbb09d0c9f0535fd14ebc22df538d55a6ce)
![{\displaystyle B\rightarrow CC\mid b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b672c8429a0c4a4b9e470d8a98ca8f7a6a042bc)
![{\displaystyle C\rightarrow AB\mid a}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fe51e223fe87a8e3bf70fb550fe377f2c0b745c5)
问:字符串 bbabaa 能不能通过该文法产生?
CYK算法可以通过一个表格来运算,表中 i 列 j 行表示由哪几个非终结符可以产生字字符串
。
i
|
1
|
2
|
3
|
4
|
5
|
6
|
ai
|
b
|
b
|
a
|
b
|
a
|
a
|
j=1
|
{B}
|
j=2
|
-
|
{B}
|
j=3
|
{A}
|
{S,A}
|
{A,C}
|
j=4
|
{S,C}
|
{S,C}
|
{S,C}
|
{B}
|
j=5
|
{B}
|
{B}
|
{B}
|
{A,S}
|
{A,C}
|
j=6
|
{A,S}
|
{A,S}
|
{A,S}
|
-
|
{B}
|
{A,C}
|
如果在表格的最左下角一格中有文法的开始非终结符 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.