1、第一章第一章 編譯程序概論編譯程序概論學(xué)習(xí)目標(biāo)：學(xué)習(xí)目標(biāo)：v掌握：編譯的各個(gè)階段掌握：編譯的各個(gè)階段v理解：編譯程序的概念理解：編譯程序的概念v了解：解釋器，編譯程序的結(jié)構(gòu)和組合了解：解釋器，編譯程序的結(jié)構(gòu)和組合1.11.1 什么是編譯程序什么是編譯程序1.21.2 編譯過(guò)程概述編譯過(guò)程概述1.31.3 編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu)1.41.4 編譯階段的組合編譯階段的組合1.51.5 編譯技術(shù)和軟件工具編譯技術(shù)和軟件工具1.11.1 什么是編譯程序什么是編譯程序1.1. 編譯程序（編譯程序（compiler）將用將用高級(jí)語(yǔ)言高級(jí)語(yǔ)言（如（如FORTRAN,PASCALFORTRAN,PASC

2、AL或或C C）書(shū)寫(xiě)）書(shū)寫(xiě)的程序翻譯成等價(jià)的的程序翻譯成等價(jià)的低級(jí)語(yǔ)言低級(jí)語(yǔ)言程序（如程序（如匯編匯編語(yǔ)言或機(jī)器語(yǔ)言語(yǔ)言或機(jī)器語(yǔ)言），這種翻譯程序稱(chēng)為編譯），這種翻譯程序稱(chēng)為編譯程序程序(compiler)。編譯程序的輸入對(duì)象稱(chēng)為編譯程序的輸入對(duì)象稱(chēng)為源程序源程序(Source program)輸出對(duì)象稱(chēng)為輸出對(duì)象稱(chēng)為目標(biāo)程序目標(biāo)程序（Targer or Object program）高級(jí)語(yǔ)高級(jí)語(yǔ)言程序言程序編譯程序編譯程序低級(jí)語(yǔ)低級(jí)語(yǔ)言程序言程序出錯(cuò)和警告信息出錯(cuò)和警告信息2.2. 解釋器解釋器(interpreter)與編譯器與編譯器共同點(diǎn)：都是語(yǔ)言的一個(gè)實(shí)現(xiàn)系統(tǒng)共同點(diǎn)：都是語(yǔ)言的一個(gè)實(shí)現(xiàn)

3、系統(tǒng)不同點(diǎn)：不同點(diǎn)：o解釋器是源程序的一個(gè)解釋器是源程序的一個(gè)執(zhí)行系統(tǒng)執(zhí)行系統(tǒng)，工作結(jié)果得到，工作結(jié)果得到源程序的執(zhí)行結(jié)果；源程序的執(zhí)行結(jié)果；o編譯器是源程序的編譯器是源程序的轉(zhuǎn)換系統(tǒng)轉(zhuǎn)換系統(tǒng)，工作結(jié)果得到等價(jià)，工作結(jié)果得到等價(jià)于源程序的某種目標(biāo)程序于源程序的某種目標(biāo)程序解釋程序解釋程序解釋器和編譯器解釋器和編譯器編譯程序編譯程序源程序源程序源程序源程序數(shù)據(jù)數(shù)據(jù)計(jì)算結(jié)果計(jì)算結(jié)果目標(biāo)程序目標(biāo)程序練習(xí)：v例1：編譯器和解釋器是兩種高級(jí)語(yǔ)言處理程序，與編譯器相比， 。 A、解釋器不參與運(yùn)行控制，程序執(zhí)行的速度慢 B、解釋器參與運(yùn)行控制，程序執(zhí)行的速度慢 C、解釋器參與運(yùn)行控制，程序執(zhí)行的速度快 D、

