[科普中國]-編譯原理

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

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

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

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

1 詞法分析3

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

2 語法分析3

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

3 語義分析3

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

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

1 詞法分析3

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

2 語義分析3

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

3 語法分析3

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

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

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

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

以實(shí)踐為導(dǎo)向的互助式編譯原理教學(xué)(一) 理論與實(shí)踐相銜接6

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

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

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

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

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

1 詞法分析2

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

2 語法分析2

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

3 語義分析2

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

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

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

5 目標(biāo)代碼的生成2

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

6 出錯(cuò)處理2

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

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

源程序是給人看的，本質(zhì)上就是文本文件，可以用Linux中的vi或Windows中的記事本之類的文本編輯程序打開、編寫，但計(jì)算機(jī)無法直接執(zhí)行源程序，需要通過一個(gè)專門的程序?qū)⒃闯绦蚓幾g為計(jì)算機(jī)可執(zhí)行程序，這個(gè)專門的程序就是編譯器。編譯過程主要分為詞法分析、語法分析、中間代碼生成、目標(biāo)代碼生成（忽略預(yù)處理、語義分析、優(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;? }而它在計(jì)算機(jī)中存儲(chǔ)的形式如圖1-36所示。8

?

圖1-36 案例程序的十六進(jìn)制形式8

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

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

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

?

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

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

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

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

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

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

?

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

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

?

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

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

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

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

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

?

圖1-40 中間代碼與目標(biāo)代碼對(duì)應(yīng)的情景示意8

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

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

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

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

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

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

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