Chomsky hierarchy
我之前寫 regular expression 一直會碰上一個問題——
沒有遞迴。後來我一直在思索究竟 regular expression
可否寫成真正的 parser? 我覺得很難，不如直接用真正的
parser generator, 會比寫 regular expression 容易得多。
根據 Chomsky hierarchy,
基本上大部分的程式語言都是屬於 context-free grammar,
所以通常要寫 parser 也是針對 context-free grammar;
然而，regular expression 僅是屬於 regular grammar,
他的層級比 context-free grammar 低了一層，
也就是說，regular expression 確實不可能能夠 parse 出
所有 context-free grammar 的 language.
而這之間的差異，在於 context-free grammar 可以在
右側置放 nonterminal 和 terminal 的組合；
然而 regular grammar 只能放一個 nonterminal?
至於 context-sensitive grammar 更可以在左側置放
terminal 與 nonterminal 的組合。這邊先不管詳細的定義，
還在試圖理解中... 總之，我想大概這就是為什麼 regular expression
難以表達一些比較複雜的 pattern, 也說明出為什麼 regular expression
會讓我有沒有「遞迴」的感覺，他確實是缺少某種程度上的遞迴。
支援遞迴的話呢？那 regular expression 就不再是 regular expression,
他必然會升級到 context-free grammar...
所以我要求的東西大概是不存在吧 :D
因為那超出其定義的範圍內了，就像超人其實不是人這樣？
==
有時候會貪婪地想知道一切
這也是為什麼會有：The Problem with Wikipedia
吧？
學問的終點無止盡啊！偏偏你又能找到好多相似的道理，看得讓人心癢癢的
