[科普中國]-編譯原理

編譯原理是計算機專業(yè)的一門重要專業(yè)課，旨在介紹編譯程序構(gòu)造的一般原理和基本方法。內(nèi)容包括語言和文法、詞法分析、語法分析、語法制導翻譯、中間代碼生成、存儲管理、代碼優(yōu)化和目標代碼生成。 編譯原理是計算機專業(yè)設(shè)置的一門重要的專業(yè)課程。編譯原理課程是計算機相關(guān)專業(yè)學生的必修課程和高等學校培養(yǎng)計算機專業(yè)人才的基礎(chǔ)及核心課程，同時也是計算機專業(yè)課程中最難及最挑戰(zhàn)學習能力的課程之一。編譯原理課程內(nèi)容主要是原理性質(zhì)，高度抽象1。

基本概念編譯原理即是對高級程序語言進行翻譯的一門科學技術(shù), 我們都知道計算機程序由程序語言編寫而成, 在早期計算機程序語言發(fā)展較為緩慢, 因為計算機存儲的數(shù)據(jù)和執(zhí)行的程序都是由0、1代碼組合而成的, 那么在早期程序員編寫計算機程序時必須十分了解計算機的底層指令代碼通過將這些微程序指令組合排列從而完成一個特定功能的程序, 這就對程序員的要求非常高了。人們一直在研究如何如何高效的開發(fā)計算機程序, 使編程的門檻降低。2

編譯器C語言編譯器是一種現(xiàn)代化的設(shè)備, 其需要借助計算機編譯程序, C語言編譯器的設(shè)計是一項專業(yè)性比較強的工作, 設(shè)計人員需要考慮計算機程序繁瑣的設(shè)計流程, 還要考慮計算機用戶的需求。計算機的種類在不斷增加, 所以, 在對C語言編譯器進行設(shè)計時, 一定要增加其適用性。C語言具有較強的處理能力, 其屬于結(jié)構(gòu)化語言, 而且在計算機系統(tǒng)維護中應用比較多, C語言具有高效率的優(yōu)點, 在其不同類型的計算機中應用比較多。3

C語言編譯器前端設(shè)計編譯過程一般是在計算機系統(tǒng)中實現(xiàn)的, 是將源代碼轉(zhuǎn)化為計算機通用語言的過程。編譯器中包含入口點的地址、名稱以及機器代碼。編譯器是計算機程序中應用比較多的工具, 在對編譯器進行前端設(shè)計時, 一定要充分考慮影響因素, 還要對詞法、語法、語義進行分析。3

1 詞法分析3

詞法分析是編譯器前端設(shè)計的基礎(chǔ)階段, 在這一階段, 編譯器會根據(jù)設(shè)定的語法規(guī)則, 對源程序進行標記, 在標記的過程中, 每一處記號都代表著一類單詞, 在做記號的過程中, 主要有標識符、關(guān)鍵字、特殊符號等類型, 編譯器中包含詞法分析器、輸入源程序、輸出識別記號符, 利用這些功能可以將字號轉(zhuǎn)化為熟悉的單詞。3

2 語法分析3

語法分析是指利用設(shè)定的語法規(guī)則, 對記號中的結(jié)構(gòu)進行標識, 這包括句子、短語等方式, 在標識的過程中, 可以形成特殊的結(jié)構(gòu)語法樹。語法分析對編譯器功能的發(fā)揮有著重要影響, 在設(shè)計的過程中, 一定要保證標識的準確性。3

3 語義分析3

語義分析也需要借助語法規(guī)則, 在對語法單元的靜態(tài)語義進行檢查時, 要保證語法規(guī)則設(shè)定的準確性。在對詞法或者語法進行轉(zhuǎn)化時, 一定要保證語法結(jié)構(gòu)設(shè)置的合法性。在對語法、詞法進行檢查時, 語法結(jié)構(gòu)設(shè)定不合理, 則會出現(xiàn)編譯錯誤的問題。前端設(shè)計對精確性要求比較好, 設(shè)計人員能夠要做好校對工作, 這會影響到編譯的準確性, 如果前端設(shè)計存在失誤, 則會影響C語言編譯的效果。3

C語言編譯器總體設(shè)計C語言編譯器是一種先進的設(shè)備, 其可以將繁瑣復雜的程序轉(zhuǎn)換為機器語言, 具有化繁為簡的功能, 在對C語言編譯器進行劃分的過程中, 需要了解語法構(gòu)成原理, 設(shè)計人員需要靈活掌握語言語法知識, 還要應用C語言代碼轉(zhuǎn)化方式, 在對C語言編譯器進行總體設(shè)計時, 需要從以下幾個方面入手。3

