編譯技術(shù)：第01章 編譯概述

1、第一章 編譯概述Zhou, Erqiang引言從語(yǔ)言說(shuō)起從語(yǔ)言說(shuō)起漢語(yǔ)、英語(yǔ)漢語(yǔ)、英語(yǔ)=自然語(yǔ)言自然語(yǔ)言旗語(yǔ)、啞語(yǔ)旗語(yǔ)、啞語(yǔ)=人工語(yǔ)言人工語(yǔ)言C C語(yǔ)言、語(yǔ)言、JavaJava程序設(shè)計(jì)語(yǔ)言程序設(shè)計(jì)語(yǔ)言=計(jì)算機(jī)語(yǔ)言計(jì)算機(jī)語(yǔ)言=人工語(yǔ)言人工語(yǔ)言為什么需要計(jì)算機(jī)語(yǔ)言？為什么需要計(jì)算機(jī)語(yǔ)言？人與計(jì)算機(jī)進(jìn)行人與計(jì)算機(jī)進(jìn)行“交流交流”告訴計(jì)算機(jī)告訴計(jì)算機(jī)“做什么做什么”和和“怎么做怎么做”人們之間交流人們之間交流思想的工具思想的工具2School of Information and Software EngineeringZhou, Erqiang引言程序設(shè)計(jì)語(yǔ)言程序設(shè)計(jì)語(yǔ)言機(jī)器語(yǔ)言（機(jī)器語(yǔ)言（Mach

2、ine Code / Machine LanguageMachine Code / Machine Language）能夠被能夠被CPUCPU直接理解并運(yùn)行直接理解并運(yùn)行直接和硬件相關(guān)直接和硬件相關(guān)指令op1op200 r/m8r801 r/m16/32r16/3202 r8r/m803 r16/32r/m16/3204 ALimm805 EAXimm16/32op1 = op1+op2 指令集指令集3School of Information and Software EngineeringZhou, Erqiang引言程序設(shè)計(jì)語(yǔ)言程序設(shè)計(jì)語(yǔ)言機(jī)器語(yǔ)言（機(jī)器語(yǔ)言（Machine Code /

3、 Machine LanguageMachine Code / Machine Language）難寫(xiě)、難懂難寫(xiě)、難懂改進(jìn)：指令符號(hào)化改進(jìn)：指令符號(hào)化例如：例如：00,01,02,03,05 = ADD00,01,02,03,05 = ADD匯編語(yǔ)言匯編語(yǔ)言解決了一小部分問(wèn)題解決了一小部分問(wèn)題依然和機(jī)器相關(guān)，指令級(jí)編寫(xiě)、讀取依然和機(jī)器相關(guān)，指令級(jí)編寫(xiě)、讀取機(jī)器機(jī)器不能不能直接運(yùn)行直接運(yùn)行匯編程序匯編程序：匯編語(yǔ)言程序：匯編語(yǔ)言程序=機(jī)器語(yǔ)言程序機(jī)器語(yǔ)言程序低 級(jí) 語(yǔ) 言4School of Information and Software EngineeringZhou, Erqiang引言程

4、序設(shè)計(jì)語(yǔ)言程序設(shè)計(jì)語(yǔ)言高級(jí)語(yǔ)言高級(jí)語(yǔ)言直觀、自然、易于理解直觀、自然、易于理解易讀，易寫(xiě)，易于交流、存檔易讀，易寫(xiě)，易于交流、存檔獨(dú)立于機(jī)器的獨(dú)立于機(jī)器的, ,易于移植易于移植高級(jí)語(yǔ)言高級(jí)語(yǔ)言=低級(jí)語(yǔ)言低級(jí)語(yǔ)言編譯程序編譯程序/ /編譯器編譯器解釋程序解釋器解釋程序解釋器5School of Information and Software EngineeringZhou, Erqiang引言解釋器解釋器源程序源程序數(shù)據(jù)數(shù)據(jù)輸出輸出編譯器編譯器源程序源程序數(shù)據(jù)數(shù)據(jù)可執(zhí)行可執(zhí)行文件文件輸出輸出在線在線離線離線6School of Information and Software Engineer

5、ingZhou, Erqiang引言程序設(shè)計(jì)語(yǔ)言程序設(shè)計(jì)語(yǔ)言編寫(xiě)一個(gè)高級(jí)語(yǔ)言的編譯或解釋程序編寫(xiě)一個(gè)高級(jí)語(yǔ)言的編譯或解釋程序?qū)υ撜Z(yǔ)言的實(shí)現(xiàn)對(duì)該語(yǔ)言的實(shí)現(xiàn)編譯還是解釋？編譯還是解釋？PascalPascal、C/C+C/C+、Object-CObject-C、JavaJava、C#C#、GoGo編譯的：編譯的：FortranFortran、ValaVala解釋的：解釋的：PythonPython、JavaScriptJavaScript、PHPPHP等等7School of Information and Software Engineering編譯的步驟詞法分析詞法分析中間代碼生成中間代碼生成