4、解釋器不參與運(yùn)行控制，程序執(zhí)行的速度快提高：v解釋型：直接執(zhí)行源程序或源程序的內(nèi)部形式，其最大的特點(diǎn)是不產(chǎn)生目標(biāo)程序，每使用一次就要解釋一次。v翻譯型：第一次使用時(shí)將可執(zhí)行語(yǔ)句翻譯成對(duì)應(yīng)的機(jī)器代碼并保存下來(lái)，之后直接使用保持的機(jī)器碼，故運(yùn)行效率高。效率高！效率高！靈活！靈活！擴(kuò)展：程序設(shè)計(jì)語(yǔ)言分類(lèi)分類(lèi)分類(lèi)主要特點(diǎn)主要特點(diǎn)代表代表命令式命令式( (過(guò)程式過(guò)程式) )基于動(dòng)作的語(yǔ)言Fortran，c，Pascal函數(shù)式函數(shù)式以表操作進(jìn)行處理Lisp，ML面向?qū)ο竺嫦驅(qū)ο?對(duì)象與類(lèi)是核心概念，封裝、繼承和多態(tài)是核心機(jī)制C+，SmallTalk，Java，C# ,Python邏輯程序邏輯程序設(shè)計(jì)設(shè)計(jì)以

5、形式邏輯為基礎(chǔ)Prolog、VHDL、VerLog面向方面面向方面隔離橫切式系統(tǒng)關(guān)注點(diǎn)Aspect腳本腳本編寫(xiě)腳本使用Python、Javascript練習(xí)：v例1： 可用于編寫(xiě)?yīng)毩⒊绦蚝涂焖倌_本的語(yǔ)言是 (20) 。(20) APython BProlog CJava DC#v例2：下面關(guān)于程序語(yǔ)言的敘述，錯(cuò)誤的是（22）A.腳本語(yǔ)言屬于動(dòng)態(tài)語(yǔ)言，其程序結(jié)構(gòu)可以在運(yùn)行中改變 B.腳本語(yǔ)言一般通過(guò)腳本引擎解釋執(zhí)行，不產(chǎn)生獨(dú)立保存的目標(biāo)程序C.php、JavaScript屬于靜態(tài)語(yǔ)言，其所有成分可在編譯時(shí)確定 D.C語(yǔ)言屬于靜態(tài)語(yǔ)言，其所有成分可在編譯時(shí)確定練習(xí)：v例3下列敘述中錯(cuò)誤的是（22）

6、。A.面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言可支持過(guò)程化的程序設(shè)計(jì) B.給定算法的時(shí)間復(fù)雜性與實(shí)現(xiàn)該算法所采用的程序設(shè)計(jì)語(yǔ)言無(wú)關(guān)C.與匯編語(yǔ)言相比，采用腳本語(yǔ)言編程可獲得更高的運(yùn)行效率 D.面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言不支持對(duì)一個(gè)對(duì)象的成員變量進(jìn)行直接訪(fǎng)問(wèn)面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言不支持對(duì)成員變量進(jìn)行直接訪(fǎng)問(wèn)需預(yù)處理的源程序需預(yù)處理的源程序預(yù)處理程序預(yù)處理程序源程序源程序編譯程序編譯程序目標(biāo)匯編程序目標(biāo)匯編程序匯編程序匯編程序可再裝配的機(jī)器代碼可再裝配的機(jī)器代碼裝配裝配/連接連接-編輯程序編輯程序絕對(duì)機(jī)器代碼絕對(duì)機(jī)器代碼可再裝配目標(biāo)文件可再裝配目標(biāo)文件3.3. 高級(jí)語(yǔ)言程序的處理過(guò)程高級(jí)語(yǔ)言程序的處理過(guò)程編譯程序的基本任務(wù)：

7、編譯程序的基本任務(wù)：將源語(yǔ)言程序翻譯成等將源語(yǔ)言程序翻譯成等價(jià)的目標(biāo)語(yǔ)言程序價(jià)的目標(biāo)語(yǔ)言程序4. 編譯程序的發(fā)展編譯程序的發(fā)展第一個(gè)編譯程序的出現(xiàn)：第一個(gè)編譯程序的出現(xiàn)：2020世紀(jì)世紀(jì)5050年代年代早期，主要將算術(shù)公式翻譯成機(jī)器代碼早期，主要將算術(shù)公式翻譯成機(jī)器代碼2020世紀(jì)世紀(jì)5050年代中期，一批編譯系統(tǒng)程序年代中期，一批編譯系統(tǒng)程序開(kāi)發(fā)成功開(kāi)發(fā)成功2020世紀(jì)世紀(jì)5050年代末，開(kāi)始研究編譯程序的年代末，開(kāi)始研究編譯程序的自動(dòng)生成工具自動(dòng)生成工具2020世紀(jì)世紀(jì)6060年代，研究使用自展技術(shù)年代，研究使用自展技術(shù)并行編譯技術(shù)并行編譯技術(shù)1.2 1.2 編譯程序概述編譯程序概述v一個(gè)

