Language

天地玄黃、宇宙洪荒、日月盈昃、辰宿列張。《千字文》

Language / Grammar

Language是一大堆字串。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。一套Language可以設計許多種不同的Grammar,不過光是學一種Grammar就夠頭痛了。

Grammar理論上必須剛好生成Language之內的所有字串、永不生成Language以外的所有字串。

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
Unrestricted Language

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

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

例如Regular Language用於字串匹配、用於驗證字串格式。例如Context-free Language用於設計程式語言、用於檢索網頁資料。身為一個程式員,其實每天都在不自覺地接觸這些語言的應用。

至於Context-sensitive Language與Unrestricted Language,由於缺乏規律、難以計算,所以鮮少討論。

Regular 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]+)?

UVa 325

String Verification / Wildcard String Matching

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

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

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

字串驗證、萬用字元字串匹配,有著許多實際運用:

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

例如申請網站帳號、例如網路購物,表單必須輸入帳號名稱、生日、電話、地址等。可以用正規表示式,驗證使用者輸入的格式是否正確:http://net.tutsplus.com/tutorials/other/8-regular-expressions-you-should-know/

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

演算法(Backtracking)

此處實作的是常見的grep指令。一開始的時候、以及遇到*號的時候,就窮舉各種匹配位置,遞迴下去判斷是否匹配;其他符號則循序匹配。

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

UVa 10058

演算法(Thompson's Algorithm)

http://swtch.com/~rsc/regexp/regexp1.html

http://swtch.com/~rsc/regexp/

正規表示式等價地轉換成Non-deterministic Finite Automata, NFA。字串匹配的空間複雜度為O(R),時間複雜度為O(TR)。

可以再等價地轉換成Deterministic Finite Automata, DFA。字串匹配的空間複雜度上升為O(2^R)、時間複雜度降低為O(T)。

UVa 12415 891 1671 1672 ICPC 6670

Regular Language的能力極限

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

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

 明天      昨天
 |       |
 明天(後天)  昨天(前天)
 |
 明天(大後天)

【感情應該要慢慢培養。這前前後後也才六天,用不著這麼激動吧。】
有一個發人省思的故事是:「哥哥說:『爸爸跟我說過:「說話要誠實,不可以
欺騙別人。」但是媽媽也跟我說過:「說話太誠實,常常無意間傷害別人。」』
弟弟說:『老師有說:「子曰:『巧言令色,鮮矣仁。』」,爸爸是對的!』」
這個故事告訴我們:正規語言難以釐清到底誰說了哪句話。

 全文____________
 |             |
 故事說______     我想說
 |        |    |
 哥哥說_     弟弟說  正規語言
 |   |    |
 爸爸說 媽媽說  老師說
 |   |    |
 要誠實 別太誠實 孔子說
          |
          巧言令色
永和有永和路,中和有中和路,
中和的中和路有接永和的中和路,永和的永和路沒接中和的永和路;
永和的中和路有接永和的永和路,中和的永和路沒接中和的中和路。
永和有中正路,中和有中正路,永和的中正路用景平路接中和的中正路;
永和有中山路,中和有中山路,永和的中山路直接接上了中和的中山路。
永和的中正路接上了永和的中山路,中和的中正路卻不接中和的中山路。
中正橋下來不是中正路,但永和有中正路;
秀朗橋下來也不是秀朗路,但永和也有秀朗路。
永福橋下來不是永福路,永和沒有永福路;
福和橋下來不是福和路,但福和路接的是永福橋。

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

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

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

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

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

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

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

Context-free Language

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」就是指:一個字串對應兩種以上的Parse Tree。換句話說:有兩種以上的Parse Tree可以得到同一個字串。

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
(ambiguous grammar) | (ambiguous grammar) | (not ambiguous grammar)
--------------------| --------------------| -----------------------
expr -> expr + expr | expr -> expr + expr | expr -> expr + term
expr -> expr × expr | expr -> term        | expr -> term
expr -> 1|2|...|9   | term -> term × term | term -> term × fact
                    | term -> 1|2|...|9   | term -> fact
                    |                     | fact -> 1|2|...|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 at left side)   | (fact at right side)
