CYK算法 （英語：Cocke–Younger–Kasami algorithm ，縮寫為CYK algorithm）是由約翰·科克 ，Younger和嵩忠雄
w
∈
Σ
∗
{\displaystyle ~w\in \Sigma ^{*}}
上下文无关文法 的算法。普通的回溯法 （backtracking）在最坏的情况下需要指数时间 才能解决这样的问题，而CYK算法只需要多项式时间 就够了（
O
(
n
3
)
{\displaystyle ~O(n^{3})}
动态规划 的思想。
对于一个任意给定的上下文无关文法，都可以使用CYK算法来计算上述问题，但首先要将该文法转换成乔姆斯基范式 。
相关参数定义
编辑
G
=
(
V
,
Σ
,
S
,
P
)
{\displaystyle ~G=(V,\Sigma ,S,P)}
对于任意字符串
w
=
σ
1
.
.
.
σ
n
∈
Σ
∗
{\displaystyle w=\sigma _{1}...\sigma _{n}\in \Sigma ^{*}}
w
[
i
,
j
]
=
σ
i
.
.
.
σ
j
,
1
≤
i
≤
j
≤
n
{\displaystyle w[i,j]=\sigma _{i}...\sigma _{j},~1\leq i\leq j\leq n}
对于任意选择的
i
,
j
{\displaystyle ~i,j}
V
i
,
j
=
{
X
∈
V
|
X
⇒
∗
w
[
i
,
j
]
}
{\displaystyle V_{i,j}=\{X\in V~|~X\Rightarrow ^{*}w[i,j]\}}
算法描述
编辑
通过由下而上的方法计算
V
i
,
j
{\displaystyle ~V_{i,j}}
S
∈
V
1
,
n
{\displaystyle S\in V_{1,n}}
w
{\displaystyle ~w}
G
{\displaystyle ~G}
因为
G
{\displaystyle ~G}
X
∈
V
i
,
j
{\displaystyle X\in V_{i,j}}
i
<
j
,
∃
Y
,
Z
,
k
:
X
→
Y
Z
{\displaystyle i<j,~\exists Y,Z,k:X\rightarrow YZ}
G
{\displaystyle ~G}
Y
∈
V
i
,
k
,
Z
∈
V
k
+
1
,
j
{\displaystyle Y\in V_{i,k},Z\in V_{k+1,j}}
FOR i:= 1 TO n DO
V
i
,
i
:=
{
X
∈
V
|
X
→
σ
i
i
n
P
}
{\displaystyle V_{i,i}:=\{X\in V~|~X\rightarrow \sigma _{i}~in~P\}}
FOR l:= 1 TO n-1
FOR i:= 1 TO n-l DO
V
i
,
i
+
l
:=
∅
{\displaystyle ~V_{i,i+l}:=\varnothing }
FOR k:= i TO i+l-1 DO
V
i
,
i
+
l
:=
V
i
,
i
+
l
∪
{
X
|
X
→
Y
Z
,
Y
∈
V
i
,
k
,
Z
∈
V
k
+
1
,
i
+
l
}
{\displaystyle ~V_{i,i+l}:=V_{i,i+l}\cup \{X~|~X\rightarrow YZ,Y\in V_{i,k},Z\in V_{k+1,i+l}\}}
IF
S
∈
V
1
,
n
{\displaystyle S\in V_{1,n}}
THEN accept ELSE reject
扩展CYK算法
编辑
对于上述CYK算法作一个小改动，也就是说记住每次的k，就可以自动产生一个由该上下文无关语言的推导树。
FOR i:= 1 TO n DO
V
i
,
i
:=
{
X
∈
V
|
X
→
σ
i
i
n
P
}
{\displaystyle V_{i,i}:=\{X\in V~|~X\rightarrow \sigma _{i}~in~P\}}
FOR l:= 1 TO n-1
FOR i:= 1 TO n-l DO
V
i
,
i
+
l
:=
∅
{\displaystyle ~V_{i,i+l}:=\varnothing }
FOR k:= i TO i+l-1 DO
V
i
,
i
+
l
:=
V
i
,
i
+
l
∪
{
(
X
,
k
)
|
X
→
Y
Z
,
Y
∈
V
i
,
k
,
Z
∈
V
k
+
1
,
i
+
l
}
{\displaystyle ~V_{i,i+l}:=V_{i,i+l}\cup \{(X,k)~|~X\rightarrow YZ,Y\in V_{i,k},Z\in V_{k+1,i+l}\}}
IF
∃
k
:
(
S
,
k
)
∈
V
1
,
n
{\displaystyle \exists k:(S,k)\in V_{1,n}}
THEN accept ELSE reject
通过对下面的方法递归运行就可以生成推导树。
Tree(X,i,j):
IF i=j THEN RETURN
σ
i
{\displaystyle ~\sigma _{i}}
(
X
,
k
)
∈
V
i
,
j
{\displaystyle (X,k)\in V_{i,j}}
X
→
Y
Z
,
Y
∈
V
i
,
k
,
Z
∈
V
k
+
1
,
j
{\displaystyle X\rightarrow YZ,Y\in V_{i,k},Z\in V_{k+1,j}}
给定一个乔姆斯基范式的上下文无关文法
G
=
(
{
S
,
A
,
B
,
C
}
,
{
a
,
b
}
,
S
,
P
)
{\displaystyle ~G=(\lbrace S,A,B,C\rbrace ,\lbrace a,b\rbrace ,S,P)}
S
→
A
B
∣
B
C
{\displaystyle S\rightarrow AB\mid BC}
A
→
B
A
∣
a
{\displaystyle A\rightarrow BA\mid a}
B
→
C
C
∣
b
{\displaystyle B\rightarrow CC\mid b}
C
→
A
B
∣
a
{\displaystyle C\rightarrow AB\mid a}
问：字符串 bbabaa 能不能通过该文法产生？
CYK算法可以通过一个表格来运算，表中 i 列 j 行表示由哪几个非终结符可以产生字字符串
σ
i
…
σ
j
{\displaystyle \sigma _{i}\dots \sigma _{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 n 3 . Information and Control 10(2): 189–208.
外部链接
编辑
![{\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)