8、編譯程序的整個(gè)工作過(guò)程是劃分成一個(gè)編譯程序的整個(gè)工作過(guò)程是劃分成階段進(jìn)行的，每個(gè)階段將源程序從一種階段進(jìn)行的，每個(gè)階段將源程序從一種表示形式轉(zhuǎn)換成另一種表示形式。表示形式轉(zhuǎn)換成另一種表示形式。v典型的劃分方法：典型的劃分方法：目標(biāo)程序目標(biāo)程序源程序源程序詞法分析詞法分析語(yǔ)法分析語(yǔ)法分析語(yǔ)義分析語(yǔ)義分析中間代碼生成中間代碼生成代碼優(yōu)化代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼生成表格管理表格管理出錯(cuò)處理出錯(cuò)處理編譯的各個(gè)階段編譯的各個(gè)階段1.1.詞法分析詞法分析 (lexical analysis or scanning)v任務(wù)任務(wù): :從左到右一個(gè)字符一個(gè)字符地讀入從左到右一個(gè)字符一個(gè)字符地讀入源程序，對(duì)構(gòu)

9、成源程序的字符流進(jìn)行掃描源程序，對(duì)構(gòu)成源程序的字符流進(jìn)行掃描和分解，從而識(shí)別出一個(gè)個(gè)和分解，從而識(shí)別出一個(gè)個(gè)單詞單詞(Token)(Token)。邏輯上緊密相連的邏輯上緊密相連的一組字符，這些字一組字符，這些字符具有集體含義。符具有集體含義。單詞：標(biāo)識(shí)符，基本字，算符，界符等單詞：標(biāo)識(shí)符，基本字，算符，界符等例例: :源程序片斷源程序片斷begin var sum,first,count:real;begin var sum,first,count:real;sum:=first+countsum:=first+count* *10 10 end.end. r r0 0u u; ; ; s s

10、t tl li ia af fe e, ,r rt t: :n nm mu uu us sa ac cr ro ov v, ,n ni ig ge eb bs* *1 1t tn nu uo oc ct t+ +s si ir rf f= =: :m m. . n nd d e e 源程序在文件中的表示源程序在文件中的表示 (基本字基本字,real)(標(biāo)識(shí)符標(biāo)識(shí)符,first)(冒號(hào)冒號(hào), :)(逗號(hào)逗號(hào), ,)(標(biāo)識(shí)符標(biāo)識(shí)符,count)(分號(hào)分號(hào), ;)(基本字基本字,var)(逗號(hào)逗號(hào), ,)(標(biāo)識(shí)符標(biāo)識(shí)符,sum)(基本字基本字,begin)(賦值號(hào)賦值號(hào), :=)(乘號(hào)乘號(hào), *)(

11、加號(hào)加號(hào), +)(標(biāo)識(shí)符標(biāo)識(shí)符,count)(標(biāo)識(shí)符標(biāo)識(shí)符,first)(標(biāo)識(shí)符標(biāo)識(shí)符,sum)(界符界符, .)(整數(shù)整數(shù),10)(基本字基本字,end)詞法分析后程序的圖形表示詞法分析后程序的圖形表示空格空格換行換行字符的內(nèi)部表示即字符的內(nèi)部表示即ASC碼碼單詞表示成二元式（單詞的種別，單詞自身值）單詞表示成二元式（單詞的種別，單詞自身值）2.2.語(yǔ)法分析語(yǔ)法分析 (syntax analysis or parsing)v 任務(wù)任務(wù)單詞符號(hào)串單詞符號(hào)串(Token串串)語(yǔ)法分析語(yǔ)法分析語(yǔ)法短語(yǔ)語(yǔ)法短語(yǔ)v 識(shí)別規(guī)則：語(yǔ)法規(guī)則識(shí)別規(guī)則：語(yǔ)法規(guī)則( (描述程序結(jié)構(gòu)的規(guī)則描述程序結(jié)構(gòu)的規(guī)則, ,通

12、常是由通常是由遞歸規(guī)則表示的遞歸規(guī)則表示的) )注注: :語(yǔ)法短語(yǔ)又稱(chēng)語(yǔ)法單位，如語(yǔ)法短語(yǔ)又稱(chēng)語(yǔ)法單位，如“表達(dá)式表達(dá)式”、“語(yǔ)句語(yǔ)句”、“分程序分程序”、“程序程序”等等v 結(jié)果結(jié)果: :判斷判斷輸入串是否構(gòu)成一個(gè)語(yǔ)法上正確的程序輸入串是否構(gòu)成一個(gè)語(yǔ)法上正確的程序, ,并并生成生成語(yǔ)法樹(shù)語(yǔ)法樹(shù)例例: :賦值語(yǔ)句賦值語(yǔ)句 sum:=first+countsum:=first+count* *1010 賦值語(yǔ)句規(guī)則賦值語(yǔ)句規(guī)則 :=:= “:=:=” :=:= “+ +” :=:= “* *” :=:=“( (” “) )” :=:= :=:= :=:= sum賦值語(yǔ)句賦值語(yǔ)句標(biāo)識(shí)符標(biāo)識(shí)符:=表