1 詞法分析3

C語言程序具有一定的復雜性, 語法分析是編譯的初級階段, 這一過程主要是對詞法進行掃描, 所以詞法分析階段, 編譯器也被用作是掃描器, 其主要的任務是將源程序中的字符進行連接, 并且對其中的詞語進行識別, 并且對詞匯進行轉(zhuǎn)化, 將其轉(zhuǎn)換為內(nèi)部編碼, 并且對其語法進行分析與標記。單詞符號在編譯的過程中, 一般會被轉(zhuǎn)化為二元式, 單詞類別主要有二進制、分隔符、單詞等, 計算機在正常工作時, 會通過掃描器自動完成詞法掃描工作, 這一過程也會自動將注釋進行刪除, 會將源程序中的單詞進行自動識別, 還會將其轉(zhuǎn)換為內(nèi)部編碼。從工作方式角度來分析, 編譯流程與語法屬于兩種接口方式, 若是從功能上講, 編譯器詞法分分析的過程主要就是將相應的字符源程序進行轉(zhuǎn)換處理, 從而變成單詞串的形式。3

2 語義分析3

將編譯程序轉(zhuǎn)換為一種內(nèi)部表現(xiàn)形式后, 我們將該種內(nèi)部表現(xiàn)形式稱之為中間語言或者是中間代碼, 它含義明確、結(jié)構(gòu)簡單, 屬于一種記號系統(tǒng)。比如一些編譯程序, 基本上沒有中間代碼, 但是為了在實際應用中, 確保機器的獨立運行, 易于實現(xiàn)目標代碼的優(yōu)化, 在許多的編譯程序中均設(shè)置了中間語言。這種中間語言介于機器語言和源程序語言中, 程序相對復雜, 而C語言編譯器卻在很大程度上改變以上現(xiàn)狀, 其語義分析和語法分析相對成熟, 理論和算法比較完善, 可仍舊存在的問題是沒有公認的形式系統(tǒng), 中間代碼仍舊接近于形式化的方法。3

3 語法分析3

語法分析主要是以單詞串形式的源程序作為分析與輸入對象, 其最為根本的目標和任務就是為了以設(shè)計語言的語法規(guī)則為標準, 對源程序的語法結(jié)構(gòu)進行具體的分析, 根據(jù)設(shè)計語言的語法規(guī)則, 對組成這些源程序的語法成分進行分析, 如函數(shù)、下標變量、各種程序語句、各種表達式等等, 并且要通過正確性的語法檢查, 將中間代碼進行階段處理。但是要注意的一點是根據(jù)需要進行了歸約處理, 必然存在著相應語法錯誤, 那么可以將其中全部輸入的符號刪除, 改變上述格局, 進行移進和歸約分析, 并且在此基礎(chǔ)上, 不斷地尋找一個相應的策略, 從而形成有效的語法分析方法。3

編譯原理課程《編譯原理》作為計算機專業(yè)的一門重要專業(yè)課程, 是日后深入研究專業(yè)領(lǐng)域知識的基礎(chǔ)。這門課作為計算機科學與技術(shù)的專業(yè)課, 融合了離散數(shù)學、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、計算機組成原理等多個學科的知識, 屬于綜合性與理論性較強的一門課, 由于編譯原理課程內(nèi)容的以上特點, 目前在實驗教學中仍存在一些問題。編譯原理實驗部分若要設(shè)計制作完整的編譯器, 實驗周期長, 涉及的模塊較多, 各模塊間銜接較復雜, 不易立即看到整體效果。4

傳統(tǒng)編譯原理課程教學中存在的問題計算機類專業(yè)本科生學習本專業(yè)的第一門語言課程是C語言。C語言由于其類型不安全性, 容易出現(xiàn)一些難以捉摸的錯誤, 使得學生難以定位和解決問題。如果能讓學生根據(jù)編譯器提供的提示信息, 精確定位程序中的錯誤類型和位置, 把編譯原理中所學用于實際C語言編程需求, 這既完成了課程的教學內(nèi)容, 也提升了學生的軟件編程和系統(tǒng)分析的能力。5

從普通高等院校的編譯原理教學實際出發(fā), 其課程覆蓋范圍一般僅限于編譯器的前端, 即詞法分析、語法分析和語法制導翻譯等內(nèi)容。這其中包括大量抽象且邏輯復雜的理論知識點, 如形式語言理論、正規(guī)式、有限自動機、上下文無關(guān)文法、屬性文法和語法制導翻譯等。傳統(tǒng)的教學方式強調(diào)知識點的灌輸, 讓學生解決孤立的單一問題, 缺乏各知識點之間的關(guān)聯(lián)。這種“只見樹木, 不見森林”的教學方式會極大地削弱學生的學習積極性, 導致整體效果不佳。5