6、語(yǔ)法分析語(yǔ)法分析語(yǔ)義分析語(yǔ)義分析中間代碼優(yōu)化中間代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼生成源程序機(jī)器代碼Zhou, Erqiang8School of Information and Software Engineering編譯的步驟詞法分析詞法分析中間代碼生成中間代碼生成語(yǔ)法分析語(yǔ)法分析語(yǔ)義分析語(yǔ)義分析中間代碼優(yōu)化中間代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼生成源程序機(jī)器代碼分析分析（前端）（前端）Zhou, Erqiang9School of Information and Software Engineering編譯的步驟詞法分析詞法分析中間代碼生成中間代碼生成

7、語(yǔ)法分析語(yǔ)法分析語(yǔ)義分析語(yǔ)義分析中間代碼優(yōu)化中間代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼生成源程序機(jī)器代碼合成合成（后端）（后端）Zhou, Erqiang10School of Information and Software Engineeringwhilewhile (y z) intint x = a + b;y += x;詞法分析詞法分析中間代碼生成中間代碼生成語(yǔ)法分析語(yǔ)法分析語(yǔ)義分析語(yǔ)義分析中間代碼優(yōu)化中間代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼生成實(shí)例Zhou, Erqiang11School of Information and Software Eng

8、ineering詞法分析whilewhile (y z) intint x = a + b;y += x;T_WhileT_WhileT_LeftParenthesesT_LeftParenthesesT_Identifier yT_Identifier yT_LessT_LessT_Identifier zT_Identifier zT_RightParenthesesT_RightParenthesesT_OpenBraceT_OpenBraceT_Identifier yT_Identifier yT_PlusAssignT_PlusAssignT_Identifier xT_Ident

9、ifier xT_SemicolonT_SemicolonT_CloseBraceT_CloseBraceT_IntT_IntT_Identifier xT_Identifier xT_AssignT_AssignT_Identifier aT_Identifier aT_PlusT_PlusT_Identifier bT_Identifier bT_SemicolonT_Semicolon詞法分析詞法分析中間代碼生成中間代碼生成語(yǔ)法分析語(yǔ)法分析語(yǔ)義分析語(yǔ)義分析中間代碼優(yōu)化中間代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼生成Zhou, Erqiang12School of Inform

10、ation and Software Engineering語(yǔ)法分析whilewhile (y z) intint x = a + b;y += x;詞法分析詞法分析中間代碼生成中間代碼生成語(yǔ)法分析語(yǔ)法分析語(yǔ)義分析語(yǔ)義分析中間代碼優(yōu)化中間代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼生成while順序yz=x+ab+yx=yZhou, Erqiang13School of Information and Software Engineering語(yǔ)義分析whilewhile (y z) intint x = a + b;y += x;詞法分析詞法分析中間代碼生成中間代碼生成語(yǔ)法分析語(yǔ)法分析

11、語(yǔ)義分析語(yǔ)義分析中間代碼優(yōu)化中間代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼生成while順序yz=x+ab+yx=yintintintintintintintintintintintboolvoidvoidintZhou, Erqiang14School of Information and Software Engineering中間代碼生成whilewhile (y z) intint x = a + b;y += x;詞法分析詞法分析中間代碼生成中間代碼生成語(yǔ)法分析語(yǔ)法分析語(yǔ)義分析語(yǔ)義分析中間代碼優(yōu)化中間代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼生成ifif y z

12、goto where_true;gotogoto where_false;t1 = a + b;x = t1t2 = x + y;y = t2gotogoto Loop; where_truewhere_true： Loop Loop：where_falsewhere_false：Zhou, Erqiang15School of Information and Software Engineering中間代碼優(yōu)化whilewhile (y z) intint x = a + b;y += x;詞法分析詞法分析中間代碼生成中間代碼生成語(yǔ)法分析語(yǔ)法分析語(yǔ)義分析語(yǔ)義分析中間代碼優(yōu)化中間代碼優(yōu)化目標(biāo)代

13、碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼生成ifif y z goto where_true;gotogoto where_false;t1 = a + b;x = t1t2 = x + y;y = t2gotogoto Loop; Loop Loop：t1 = a + b;t1 = a + b;x = t1x = t1Zhou, Erqiang16School of Information and Software Engineeringwhere_truewhere_true：where_falsewhere_false：目標(biāo)代碼生成MIPS Instructions MeaningMIPS

