[ Earley parser ] Earley語法解析器

有一天蚯蚓跟我說CYK算法很慢，推薦了這個東西，所以我就把他寫出來了。
他主要是先建構出類似於自動機的圖，有很多個狀態在跳來跳去，在我的實作裡有將其轉成語法樹的方法。
這裡需要自己實作的有lexer，還有最後的語法一定要有一個gamma rule，gamma rule就是有一個$gamma \Longrightarrow S$，$S$是初始符號。
首先是語法規則的部分:

	struct Rule{
	vector<vector<Rule*> > p;
	void add(const vector<Rule*> &l){
	p.push_back(l);
	}
	};
	map<string,Rule*> NameRule;
	map<Rule*,string> RuleName;
	inline void init_Rule(){
	for(auto r:RuleName)delete r.first;
	RuleName.clear();
	NameRule.clear();
	}
	inline Rule *add_rule(const string &s){
	if(NameRule.find(s)!=NameRule.end())return NameRule[s];
	Rule *r=new Rule();
	RuleName[r]=s;
	NameRule[s]=r;
	return r;
	}
	//範例
	inline Rule *get_my_Rule(){
	//可以由題目輸入語法，也可以自己設定
	Rule *S=add_rule("S"),*E=add_rule("E"),*L=add_rule("L");
	Rule *list=add_rule("("),*AND=add_rule(")"),*T=add_rule("T");
	S->add({list,E});
	S->add({list,L});
	L->add({E,L});
	L->add({E,AND,E});
	E->add({T});
	E->add({S});
	Rule *GAMMA=add_rule("GAMMA");//一定要有gamma rule當作是最上層的語法
	GAMMA->add({S});
	return GAMMA;
	}

view raw rule.cpp hosted with ❤ by GitHub

這是分析器的本體，lexer的部分要自己去完成，lexer的結果會是parse的第二個參數，計算出來一些資料會存在table裡面
以下為模板:

	typedef vector<Rule*> production;
	struct State{
	Rule *r;
	int rid,dot_id,start,end;
	State(Rule *r,int rid,int dot,int start):r(r),rid(rid),dot_id(dot),start(start),end(-1){}
	State(Rule *r=0,int col=0):r(r),rid(-1),dot_id(-1),start(-1),end(col){}
	bool completed()const{
	return rid==-1||dot_id>=(int)r->p[rid].size();
	}
	Rule *next_term()const{
	if(completed())return 0;
	return r->p[rid][dot_id];
	}
	bool operator<(const State& b)const{
	if(start!=b.start)return start<b.start;
	if(dot_id!=b.dot_id)return dot_id<b.dot_id;
	if(r!=b.r)return r<b.r;
	return rid<b.rid;
	}
	void print()const{
	cout<<RuleName[r]<<"->";
	if(rid!=-1)for(size_t i=0;;++i){
	if((int)i==dot_id)cout<<" "<<"$";
	if(i>=r->p[rid].size())break;
	cout<<" "<<RuleName[r->p[rid][i]];
	}
	cout<<" "<<"["<<start<<","<<end<<"]"<<endl;
	}
	};
	struct Column{
	Rule *term;
	string value;
	vector<State> s;
	map<State,set<pair<State,State> > > div;
	//div比較像一棵 左兄右子的樹
	Column(Rule *r,const string &s):term(r),value(s){}
	Column(){}
	bool add(const State &st,int col){
	if(div.find(st)==div.end()){
	div[st];
	s.push_back(st);
	s.back().end=col;
	return true;
	}else return false;
	}
	};
	inline vector<Column> lexer(string text){
	//tokenize，要自己寫
	//他會把 input stream 變成 token stream，就是(terminal,value)pair
	vector<Column> token;
	//自己寫的地方
	return token;
	}
	vector<Column> table;
	inline void predict(int col,Rule *rul){
	for(size_t i=0;i<rul->p.size();++i){
	table[col].add(State(rul,i,0,col),col);
	}
	}
	inline void scan(int col,const State &s,Rule *r){
	if(r!=table[col].term)return;
	State ns(s.r,s.rid,s.dot_id+1,s.start);
	table[col].add(ns,col);
	table[col].div[ns].insert(make_pair(s,State(r,col)));
	}
	inline void complete(int col,const State &s){
	for(size_t i=0;i<table[s.start].s.size();++i){
	State &st=table[s.start].s[i];
	Rule *term=st.next_term();
	if(!term||term->p.size()==0)continue;
	if(term==s.r){
	State nst(st.r,st.rid,st.dot_id+1,st.start);
	table[col].add(nst,col);
	table[col].div[nst].insert(make_pair(st,s));
	}
	}
	}
	inline pair<bool,State> parse(Rule *GAMMA,const vector<Column > &token){
	table.resize(token.size()+1);
	for(size_t i=0;i<token.size();++i){
	table[i+1]=Column(token[i]);
	}
	table[0]=Column();
	table[0].add(State(GAMMA,0,0,0),0);
	for(size_t i=0;i<table.size();++i){
	for(size_t j=0;j<table[i].s.size();++j){
	State state=table[i].s[j];
	if(state.completed())complete(i,state);
	else{
	Rule *term=state.next_term();
	if(term->p.size())predict(i,term);
	else if(i+1<table.size())scan(i+1,state,term);
	}
	}
	}
	for(size_t i=0;i<table.back().s.size();++i){
	if(table.back().s[i].r==GAMMA&&table.back().s[i].completed()){
	return make_pair(true,table.back().s[i]);
	}
	}
	return make_pair(false,State(0,-1));
	}

