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算法作一個小改動，也就是說記住每次的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)