14、 Instructions Meaningaddadd $s1,$s2,$s3 $s1,$s2,$s3 $s1 = $s2 + $s3$s1 = $s2 + $s3subsub $s1,$s2,$s3 $s1,$s2,$s3 $s1 = $s2 $s3$s1 = $s2 $s3bnebne $s4,$s5,Label $s4,$s5,Label 下一條指令在下一條指令在 Label if $s4 $s5 Label if $s4 $s5 beqbeq $s4,$s5,Label $s4,$s5,Label 下一條指令在下一條指令在 Label if $s4 = $s5 Label if $s4

15、 = $s5 j j Label Label 下一條指令在下一條指令在 LabelLabelsltslt $t1,$s2,$s3 $t1,$s2,$s3 if $s2 $s3, $t1 = 1 else $t1 = 0if $s2 $s3, $t1 = 1 else $t1 = 0Zhou, Erqiang17School of Information and Software Engineeringslt: Set on less than目標(biāo)代碼生成whilewhile (y z) intint x = a + b;y += x;詞法分析詞法分析中間代碼生成中間代碼生成語(yǔ)法分析語(yǔ)法分析語(yǔ)義

16、分析語(yǔ)義分析中間代碼優(yōu)化中間代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼生成add add $x, $a, $b$x, $a, $bsltslt $_t1, $y, $z $_t1, $y, $zbeqbeq $_t1, 1, where_true $_t1, 1, where_truej j where_falsewhere_falseaddadd $y, $x, $y$y, $x, $yj j Loop Loopwhere_truewhere_true： Loop Loop：where_falsewhere_false：Zhou, Erqiang18School of Inform

17、ation and Software Engineering目標(biāo)代碼生成whilewhile (y z) intint x = a + b;y += x;詞法分析詞法分析中間代碼生成中間代碼生成語(yǔ)法分析語(yǔ)法分析語(yǔ)義分析語(yǔ)義分析中間代碼優(yōu)化中間代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼生成add $x, $a, $badd $x, $a, $bsltslt $_t1, $y, $z $_t1, $y, $zbeqbeq $_t1, 1, where_true $_t1, 1, where_truej j where_falsewhere_falseaddadd $y, $x, $y$y

18、, $x, $yj Loopj Loop Loop Loop：blt $y, $z, where_trueblt $y, $z, where_trueZhou, Erqiang19School of Information and Software Engineeringwhere_truewhere_true：where_falsewhere_false：關(guān)于“綁定”實(shí)體：程序的組成部分實(shí)體：程序的組成部分變量、表達(dá)式、函數(shù)等變量、表達(dá)式、函數(shù)等屬性：實(shí)體具有的特性屬性：實(shí)體具有的特性變量名、變量的類型、函數(shù)名、函數(shù)的參數(shù)變量名、變量的類型、函數(shù)名、函數(shù)的參數(shù)綁定綁定實(shí)體與其屬性建立某種聯(lián)系

19、的過(guò)程稱為綁定實(shí)體與其屬性建立某種聯(lián)系的過(guò)程稱為綁定實(shí)際上就是建立了某種約束實(shí)際上就是建立了某種約束Zhou, Erqiang20School of Information and Software Engineering是否要保存實(shí)體與屬性的綁定信息？是否要保存實(shí)體與屬性的綁定信息？哪些地方需要保存？哪些地方需要保存？如何保存？如何保存？需要檢查需要檢查 變量是否被聲明或聲明多次變量是否被聲明或聲明多次 變量在聲明前被賦值或被引用變量在聲明前被賦值或被引用 操作符與變量類型兼容操作符與變量類型兼容 等等等等需要數(shù)據(jù)結(jié)構(gòu)保存實(shí)體屬性信息需要數(shù)據(jù)結(jié)構(gòu)保存實(shí)體屬性信息 符號(hào)表符號(hào)表符號(hào)表Zhou,

20、 Erqiang21School of Information and Software Engineeringint a;b = 1;a = “hello”;哪些地方需要？哪些地方需要？ 編譯器：源程序語(yǔ)義檢查編譯器：源程序語(yǔ)義檢查 目標(biāo)文件、庫(kù)文件：目標(biāo)文件、庫(kù)文件： 例如例如函數(shù)名函數(shù)名與與地址地址的對(duì)應(yīng)的對(duì)應(yīng) 將多個(gè)目標(biāo)文件將多個(gè)目標(biāo)文件鏈接鏈接為可執(zhí)行文件為可執(zhí)行文件 可執(zhí)行文件：可執(zhí)行文件： 調(diào)試時(shí)由調(diào)試時(shí)由地址地址得到得到實(shí)體名實(shí)體名符號(hào)表Zhou, Erqiang22School of Information and Software Engineering符號(hào)表的形式符號(hào)表的

