\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2016年10月28日 星期五

[ Earley parser ] Earley語法解析器

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

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

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

2016年10月11日 星期二

[ 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的規則。
接著就可以跑我們的演算法啦:
當然它也可以用來判斷是不是有曖昧語法(ambiguous),只要做一些小修改就行了

2016年10月3日 星期一

[ cantor expansion ] 康托展开

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

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