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

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

還是讓我們回顧一下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ǔ)言編寫操作系統(tǒng)。

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

但是，B語(yǔ)言的效率比較低，如果全部用匯編語(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ò)程：

這張圖是不是有點(diǎn)熟悉?對(duì)了，就是在將虛擬機(jī)的時(shí)候見(jiàn)到過(guò)!不過(guò)，這里是CVM(CLanguageVirtualMachine)，每種語(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)物吧?

那么，這種大膽的子集簡(jiǎn)化的方法是怎么實(shí)現(xiàn)的?又有什么理論依據(jù)呢?先介紹一個(gè)概念——“自編譯”(Self-Compile)，也就是對(duì)于某些具有明顯自舉性質(zhì)的強(qiáng)類型(所謂強(qiáng)類型就是程序中的每個(gè)變量必學(xué)聲明類型后才能使用，比如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)有CS科學(xué)家證明了，C語(yǔ)言理論上是可以通過(guò)上面說(shuō)的CVM的方法實(shí)現(xiàn)完整的編譯器的。

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

//共37個(gè)
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個(gè)
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個(gè)
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個(gè)

接近完美了，不過(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...{}...elseif...,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è)
break voidgoto int double

只有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í)在巧妙!

任何一種語(yǔ)言的第一個(gè)編譯器肯定是使用其他語(yǔ)言寫出來(lái)的。那就有一個(gè)問(wèn)題了：第一種語(yǔ)言的第一個(gè)編譯器是怎么來(lái)的呢?哈哈!

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

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

審核編輯：湯梓紅