歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

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

首先向C語言之父Dennis Ritchie致敬!

當今幾乎所有的實用的編譯器/解釋器(以下統稱編譯器)都是用C語言編寫的,有一些語言比如Clojure,Jython等是基於JVM或者說是用Java實現的,IronPython等是基於.NET實現的,但是Java和C#等本身也要依靠C/C++來實現,等於是間接調用了調用了C。所以衡量某種高級語言的可移植性其實就是在討論ANSI/ISO C的移植性。

C語言是很低級的語言,很多方面都近似於匯編語言,在《Intel 32位匯編語言程序設計》一書中,甚至介紹了手工把簡單的C語言翻譯成匯編的方法。對於編譯器這種系統軟件,用C語言來編寫是很自然不過的,即使是像Python這樣的高級語言依然在底層依賴於C語言(舉Python的例子是因為因特爾的黑客正在嘗試讓Python不需要操作系統就能運行——實際上是免去了BIOS上的一次性C代碼)。現在的學生,學過編譯原理後,只要有點編程能力的都可以實現一個功能簡單的類C語言編譯器。

可是問題來了,不知道你有沒有想過,大家都用C語言或基於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了。下面的圖說明了這個抽象過程:

C語言 CN語言 …… C0語言 匯編語言 機器語言

那麼這種大膽的子集簡化的方法,是怎麼實現的,又有什麼理論依據呢?先介紹一個概念,“自編譯”(Self-Compile),也就是對於某些具有明顯自舉性質的強類型(所謂強類型就是程序中的每個變量必學聲明類型後才能使用,比如C語言,相反有些腳本語言則根本沒有類型這一說法)編程語言,可以借助它們的一個有限小子集,通過有限次數的遞推來實現對它們自身的表述,這樣的語言有C、Pascal、Ada等等,至於為什麼可以自編譯,可以參見清華大學出版社的《編譯原理》,書中實現了一個Pascal的子集的編譯器。總之,已經有CS科學家證明了,C語言理論上是可以通過上面說的CVM的方法實現完整的編譯器的,那麼實際上是怎樣做到簡化的呢?這張圖是不是有點熟悉?對了就是在將虛擬機的時候見到過,不過這裡是CVM(C Language Virtual Machine),每種語言都是在每個虛擬層上可以獨立實現編譯的,並且除了C語言外,每一層的輸出都將作為下一層的輸入(最後一層的輸出就是應用程序了),這和滾雪球是一個道理。用手(匯編語言)把一小把雪結合在一起,一點點地滾下去就形成了一個大雪球,這大概就是所謂的0生1,1生C,C生萬物吧?

下面是C99的關鍵字:

  1. autoenum restrict unsigned
  2. breakexternreturnvoid
  3. casefloatshortvolatile
  4. charforsignedwhile
  5. constgotosizeof_Bool
  6. continueifstatic_Complex
  7. defaultinlinestruct_Imaginary
  8. dointswitch
  9. doublelongtypedef
  10. elseregisterunion
  11. //共37個

仔細看看,其實其中有很多關鍵字是為了幫助編譯器進行優化的,還有一些是用來限定變量、函數的作用域、鏈接性或者生存周期(函數沒有)的,這些在編譯器實現的早期根本不必加上,於是可以去掉auto,restrict,extern,volatile,const,sizeof,static,inline,register,typedef,這樣就形成了C的子集,C3語言,C3語言的關鍵字如下:

  1. enumunsigned
  2. breakreturnvoid
  3. casefloatshort
  4. charforsignedwhile
  5. goto_Bool
  6. continueif_Complex
  7. defaultstruct_Imaginary
  8. dointswitch
  9. doublelong
  10. elseunion
  11. //共27個

再想一想,發現C3中其實有很多類型和類型修飾符是沒有必要一次性都加上去的,比如三種整型,只要實現int就行了,因此進一步去掉這些關鍵詞,它們是:unsigned,float,short,char(char is int),signed,_Bool,_Complex,_Imaginary,long,這樣就形成了我們的C2語言,C2語言關鍵字如下:

  1. enum
  2. breakreturnvoid
  3. case
  4. forwhile
  5. goto
  6. continueif
  7. defaultstruct
  8. dointswitch
  9. double
  10. elseunion
  11. //共18個

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

  1. breakreturnvoid
  2. case
  3. forwhile
  4. goto
  5. continueif
  6. default
  7. dointswitch
  8. double
  9. else
  10. //共15個

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

  1. breakvoid
  2. goto
  3. int
  4. double
  5. //共5個

這已經是簡約的極致了。

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

Copyright © Linux教程網 All Rights Reserved