金日開業——專欄簡介

04-06

在百忙之中也終於算是開了自己的專欄了。說來可笑，本來打算弄有關計算機Organization和Architecture的，結果最後居然跳到編譯的坑了。

總想給自己弄個炫酷的專欄名，最後起名為Discrete Leviathan。霍布斯在《利維坦》一書中描述了一個龐然大物，指的是由人組成的國家，這個龐然大物——利維坦，如何運作，宏觀上，微觀上之類。那麼很顯然，我們接觸的這個龐雜的計算機系統，何嘗不是一個龐然巨物，在無數電子的穿梭之中向世界張牙舞爪。那麼用這個「離散的」利維坦描述這些個帶電的巨物簡直在合適不過。當然，我所創造的「離散利維坦」這個概念應該更加廣泛：不僅是實際的機器，理論上的模型——自動機也是合適的。

那麼此專欄到底是講啥的呢？稍有察覺的讀者會發現三個標籤：編譯原理，形式語言，自動機，它們貌似是弱相關的，其實不然。

儘管當代編譯原理的重心已經放在喪心病狂的搞代碼優化上，但是呢，一個編譯器最根本的核心是這個由高級語言向低級語言轉化的過程，上述的代碼優化也只是一個錦上添花的問題：有人用十句話講的事，有人能用一句話解決。

那麼上述這個轉化的過程，怎麼就能轉化過來呢？你看形式語言，那幾個破production，給人算都未必能算出。

在這裡得提到一人，克林（Kleene），以及他的一個定理，此定理讓無數學彙編費勁的傢伙也搞出了無窮的大新聞：Kleenes Therom。

此定理（證明可以見自己的離散教材）主要是講：這些個語法表達式跟某種自動機是等價的，因此只要給我一個一堆表達式，一個簡單句是主謂賓之類，我就能造一個自動機，跟表達式相同的效果：輸入一句話，首先看看這句話對不對，再理解它的意思是啥。

自動機有是個很有意思的玩意兒，它能根據自己的狀態，根據輸入來決定下一個狀態是啥，輸出的話輸出啥。就像你玩遊戲存了個檔，再打開玩，就跟新玩大有不同。還記得學VHDL的時候有次作業是寫個「自動售飲料機」，之後看到自己離散教材講自動機的一節，例子是「Vending Machine」，當時慶幸：還好中國硬幣就三種，要不狀態表就炸了...可以說自動機是基於離散數學，用的神tm廣泛的一種數學模型，廣泛到以至於你根本不知道這玩意到處都是，比如基本上任何數字電路都是根據自動機的各種變種造出來的。

因為用邏輯電路來套自動機的模型簡直不能再貼，所以幹啥都得套個自動機，連尿池自動沖水那玩意也能畫個狀態轉換圖出來，這不全托克林那定理，噢，原來語法推導跟自動機等價啊，好啊，那就說電腦會聽懂人話嘍。

於是出現了各種各樣的編譯器。

然後這幫子人狂搞一通語言轉化之後發現，自己碼的這孫子講話太羅嗦，就再打算告訴編譯器一點人生經驗——代碼優化。

本來打算介紹一下專欄方向的，實際上寫著寫著發現，看看那三個標籤也就足夠明白了：也就上文那堆不痛不癢，深奧起來卻要人命的玩意兒。

小時候一家三口出去下館子，飯館門上貼著四個字，金日開業。我跟我媽講：看，字錯了，應該是今日。我媽一笑：這麼說吉利。

金日開業，歡迎高人指點，歡迎有興趣者前來探討。