第一個C語言編譯器是怎樣編寫的？

2021-12-31 15:45 作者:C語言編程__Plus 0人讀過 | 我要投稿

不知道你有沒有想過，某種編程語言的第一個編譯器是怎么來的呢？這不就是“雞生蛋，蛋生雞”的問題嗎？

先說最后的結論：?任何一種語言的第一個編譯器肯定是使用其他語言寫出來的。

作者：Chaobs
鏈接：https://www.cnblogs.com/Chaobs/p/4510768.html

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

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

可見，在C語言實現(xiàn)以前，B語言已經(jīng)可以投入實用了。因此第一個C語言編譯器的原型完全可能是用B語言或者混合B語言與PDP匯編語言編寫的。但是B語言的效率比較低，如果全部用匯編語言來編寫，不僅開發(fā)周期長、維護難度大，更可怕的是失去了高級程序設計語言必需的移植性。

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

先用匯編語言編寫一個C語言的一個子集的編譯器，再通過這個子集去遞推完成完整的C語言編譯器。

詳細的過程如下：

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

至于這里的N是多少，這取決于你的目標語言（這里是C語言）的復雜程度和程序員的編程能力。簡單地說，如果到了某個子集階段，可以很方便地利用現(xiàn)有功能實現(xiàn)C語言時，那么你就找到N了。

下面的圖說明了這個抽象過程：

這張圖是不是有點熟悉？對了就是在將虛擬機的時候見到過，不過這里是CVM（CLanguageVirtualMachine），每種語言都是在每個虛擬層上可以獨立實現(xiàn)編譯的，并且除了C語言外，每一層的輸出都將作為下一層的輸入（最后一層的輸出就是應用程序了）。

這和滾雪球是一個道理。用手（匯編語言）把一小把雪結合在一起，一點點地滾下去就形成了一個大雪球，這大概就是所謂的0生1，1生C，C生萬物吧？

那么這種大膽的子集簡化的方法，是怎么實現(xiàn)的，又有什么理論依據(jù)呢？

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

下面是C99的關鍵字：

仔細看看，其中有很多關鍵字是為了幫助編譯器進行優(yōu)化的，還有一些是用來限定變量、函數(shù)的作用域、鏈接性或者生存周期（函數(shù)沒有）的，這些在編譯器實現(xiàn)的早期根本不必加上，于是可以去掉

auto,restrict,extern,volatile,const,sizeof,static,inline,register,typedef，這樣就形成了C的子集，C3語言，C3語言的關鍵字如下：

再想一想，發(fā)現(xiàn)C3中其實有很多類型和類型修飾符是沒有必要一次性都加上去的，比如三種整型，只要實現(xiàn)int就行了，因此進一步去掉這些關鍵詞，它們是：

unsigned,float,short,char(charisint),signed,_Bool,_Complex,_Imaginary,long，

這樣就形成了我們的C2語言，C2語言關鍵字如下：

繼續(xù)思考，即使是只有18個關鍵字的C2語言，依然有很多，高級的地方，比如基于基本數(shù)據(jù)類型的復合數(shù)據(jù)結構，另外我們的關鍵字表中是沒有寫運算符的，在C語言中的復合賦值運算符->運算符等的++，--等過于靈活的表達方式此時也可以完全刪除掉，因此可以去掉的關鍵字有：enum,struct,union，這樣我們可以得到C1語言的關鍵字：

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