21、形式 每個(gè)每個(gè)名字名字對(duì)應(yīng)一個(gè)對(duì)應(yīng)一個(gè)表項(xiàng)表項(xiàng) 一個(gè)表項(xiàng)包括一個(gè)表項(xiàng)包括名字域名字域和和信息域信息域 (key, value)(key, value)符號(hào)表的實(shí)現(xiàn)符號(hào)表的實(shí)現(xiàn) 線性表、線性表、HashHash表表名字名字屬性信息屬性信息符號(hào)表Zhou, Erqiang23School of Information and Software Engineering屬性域?qū)傩杂?多個(gè)多個(gè)子域子域及及標(biāo)志位標(biāo)志位單詞記號(hào)：標(biāo)識(shí)符、數(shù)字、符號(hào)單詞記號(hào)：標(biāo)識(shí)符、數(shù)字、符號(hào)標(biāo)識(shí)符標(biāo)識(shí)符：變量？函數(shù)名？標(biāo)號(hào)變量？函數(shù)名？標(biāo)號(hào)？變量變量：類型？有初值？：類型？有初值？函數(shù)函數(shù)：返回類型？參數(shù)個(gè)數(shù)、類型等：返回

22、類型？參數(shù)個(gè)數(shù)、類型等標(biāo)號(hào)標(biāo)號(hào)：標(biāo)號(hào)地址、轉(zhuǎn)移地址：標(biāo)號(hào)地址、轉(zhuǎn)移地址符號(hào)表Zhou, Erqiang24School of Information and Software Engineering名字域：名字多長(zhǎng)？名字域：名字多長(zhǎng)？名字域如何實(shí)現(xiàn)？名字域如何實(shí)現(xiàn)？ 直接存儲(chǔ)：直接存儲(chǔ)： 每個(gè)標(biāo)識(shí)符分配最大允許空間每個(gè)標(biāo)識(shí)符分配最大允許空間 間接表技術(shù)間接表技術(shù) 名字域存放指針名字域存放指針 符號(hào)表Zhou, Erqiang25School of Information and Software EngineeringMicrosoft： the first 2048 charactersGC

23、C: no limit出錯(cuò)處理為什么需要出錯(cuò)處理？為什么需要出錯(cuò)處理？ 編譯各個(gè)階段都可能發(fā)現(xiàn)錯(cuò)誤編譯各個(gè)階段都可能發(fā)現(xiàn)錯(cuò)誤出錯(cuò)處理的內(nèi)容出錯(cuò)處理的內(nèi)容 報(bào)告錯(cuò)誤的報(bào)告錯(cuò)誤的性質(zhì)性質(zhì)、位置位置 盡量縮小范圍、查找出更多的錯(cuò)誤盡量縮小范圍、查找出更多的錯(cuò)誤Zhou, Erqiang26School of Information and Software Engineering編譯器的結(jié)構(gòu)詞法分析詞法分析語(yǔ)法分析語(yǔ)法分析單詞符號(hào)串單詞符號(hào)串語(yǔ)法樹(shù)語(yǔ)法樹(shù)語(yǔ)義分析和中間代碼生成語(yǔ)義分析和中間代碼生成中間代碼中間代碼優(yōu)化優(yōu)化經(jīng)優(yōu)化的中間代碼經(jīng)優(yōu)化的中間代碼代碼生成代碼生成源程序源程序目標(biāo)程序目標(biāo)程序源程序的分析源程序的分析目標(biāo)程序的合成目標(biāo)程序的合成符符號(hào)號(hào)表表管管理理出出錯(cuò)錯(cuò)處處理理Zhou, Erqiang27School of Information and Software Engineering（可執(zhí)行）（可執(zhí)行）( (多個(gè)源程序文件多個(gè)源程序文件) )完完整整的的程程序序處處理理過(guò)過(guò)程程預(yù)處理器預(yù)處理器編譯器編譯器源程序源程序匯編語(yǔ)言程序匯編語(yǔ)言程序匯編器匯編器目標(biāo)程序目標(biāo)程序( (可重定位可重定位) )連接器、裝入器連接器、裝入器目標(biāo)程序目標(biāo)程序源程序源程序庫(kù)程序庫(kù)程序Zhou, Erqiang28School of Informati