view raw parser.cpp hosted with ❤ by GitHub

最後是構造語法樹的部分，因為div是一顆左兄弟右兒子的樹，所以要將她轉換成正常的語法樹，還要去記錄曖昧文法的部分:

	struct node{//語法樹的節點
	State s;
	vector<vector<node*> > child;//vector<node*>.size()>1表示ambiguous
	node(const State &s):s(s){}
	node(){}
	};
	struct State_end_cmp{
	bool operator()(const State &a,const State &b)const{
	return a.end<b.end||(a.end==b.end&&a<b);
	}
	};
	map<State,node*,State_end_cmp> cache;
	vector<node*> node_set;
	inline void init_cache(){
	for(auto d:node_set)delete d;
	cache.clear();
	node_set.clear();
	}
	void _build_tree(const State &s,node *pa,bool amb=0){
	if(cache.find(s)!=cache.end()){
	pa->child.push_back(vector<node*>(1,cache[s]));
	return;
	}
	node *o;
	if(s.completed()){
	o=new node(s);
	if(amb)pa->child.back().push_back(o);
	else pa->child.push_back(vector<node*>(1,o));
	}else o=pa->child.back().back();
	amb=0;
	for(auto div:table[s.end].div[s]){
	if(!amb)_build_tree(div.first,pa);
	_build_tree(div.second,o,amb);
	amb=1;
	}
	if(s.completed())cache[s]=o;
	}
	inline node *build_tree(const State &s){
	init_cache();
	node o;
	_build_tree(s,&o);
	assert(o.child.size()==1);
	assert(o.child.back().size()==1);
	return o.child.back().back();
	}
	void print_tree(node *o,int dep=0){
	cout<<string(dep,' '),o->s.print();
	for(auto div:o->child){
	for(auto nd:div){
	print_tree(nd,dep+2);
	}
	}
	}

view raw build_tree.cpp hosted with ❤ by GitHub

[ 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)，只要做一些小修改就行了

[ cantor expansion ] 康托展开

給一個$0 \sim n-1$共$n$個數字的全排列，求他是排名第幾的全排列；給一個名次，求全排列。這東西可以有效的減少hash_table的大小。
以下附上code:

	#include<vector>
	#define MAXN 11
	int factorial[MAXN];
	inline void init(){
	factorial[0]=1;
	for(int i=1;i<=MAXN;++i){
	factorial[i]=factorial[i-1]*i;
	}
	}
	inline int encode(const std::vector<int> &s){
	int n=s.size(),res=0;
	for(int i=0;i<n;++i){
	int t=0;
	for(int j=i+1;j<n;++j){
	if(s[j]<s[i])++t;
	}
	res+=t*factorial[n-i-1];
	}
	return res;
	}
	inline std::vector<int> decode(int a,int n){
	std::vector<int> res;
	std::vector<bool> vis(n,0);
	for(int i=n-1;i>=0;--i){
	int t=a/factorial[i],j;
	for(j=0;j<n;++j){
	if(!vis[j]){
	if(t==0)break;
	--t;
	}
	}
	res.push_back(j);
	vis[j]=1;
	a%=factorial[i];
	}
	return res;
	}

view raw cantor_expansion.cpp hosted with ❤ by GitHub

使用前記得要呼叫init();

[ closest pair of points ] 平面上歐基里德距離最近點對

用分治法寫的，複雜度$\ord{n\log^2 n}$:

	#include<cmath>
	#include<vector>
	#include<algorithm>
	using namespace std;
	template<typename T>
	struct point{
	T x,y;
	point(){}
	point(const T&dx,const T&dy):x(dx),y(dy){}
	inline const point operator-(const point &b)const{
	return point(x-b.x,y-b.y);
	}
	inline const T dot(const point &b)const{
	return x*b.x+y*b.y;
	}
	inline const T abs2()const{/*向量長度的平方*/
	return dot(*this);
	}
	static bool x_cmp(const point<T>& a,const point<T>& b){
	return a.x<b.x;
	}
	static bool y_cmp(const point<T>& a,const point<T>& b){
	return a.y<b.y;
	}
	};
	#define INF LLONG_MAX/*預設是long long最大值*/
	template<typename T>
	T closest_pair(vector<point<T> >&v,vector<point<T> >&t,int l,int r){
	T dis=INF,tmd;
	if(l>=r)return dis;
	int mid=(l+r)/2;
	if((tmd=closest_pair(v,t,l,mid))<dis)dis=tmd;
	if((tmd=closest_pair(v,t,mid+1,r))<dis)dis=tmd;
	t.clear();
	for(int i=l;i<=r;++i)
	if((v[i].x-v[mid].x)*(v[i].x-v[mid].x)<dis)t.push_back(v[i]);
	sort(t.begin(),t.end(),point<T>::y_cmp);/*如果用merge_sort的方式可以O(n)*/
	for(int i=0;i<(int)t.size();++i)
	for(int j=1;j<=3&&i+j<(int)t.size();++j)
	if((tmd=(t[i]-t[i+j]).abs2())<dis)dis=tmd;
	return dis;
	}
	template<typename T>
	inline T closest_pair(vector<point<T> > &v){
	vector<point<T> >t;
	sort(v.begin(),v.end(),point<T>::x_cmp);
	return closest_pair(v,t,0,v.size()-1);/*最近點對距離*/
	}

view raw closest_pair_of_points.cpp hosted with ❤ by GitHub