expr -> expr + term   | fact -> base ^ fact
expr -> term          | fact -> base
term -> 1|2|...|9     | fact -> 1|2|...|9
----------------------| -----------------------
            expr      |     fact               
            / | \     |     / | \              
        expr  +  term | base  +  fact          
        / | \      |  |   |      / | \         
    expr  +  term  4  |   1  base  +  fact     
    / | \      |      |        |      / | \    
expr  +  term  3      |        2  base  +  fact
  |        |          |             |        | 
term       2          |             3      base
  |                   |                      | 
  1                   |                      4 
      1+2+3+4         |       1^2^3^4
    = ((1+2)+3)+4     |     = 1^(2^(3^4))

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

不同運算子之間,有固定的優先權;相同運算子之間,有固定的結合性:http://en.cppreference.com/w/cpp/language/operator_precedence

還有Parse Tree的最底層樹葉,也必須考量計算順序:http://en.cppreference.com/w/cpp/language/eval_order。四則運算的Parse Tree最底層,都是確切數值,不必考量這種問題。

parse augment list of print_sum

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

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

無法計算的問題!

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

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

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

Context-free Language的極限

正規語言處理循序文字,是字串匹配的終極武器。

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

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

Context-free Language: Recursive Descent Parser

演算法

剖析一個字串、建立Parse Tree,有一個人人都懂的基礎方法,就是窮舉法。此演算法其實就是Backtracking而已,主要有兩種窮舉策略:

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

二、先窮舉字串的分割位置,從左端切下一段子字串;再窮舉子字串的對應規則。

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

UVa 134 171 293 586

範例:括號平衡

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

S -> [S] | (S) | SS | Ø

UVa 673 551 442

範例:多項式

一項一項剖析,直接採用迴圈語法,連堆疊都不用了。事實上這是正規語言。

UVa 126 327

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

由左到右一項一項剖析。事實上這是正規語言。

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

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

UVa 533 622 695 10454 11724 10614 11808 1293

範例:計算機

UVa 172 198

範例:程式語言

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

範例:製圖

UVa 692 10155 10467 10562 1152

Context-free Language: Cocke-Younger-Kasami Algorithm

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^3 * R),T為字串長度,R為規則數量。

Matrix Chain Multiplication」的演算法以及此演算法,兩者的遞迴關係非常相似。因為Matrix Chain Multiplication的演算法可以加速至O(NlogN),所以此演算法也許還可以加速。

奇技淫巧

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

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

UVa 10597

Context-free Language: Earley Parser

https://en.wikipedia.org/wiki/Earley_parser

Context-free Language: LL Parser(Under Construction!)

Top-down。

peek / pop

no precedence
1. expr -> expr + expr
2. expr -> expr × expr
3. expr -> x | y | z
4. expr -> ( expr )
no associativity
1. expr -> expr + expr
2. expr -> term
3. term -> term × term
4. term -> x | y | z
5. term -> ( expr )
left derivation
1. expr -> expr + term
2. expr -> term
3. term -> term × factor
4. term -> factor
5. factor -> x | y | z
5. factor -> ( expr )
right derivation, LL(1)
1. expr -> term termlist
2. termlist -> + term termlist
3. termlist -> λ
4. term -> factor factorlist
5. factorlist -> × factor factorlist
6. factorlist ->  λ
7. factor -> x | y | z
8. factor -> ( expr )
   expr             |    expr             |    expr             
   / | \            |    / | \            |    / | \            
expr + expr         | expr + expr         | expr + term         
  |    / | \        |   |      |          |   |      |          
  1 expr × expr     | term   term         |   1    term         
      |    / | \    |   |    / | \        |        / | \        
      2  ( expr )   |   1 term × term     |     term × term     
           / | \    |       |    / | \    |       |    / | \    
        expr + expr |       2  ( expr )   |       2  ( expr )   
          |      |  |            / | \    |            / | \    
          3      4  |         expr + expr |         expr + expr 
                    |           |      |  |           |      |  
      1+2×3+4       |         term   term |         term   term 
 ---> ((1+2)×3)+4   |           |      |  |
                    |           3      4  |           3      4  

Context-free Language: LR Parser(Under Construction!)

Bottom-up。

Context-free Language: Sequitur Algorithm(Under Construction!)

http://en.wikipedia.org/wiki/Sequitur_algorithm