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

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

2、ine Code / Machine LanguageMachine Code / Machine Language）能夠被能夠被CPUCPU直接理解并運行直接理解并運行直接和硬件相關(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è)計語言程序設(shè)計語言機器語言（機器語言（Machine Code /

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

4、序設(shè)計語言程序設(shè)計語言高級語言高級語言直觀、自然、易于理解直觀、自然、易于理解易讀，易寫，易于交流、存檔易讀，易寫，易于交流、存檔獨立于機器的獨立于機器的, ,易于移植易于移植高級語言高級語言=低級語言低級語言編譯程序編譯程序/ /編譯器編譯器解釋程序解釋器解釋程序解釋器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è)計語言程序設(shè)計語言編寫一個高級語言的編譯或解釋程序編寫一個高級語言的編譯或解釋程序?qū)υ撜Z言的實現(xiàn)對該語言的實現(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ōu)化中間代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼生成源程序機器代碼Zhou, Erqiang8School of Information and Software Engineering編譯的步驟詞法分析詞法分析中間代碼生成中間代碼生成語法分析語法分析語義分析語義分析中間代碼優(yōu)化中間代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼生成源程序機器代碼分析分析（前端）（前端）Zhou, Erqiang9School of Information and Software Engineering編譯的步驟詞法分析詞法分析中間代碼生成中間代碼生成

7、語法分析語法分析語義分析語義分析中間代碼優(yōu)化中間代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼生成源程序機器代碼合成合成（后端）（后端）Zhou, Erqiang10School of Information and Software Engineeringwhilewhile (y z) intint x = a + b;y += x;詞法分析詞法分析中間代碼生成中間代碼生成語法分析語法分析語義分析語義分析中間代碼優(yōu)化中間代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼生成實例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ōu)化中間代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼生成Zhou, Erqiang12School of Inform

10、ation and Software Engineering語法分析whilewhile (y z) intint x = a + b;y += x;詞法分析詞法分析中間代碼生成中間代碼生成語法分析語法分析語義分析語義分析中間代碼優(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語義分析whilewhile (y z) intint x = a + b;y += x;詞法分析詞法分析中間代碼生成中間代碼生成語法分析語法分析

11、語義分析語義分析中間代碼優(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ō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ō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;詞法分析詞法分析中間代碼生成中間代碼生成語法分析語法分析語義

16、分析語義分析中間代碼優(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ō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ù)等屬性：實體具有的特性屬性：實體具有的特性變量名、變量的類型、函數(shù)名、函數(shù)的參數(shù)變量名、變量的類型、函數(shù)名、函數(shù)的參數(shù)綁定綁定實體與其屬性建立某種聯(lián)系

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

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

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

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

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