CYK演算法(英語:Cocke–Younger–Kasami algorithm,縮寫為CYK algorithm)是由約翰·科克,Younger和嵩忠雄(日語:嵩忠雄)共同研究出來大約發表於1965年的一個演算法,它是一個用來判定任意給定的字串 是否屬於一個上下文無關文法的演算法。普通的回溯法(backtracking)在最壞的情況下需要指數時間才能解決這樣的問題,而CYK演算法只需要多項式時間就夠了( , n 為字串 w 的長度)。CYK演算法採用了動態規劃的思想。
FOR i:= 1 TO n DOFOR l:= 1 TO n-1
FOR i:= 1 TO n-l DOFOR k:= i TO i+l-1 DOIFTHEN 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 如下:
問:字串 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.