以實踐為導向的互助式編譯原理教學(一) 理論與實踐相銜接6

理論知識的來源一般都有其確定的問題背景。脫離實際問題來進行理論教學, 對學生實際能力的提升沒有益處。編譯原理課程中的大量理論知識, 存在一種銜接遞進的關(guān)系, 每個知識點的引入和拓展, 都是對于現(xiàn)實遇到問題的解決路徑再現(xiàn)。因此, 整個授課過程就在重現(xiàn)這種解決方案演變的變化歷程。而實現(xiàn)這一目標的關(guān)鍵之處, 是教師從之前的“站到講臺前”變到現(xiàn)在的“坐在學生中”。這一變化絕不僅僅是簡單地將所有問題留給學生, 從“講授”變成“答疑”, 而是從問題設(shè)計、思考啟迪、討論引導到過程管理等各方面都對教師提高了要求。特別是現(xiàn)代高級語言發(fā)展日新月異, 各種新問題層出不窮, 如何在面對開放性的未知問題時, 從系統(tǒng)和整體的角度給出學生解決問題的方式方法, 而不是給出具體每個問題的回答, 這是對教師能力的一種新考驗。6

(二) 編譯器設(shè)計實現(xiàn)方案6

編譯原理課程教學理想情況, 學生應該能夠獨立自主完成小型編譯系統(tǒng)的構(gòu)造。實際教學中, 學生只需吃透關(guān)鍵的幾條原理知識, 如NFA的確定化, LL (1) 文法中FIRST和FOLLOW集合的構(gòu)造,LR (1) 文法中識別活前綴DFA構(gòu)造等, 基本上已經(jīng)滿足了課程考試要求。然而, 僅靠理論學習對實現(xiàn)一個基礎(chǔ)編譯器來說是遠遠不足的。相比較于學生對理論知識的接受程度, 學生自主動手完成編譯系統(tǒng)的能力缺乏就更為明顯。如何面對全體學生, 制定出一套適用的實踐方案, 是課程實際效用的關(guān)鍵。7

編譯技術(shù)的發(fā)展在早期馮諾依曼計算機時期 (20世紀40年代) 程序都是以機器語言編寫, 機器語言就是實際存儲的01代碼, 編寫程序是十分枯燥乏味的。后來匯編語言代替機器語言一符號形式該處操作指令和地址編碼。但匯編語言仍有許多缺點, 閱讀理解起來很難, 而且必須依賴于特定的機器, 如果想使編寫好的程序再另一臺計算機上運行必須重寫。在20實際50年代IBM的John Backus帶領(lǐng)一個研究小組對FORTRAN高級語言及其編譯器進行開發(fā)。編譯程序的自動生成工具初現(xiàn)端倪, 現(xiàn)在很多自動生成工具已經(jīng)廣泛使用例如語法分析工具LEX, 語言分析程序YACC等。在20世紀60年代人們不斷的用自編譯技術(shù)構(gòu)造編譯程序, 即用被編譯的語言本身來實現(xiàn)該語言的編譯程序, 但其基本原理和結(jié)構(gòu)大體相同。經(jīng)過不斷發(fā)展現(xiàn)代編譯技術(shù)已經(jīng)較為成熟, 多種高級語言發(fā)展迅速都離不開編譯技術(shù)的進步。2

編譯的基本流程編譯可以分為五個基本步驟:詞法分析、語法分析、語義分析及中間代碼的生成、優(yōu)化、目標代碼的生成。這是每個編譯器都必須的基本步驟和流程, 從源頭輸入高級語言源程序輸出目標語言代碼。2

1 詞法分析2

詞法分析器是通過詞法分析程序?qū)?gòu)成源程序的字符串從左到右的掃描, 逐個字符地讀, 識別出每個單詞符號, 識別出的符號一般以二元式形式輸出, 即包含符號種類的編碼和該符號的值。詞法分析器一般以函數(shù)的形式存在, 供語法分析器調(diào)用。當然也可以一個獨立的詞法分析器程序存在。完成詞法分析任務的程序稱為詞法分析程序或詞法分析器或掃描器。2

2 語法分析2