13、達(dá)式表達(dá)式表達(dá)式表達(dá)式+表達(dá)式表達(dá)式標(biāo)識(shí)符標(biāo)識(shí)符first表達(dá)式表達(dá)式*表達(dá)式表達(dá)式標(biāo)識(shí)符標(biāo)識(shí)符count整數(shù)整數(shù)10語(yǔ)法樹(shù)為語(yǔ)法樹(shù)為:3.3.語(yǔ)義分析語(yǔ)義分析 (semantic analysis)v任務(wù)任務(wù): :審查源程序是否有語(yǔ)義錯(cuò)誤，為代審查源程序是否有語(yǔ)義錯(cuò)誤，為代碼生成階段收集類(lèi)型信息碼生成階段收集類(lèi)型信息v類(lèi)型審查（靜態(tài)語(yǔ)義）：類(lèi)型審查（靜態(tài)語(yǔ)義）：上下文相關(guān)性上下文相關(guān)性類(lèi)型匹配：每個(gè)算符是否具有語(yǔ)言規(guī)類(lèi)型匹配：每個(gè)算符是否具有語(yǔ)言規(guī)范允許的運(yùn)算對(duì)象范允許的運(yùn)算對(duì)象類(lèi)型轉(zhuǎn)換類(lèi)型轉(zhuǎn)換例：例：program p( )var rate:real;procedure initial;p

