language / grammar

「語言language」是一大堆字串、是一個字串集合。

括號對稱的language
使用的字元是「(」與「)」。

()
()()()
(((())))
(((()(()))()))
......

聖經人名的language
使用的字元是52種大小寫英文字母。

Aaron
Abaddon
Abagtha
Abana
Abba
Abda
......

C programming language
使用的字元是ASCII當中的可見符號、換行、空白、……。

int main() {return 0;}

int main(int argc, char* argv[]) {return 0;}

int main( int argc , char * argv[] ) {
    return 0;
}

English language
使用的字元是52種大小寫英文字母、標點符號。

Whatever, you know, just sayin.
How are you? I am fine, thank you.

Chinese language
使用的字元是漢字，大約七萬字。

臣亮言：先帝創業未半，而中道崩殂；今天下三分，益州疲敝，此誠危急存亡之秋也。
為著環境未凍來完成彼段永遠難忘的戀情。孤單來到昔日的海岸，景致猶原也無改變。
為了防止世界被破壞，為了守護世界的和平，貫徹愛與真實的邪惡。

「文法grammar」是一組規則，用三言兩語構築一大堆字串、構築一套language。

grammar必須剛好生成language之內的所有字串、必須永不生成language以外的所有字串。

一套Language可以設計許多種不同的grammar，不過光是學一種grammar就夠頭痛了。

English grammar
主詞S，動詞V，受詞O，補語C。

1. S + V
2. S + V + C
3. S + V + O
4. S + V + O + C
5. S + V + O + O
6. V + S + O
7. S + do/does + V + C
......
......
......
123. S = dog / cat / ...
124. V = run / sleep / ...
......
......
......

以數學的觀點來看，grammar就像是數學公式。從資料結構的觀點來看，grammar是language的資料結構。從資料壓縮的觀點來看，不失真地壓縮language，就得到grammar。

syntax / semantics

「語法syntax」是字串的格式；字串對應到文法即可求得。

      I            love          you.
[名詞主格nom.] [及物動詞vt.] [名詞受格obj.]

  我     愛     你。
[名詞] [動詞] [受詞]

「語義semantics」是字串的含意；確立語法之後，根據上下文、根據現場情境求得。

小孩對媽媽說：我　愛　你。
　　　　　　　[溫馨的親情]

丈夫對妻子說：我　愛　你。
　　　　　　　[甜蜜的愛情]

丈夫強忍眼淚，緊抱著患病的妻子說：我　愛　你。
　　　　　　　　　　　　　　　　　[心痛的悲情]

parse / evaluate

剖析解讀語法，求值總結語義。

我們可以「剖析parse」一個字串，逐字對應至grammar、確立語法，進而判斷原本字串是不是language當中的字串。

字串對應到文法時，有兩種以上的對應方式，那麼此文法就稱作「曖昧文法ambiguous grammar」。

曖昧文法使得同一個字串擁有許多種語法，難以剖析。曖昧文法也很容易讓人誤解字串涵義，而中文文法就是一個著名的曖昧文法。例如下面兩例，每一行句子的語法都略有不同。

已結婚的和尚未結婚的青年都要實行生育計畫

一、已結婚的、和、尚未結婚的青年，都要實行生育計畫！（「和」當作連詞）
二、已結婚的和尚、未結婚的青年，都要實行生育計畫！（「和尚」當作名詞）

下雨天留客天留我不留

一、下雨，天留客。天留，我不留。
二、下雨，天留客。天留我？不留。
三、下雨，天留客。天留我不？留。
四、下雨，天留客。天，留我不留？
五、下雨天，留客天。留我？不留。
六、下雨天，留客天。留我不？留。
七、下雨天，留客天。留我不留？

接著可以「求值evaluate」一個字串，逐字確認語義，進而得到原本字串的意義。

例如下例第一句是語法和語義都正確；第二句是語法正確、語義採用了轉化修辭；第三句是語法正確、語義不正確，語焉不詳。

女孩對我眨眼。
星星對我眨眼。
空氣對我眨眼。

例如下例第一句、第三句之中重複的地方，就是語法相同、語義不同。第二句是語法不同、語義也不同。

有兩種人不談戀愛：一種是誰都看不上，另一種是誰都看不上。
有兩種人最容易被甩：一種人不知道什麼叫做愛，一種人不知道什麼叫做愛。
這些人都是原先喜歡一個人，後來喜歡一個人。

電腦習慣先判定語法、再判定語義，曖昧文法應予盡量避免。人類習慣先揣摩語義、再揣摩語法，曖昧文法實則影響不大。

UVa 271 310 384 620 743 1089 10027 10981 11108 ICPC 3623 4455

formal language / Natural language

接下來要介紹的language，是以數學方式建構而得的語言，是一套數學理論，稱作「形式語言formal language」。

人類互相交流的語言，例如中文、英文、閩南語、客家話、粵語，則相對地稱作「自然語言natural language」。

以數學方式建構而得的語言，規律太過完美，不足以表達現實生活那些缺乏規律的語言。解析人類語言的方法，是自成一系的古老學問，屬於「語言學linguistics」的範疇，是人文方面的學問。

運用電腦處理人類語言，例如語言翻譯、人機對話，則是屬於「計算語言學computational linguistics」的範疇。

formal language四大類型

regular language
context-free language
context-sensitive language
recursively enumerable language

古早人以數學方式，研發了四種語言規律，由規律嚴謹到規律寬鬆排列，前者是後者的特例。大家稱作Chomsky hierarchy。

其中regular language與context-free language，由於規律十分嚴謹，所以得以設計效率極高的演算法、擁有實務價值。

例如regular language用於字串搜尋、用於驗證字串格式。例如context-free language用於設計程式語言、用於檢索網頁資料。身為一個程式員，其實每天都在不自覺地接觸這些語言的應用。

至於context-sensitive language與recursively enumerable language，由於缺乏規律、難以計算，所以鮮少討論。

regular language

「正規語言」規律十分簡單：