語法分析是編譯過程的第二個階段。這階段的任務是在詞法分析的基礎(chǔ)上將識別出的單詞符號序列組合成各類語法短語, 如“語句”, “表達式”等.語法分析程序的主要步驟是判斷源程序語句是否符合定義的語法規(guī)則, 在語法結(jié)構(gòu)上是否正確。而一個語法規(guī)則又稱為文法, 喬姆斯基將文法根據(jù)施加不同的限制分為0型、1型、2型、3型文法, 0型文法又稱短語文法, 1型稱為上下文有關(guān)文法, 2型稱為上下文無關(guān)文法, 3型文法稱為正規(guī)文法, 限制條件依次遞增。2

3 語義分析2

詞法分析注重的是每個單詞是否合法, 以及這個單詞屬于語言中的哪些部分。語法分析的上下文無關(guān)文法注重的是輸入語句是否可以依據(jù)文法匹配產(chǎn)生式。那么, 語義分析就是要了解各個語法單位之間的關(guān)系是否合法。實際應用中就是對結(jié)構(gòu)上正確的源程序進行上下文有關(guān)性質(zhì)的審查, 進行類型審查等。2

4 中間代碼生成與優(yōu)化2

在進行了語法分析和語義分析階段的工作之后, 有的編譯程序?qū)⒃闯绦蜃兂梢环N內(nèi)部表示形式, 這種內(nèi)部表示形式叫做中間語言或中間表示或中間代碼。所謂“中間代碼”是一種結(jié)構(gòu)簡單、含義明確的記號系統(tǒng), 這種記號系統(tǒng)復雜性介于源程序語言和機器語言之間, 容易將它翻譯成目標代碼。另外, 還可以在中間代碼一級進行與機器無關(guān)的優(yōu)化。2

5 目標代碼的生成2

根據(jù)優(yōu)化后的中間代碼, 可生成有效的目標代碼。而通常編譯器將其翻譯為匯編代碼, 此時還需要將匯編代碼經(jīng)匯編器匯編為目標機器的機器語言。2

6 出錯處理2

編譯的各個階段都有可能發(fā)現(xiàn)源碼中的錯誤, 尤其是語法分析階段可能會發(fā)現(xiàn)大量的錯誤, 因此編譯器需要做出錯處理, 報告錯誤類型及錯誤位置等信息。2

編譯過程概述C語言的源程序和對應的可執(zhí)行程序執(zhí)行時在內(nèi)存中的運行結(jié)構(gòu)，實現(xiàn)這一轉(zhuǎn)換的最主要的過程就是編譯。8

源程序是給人看的，本質(zhì)上就是文本文件，可以用Linux中的vi或Windows中的記事本之類的文本編輯程序打開、編寫，但計算機無法直接執(zhí)行源程序，需要通過一個專門的程序?qū)⒃闯绦蚓幾g為計算機可執(zhí)行程序，這個專門的程序就是編譯器。編譯過程主要分為詞法分析、語法分析、中間代碼生成、目標代碼生成（忽略預處理、語義分析、優(yōu)化等）。下面我們依次簡要講解編譯的主要過程。8

詞法分析人眼中看到的源代碼是這樣的：8

? int fun(int a,int b);? int m=10;? int main()? {? int i=4;? int j=5;? m = fun(i,j);? return 0;? }? int fun(int a,int b)? {? int c=0;? c=a+b;? return c;? }而它在計算機中存儲的形式如圖1-36所示。8

?

圖1-36 案例程序的十六進制形式8

這里看不出關(guān)鍵字、運算符、標識符，甚至看不出哪幾個字符屬于同一個符號。編譯的第一階段是詞法分析，目的就是在連續(xù)的字符中識別出一個一個的符號，并盡可能地識別出符號的屬性。8

人們在看C語言源程序時，借助空格、括號等一眼就可以看出標識符、關(guān)鍵字。與人相比，現(xiàn)在計算機的智能還是相當?shù)偷?，無法像人那樣同時看多個字符，只能依據(jù)一個非常機械的“電子版”詞法，一個字符一個字符地識別?！半娮影妗痹~法是將狀態(tài)轉(zhuǎn)換圖的思路融匯在詞法分析器的代碼中得以體現(xiàn)的。詞法分析器從源程序的字符串中識別出一個個符號（token），并按序保存。8

詞法分析的結(jié)果如圖1-37所示。8

?

圖1-37 詞法分析的結(jié)果8

在詞法分析階段能夠識別出一些符號的含義，它們包括關(guān)鍵字、數(shù)字、字符串、分隔符，這些符號的含義不需要其他符號的輔助就能確定本身的含義。比如，“int”一定代表整數(shù)類型，它不可能是一個變量名稱，也不可能是一個運算符。8

而另外一些符號需要通過前后的其他符號才能確定出準確含義。比如“m”，在詞法階段僅能判斷這是一個標識符，但是如果不對所在的句做分析，就無法得知這個標識符代表一個變量還是一個函數(shù)。更多詳細的信息需要對符號所在的句型做分析才能獲得。這部分工作由語法分析來完成。8