14、osition:=initial+rate*60/*error*/*error*/*warnning*/例例 源程序：源程序：Sum:=first + count Sum:=first + count * * 10 10countcount是實(shí)型是實(shí)型,10,10是整型是整型, ,語(yǔ)義分析后得到新語(yǔ)法樹(shù)為語(yǔ)義分析后得到新語(yǔ)法樹(shù)為: :賦值語(yǔ)句賦值語(yǔ)句標(biāo)識(shí)符標(biāo)識(shí)符:=表達(dá)式表達(dá)式sum表達(dá)式表達(dá)式+表達(dá)式表達(dá)式標(biāo)識(shí)符標(biāo)識(shí)符first表達(dá)式表達(dá)式*表達(dá)式表達(dá)式標(biāo)識(shí)符標(biāo)識(shí)符count實(shí)數(shù)實(shí)數(shù)10inttoreal4.4.中間代碼生成中間代碼生成(intermediate code generatio

15、n)v 任務(wù)：將源程序生成一種內(nèi)部表示形式，這種內(nèi)部表任務(wù)：將源程序生成一種內(nèi)部表示形式，這種內(nèi)部表示形式叫中間代碼。示形式叫中間代碼。v 四元式中間代碼四元式中間代碼: :( (運(yùn)算符，運(yùn)算對(duì)象運(yùn)算符，運(yùn)算對(duì)象1 1，運(yùn)算對(duì)象，運(yùn)算對(duì)象2 2，結(jié)果，結(jié)果) )v 例如：將例如：將Sum:=first + count Sum:=first + count * * 10 10翻譯成四元式翻譯成四元式(1)(1)(inttoreal 10 - T1 )(inttoreal 10 - T1 )(2)(2)( (* * count T1 T2) count T1 T2)(3)(3)(+ first T

16、2 T3)(+ first T2 T3)(4)(4)(:= T3 - sum)(:= T3 - sum)5.5.代碼優(yōu)化代碼優(yōu)化 (code optimization)v 任務(wù)：對(duì)中間代碼進(jìn)行等價(jià)變換，以便生成更高效的任務(wù)：對(duì)中間代碼進(jìn)行等價(jià)變換，以便生成更高效的目標(biāo)代碼目標(biāo)代碼v 舉例舉例: :(1)(1) (inttoreal 10 - T1 )(inttoreal 10 - T1 )(2)(2) ( (* * count T1 T2) count T1 T2)(3)(3) (+ first T2 T3)(+ first T2 T3)(4)(4) (:= T3 - sum)(:= T3 -

17、 sum)簡(jiǎn)化后簡(jiǎn)化后: :( (* * count 10.0 T1) count 10.0 T1)(+ first T1 sum)(+ first T1 sum)6.6.目標(biāo)代碼生成目標(biāo)代碼生成 (code generation)v 任務(wù)：把中間代碼變換成特定機(jī)器上的絕對(duì)指令代碼任務(wù)：把中間代碼變換成特定機(jī)器上的絕對(duì)指令代碼或可重定位的指令代碼或匯編指令代碼或可重定位的指令代碼或匯編指令代碼, ,它的工作與硬它的工作與硬件系統(tǒng)和指令含義有關(guān)件系統(tǒng)和指令含義有關(guān). .v 例如例如: :( (* * count 10.0 T1 ) count 10.0 T1 )(+ first T1 sum)(

18、+ first T1 sum)生成匯編代碼如下生成匯編代碼如下: : MOV count, R2MOV count, R2MUL #10.0, R2MUL #10.0, R2MOV first, R1MOV first, R1ADD R1, R2ADD R1, R2MOV R1, sum MOV R1, sum 7.7.表格管理和出錯(cuò)處理表格管理和出錯(cuò)處理v 出錯(cuò)處理：編譯過(guò)程中，發(fā)現(xiàn)源程序有錯(cuò)誤（詞法錯(cuò)出錯(cuò)處理：編譯過(guò)程中，發(fā)現(xiàn)源程序有錯(cuò)誤（詞法錯(cuò)誤、語(yǔ)法錯(cuò)誤、語(yǔ)義錯(cuò)誤），編譯程序應(yīng)報(bào)告錯(cuò)誤的誤、語(yǔ)法錯(cuò)誤、語(yǔ)義錯(cuò)誤），編譯程序應(yīng)報(bào)告錯(cuò)誤的性質(zhì)和出錯(cuò)的地點(diǎn)，并將錯(cuò)誤所造成的影響限制在盡性質(zhì)和出

19、錯(cuò)的地點(diǎn)，并將錯(cuò)誤所造成的影響限制在盡可能小的范圍內(nèi)，使得源程序的其余部分繼續(xù)被編譯可能小的范圍內(nèi)，使得源程序的其余部分繼續(xù)被編譯下去。這些工作稱(chēng)為出錯(cuò)處理下去。這些工作稱(chēng)為出錯(cuò)處理(error handling)。v 編譯過(guò)程中源程序的各種信息被保留在種種不同的表編譯過(guò)程中源程序的各種信息被保留在種種不同的表格里，編譯各階段的工作涉及到構(gòu)造、查找或更新有格里，編譯各階段的工作涉及到構(gòu)造、查找或更新有關(guān)的表格，因此需要有表格管理工作。關(guān)的表格，因此需要有表格管理工作。1.3 1.3 編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu)(components)源程序源程序詞法分析程序詞法分析程序語(yǔ)法分析程序語(yǔ)法分析程序