一、空集合：一套正規語言可以只包含一個字串，而且是空字串。
{Ø}

二、字元：一套正規語言可以只包含一個字串，而且是長度為一的字串。
{a}、{b}、{c}

三、銜接：一套正規語言可以只包含一個字串，是上述某些字串銜接而得的字串。
{aa}、{aaa}、{aaabbb}、{abc}、{aabbccabc}、{ababab}

四、聯集：一套正規語言可以是上述某些字串的聯集。
{aaabbb, ab, ba, cat, dog, Ø}
{Aaron, Abaddon, Abagtha, Abana, Abba, Abda, ......}

regular expression

「正規表示式」用來輕鬆描述一種正規文法、輕鬆生成一套正規語言。書寫語法如下表所示：

   | regExp | regular language        | 意義
---| -------| ------------------------| ---------------
   | ab     | {ab}                    | 銜接
   | abc    | {abc}                   |
---| -------| ------------------------| ---------------
() | (ab)   | {ab}                    | 包裝
   | (ab)c  | {abc}                   |
---| -------| ------------------------| ---------------
+  | a+     | {a, aa, aaa, ...}       | 出現一次以上
   | ab+    | {ab, abb, abbb, ...}    |
   | (ab)+  | {ab, abab, ababab, ...} |
   | a+b    | {ab, aab, aaab, ...}    |
---| -------| ------------------------| ---------------
*  | a*     | {Ø, a, aa, aaa, ...}    | 出現零次以上
   | ab*    | {a, ab, abb, abbb, ...} |
---| -------| ------------------------| ---------------
?  | a?     | {Ø, a}                  | 出現零次或一次
   | abc?   | {ab, abc}               |
   | (abc)? | {Ø, abc}                |
   | a?b    | {b, ab}                 |
---| -------| ------------------------| ---------------
{} | a{3,5} | {aaa, aaaa, aaaaa}      | 出現x次或至y次
---| -------| ------------------------| ---------------
|  | a|b    | {a, b}                  | 聯集
   | a|b|c  | {a, b, c}               |
   | ab|cd  | {ab, cd}                |
   | (a|b)c | {ac, bc}                |
   | (a|b)? | {Ø, a, b}               |
   | (a|b)+ | {a, b,                  |
   |        |  aa, ab, ba, bb,        |
   |        |  aaa, aab, aba, ...}    |
---| -------| ------------------------| ---------------
[] | [abc]  | {a, b, c}               | 字元的聯集
   | [a-z]  | {a, b, c, ..., z}       |
   | [a-zA] | {a, ..., z, A}          |
   [a-zA-Z] | {a, ..., z, A, ..., Z}  |
---| -------| ------------------------| ---------------
.  | .      | {a, b, c, ...,          | 全部字元的聯集
   |        |  A, B, C, ...,          | 或者說
   |        |  1, 2, 3, ...,          | 任意一個字元
   |        |  (, ), +, *, ?, ...}    |
   | a.     | {aa, ab, ac, ...}       |
   | a..    | {aaa, aab, aac, ...}    |
