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