第一個C語言編譯器的來源

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

以我們嵌入式開發(fā)中經(jīng)常使用的C語言為例，我們來介紹一下第一個C語言編譯器的來源。

還是讓我們回顧一下C語言歷史：1970年Tomphson和Ritchie在BCPL(一種解釋型語言)的基礎(chǔ)上開發(fā)了B語言，1973年又在B語言的基礎(chǔ)上成功開發(fā)出了現(xiàn)在的C語言。在C語言被用作系統(tǒng)編程語言之前，Tomphson也用過B語言編寫操作系統(tǒng)。

可見，在C語言實(shí)現(xiàn)以前，B語言已經(jīng)可以投入實(shí)用了，因此第一個C語言編譯器的原型完全可能是用B語言或混合B語言與PDP匯編語言編寫的。

但是，B語言的效率比較低，如果全部用匯編語言來編寫，不僅開發(fā)周期長、維護(hù)難度大，更可怕的是失去了高級程序設(shè)計語言必需的移植性。

所以，早期的C語言編譯器就采取了一個取巧的辦法：

先用匯編語言編寫一個C語言的一個子集的編譯器，再通過這個子集去遞推完成完整的C語言編譯器。詳細(xì)的過程如下：先創(chuàng)造一個只有C語言最基本功能的子集，記作C0語言，C0語言已經(jīng)足夠簡單了，可以直接用匯編語言編寫出C0的編譯器。依靠C0已有的功能，設(shè)計比C0復(fù)雜，但仍然不完整的C語言的又一個子集C1語言，其中C0屬于C1，C1屬于C，用C0開發(fā)出C1語言的編譯器。在C1的基礎(chǔ)上設(shè)計C語言的又一個子集C2語言，C2語言比C1復(fù)雜，但是仍然不是完整的C語言，開發(fā)出C2語言的編譯器……如此直到CN，CN已經(jīng)足夠強(qiáng)大了，這時候就足夠開發(fā)出完整的C語言編譯器的實(shí)現(xiàn)了。

至于這里的N是多少，這取決于你的目標(biāo)語言(這里是C語言)的復(fù)雜程度和程序員的編程能力。簡單地說，如果到了某個子集階段，可以很方便地利用現(xiàn)有功能實(shí)現(xiàn)C語言時，那么你就找到N了。下面的圖說明了這個抽象過程：

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

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

那么，實(shí)際上是怎樣做到簡化的呢?下面是C99的關(guān)鍵字：

//共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個

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

因此，大膽去掉所有結(jié)構(gòu)化關(guān)鍵字，連函數(shù)也沒有，得到的C0語言關(guān)鍵字如下：

//共5個
break voidgoto int double

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

0生1，1生C，C生萬物，實(shí)在巧妙!

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

原文標(biāo)題：第一個編譯器是怎么來的?

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

審核編輯：湯梓紅