---| -------| ------------------------| ---------------
\  | \(     | {(}                     | escape
   | \.     | {.}                     |

註：作業系統的檔案名稱，也常常寫成正規表示式，例如*.txt。但是檔案名稱採用的是另一種書寫語法，像是?是指任意一個字元、*是指任意一個字串，都與上表的意義不同。千萬不要搞混。

範例：行動電話號碼

台灣的行動電話號碼，諸如0935-120-188、0982647356，所有的行動電話號碼字串構成的集合，正是一套正規語言。對應的正規表示式有許多種寫法：

09[0-9][0-9]-?[0-9][0-9][0-9]-?[0-9][0-9][0-9]
09[0-9]{2,2}-?[0-9]{3,3}-?[0-9]{3,3}
09[0-9]{2,2}(-?[0-9]{3,3}){2,2}
09([0-9][0-9]-?[0-9]){2,2}[0-9][0-9]
......

先前提到一套語言可以設計許多種不同的文法，想當然一套正規語言可以設計許多種正規表示式。

範例：浮點數

程式語言的浮點數，諸如-1.23、4.56e-7，所有的浮點數字串構成的集合，正是一套正規語言。對應的正規表示式為：

[-+]?[0-9]*\.?[0-9]+([eE][-+]?[0-9]+)?

bool is_float(string s) { s = regex_replace(s, regex("^\\s+"), ""); // 清除開頭連續空白 s = regex_replace(s, regex("\\s+$"), ""); // 清除結尾連續空白 regex e("[-+]?[0-9]*\.?[0-9]+([eE][-+]?[0-9]+)?"); return regex_match(s, e); }

UVa 325

string verification / wildcard string searching

大部分的程式語言都有內建正規表示式的功能，可以驗證一個字串是否符合給定的正規表示式（字串驗證），還可以搜尋一個字串、找到符合正規表示式的字串片段（萬用字元字串搜尋）。

萬用字元字串搜尋當中，當出現多種對齊位置，默認的結果是對齊位置盡量靠左、然後字串長度盡量長。另外也有特殊語法可以限制對齊位置：

   | string | RegExp | pattern  | 意義
---| -------| -------| ---------| --------------------
^  | abcabc | ^ab    | ab       | 一定要出現於字串開頭
   | abcabc | ^a.*   | abcabc   |
---| -------| -------| ---------| --------------------
$  | abcabc | ab$    | Ø        | 一定要出現於字串結尾
   | abcabc | ^a.*c$ | abcabc   |

字串驗證、萬用字元字串搜尋，有著許多實際運用：

例如用正規表示式一口氣涵蓋所有需要的檔案名稱。

例如申請網站帳號、例如網路購物，表單必須輸入帳號名稱、生日、電話、地址、……。可以用正規表示式，驗證使用者輸入的格式是否正確。

例如公司欲偵測員工是否偷玩臉書、偷逛網拍，就在防火牆安裝snort，設計正規表示式，擷取送往臉書與購物網站的封包。

regular language的能力極限

正規語言是循序性的語言，不具備從屬關係、階層關係、巢狀結構、樹狀結構、遞迴結構。

如果你沒勇氣陪我到明天的明天的明天倒不如就忘了就斷了寂寞的昨天的昨天

　明天　　　　　　昨天
　｜　　　　　　　｜
　明天（後天）　　昨天（前天）
　｜
　明天（大後天）

【感情應該要慢慢培養。這前前後後也才六天，用不著這麼激動吧。】

有一個發人省思的故事是：「哥哥說：『爸爸跟我說過：「說話要誠實，不可以
欺騙別人。」但是媽媽也跟我說過：「說話太誠實，常常無意間傷害別人。」』
弟弟說：『老師有說：「子曰：『巧言令色，鮮矣仁。』」，爸爸是對的！』」
這個故事告訴我們：正規語言難以釐清到底誰說了哪句話。

　全文＿＿＿＿＿＿＿＿＿＿＿＿
　｜　　　　　　　　　　　　　｜
　故事說＿＿＿＿＿＿　　　　　我想說
　｜　　　　　　　　｜　　　　｜
　哥哥說＿　　　　　弟弟說　　正規語言
　｜　　　｜　　　　｜
　爸爸說　媽媽說　　老師說
　｜　　　｜　　　　｜
　要誠實　別太誠實　孔子說
　　　　　　　　　　｜
　　　　　　　　　　巧言令色

永和有永和路，中和有中和路，
中和的中和路有接永和的中和路，永和的永和路沒接中和的永和路；
永和的中和路有接永和的永和路，中和的永和路沒接中和的中和路。
永和有中正路，中和有中正路，永和的中正路用景平路接中和的中正路；
永和有中山路，中和有中山路，永和的中山路直接接上了中和的中山路。
永和的中正路接上了永和的中山路，中和的中正路卻不接中和的中山路。
中正橋下來不是中正路，但永和有中正路；
秀朗橋下來也不是秀朗路，但永和也有秀朗路。
永福橋下來不是永福路，永和沒有永福路；
福和橋下來不是福和路，但福和路接的是永福橋。

【這個亂到我實在畫不出階層架構圖，誠徵在地人幫忙畫個純文字版的架構圖。】

教科書經常用下例說明正規語言的能力極限：

連續的「(」緊接著連續的「)」，並且「(」與「)」剛好一樣多的語言。

按照數學定義，正規文法只能是有限長度，但是正規語言可以是有限集合或無限集合。我們可以使用窮舉法、預處理的思路，聯集所有層次的括號，涵蓋這個語言；但是當括號層數不固定、可達無限多層時，就無法用有限長度的正規表示式涵蓋這個語言了。

regular expression         | regular language
---------------------------| ---------------------------
                           | {Ø}
\(\)                       | {Ø, ()}
\(\)|\(\(\)\)              | {Ø, (), (())}
\(\)|\(\(\)\)|\(\(\(\)\)\) | {Ø, (), (()), ((()))}
---------------------------| ---------------------------
not exist                  | {Ø, (), (()), ((())), ...}
                           | it's not a regular language
---------------------------| ---------------------------
\(*\)*                     | {Ø, (, ), ((, (), )), ...}
(\(\))*                    | {Ø, (), ()(), ()()(), ...}

更進一步來說，擁有巢狀括號、括號裡面又有文字的語言，也不是正規語言。實務上我們可以運用大量正規表示式，逐次得到每一層每一個括號裡面的字串，然後建立階層架構；但是當巢狀括號沒有固定的數量，實在是不適合採用這種方式。

諸如四則運算式子、HTML、C程式語言，都不是正規語言，而是接下來介紹的context-free language。

演算法

剖析一個字串，有一個人人都懂的基礎方法，就是窮舉法。此演算法其實就是backtracking。先窮舉字串的分割位置，從左端切下一段子字串；再窮舉子字串的對應文法。

範例：Linux的grep指令

一開始的時候、以及遇到*號的時候，就窮舉各種對齊位置，遞迴下去；其他符號則循序比對。

時間複雜度與正規表示式之中*號的數量有關。無星號，就是普通的字串搜尋，時間複雜度O(TR)；T是字串長度、R是正規表示式長度。有星號，我就不會分析了，或許跟k-partition problem差不多。

bool search(char* text, char* regexp) { if (regexp[0] == '^') return searchhere(text, regexp+1); // 窮舉對齊位置 for (; *text != '\0'; text++) if (searchhere(text, regexp)) return true; // 空字串也得處理 if (*text == '\0' && regexp[0] == '\0') return true; return false; } bool searchhere(char* text, char* regexp) { if (regexp[0] == '\0') return true; if (regexp[1] == '*') return searchstar(text, regexp+2, regexp[0]); if (regexp[0] == '$' && regexp[1] == '\0') return *text == '\0'; if (*text != '\0' && (regexp[0] == '.' || regexp[0] == *text)) return searchhere(text+1, regexp+1); return false; } // 開頭是c* bool searchstar(char* text, char* regexp, char c) { // 字串長度儘可能長 char* t = text; while (*t != '\0' && (c == '.' || *t == c)) t++; // 窮舉對齊位置，從字串最長的情況開始嘗試。 for ( ; t >= text; t--) if (searchhere(t, regexp)) return true; return false; }

UVa 10058

範例：多項式

一項一項剖析，直接採用迴圈語法，不必backtracking。

char s[100] = "-1x^2y^2 + 2xyz + y^1 - 5"; struct Poly {int c, x, y, z;} p[100]; // 一百項 // 彈出數字 void pop(char* s, int& i, int& n) { // 忽略次方符號 if (s[i] == '^') ++i; // 數值 n = 0; bool digit = false; for (; isdigit(s[i]); ++i) { n = n * 10 + s[i] - '0'; digit = true; } if (n == 0 && !digit) n = 1; } void parse(char* s, Poly p[100], int& n) { memset(p, 0, sizeof(Poly)*100); n = 0; tight(s); for (int i=0; s[i]; ++n) { // 正負號 int m = 1; if (s[i] == '+') m = +1, ++i; if (s[i] == '-') m = -1, ++i; // 係數 pop(s, i, p[n].c); p[n].c *= m; // 元與次方 if (s[i] == 'x') pop(s, ++i, p[n].x); if (s[i] == 'y') pop(s, ++i, p[n].y); if (s[i] == 'z') pop(s, ++i, p[n].z); } }

UVa 126 327

範例：正整數四則運算，運算符號沒有優先順序。

由左到右一項一項剖析。

char s[100] = "1 + 2 * 3 - 4 / 5"; // 去除多餘空白 int tight(char* s) { int n = 0; for (int i=0; s[i]; ++i) if (s[i] != ' ') s[n++] = s[i]; s[n++] = '\0'; return n; } int evaluate() { int length = tight(s); char op = 0; int v = 0, n = 0; for (int i=0; i<length; ++i) if (isdigit(s[i])) n = n * 10 + s[i] - '0'; else { if (!op) v = n; else if (op == '+') v += n; else if (op == '-') v -= n; else if (op == '*') v *= n; else if (op == '/') v /= n; op = s[i]; n = 0; } return v; }

演算法

正規表示式等價地轉換成non-deterministic finite automata, NFA。字串搜尋的空間複雜度O(R)，時間複雜度O(TR)。

可以再等價地轉換成deterministic finite automata, DFA。字串搜尋的空間複雜度上升為O(2ᴿ)、時間複雜度降低為O(T)。

UVa 12415 891 1671 1672 ICPC 6670

context-free grammar

一個上下文無關文法，有許多條衍生規則。規則裡面是符號、字元、箭頭。

個位數四則運算文法：
S → SAS
S → (S)
S → 0
S → 1
  :
S → 9
A → +
A → -
A → ×
A → ÷

從起始符號S開始，隨意套用規則、不斷衍生，直到消除所有符號、形成一個字串。

套用各種規則，所得到的各種字串，就是該文法對應的語言。

rule    | string     rule    | string     rule    | string 
--------| -------    --------| -------    --------| -------
        | S                  | S                  | S      
S → SAS | SAS        S → 0   | 0          S → SAS | SAS    
A → ×   | S×S                             S → SAS | SASAS  
S → (S) | (S)×S      rule    | string     S → 1   | SA1AS  
S → 1   | (S)×1      --------| -------    A → -   | SA1-S  
S → SAS | (SAS)×1            | S          S → 7   | 7A1-S  
S → 3   | (3AS)×1    S → (S) | (S)        A → ÷   | 7÷1-S  
S → 2   | (3A2)×1    S → 0   | (0)        S → 3   | 7÷1-3  
A → +   | (3+2)×1

language = {(3+2)×1, 0, (0), 7÷1-3, ...}

一律先消除最左邊的符號，稱作「左衍生leftmost derivation」；一律先消除最右邊的符號，稱作「右衍生rightmost derivation」。調整消除符號的順序，不會改變字串，可以放心調整。

採用左衍生或者右衍生，可以讓別人容易看懂衍生過程，是比較貼心的方式。

                      leftmost derivation   rightmost derivation
rule    | string      rule    | string      rule    | string 
--------| -------     --------| -------     --------| --------
        | S                   | S                   | S      
S → SAS | SAS         S → SAS | SAS         S → SAS | SAS    
A → ×   | S×S         S → (S) | (S)AS       S → 1   | SA1    
S → (S) | (S)×S       S → SAS | (SAS)AS     A → ×   | S×1    
S → 1   | (S)×1       S → 3   | (3AS)AS     S → (S) | (S)×1  
S → SAS | (SAS)×1     A → +   | (3+S)AS     S → SAS | (SAS)×1
S → 3   | (3AS)×1     S → 2   | (3+2)AS     S → 2   | (SA2)×1
S → 2   | (3A2)×1     A → ×   | (3+2)×S     A → +   | (S+2)×1
A → +   | (3+2)×1     S → 1   | (3+2)×1     S → 3   | (3+2)×1

「上下文無關」是指符號不會連帶上下文一起衍生。也就是每條規則的左式，只有一個符號，而不會連帶其他符號和字元。

A   → By    context-free
A   → xBy   context-free
A   → xByCz context-free
A   → xyz   context-free
xAy → B     context-sensitive
xA  → B     context-sensitive
xA  → yB    context-sensitive
AB  → C     context-sensitive

正規語言是上下文無關語言的特例。在上下文無關文法當中，只需三種規則，就能構築任何一種正規語言：

1. A → bB
2. A → b
3. A → Ø

UVa 464

context-free grammar書寫方式：Backus–Naur form

個位數四則運算文法：
<expression> ::= <expression> <operator> <expression>
<expression> ::= "(" <expression> ")"
<expression> ::= "0" | "1" | "2" | "3" | "4" |
                 "5" | "6" | "7" | "8" | "9"
<operator> ::= "+" | "-" | "×" | "÷"

其他比較罕見的還有extended Backus–Naur form、van Wijngaarden form。

parse / evaluate

衍生過程畫成樹狀圖，成為「剖析樹parse tree」。

        |         | parse tree /         |
rule    | string  | concrete syntax tree | abstract syntax tree
--------| ------- | ---------------------| --------------------
        | S       |             S        |           ×  
S → SAS | SAS     |          /  | \      |          / \ 
A → ×   | S×S     |       S     A  S     |         +   1
S → (S) | (S)×S   |     / | \   |  |     |        / \   
S → 1   | (S)×1   |    (  S  )  ×  1     |       3   2  
S → SAS | (SAS)×1 |      /|\             |
S → 3   | (3AS)×1 |     S A S            |
S → 2   | (3A2)×1 |     | | |            |
A → +   | (3+2)×1 |     3 + 2            |

「剖析parse」就是掃描字串、建立剖析樹。「求值evaluate」就是在剖析樹上面，以bottom-up順序進行計算。

先前提到的「曖昧文法ambiguous grammar」就是指：一個字串對應兩種以上的剖析樹。換句話說：有兩種以上的剖析樹可以得到同一個字串。

rule    | string | parse tree
--------| -------| -------------
        | S      |          S   
S → SAS | SAS    |      /   | \ 
S → SAS | SASAS  |    S     A  S
(1st S) |        |  / | \   |  |
S → 1   | SA1AS  | S  A  S  -  3   ambiguous grammar
A → -   | SA1-S  | |  |  |            -----------
S → 7   | 7A1-S  | 7  ÷  1            | S → SAS |
A → ÷   | 7÷1-S  |                    | S → (S) |
S → 3   | 7÷1-3  |                    | S → 0   |
                                      | S → 1   |
rule    | string | parse tree         |   :     |
--------| -------| -------------      | S → 9   |
        | S      |    S               | A → +   |
S → SAS | SAS    | /  |   \           | A → -   |
S → SAS | SASAS  | S  A     S         | A → ×   |
(2nd S) |        | |  |   / | \       | A → ÷   |
S → 1   | SA1AS  | 7  ÷  S  A  S      -----------
A → -   | SA1-S  |       |  |  |
S → 7   | 7A1-S  |       1  -  3
A → ÷   | 7÷1-S  |
S → 3   | 7÷1-3  |

UVa 10906 ICPC 3513

延伸閱讀：四則運算的運算符號計算順序

數學算式必須擁有明確的計算流程，不然每個人的計算結果都會不一樣，永遠得不到共識。也就是說，數學算式只能有唯一一種解讀方式，不能是曖昧文法。

6÷2(1+2)=?
曖昧文法，導致出現兩種解讀方式。

6÷2×(1+2)=?
詳細填入運算符號，只有唯一一種解讀方式。

   6
—————— = ?
2(1+2)
改成適當的運算符號，只有唯一一種解讀方式。

數學算式除了必須詳細填入運算符號之外，也必須嚴謹規定運算符號的結合順序，才能杜絕曖昧文法。

「優先權precedence」是指不同運算符號的結合順序。例如先乘除、後加減。

「結合性associativity」是指相同運算符號的結合順序，普遍採用左結合（從左往右算）或者右結合（從右往左算）。例如加減乘除是左結合、次方是右結合。

precedence    | left associativity | right associativity
--------------| -------------------| -------------------
     +        |           +        |        ^           
    / \       |          / \       |       / \          
   1   ×      |         +   4      |      1   ^         
      / \     |        / \         |         / \        
     ^   4    |       +   3        |        2   ^       
    / \       |      / \           |           / \      
   2   3      |     1   2          |          3   4     
              |                    |                    
  1+2^3×4     |     1+2+3+4        |      1^2^3^4       
= 1+((2^3)×4) |   = ((1+2)+3)+4    |    = 1^(2^(3^4))   

我們可以修改文法，讓文法擁有優先權和結合性；當文法擁有優先權和結合性，就不是曖昧文法。

no precedence       | have precedence     | have precedence
no associativity    | no associativity    | have associativity
--------------------| --------------------| -----------------------
expr → expr + expr  | expr → expr + expr  | expr → expr + term
expr → expr × expr  | expr → term         | expr → term
expr → 1            | term → term × term  | term → term × fact
     :              | term → 1            | term → fact
expr → 9            |      :              | fact → 1
                    | term → 9            |      :
                    |                     | fact → 9
--------------------| --------------------| -----------------------
   expr             |      expr           |           expr       
   / | \            |    /   |   \        |        /    |     \  
expr + expr         | expr   +  expr      |     expr    +    term
  |    / | \        |   |       / | \     |     / | \          | 
  1 expr × expr     | term  expr  +  expr | expr  +  term    fact
      |    / | \    |   |     |        |  |   |      / | \     | 
      2 expr + expr |   1   term     term | term  term × fact  4 
          |      |  |       / | \      |  |   |     |     |      
          3      4  |    term × term   4  | fact  fact    3      
                    |      |     |        |   |     |            
                    |      2     3        |   1     2            
                    |                     |                      
     1+2×3+4        |      1+2×3+4        |      1+2×3+4         
   ≠ 1+(2×(3+4))    |    ≠ 1+((2×3)+4)    |    = (1+(2×3))+4     

文法的左遞迴導致左結合、右遞迴導致右結合。

left recursion        | right recursion
& left associativity  | & right associativity
----------------------| -----------------------
expr → expr + term    | expo → base ^ expo
expr → term           | expo → base
term → 1              | expo → 1
     :                |      :
term → 9              | expo → 9
----------------------| -----------------------
            expr      |     expo               
            / | \     |     / | \              
        expr  +  term | base  ^  expo          
        / | \      |  |   |      / | \         
    expr  +  term  4  |   1  base  ^  expo     
    / | \      |      |        |      / | \    
expr  +  term  3      |        2  base  ^  expo
  |        |          |             |        | 
term       2          |             3      base
  |                   |                      | 
  1                   |                      4 
      1+2+3+4         |       1^2^3^4
    = ((1+2)+3)+4     |     = 1^(2^(3^4))

延伸閱讀：程式語言的運算子優先權

不同運算子之間，有明確的優先權；相同運算子之間，有明確的結合性。

還有parse tree的最底層樹葉，也必須考量計算順序。

int a = 0, b = 0; int get_a() {return a;} int get_b() {return b;} void print_sum(int p, int q, int r, int s) { cout << p + q + r + s; } int main() { print_sum(++a, --b, get_a(), get_b()); return 0; }

parse augment list of print_sum

        ,
       / \
      ,   get_b()
     / \
    ,   get_a()
   / \
++a   --b

在C語言規格書當中，此為unspecified behavior。
無法確定++a、--b、get_a()、get_b()誰先計算。

延伸閱讀：程式語言的if-else結合性

if-else是右結合。

S → if statement then S
S → if statement then A else S
S → statement
A → if statement then A else A
A → statement

無法計算的問題！

判斷context-free grammar是否正確生成給定的context-free language。
判斷context-free grammar是不是曖昧文法。
判斷兩種context-free grammar是否等價、生成同一種context-free language。
計算兩種context-free language的交集。

判斷一種文法是否正確生成一套語言、判斷一支程式是否有無窮迴圈，兩者都是屬於無法計算的問題。因此實務上我們只能設計文法、得到語言；無法設計語言、找出文法。

我們可以小心翼翼的設計文法，盡量避免曖昧文法，盡量讓文法能夠生成我們想要的語言；一如我們小心翼翼的設計程式，盡量避免無窮迴圈，盡量讓程式能夠生成我們想要的結果。

context-free language的能力極限

正規語言處理循序文字，是字串搜尋的終極武器。

上下文無關語言處理巢狀文字，是程式語言的濫觴。

至於有哪些事情是上下文無關語言無法做到的呢？老實說我也不太清楚。交給各位研究吧！

演算法

固定採用「左衍生leftmost derivation」，窮舉每次選中的規則。這個方式可能會造成無窮遞迴。如果改用狀態空間搜尋的DLS、IDA*，就能避免無窮遞迴。

實作時，通常是一條規則就寫一個函式，互相對應。呼叫S()、傳入原字串，就得到剖析結果。

UVa 134 171 293 586

範例：正整數四則運算，運算符號擁有優先順序，有括號。

找到最後計算的運算符號，再將原本字串從中切開，成為左右兩個子字串，分頭遞迴下去。

char s[100] = "(1 + 2 * 3) * ((4 - 5) / 6)"; // 計算 int cal(int lv, char op, int rv) { if (op == '+') return lv + rv; if (op == '-') return lv - rv; if (op == '*') return lv * rv; if (op == '/') return lv / rv; return 0; // crash } // 尋找運算子的位置。左結合，故從右端找。 int findop(int L, int R, char op1, char op2) { int c = 0; for (int i=R; i>=L; --i) { if (s[i] == '(') c++; if (s[i] == ')') c--; if (c == 0 && (s[i] == op1 || s[i] == op2)) return i; } return -1; } // 擷取數值 int number(int L, int R) { int n = 0; for (int i=L; i<=R; ++i) n = n * 10 + s[i] - '0'; return n; } int parse(int L, int R) { // 先找優先權最低的運算符號。最先分解、最後計算。 int M = findop(L, R, '+', '-'); // 找不到低的，再找優先權次低的運算符號。 if (M == -1) findop(L, R, '*', '/'); // 運算符號的左右兩式遞迴下去求得確切數值，然後再計算。 // unspecified behavior：左式、右式，不知先呼叫誰！ if (M != -1) return cal(parse(L, M-1), s[M], parse(M+1, R)); // 括號 if (s[L] == '(' && s[R] == ')') return parse(L+1, M-1); // 數值 return number(L, R); } int evaluate() { return parse(0, tight(s) - 1); }

UVa 533 622 695 10454 11724 10614 11808 1293

範例：括號平衡

遞迴分支只有一個，直接採用迴圈語法、輔以堆疊來實作，不必backtracking。

S → SS
S → [S]
S → (S)
S → Ø

UVa 673 551 442

範例：計算機

UVa 172 198

範例：程式語言

UVa 174 189 342 10151 10757 12421 12422 12423 1090 ICPC 4785

範例：製圖

UVa 692 10155 10467 10562 1152

context-free grammar特殊格式：Chomsky normal form

一套語言可以設計各種不同的文法。為了讓文法簡潔易懂，就有人嚴謹地限定了文法格式。比如Chomsky normal form，文法規則只能是這兩種格式：

1. A → BC    （一個符號衍生兩個符號）
2. A → a     （一個符號衍生一個字元）

context-free grammar很容易改寫成Chomsky normal form──凡是遇到符號太多、字元太多的規則，就分離成新規則。

grammar | Chomsky normal form
--------| -------------------
S → SAS | S → SB
        | B → AS
S → (S) | S → CD
        | C → (
        | D → SE
        | E → )
S → 0   | S → 0
S → 1   | S → 1
  :     |   :
S → 9   | S → 9
A → +   | A → +
A → -   | A → -
A → ×   | A → ×
A → ÷   | A → ÷

其他比較罕見的還有beta normal form、Greibach normal form、Kuroda normal form。

Chomsky normal form與parse tree

文法結構一旦改寫成Chomsky normal form，parse tree就是一棵二元樹，得以設計高效率的資料結構與演算法。

parse tree    | parse tree
              | (Chomsky normal form)
--------------| ---------------------
         S    |           S
      /  | \  |        /     \
   S     A  S |      S        B
 / | \   |  | |    /   \      /\
(  S  )  ×  1 |   C     D    A  S
  /|\         |   |   /  \   |  |
 S A S        |   (  S    E  ×  1
 | | |        |     / \   |
 3 + 2        |    S   B  )
              |    |   /\
              |    3  A  S
              |       |  |
              |       +  2

演算法

剖析一個字串，判斷是否符合context-free grammar。

首先將文法結構改寫成Chomsky normal form，再採用dynamic programming：先窮舉字串的對應規則；再窮舉字串的分割位置，分割成左右兩個子字串，連同對應符號，分別遞迴下去。原始論文採用bottom-up實作方式。

時間複雜度O(T³R)，T為字串長度，R為規則數量。

「matrix chain multiplication」的演算法以及此演算法，兩者的遞迴關係非常相似。因為matrix chain multiplication的演算法可以加速至O(NlogN)，所以此演算法也許還可以加速。

// 假設字串都是小寫字母，符號都是大寫字母。 const int R = 10, T = 100; struct {char x, y, z;} rule[R]; // x=>yz char s[T+1] = "aabba"; int a[T][T]; // DP table int getrules(int r1, int r2) { int r = 0; for (int i=0; i<R; i++) { if (rule[i].z == '\0') continue; int x = rule[i].x - 'A'; int y = rule[i].y - 'A'; int z = rule[i].z - 'A'; if ((r1 & (1 << y)) && (r2 & (1 << z))) r |= (1 << rule[i].x); } return r; } bool Cocke_Younger_Kasami() { memset(a, 0, sizeof(a)); for (int i=0; i<T; i++) { for (int j=0; j<R; j++) if (rule[j].y == s[i]) a[i][i] |= (1 << (rule[j].x - 'A')); // if (!a[i][i]) return false; } // online matrix chain multiplication for (int k=1; k<T; ++k) for (int i=k-1; i>=0; --i) for (int j=k-1; j>=i; --j) a[i][k] |= getrules(a[i][j], a[j+1][k]); int start = 'S' - 'A'; return a[0][T-1] & (1 << start); }

奇技淫巧

bottom-up實作方式當中，可以用文法規則等號右側的兩個符號，替文法規則建立二維索引表格。時間複雜度成為O(T³A³)，A是符號種類數目。

A³是規則種類數目的上限，看似沒有好處。但是當符號種類不超過32種，運用int當作集合的資料結構，讓時間複雜度壓至O(T³A²)。當規則超過A²條，就有好處。

const int R = 10, T = 100; struct {char x, y, z;} rule[R]; // x=>yz int letter[26], symbol[26][26]; // 索引表格 char s[T+1] = "aabba"; int a[T][T]; // DP table int get_rules(int r1, int r2) { int r = 0; for (int i=0; r1>>i; i++) if (r1 & (1 << i)) for (int j=0; r2>>j; j++) if (r2 & (1 << j)) r |= symbol[i][j]; return r; } bool Cocke_Younger_Kasami() { /* 建立索引表 */ memset(letter, 0, sizeof(letter)); memset(symbol, 0, sizeof(symbol)); for (int i=0; i<R; ++i) if (rule[i].z == '\0') { int x = rule[i].x - 'A'; int y = rule[i].y - 'a'; letter[y] |= (1 << x); } else { int x = rule[i].x - 'A'; int y = rule[i].y - 'A'; int z = rule[i].z - 'A'; symbol[y][z] |= (1 << x); } /* dynamic programming */ memset(a, 0, sizeof(a)); for (int i=0; i<T; i++) { // if (!letter[s[i] - 'a']) return false; a[i][i] = letter[s[i] - 'a']; } // 以下同前 // online matrix chain multiplication for (int k=1; k<T; ++k) for (int i=k-1; i>=0; --i) for (int j=k-1; j>=i; --j) a[i][k] |= get_rules(a[i][j], a[j+1][k]); int start = 'S' - 'A'; return a[0][T-1] & (1 << start); }

UVa 10597

http://sunmoon-template.blogspot.tw/2016/10/earley-parser.html

predictive language【尚無正式名稱】

context-free grammar暨剖析演算法，時間複雜度太高，不實用。大家只好調整文法、調整剖析演算法，降低時間複雜度。

魔改過的文法，生成了正體不明的語言，嚴謹程度介於regular language與context-free language之間。這些語言與文法沒有特地取名，直接跟剖析演算法同名。例如LL parser能夠處理的語言與文法，直接稱作LL language與LL grammar。

程式語言，諸如Java、Python，習慣採用魔改的文法暨剖析演算法，諸如LL、LR、LALR。維基百科整理了一份詳細列表：

知名工具ANTLR4、Parboiled2、Yacc。

predictive parser

剖析時，偷看目標字串，以便判斷要套用哪一條文法規則。

LL parser

由上往下建立剖析樹：套用適當規則，衍生目標字串。

第一個L是指：從左往右掃描字串。第二個L是指：左衍生。

grammar  string   top-down parsing
-------  -------  -------------------------------------
S → SAS  (3+2)×1  | rule    | string  | parse tree    |
S → (S)           | --------| ------- | --------------|
S → 0             |         | S       |          S    |
S → 1             | S → SAS | SAS     |       /  | \  |
  :               | S → (S) | (S)AS   |    S     A  S |
S → 9             | S → SAS | (SAS)AS |  / | \   |  | |
A → +             | S → 3   | (3AS)AS | (  S  )  ×  1 |
A → -             | A → +   | (3+S)AS |   /|\         |
A → ×             | S → 2   | (3+2)AS |  S A S        |
A → ÷             | A → ×   | (3+2)×S |  | | |        |
                  | S → 1   | (3+2)×1 |  3 + 2        |
                  -------------------------------------

問題：同一個符號有許多條規則，應該套用哪一條規則呢？

傳統做法：backtracking，分別套用每條規則，各自遞迴下去，嘗試衍生目標字串。時間複雜度太高。

取巧做法：剖析前，求得每條規則衍生的字串們，觀察前綴，區分規則。剖析時，偷看目標字串，就能知道應該套用哪一條規則。

LL(1)文法

先來一個簡單範例。

LL(1)
grammar | language suffix  | category
--------| -----------------| --------
S -> aS | {a, ab, aa, ...} | {a}
S -> bS | {b, ba, bb, ...} | {b}
S -> Ø  | {Ø}              | {Ø}

再來一個普通範例。

LL(1)
grammar | language suffix     | category
--------| --------------------| --------
S → AB  | {x, ax, aax, ...}   | {a, x}
        | × {y, by, bby, ...} |
S → BA  | {y, by, bby, ...}   | {b, y}
        | × {x, ax, aax, ...} |
A → aA  | {ax, aax, ...}      | {a}
A → x   | {x}                 | {x}
B → bB  | {by, bby, ...}      | {b}
B → y   | {y}                 | {y}

再來幾個特殊範例。

LL(0)   | LL(1)   | LL(2)   | LL(3)  
grammar | grammar | grammar | grammar
--------| --------| --------| -------
S → aA  | S → aS  | S → aS  | S → aS 
A → Ø   | S → Ø   | S → a   | S → aa 

再來一個複雜範例。

first set  ：此文法規則之內，第一個字元有哪些可能。
follow set ：此文法規則之右，第一個字元有哪些可能。
predict set：此文法規則之內之右，第一個字元有哪些可能。

LL(1)                              (category)
grammar | first set | follow set | predict set
--------| ----------| -----------| -----------
S → Aa  | {a, b, c} | {Ø}        | {a, b, c}
A → BC  | {Ø, b, c} | {a}        | {a, b, c}
B → b   | {b}       | {c, a}     | {b}
B → Ø   | {Ø}       | {a}        | {a, c}
C → c   | {c}       | {a}        | {c}
C → Ø   | {Ø}       | {a}        | {a}

求得first set，藉此求得follow set，藉此求得predict set。同一個符號的文法規則，predict set沒有交集，即是LL(1)文法。

建立表格、建立自動機

當前符號暨當前字元的表格，以便查詢要套用哪一條規則。

LL(1)                      LL(1)
grammar   | predict set    lookup table
----------| -----------        a b c
1. S → Aa | {a, b, c}        +-------
2. A → BC | {a, b, c}      S | 1 1 1
3. B → b  | {b}            A | 2 2 2
4. B → Ø  | {a, c}         B | 4 3 4
5. C → c  | {c}            C | 6 X 5
6. C → Ø  | {a}

表格納入剖析步驟，形成自動機。剖析只需查表，輔以堆疊。

  | a      | b      | c     
--| -------| -------| ------
S | pop S  | pop S  | pop S 
  | push a | push a | push a
  | push A | push A | push A
--| -------| ------ | ------
A | pop A  | pop A  | pop A 
  | push C | push C | push C
  | push B | push B | push B
--| -------| ------ | ------
B | pop B  | pop B  | pop B 
  |        | push b |       
--| -------| ------ | ------
C | pop C  | false  | pop C 
  |        |        | push c

時間複雜度，建表O(AR)，剖析O(T)。

實務上還有另外兩種實作方式。一、preprocessing：剖析步驟直接寫成程式碼。二、metaprogramming：讀取文法，生成程式碼。大家稱作parser generator。

https://morris821028.github.io/2014/05/11/lesson/compiler-clg-ll(1)/ https://en.wikipedia.org/wiki/LL_parser#Parser_implementation_in_C++

將文法調整成LL(1)文法

一個字元足以區分規則，偷看一個字元，就是LL(1)文法。兩個字元以下是LL(2)文法。三個字元以下是LL(3)文法。以此類推。

如果無法區分規則，那就沒轍了。乖乖使用先前章節的演算法，或者調整文法吧。一般來說，大家習慣調整文法，成為LL(1)文法。

章節開始的範例，個位數四則運算文法，調整成LL(1)。

ambiguous grammar
1. expr → expr + expr
2. expr → expr - expr
3. expr → expr × expr
4. expr → expr ÷ expr
5. expr → ( expr )
6. expr → 0
7. expr → 1
        :

add precedence (new symbol)
1. expr → expr + expr
2. expr → expr - expr
3. expr → term
4. term → term × term
5. term → term ÷ term
6. term → ( expr )
7. term → 0
8. term → 1
        :

add associativity (leftmost recursion)
1. expr → expr + term
2. expr → expr - term
3. expr → term
4. term → term × factor
5. term → term ÷ factor
6. term → factor
7. factor → ( expr )
8. factor → 0
9. factor → 1
          :

LL(1) (rightmost recursion with a character)
1. expr → term termlist
2. termlist → + term termlist
3. termlist → - term termlist
4. termlist → Ø
5. term → factor factorlist
6. factorlist → × factor factorlist
7. factorlist → ÷ factor factorlist
8. factorlist → Ø
9. factor → ( expr )
10. factor → 0
11. factor → 1
           :

LR parser

由下往上建立剖析樹：套用適當規則，目標字串簡化為S。

L是指：從左往右掃描字串。R是指：右衍生。

grammar  string   bottom-up parsing
-------  -------  -------------------------------------
S → SAS  (3+2)×1  | rule    | string  | parse tree    |
S → (S)           | --------| ------- | --------------|
S → 0             |         | (3+2)×1 |          S    |
S → 1             | S → 3   | (S+2)×1 |       /  | \  |
  :               | A → +   | (SA2)×1 |    S     A  S |
S → 9             | S → 2   | (SAS)×1 |  / | \   |  | |
A → +             | S → SAS | (S)×1   | (  S  )  ×  1 |
A → -             | S → (S) | S×1     |   /|\         |
A → ×             | A → ×   | SA1     |  S A S        |
A → ÷             | S → 1   | SAS     |  | | |        |
                  | S → SAS | S       |  3 + 2        |
                  -------------------------------------

reduce-reduce conflict：有許多條規則得到同一組符號，應該套用哪一條規則呢？

解法：偷看目標字串。LL parser採用predict set，LR parser採用follow set。

shift-reduce conflict：應該掃描目標字串（堆疊變長）呢、還是套用規則（堆疊變短）呢？

解法：優先掃描目標字串，導致右結合。優先套用規則，導致左結合。看你喜歡哪一種。

LL parser無此問題。上下文無關文法，左式只有一個符號，毋須掃描目標字串。

建立表格、建立自動機

時間複雜度，建表O(AR)，剖析O(T)。

LL parser與LR parser的差別

對於一條規則而言，左側僅一個符號，右側有多個符號。

對於一條規則而言，LL parser左變右，LR parser右變左。

LL parser的優點：套用規則前，只需比對一個符號。缺點：套用規則時，容易衝突，需要偷看較多字元。

LR parser的優點：套用規則時，不易衝突，只需偷看較少字元。缺點：套用規則前，需要比對多個符號。

LR parser改良版本

SLR：follow set不納入表格，而是另行判斷。優點是表格較小，缺點是reduce-reduce conflict的處理變得不靈活。

LALR：相同行為的格子，進行合併。優點是表格較小，缺點是建表較久。

GLR：遇到曖昧文法，只好使用窮舉法。狀態空間搜尋BFS。

parsing expression language

同樣是魔改。context-free language追加限制條件而得。嚴謹程度介於regular language與context-free language之間。

top-down。

bottom-up。

給定語言（大量字串），求得文法。用於資料壓縮。