語法分析如果說詞法分析的作用是從連續(xù)的字符中識別出標識符、關(guān)鍵字、數(shù)字、運算符并存儲為符號（token）流，語法分析的作用就是從詞法分析識別出的符號流中識別出符合C語言語法的語句。8

因為計算機無法像人那樣同時看多個標識符、關(guān)鍵字、數(shù)字、運算符，無法像人那樣一眼看出這是一個函數(shù)聲明，那是一個if語句，只能非常笨拙地一個符號一個符號去識別。與詞法分析器有些類似，語法分析器也是依據(jù)用計算機表示的語法，一個符號一個符號地識別出符合C語言語法的語句。語法的計算機表示就是產(chǎn)生式。在語法分析器中把通過產(chǎn)生式產(chǎn)生的C語言語法映射成一套模板，并把這套模板融匯在語法分析器的程序中。語法分析器的作用就是將詞法分析器識別出的符號（token）一個一個地與這套模板進行匹配，匹配上這套模板中的某個語法，就可以識別出一句完整的語句，并確定這條語句的語法。8

我們以案例中“int fun(int a，int b);”這條函數(shù)聲明語句為例描述這個過程，它與語句模板的匹配情景如圖1-38所示。8

?

圖1-38 fun函數(shù)聲明語句與模板匹配的結(jié)果8

這段token流最終與函數(shù)聲明模板相匹配，在匹配成功后，計算機就認為此語句為函數(shù)聲明語句，并以語法樹的形式在內(nèi)存中記錄下來，情景如圖1-39所示。8

?

圖1-39 fun函數(shù)聲明語句生成的語法樹8

以樹型結(jié)構(gòu)來記錄分析出的語句是一個非常巧妙、深謀遠慮、通盤考慮的選擇。一方面，樹型結(jié)構(gòu)能夠“記住”源程序全部的“意思”，另一方面，樹型結(jié)構(gòu)更容易對應到運行時結(jié)構(gòu)。8

從語法樹到中間代碼再到目標代碼至此，語法樹已經(jīng)承載了源程序的全部信息，后續(xù)的轉(zhuǎn)換工作就和源程序沒關(guān)系了。8

如果希望一步到位，從語法樹轉(zhuǎn)換為目標代碼，理論上和實際上都是可行的。但計算機存在多種CPU硬件平臺，考慮到程序在不同CPU之間的可移植性，先轉(zhuǎn)換成一個通用的、抽象的“CPU指令”，這就是中間代碼最初的設(shè)計思想。然后根據(jù)具體選定的CPU，將中間代碼落實到具體CPU的目標代碼。8

語法樹是個二維結(jié)構(gòu)，中間代碼是準一維結(jié)構(gòu)，語法樹到中間代碼的轉(zhuǎn)換過程，本質(zhì)上是將二維結(jié)構(gòu)轉(zhuǎn)換為準一維結(jié)構(gòu)的過程。中間代碼特別是RTL已經(jīng)可以和運行時結(jié)構(gòu)一一對應了。如圖1-40所示。8

?

圖1-40 中間代碼與目標代碼對應的情景示意8

運行時結(jié)構(gòu)也是一維的，圖1-40左側(cè)部分的轉(zhuǎn)換結(jié)果將更貼近運行時結(jié)構(gòu)。8

選定具體的CPU、操作系統(tǒng)后，中間代碼就可以轉(zhuǎn)換為目標代碼——匯編代碼（我們配置的是AT&T匯編），這時操作系統(tǒng)的影響還比較小。然后由匯編器依照選定操作系統(tǒng)的目標文件格式，將.s文件轉(zhuǎn)換為具體的目標文件，對于Linux而言是.o文件，對于Windows而言是.obj文件。目標文件中已經(jīng)是選定的CPU的機器指令了。8

最后鏈接器把一個或多個目標文件（庫文件本質(zhì)上也是目標文件）鏈接成符合選定操作系統(tǒng)指定格式的可執(zhí)行文件。8

通過操作系統(tǒng)，可執(zhí)行程序就可以被載入內(nèi)存執(zhí)行，形成前兩節(jié)我們所看到的運行時結(jié)構(gòu)。8

本書后續(xù)內(nèi)容將詳細講解編譯的主要過程：詞法分析、語法分析、中間代碼到目標代碼，然后是匯編與鏈接，最后講解預處理。8

本詞條內(nèi)容貢獻者為:

尚軼倫 - 副教授 - 同濟大學數(shù)學科學學院