先有雞還是先有蛋？第一個(gè)編譯器是怎么來的？
轉(zhuǎn)自： www.cnblogs.com/Chaobs/p/4510768.html
不知道你有沒有想過，某種編程語(yǔ)言的第一個(gè)編譯器是怎么來的呢？這不就是“雞生蛋，蛋生雞”的問題嗎？
先說最后的結(jié)論：任何一種語(yǔ)言的第一個(gè)編譯器肯定是使用其他語(yǔ)言寫出來的。
以我們嵌入式開發(fā)中經(jīng)常使用的C語(yǔ)言為例，我們來介紹一下第一個(gè)C語(yǔ)言編譯器的來源。
還是讓我們回顧一下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也用過B語(yǔ)言編寫操作系統(tǒng)。
可見，在C語(yǔ)言實(shí)現(xiàn)以前，B語(yǔ)言已經(jīng)可以投入實(shí)用了。因此第一個(gè)C語(yǔ)言編譯器的原型完全可能是用B語(yǔ)言或者混合B語(yǔ)言與PDP匯編語(yǔ)言編寫的。但是B語(yǔ)言的效率比較低，如果全部用匯編語(yǔ)言來編寫，不僅開發(fā)周期長(zhǎng)、維護(hù)難度大，更可怕的是失去了高級(jí)程序設(shè)計(jì)語(yǔ)言必需的移植性。
所以，早期的C語(yǔ)言編譯器就采取了一個(gè)取巧的辦法：
先用匯編語(yǔ)言編寫一個(gè)C語(yǔ)言的一個(gè)子集的編譯器，再通過這個(gè)子集去遞推完成完整的C語(yǔ)言編譯器。
詳細(xì)的過程如下：
先創(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)單地說，如果到了某個(gè)子集階段，可以很方便地利用現(xiàn)有功能實(shí)現(xiàn)C語(yǔ)言時(shí)，那么你就找到N了。
下面的圖說明了這個(gè)抽象過程：
這張圖是不是有點(diǎn)熟悉？對(duì)了就是在將虛擬機(jī)的時(shí)候見到過，不過這里是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ǔ)言則根本沒有類型這一說法）編程語(yǔ)言，可以借助它們的一個(gè)有限小子集，通過有限次數(shù)的遞推來實(shí)現(xiàn)對(duì)它們自身的表述，這樣的語(yǔ)言有C、Pascal、Ada等等，至于為什么可以自編譯，可以參見清華大學(xué)出版社的《編譯原理》，書中實(shí)現(xiàn)了一個(gè)Pascal的子集的編譯器。總之，已經(jīng)有CS科學(xué)家證明了，C語(yǔ)言理論上是可以通過上面說的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
仔細(xì)看看，其中有很多關(guān)鍵字是為了幫助編譯器進(jìn)行優(yōu)化的，還有一些是用來限定變量、函數(shù)的作用域、鏈接性或者生存周期（函數(shù)沒有）的，這些在編譯器實(shí)現(xiàn)的早期根本不必加上，于是可以去掉
auto,restrict,extern,volatile,const,sizeof,static,inline,register,typedef，這樣就形成了C的子集，C3語(yǔ)言，C3語(yǔ)言的關(guān)鍵字如下：
//共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
再想一想，發(fā)現(xiàn)C3中其實(shí)有很多類型和類型修飾符是沒有必要一次性都加上去的，比如三種整型，只要實(shí)現(xiàn)int就行了，因此進(jìn)一步去掉這些關(guān)鍵詞，它們是：
unsigned,float,short,char(charisint),signed,_Bool,_Complex,_Imaginary,long，
這樣就形成了我們的C2語(yǔ)言，C2語(yǔ)言關(guān)鍵字如下：
//共18個(gè)
enum break return void
case for while goto continue
if default struct do int
switch double else union
繼續(xù)思考，即使是只有18個(gè)關(guān)鍵字的C2語(yǔ)言，依然有很多，高級(jí)的地方，比如基于基本數(shù)據(jù)類型的復(fù)合數(shù)據(jù)結(jié)構(gòu)，另外我們的關(guān)鍵字表中是沒有寫運(yùn)算符的，在C語(yǔ)言中的復(fù)合賦值運(yùn)算符->運(yùn)算符等的++，--等過于靈活的表達(dá)方式此時(shí)也可以完全刪除掉，因此可以去掉的關(guān)鍵字有：enum,struct,union，這樣我們可以得到C1語(yǔ)言的關(guān)鍵字：
break return void case for while
goto continue if default do int
switch double else
//共15個(gè)
接近完美了，不過最后一步手筆自然要大一點(diǎn)。這個(gè)時(shí)候數(shù)組和指針也要去掉了，另外C1語(yǔ)言其實(shí)仍然有很大的冗雜度，比如控制循環(huán)和分支的都有多種表述方法，其實(shí)都可簡(jiǎn)化成一種，具體的來說，循環(huán)語(yǔ)句有while循環(huán)，do...while循環(huán)和for循環(huán)，只需要保留while循環(huán)就夠了；分支語(yǔ)句又有if...{},if...{}...else,if...{}...elseif...,switch，這四種形式，它們都可以通過兩個(gè)以上的if...{}來實(shí)現(xiàn)，因此只需要保留if,...{}就夠了?？墒窃僖幌?，所謂的分支和循環(huán)不過是條件跳轉(zhuǎn)語(yǔ)句罷了，函數(shù)調(diào)用語(yǔ)句也不過是一個(gè)壓棧和跳轉(zhuǎn)語(yǔ)句罷了，因此只需要goto（未限制的goto）。
因此大膽去掉所有結(jié)構(gòu)化關(guān)鍵字，連函數(shù)也沒有，得到的C0語(yǔ)言關(guān)鍵字如下：
//共5個(gè)
break voidgoto int double
這已經(jīng)是簡(jiǎn)約的極致了。
只有5個(gè)關(guān)鍵字，已經(jīng)完全可以用匯編語(yǔ)言快速的實(shí)現(xiàn)了。通過逆向分析我們還原了第一個(gè)C語(yǔ)言編譯器的編寫過程，也感受到了前輩科學(xué)家們的智慧和勤勞！我們都不過是巨人肩膀上的灰塵罷了！
0生1，1生C，C生萬(wàn)物，實(shí)在巧妙！
任何一種語(yǔ)言的第一個(gè)編譯器肯定是使用其他語(yǔ)言寫出來的。那就有一個(gè)問題了：第一種語(yǔ)言的第一個(gè)編譯器是怎么來的呢？哈哈！
推薦閱讀
我的博客：www.wangchaochao.top
我的公眾號(hào)：mcu149
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。文章僅代表作者個(gè)人觀點(diǎn)，不代表本平臺(tái)立場(chǎng)，如有問題，請(qǐng)聯(lián)系我們，謝謝！
下載文檔
