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算法
簡介
對於上述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.
外部連結