當(dāng)今幾乎所有的實(shí)用的編譯器/解釋器（以下統(tǒng)稱編譯器）都是用 C 語(yǔ)言編寫的，有一些語(yǔ)言比如 Clojure,Jython 等是基于 JVM 或者說(shuō)是用 Java 實(shí)現(xiàn)的，IronPython 等是基于 .NET 實(shí)現(xiàn)的，但是 Java 和 C# 等本身也要依靠 C/C++ 來(lái)實(shí)現(xiàn)，等于是間接調(diào)用了 C。所以衡量某種高級(jí)語(yǔ)言的可移植性其實(shí)就是在討論 ANSI/ISO C 的移植性。
C 語(yǔ)言是很低級(jí)的語(yǔ)言，很多方面都近似于匯編語(yǔ)言，在《Intel 32 位匯編語(yǔ)言程序設(shè)計(jì)》一書中，甚至介紹了手工把簡(jiǎn)單的 C 語(yǔ)言翻譯成匯編的方法。對(duì)于編譯器這種系統(tǒng)軟件，用 C 語(yǔ)言來(lái)編寫是很自然不過(guò)的，即使是像 Python 這樣的高級(jí)語(yǔ)言依然在底層依賴于 C 語(yǔ)言?，F(xiàn)在的學(xué)生，學(xué)過(guò)編譯原理后，只要有點(diǎn)編程能力的都可以實(shí)現(xiàn)一個(gè)功能簡(jiǎn)單的類 C 語(yǔ)言編譯器。
可是問(wèn)題來(lái)了，不知道你有沒(méi)有想過(guò)，大家都用 C 語(yǔ)言或基于 C 語(yǔ)言的語(yǔ)言來(lái)寫編譯器，那么世界上第一個(gè) C 語(yǔ)言編譯器又是怎么編寫的呢？這不是一個(gè)“雞和蛋”的問(wèn)題……
還是讓我們回顧一下 C 語(yǔ)言歷史：1970 年 Tomphson 和 Ritchie 在 BCPL（一種解釋型語(yǔ)言）的基礎(chǔ)上開發(fā)了 B 語(yǔ)言，1973 年又在 B 語(yǔ)言的基礎(chǔ)上成功開發(fā)出了現(xiàn)在的 C 語(yǔ)言。在 C 語(yǔ)言被用作系統(tǒng)編程語(yǔ)言之前，Tomphson 也用過(guò) B 語(yǔ)言編寫過(guò)操作系統(tǒng)。可見(jiàn)在 C 語(yǔ)言實(shí)現(xiàn)以前，B 語(yǔ)言已經(jīng)可以投入實(shí)用了。因此第一個(gè) C 語(yǔ)言編譯器的原型完全可能是用 B 語(yǔ)言或者混合 B 語(yǔ)言與 PDP 匯編語(yǔ)言編寫的。我們現(xiàn)在都知道，B 語(yǔ)言的執(zhí)行效率比較低，但是如果全部用匯編語(yǔ)言來(lái)編寫，不僅開發(fā)周期長(zhǎng)、維護(hù)難度大，更可怕的是失去了高級(jí)程序設(shè)計(jì)語(yǔ)言必需的移植性。所以早期的 C 語(yǔ)言編譯器就采取了一個(gè)取巧的辦法：先用匯編語(yǔ)言編寫一個(gè) C 語(yǔ)言的一個(gè)子集的編譯器，再通過(guò)這個(gè)子集去遞推完成完整的 C 語(yǔ)言編譯器。詳細(xì)的過(guò)程如下：
先創(chuàng)造一個(gè)只有 C 語(yǔ)言最基本功能的子集，記作 C0 語(yǔ)言，C0 語(yǔ)言已經(jīng)足夠簡(jiǎn)單了，可以直接用匯編語(yǔ)言編寫出 C0 的編譯器。依靠 C0 已有的功能，設(shè)計(jì)比 C0 復(fù)雜，但仍然不完整的 C 語(yǔ)言的又一個(gè)子集 C1 語(yǔ)言，其中 C0 屬于 C1，C1 屬于 C，用 C0 開發(fā)出 C1 語(yǔ)言的編譯器。在 C1 的基礎(chǔ)上設(shè)計(jì) C 語(yǔ)言的又一個(gè)子集 C2 語(yǔ)言，C2 語(yǔ)言比 C1 復(fù)雜，但是仍然不是完整的 C 語(yǔ)言，開發(fā)出 C2 語(yǔ)言的編譯器……如此直到 CN，CN 已經(jīng)足夠強(qiáng)大了，這時(shí)候就足夠開發(fā)出完整的 C 語(yǔ)言編譯器的實(shí)現(xiàn)了。至于這里的 N 是多少，這取決于你的目標(biāo)語(yǔ)言（這里是 C 語(yǔ)言）的復(fù)雜程度和程序員的編程能力——簡(jiǎn)單地說(shuō)，如果到了某個(gè)子集階段，可以很方便地利用現(xiàn)有功能實(shí)現(xiàn) C 語(yǔ)言時(shí)，那么你就找到 N 了。下面的圖說(shuō)明了這個(gè)抽象過(guò)程：
那么這種大膽的子集簡(jiǎn)化的方法，是怎么實(shí)現(xiàn)的，又有什么理論依據(jù)呢？先介紹一個(gè)概念，“自編譯”Self-Compile，也就是對(duì)于某些具有明顯自舉性質(zhì)的強(qiáng)類型（所謂強(qiáng)類型就是程序中的每個(gè)變量必須聲明類型后才能使用，比如 C 語(yǔ)言，相反有些腳本語(yǔ)言則根本沒(méi)有類型這一說(shuō)法）編程語(yǔ)言，可以借助它們的一個(gè)有限小子集，通過(guò)有限次數(shù)的遞推來(lái)實(shí)現(xiàn)對(duì)它們自身的表述，這樣的語(yǔ)言有 C、Pascal、Ada 等等，至于為什么可以自編譯，可以參見(jiàn)清華大學(xué)出版社的《編譯原理》，書中實(shí)現(xiàn)了一個(gè) Pascal 的子集的編譯器?？傊?，已經(jīng)有計(jì)算機(jī)科學(xué)家證明了，C 語(yǔ)言理論上是可以通過(guò)上面說(shuō)的 CVM 的方法實(shí)現(xiàn)完整的編譯器的，那么實(shí)際上是怎樣做到簡(jiǎn)化的呢？這張圖是不是有點(diǎn)熟悉？對(duì)了就是在講虛擬機(jī)的時(shí)候見(jiàn)到過(guò)，不過(guò)這里是 CVM（C Language Virtual Machine），每種語(yǔ)言都是在每個(gè)虛擬層上可以獨(dú)立實(shí)現(xiàn)編譯的，并且除了 C 語(yǔ)言外，每一層的輸出都將作為下一層的輸入（最后一層的輸出就是應(yīng)用程序了），這和滾雪球是一個(gè)道理。用手（匯編語(yǔ)言）把一小把雪結(jié)合在一起，一點(diǎn)點(diǎn)地滾下去就形成了一個(gè)大雪球，這大概就是所謂的 0 生 1，1 生 C，C 生萬(wàn)物吧？
下面是 C99 的關(guān)鍵字：
仔細(xì)看看，其實(shí)其中有很多關(guān)鍵字是為了幫助編譯器進(jìn)行優(yōu)化的，還有一些是用來(lái)限定變量、函數(shù)的作用域、鏈接性或者生存周期（函數(shù)沒(méi)有）的，這些在編譯器實(shí)現(xiàn)的早期根本不必加上，于是可以去掉 auto, restrict, extern, volatile, const, sizeof, static, inline, register, typedef，這樣就形成了 C 的子集，C3 語(yǔ)言，C3 語(yǔ)言的關(guān)鍵字如下：
再想一想，發(fā)現(xiàn) C3 中其實(shí)有很多類型和類型修飾符是沒(méi)有必要一次性都加上去的，比如三種整型，只要實(shí)現(xiàn) int 就行了，因此進(jìn)一步去掉這些關(guān)鍵詞，它們是：unsigned, float, short, char(char 是 int), signed, _Bool, _Complex, _Imaginary, long，這樣就形成了我們的C2語(yǔ)言，C2 語(yǔ)言關(guān)鍵字如下：
繼續(xù)思考，即使是只有 18 個(gè)關(guān)鍵字的 C2 語(yǔ)言，依然有很多高級(jí)的地方，比如基于基本數(shù)據(jù)類型的復(fù)合數(shù)據(jù)結(jié)構(gòu)，另外我們的關(guān)鍵字表中是沒(méi)有寫運(yùn)算符的，在 C 語(yǔ)言中的復(fù)合賦值運(yùn)算符 ->、運(yùn)算符的 ++、–– 等過(guò)于靈活的表達(dá)方式此時(shí)也可以完全刪除掉，因此可以去掉的關(guān)鍵字有：enum, struct, union，這樣我們可以得到 C1 語(yǔ)言的關(guān)鍵字：
接近完美了，不過(guò)最后一步手筆自然要大一點(diǎn)。這個(gè)時(shí)候數(shù)組和指針也要去掉了，另外 C1 語(yǔ)言其實(shí)仍然有很大的冗雜度，比如控制循環(huán)和分支的都有多種表述方法，其實(shí)都可簡(jiǎn)化成一種，具體的來(lái)說(shuō)，循環(huán)語(yǔ)句有 while 循環(huán)，do…while 循環(huán)和 for 循環(huán)，只需要保留while循環(huán)就夠了；分支語(yǔ)句又有 if…{}, if…{}…else, if…{}…else if…, switch，這四種形式，它們都可以通過(guò)兩個(gè)以上的 if…{} 來(lái)實(shí)現(xiàn)，因此只需要保留 if,…{} 就夠了?？墒窃僖幌?，所謂的分支和循環(huán)不過(guò)是條件跳轉(zhuǎn)語(yǔ)句罷了，函數(shù)調(diào)用語(yǔ)句也不過(guò)是一個(gè)壓棧和跳轉(zhuǎn)語(yǔ)句罷了，因此只需要 goto（未限制的 goto）。因此大膽去掉所有結(jié)構(gòu)化關(guān)鍵字，連函數(shù)也沒(méi)有，得到的 C0 語(yǔ)言關(guān)鍵字如下：
只有 5 個(gè)關(guān)鍵字，已經(jīng)完全可以用匯編語(yǔ)言快速的實(shí)現(xiàn)了。通過(guò)逆向分析我們還原了第一個(gè) C 語(yǔ)言編譯器的編寫過(guò)程，也感受到了前輩科學(xué)家們的智慧和勤勞！我們都不過(guò)是巨人肩膀上的灰塵罷了！0 生 1，1 生 C，C 生萬(wàn)物，實(shí)在巧妙！