20、語(yǔ)義分析程序語(yǔ)義分析程序中間代碼生成程序中間代碼生成程序代碼優(yōu)化程序代碼優(yōu)化程序目標(biāo)代碼生成程序目標(biāo)代碼生成程序表格管理程序表格管理程序出錯(cuò)處理程序出錯(cuò)處理程序目標(biāo)程序目標(biāo)程序1.4 1.4 編譯階段的組合編譯階段的組合1.1. 分析與綜合分析與綜合(analysis and synthesis)(analysis and synthesis)分析階段：詞法分析、語(yǔ)法分析、語(yǔ)義分析，只分析階段：詞法分析、語(yǔ)法分析、語(yǔ)義分析，只對(duì)程序進(jìn)行識(shí)別和檢查，沒(méi)作實(shí)質(zhì)翻譯對(duì)程序進(jìn)行識(shí)別和檢查，沒(méi)作實(shí)質(zhì)翻譯綜合階段：中間代碼的生成，代碼優(yōu)化，目標(biāo)代綜合階段：中間代碼的生成，代碼優(yōu)化，目標(biāo)代碼生成，對(duì)源程序進(jìn)

21、行翻譯，生成目標(biāo)代碼碼生成，對(duì)源程序進(jìn)行翻譯，生成目標(biāo)代碼編譯過(guò)程的劃分：編譯過(guò)程的劃分：2.2. 前端與后端前端與后端 前端前端( (依賴(lài)于源語(yǔ)言而與依賴(lài)于源語(yǔ)言而與目標(biāo)機(jī)無(wú)關(guān)目標(biāo)機(jī)無(wú)關(guān)) )：詞法分析、語(yǔ)法分析、語(yǔ)義分析和中間詞法分析、語(yǔ)法分析、語(yǔ)義分析和中間代碼的生成，中間代碼優(yōu)化代碼的生成，中間代碼優(yōu)化; ; 后端后端( (依賴(lài)于目標(biāo)機(jī)而一般不依賴(lài)源語(yǔ)依賴(lài)于目標(biāo)機(jī)而一般不依賴(lài)源語(yǔ)言言) )：目標(biāo)代碼生成：目標(biāo)代碼生成; ;編譯過(guò)程的實(shí)現(xiàn)：編譯過(guò)程的實(shí)現(xiàn)：一個(gè)編譯過(guò)程可以由一遍、兩遍或多遍完成一個(gè)編譯過(guò)程可以由一遍、兩遍或多遍完成v遍遍(pass)(pass) : :對(duì)源程序或中間語(yǔ)言程序從頭對(duì)源程序或中間語(yǔ)言程序從頭到尾掃描并完成規(guī)定任務(wù)的過(guò)程。到尾掃描并完成規(guī)定任務(wù)的過(guò)程。v一遍的編譯器是通過(guò)一遍掃描直接從源程一遍的編譯器是通過(guò)一遍掃描直接從源程序生成出目標(biāo)代碼，而多遍的編譯器則通序生成出目標(biāo)代碼，而多遍的編譯器則通過(guò)多遍掃描產(chǎn)生目標(biāo)代碼。比如第一遍進(jìn)過(guò)多遍掃描產(chǎn)生目標(biāo)代碼。比如第一遍進(jìn)行詞法分析、語(yǔ)法分析、中間代碼生成和行詞法分析、語(yǔ)法分析、中間代碼生成和中間代碼優(yōu)化，而第二遍掃描則從中間代中間代碼優(yōu)化，而第二遍掃描則從中間代碼產(chǎn)生目標(biāo)代碼碼產(chǎn)生目標(biāo)代碼v影響分遍的因素：源語(yǔ)言結(jié)構(gòu)，目標(biāo)機(jī)資影響分遍的因素：源語(yǔ)言結(jié)構(gòu)，目標(biāo)機(jī)資源源1.5 1.5 編譯技術(shù)和軟件工