不知道你有沒有想過，某種編程語言的第一個編譯器是怎么來的呢?這不就是“雞生蛋，蛋生雞”的問題嗎?先說最后的結論：任何一種語言的第一個編譯器肯定是使用其他語言寫出來的。

以我們嵌入式開發中經常使用的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了。下面的圖說明了這個抽象過程：

這張圖是不是有點熟悉?對了，就是在將虛擬機的時候見到過!不過，這里是CVM(CLanguageVirtualMachine)，每種語言都是在每個虛擬層上可以獨立實現編譯的，并且除了C語言外，每一層的輸出都將作為下一層的輸入(最后一層的輸出就是應用程序了)。這和滾雪球是一個道理。用手(匯編語言)把一小把雪結合在一起，一點點地滾下去就形成了一個大雪球，這大概就是所謂的0生1，1生C，C生萬物吧?

那么，這種大膽的子集簡化的方法是怎么實現的?又有什么理論依據呢?先介紹一個概念——“自編譯”(Self-Compile)，也就是對于某些具有明顯自舉性質的強類型(所謂強類型就是程序中的每個變量必學聲明類型后才能使用，比如C語言，相反有些腳本語言則根本沒有類型這一說法)編程語言，可以借助它們的一個有限小子集，通過有限次數的遞推來實現對它們自身的表述，這樣的語言有C、Pascal、Ada……至于為什么可以自編譯，可以參見清華大學出版社的《編譯原理》，書中實現了一個Pascal的子集的編譯器。總之，已經有CS科學家證明了，C語言理論上是可以通過上面說的CVM的方法實現完整的編譯器的。

那么，實際上是怎樣做到簡化的呢?下面是C99的關鍵字：

//共37個
auto enum restrict unsigned
break extern return void
case float short volatile
char for signed while
const goto sizeof _Bool
continue if static _Complex
default inline struct _Imaginary
do int switch double long typedef
else register union

//共27個
enum unsigned break return
void case float short char
for signed while goto _Bool
continue if _Complex default
struct _Imaginary do int switch
double long else union

//共18個
enum break return void
case for while goto continue
if default struct do int
switch double else union

break return void case for while
goto continue if default do int
switch double else
//共15個

接近完美了，不過最后一步手筆自然要大一點。這個時候數組和指針也要去掉了，另外C1語言其實仍然有很大的冗雜度，比如控制循環和分支的都有多種表述方法，其實都可簡化成一種。具體來說，循環語句有while循環，do...while循環和for循環，只需要保留while循環就夠了;分支語句又有if...{},if...{}...else,if...{}...elseif...,switch，這四種形式，它們都可以通過兩個以上的if...{}來實現，因此只需要保留if,...{}就夠了。可是再一想，所謂的分支和循環不過是條件跳轉語句罷了，函數調用語句也不過是一個壓棧和跳轉語句罷了，因此只需要goto(未限制的goto)。

因此，大膽去掉所有結構化關鍵字，連函數也沒有，得到的C0語言關鍵字如下：

//共5個
break voidgoto int double

只有5個關鍵字，已經完全可以用匯編語言快速的實現了。通過逆向分析我們還原了第一個C語言編譯器的編寫過程，也感受到了前輩科學家們的智慧和勤勞!我們都不過是巨人肩膀上的灰塵罷了!

0生1，1生C，C生萬物，實在巧妙!

任何一種語言的第一個編譯器肯定是使用其他語言寫出來的。那就有一個問題了：第一種語言的第一個編譯器是怎么來的呢?哈哈!

原文標題：第一個編譯器是怎么來的?

文章出處：【微信公眾號：嵌入式ARM】歡迎添加關注!文章轉載請注明出處。

審核編輯：湯梓紅