[ Cocke-Younger-Kasami algorithm ] CYK算法

它是一個用來判定任意給定的字符串是否屬於某一個上下文無關文法的算法，還可以順便構造出二元語法樹和判斷是否有曖昧文法(Ambiguous Grammar)。對於一個任意給定的上下文無關文法，都可以使用CYK算法來計算上述問題，所以它是一個幾乎萬能的算法，但首先要將該文法轉換成喬姆斯基範式(CNF)。
這個算法主要是利用動態規劃的思想，給一個有$n$個字符的字符串s，和$R$條語法規則，則他的計算複雜度為$\ord{n^3R}$，空間複雜度為$\ord{n^2R}$。類似於optimal binary search tree的算法，對於每個s[l,r]我們去計算s[l,k]和s[k+1,r]能符合的所有規則。

我們用2016 NCPC的題目當例子
這裡給一個簡單的範例，給你一個語法規則如下 :
$A \Longrightarrow AAAAAAA \qquad 20 \\ A \Longrightarrow AA \qquad 15 \\ A \Longrightarrow a \qquad 5$
如果看不懂的，他大約的意思如下:
一個合法字串$A$可以是七個合法字串$A$所組成，也可以是兩個合法字串$A$所組成，也可以是小寫字母$a$所組成。
每個規則都給他一個權重，表示經過這個規則的轉換會有這些花費，我們會給一個目標字串，要找出把整個字串轉換成$A$的最小花費，例如給定字串$aaaaaaaa$，他的最小花費就是75。
這裡舉另一個例子:
$A \Longrightarrow BA \qquad 10 \\ A \Longrightarrow bcd \qquad 5 \\ B \Longrightarrow c \qquad 4$
給定字串$ccbcd$，他的最小花費就是33。
當然也會發生無法轉換的情況，這個時候叫要輸出$NIR$ 。

首先必須要把規則轉成喬姆斯基範式，這裡我以數字當作規則的名稱，當y=-1時表示這個cnf是s->x的規則，否則是s->xy的規則。

	#define MAXN 55
	struct CNF{
	int s,x,y;//s->xy | s->x, if y==-1
	int cost;
	CNF(){}
	CNF(int s,int x,int y,int c):s(s),x(x),y(y),cost(c){}
	};
	int state;//規則數量
	map<char,int> rule;//每個字元對應到的規則，小寫字母為終端字符
	vector<CNF> cnf;
	inline void init(){
	state=0;
	rule.clear();
	cnf.clear();
	}
	inline void add_to_cnf(char s,const string &p,int cost){
	if(rule.find(s)==rule.end())rule[s]=state++;
	for(auto c:p)if(rule.find(c)==rule.end())rule[c]=state++;
	if(p.size()==1){
	cnf.push_back(CNF(rule[s],rule[p[0]],-1,cost));
	}else{
	int left=rule[s];
	int sz=p.size();
	for(int i=0;i<sz-2;++i){
	cnf.push_back(CNF(left,rule[p[i]],state,0));
	left=state++;
	}
	cnf.push_back(CNF(left,rule[p[sz-2]],rule[p[sz-1]],cost));
	}
	}

view raw make_cnf.cpp hosted with ❤ by GitHub

接著就可以跑我們的演算法啦:

	vector<long long> dp[MAXN][MAXN];
	vector<bool> neg_INF[MAXN][MAXN];//如果花費是負的可能會有無限小的情形
	inline void relax(int l,int r,const CNF &c,long long cost,bool neg_c=0){
	if(!neg_INF[l][r][c.s]&&(neg_INF[l][r][c.x]||cost<dp[l][r][c.s])){
	if(neg_c||neg_INF[l][r][c.x]){
	dp[l][r][c.s]=0;
	neg_INF[l][r][c.s]=true;
	}else dp[l][r][c.s]=cost;
	}
	}
	inline void bellman(int l,int r,int n){
	for(int k=1;k<=state;++k)
	for(auto c:cnf)
	if(c.y==-1)relax(l,r,c,dp[l][r][c.x]+c.cost,k==n);
	}
	inline void cyk(const vector<int> &tok){
	for(int i=0;i<(int)tok.size();++i){
	for(int j=0;j<(int)tok.size();++j){
	dp[i][j]=vector<long long>(state+1,INT_MAX);
	neg_INF[i][j]=vector<bool>(state+1,false);
	}
	dp[i][i][tok[i]]=0;
	bellman(i,i,tok.size());
	}
	for(int r=1;r<(int)tok.size();++r){
	for(int l=r-1;l>=0;--l){
	for(int k=l;k<r;++k)
	for(auto c:cnf)
	if(~c.y)relax(l,r,c,dp[l][k][c.x]+dp[k+1][r][c.y]+c.cost);
	bellman(l,r,tok.size());
	}
	}
	}

view raw CYK.cpp hosted with ❤ by GitHub

當然它也可以用來判斷是不是有曖昧語法(ambiguous)，只要做一些小修改就行了