前言
如果你也在搜索引擎上搜索過(guò)類(lèi)似的關(guān)鍵字灭返,那么你應(yīng)該能夠看到這篇文章。但是文章的最初來(lái)源我并沒(méi)有找到坤邪,索性轉(zhuǎn)載了一篇來(lái)自CSDN的熙含。
CSDN原文地址
首先向C語(yǔ)言之父Dennis Ritchie致敬!
當(dāng)今幾乎所有的實(shí)用的編譯器/解釋器(以下統(tǒng)稱(chēng)編譯器)都是用C語(yǔ)言編寫(xiě)的罩扇,有一些語(yǔ)言比如Clojure,Jython等是基于JVM或者說(shuō)是用Java實(shí)現(xiàn)的婆芦,IronPython等是基于.NET實(shí)現(xiàn)的,但是Java和C#等本身也要依靠C/C++來(lái)實(shí)現(xiàn)喂饥,等于是間接調(diào)用了C。所以衡量某種高級(jí)語(yǔ)言的可移植性其實(shí)就是在討論ANSI/ISO C的移植性肠鲫。
C語(yǔ)言是很低級(jí)的語(yǔ)言员帮,很多方面都近似于匯編語(yǔ)言,在《Intel 32位匯編語(yǔ)言程序設(shè)計(jì)》一書(shū)中导饲,甚至介紹了手工把簡(jiǎn)單的C語(yǔ)言翻譯成匯編的方法捞高。對(duì)于編譯器這種系統(tǒng)軟件,用C語(yǔ)言來(lái)編寫(xiě)是很自然不過(guò)的渣锦,即使是像Python這樣的高級(jí)語(yǔ)言依然在底層依賴(lài)于C語(yǔ)言(舉Python的例子是因?yàn)镮ntel的黑客正在嘗試讓Python不需要操作系統(tǒng)就能運(yùn)行——實(shí)際上是免去了BIOS上的一次性C代碼)∠醺冢現(xiàn)在的學(xué)生,學(xué)過(guò)編譯原理后袋毙,只要有點(diǎn)編程能力的都可以實(shí)現(xiàn)一個(gè)功能簡(jiǎn)單的類(lèi)C語(yǔ)言編譯器型檀。
可是問(wèn)題來(lái)了,不知道你有沒(méi)有想過(guò)听盖,大家都用C語(yǔ)言或基于C語(yǔ)言的語(yǔ)言來(lái)寫(xiě)編譯器胀溺,那么世界上第一個(gè)C語(yǔ)言編譯器又是怎么編寫(xiě)的呢?這不是一個(gè)“雞和蛋”的問(wèn)題……
還是讓我們回顧一下C語(yǔ)言歷史:1970年Tomphson和Ritchie在BCPL(一種解釋型語(yǔ)言)的基礎(chǔ)上開(kāi)發(fā)了B語(yǔ)言皆看,1973年又在B語(yǔ)言的基礎(chǔ)上成功開(kāi)發(fā)出了現(xiàn)在的C語(yǔ)言仓坞。在C語(yǔ)言被用作系統(tǒng)編程語(yǔ)言之前,Tomphson也用過(guò)B語(yǔ)言編寫(xiě)過(guò)操作系統(tǒng)腰吟∥薨#可見(jiàn)在C語(yǔ)言實(shí)現(xiàn)以前,B語(yǔ)言已經(jīng)可以投入實(shí)用了毛雇。因此第一個(gè)C語(yǔ)言編譯器的原型完全可能是用B語(yǔ)言或者混合B語(yǔ)言與PDP匯編語(yǔ)言編寫(xiě)的嫉称。我們現(xiàn)在都知道,B語(yǔ)言的執(zhí)行效率比較低禾乘,但是如果全部用匯編語(yǔ)言來(lái)編寫(xiě)澎埠,不僅開(kāi)發(fā)周期長(zhǎng)、維護(hù)難度大始藕,更可怕的是失去了高級(jí)程序設(shè)計(jì)語(yǔ)言必需的移植性蒲稳。所以早期的C語(yǔ)言編譯器就采取了一個(gè)取巧的辦法:先用匯編語(yǔ)言編寫(xiě)一個(gè)C語(yǔ)言的一個(gè)子集的編譯器氮趋,再通過(guò)這個(gè)子集去遞推完成完整的C語(yǔ)言編譯器。詳細(xì)的過(guò)程如下:
先創(chuàng)造一個(gè)只有C語(yǔ)言最基本功能的子集江耀,記作C0語(yǔ)言剩胁,C0語(yǔ)言已經(jīng)足夠簡(jiǎn)單了,可以直接用匯編語(yǔ)言編寫(xiě)出C0的編譯器祥国。依靠C0已有的功能昵观,設(shè)計(jì)比C0復(fù)雜,但仍然不完整的C語(yǔ)言的又一個(gè)子集C1語(yǔ)言舌稀,其中C0屬于C1啊犬,C1屬于C,用C0開(kāi)發(fā)出C1語(yǔ)言的編譯器壁查。在C1的基礎(chǔ)上設(shè)計(jì)C語(yǔ)言的又一個(gè)子集C2語(yǔ)言觉至,C2語(yǔ)言比C1復(fù)雜,但是仍然不是完整的C語(yǔ)言睡腿,開(kāi)發(fā)出C2語(yǔ)言的編譯器……如此直到CN语御,CN已經(jīng)足夠強(qiáng)大了,這時(shí)候就足夠開(kāi)發(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ò)程:
那么這種大膽的子集簡(jiǎn)化的方法细层,是怎么實(shí)現(xiàn)的惜辑,又有什么理論依據(jù)呢?先介紹一個(gè)概念疫赎,“自編譯”Self-Compile盛撑,也就是對(duì)于某些具有明顯自舉性質(zhì)的強(qiáng)類(lèi)型(所謂強(qiáng)類(lèi)型就是程序中的每個(gè)變量必須聲明類(lèi)型后才能使用,比如C語(yǔ)言捧搞,相反有些腳本語(yǔ)言則根本沒(méi)有類(lèi)型這一說(shuō)法)編程語(yǔ)言抵卫,可以借助它們的一個(gè)有限小子集,通過(guò)有限次數(shù)的遞推來(lái)實(shí)現(xiàn)對(duì)它們自身的表述胎撇,這樣的語(yǔ)言有C介粘、Pascal、Ada等等晚树,至于為什么可以自編譯姻采,可以參見(jiàn)清華大學(xué)出版社的《編譯原理》,書(shū)中實(shí)現(xiàn)了一個(gè)Pascal的子集的編譯器爵憎】祝總之婚瓜,已經(jīng)有計(jì)算機(jī)科學(xué)家證明了,C語(yǔ)言理論上是可以通過(guò)上面說(shuō)的CVM的方法實(shí)現(xiàn)完整的編譯器的刑棵,那么實(shí)際上是怎樣做到簡(jiǎn)化的呢巴刻?這張圖是不是有點(diǎn)熟悉?對(duì)了就是在講虛擬機(jī)的時(shí)候見(jiàn)到過(guò)蛉签,不過(guò)這里是CVM(C Language Virtual Machine)胡陪,每種語(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)物吧?
下面是C99的關(guān)鍵字:
仔細(xì)看看录煤,其實(shí)其中有很多關(guān)鍵字是為了幫助編譯器進(jìn)行優(yōu)化的鳄厌,還有一些是用來(lái)限定變量、函數(shù)的作用域妈踊、鏈接性或者生存周期(函數(shù)沒(méi)有)的了嚎,這些在編譯器實(shí)現(xiàn)的早期根本不必加上,于是可以去掉auto, restrict, extern, volatile, const, sizeof, static, inline, register, typedef廊营,這樣就形成了C的子集歪泳,C3語(yǔ)言,C3語(yǔ)言的關(guān)鍵字如下:
再想一想露筒,發(fā)現(xiàn)C3中其實(shí)有很多類(lèi)型和類(lèi)型修飾符是沒(méi)有必要一次性都加上去的呐伞,比如三種整型,只要實(shí)現(xiàn)int就行了慎式,因此進(jìn)一步去掉這些關(guān)鍵詞伶氢,它們是:unsigned, float, short, char(char 是 int), signed, _Bool, _Complex, _Imaginary, long,這樣就形成了我們的C2語(yǔ)言瘪吏,C2語(yǔ)言關(guān)鍵字如下:
繼續(xù)思考癣防,即使是只有18個(gè)關(guān)鍵字的C2語(yǔ)言,依然有很多高級(jí)的地方掌眠,比如基于基本數(shù)據(jù)類(lèi)型的復(fù)合數(shù)據(jù)結(jié)構(gòu)蕾盯,另外我們的關(guān)鍵字表中是沒(méi)有寫(xiě)運(yùn)算符的,在C語(yǔ)言中的復(fù)合賦值運(yùn)算符->蓝丙、運(yùn)算符的++级遭、– 等過(guò)于靈活的表達(dá)方式此時(shí)也可以完全刪除掉望拖,因此可以去掉的關(guān)鍵字有:enum, struct, union,這樣我們可以得到C1語(yǔ)言的關(guān)鍵字:
接近完美了装畅,不過(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…{}…else if…, 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è)關(guān)鍵字模软,已經(jīng)完全可以用匯編語(yǔ)言快速的實(shí)現(xiàn)了伟骨。通過(guò)逆向分析我們還原了第一個(gè)C語(yǔ)言編譯器的編寫(xiě)過(guò)程,也感受到了前輩科學(xué)家們的智慧和勤勞燃异!我們都不過(guò)是巨人肩膀上的灰塵罷了携狭!0生1,1生C特铝,C生萬(wàn)物暑中,實(shí)在巧妙!