Chapter 01--編譯概述

1、LI Wensheng, SCS, BUPT 第第1 1章章 編譯概述編譯概述知識點：知識點：翻譯、解釋、編譯翻譯、解釋、編譯 編譯的階段、任務、及典型結構編譯的階段、任務、及典型結構 編譯程序的伙伴工具編譯程序的伙伴工具Wensheng Li BUPT2編譯概述編譯概述 簡介簡介1.1 1.1 翻譯和解釋翻譯和解釋1.2 1.2 編譯的階段和任務編譯的階段和任務1.3 1.3 編譯有關的其他概念編譯有關的其他概念1.4 1.4 編譯程序的伙伴工具編譯程序的伙伴工具1.5 1.5 編譯原理的編譯原理的應用應用 小結小結Wensheng Li BUPT3簡介簡介n什么是編譯？什么是編譯？u把源程

2、序轉換成等價的目標程序的過程即是編譯。把源程序轉換成等價的目標程序的過程即是編譯。n編譯程序的設計涉及到的知識：編譯程序的設計涉及到的知識：u程序設計語言程序設計語言u形式語言與自動機理論形式語言與自動機理論u計算機體系結構計算機體系結構u數據結構數據結構u算法分析與設計算法分析與設計u操作系統(tǒng)操作系統(tǒng)u軟件工程等軟件工程等Wensheng Li BUPT41.1 1.1 翻譯和解釋翻譯和解釋一、程序設計語言一、程序設計語言二、翻譯程序二、翻譯程序Wensheng Li BUPT5一、程序設計語言一、程序設計語言n低級語言低級語言u機器語言機器語言u符號語言符號語言 匯編語言匯編語言n高級語言

3、高級語言u過程性語言過程性語言面向用戶的語言面向用戶的語言 如：如：C C、PascalPascalu專用語言專用語言面向問題的語言面向問題的語言 如：如：SQLSQLu面向對象的語言面向對象的語言 如：如：JavaJava、C+C+Wensheng Li BUPT6高級語言的優(yōu)點高級語言的優(yōu)點n高級語言獨立于機器。所編程序移植性比較好。高級語言獨立于機器。所編程序移植性比較好。n不必考慮不必考慮存儲存儲空間空間的的分配問題分配問題，不需要了解數據，不需要了解數據從從外部外部形式轉換成形式轉換成機器內部形式的細節(jié)機器內部形式的細節(jié)。u用變量描述存儲單元用變量描述存儲單元n具有豐富的數據結構和控

4、制結構。具有豐富的數據結構和控制結構。u數據結構：數組、記錄等數據結構：數組、記錄等u控制結構：循環(huán)、分支、過程調用等?？刂平Y構：循環(huán)、分支、過程調用等。n更接近于自然語言。更接近于自然語言。u可讀性好，便于維護。可讀性好，便于維護。n編程效率高。編程效率高。Wensheng Li BUPT7二、翻譯程序二、翻譯程序n翻譯程序掃描所輸入的源程序，并將其轉換為目標翻譯程序掃描所輸入的源程序，并將其轉換為目標程序，程序，或將源程序直接翻譯成結果或將源程序直接翻譯成結果。翻譯程序翻譯程序源程序源程序目標程序或執(zhí)行結果目標程序或執(zhí)行結果n翻譯程序分為兩大類：翻譯程序分為兩大類：1.1.編譯程序編譯程序

5、( (即編譯器即編譯器) )：把源程序翻譯成目標程序：把源程序翻譯成目標程序的翻譯程序的翻譯程序。2.2.解釋程序解釋程序( (即解釋器即解釋器) )：直接執(zhí)行源程序的翻譯程：直接執(zhí)行源程序的翻譯程序。序。Wensheng Li BUPT8編譯程序編譯程序匯編程序匯編程序匯編語言程序匯編語言程序機器語言程序機器語言程序編譯程序編譯程序高級語言程序高級語言程序低級語言程序低級語言程序n源程序是用高級語言或匯編語言編寫的，目標程序源程序是用高級語言或匯編語言編寫的，目標程序是是用用匯編或機器匯編或機器語言語言表示的表示的。n兩兩類編譯程序：類編譯程序：u匯編程序匯編程序u編譯程序編譯程序Wensh

6、eng Li BUPT9編譯和執(zhí)行階段編譯和執(zhí)行階段n編譯時間：實現源程序到目標程序的轉換所占用的編譯時間：實現源程序到目標程序的轉換所占用的時間。時間。n源程序和數據是在不同時間（即分別在編譯階段和源程序和數據是在不同時間（即分別在編譯階段和運行階段）進行處理的。運行階段）進行處理的。源程序源程序目標程序目標程序編譯程序編譯程序編譯時編譯時數據數據計算機計算機結果結果執(zhí)行時執(zhí)行時Wensheng Li BUPT10解釋程序解釋程序n解釋程序解釋執(zhí)行源程序，不生成目標程序解釋程序解釋執(zhí)行源程序，不生成目標程序n同時處理源程序和數據同時處理源程序和數據n一種有效的方法：先將源程序轉換為某種中間形

7、式，一種有效的方法：先將源程序轉換為某種中間形式，然后對中間形式的程序解釋執(zhí)行。然后對中間形式的程序解釋執(zhí)行。源程序源程序數據數據結果結果解釋程序解釋程序Wensheng Li BUPT11total:=total+ratetotal:=total+rate* *4 4 的解釋過程的解釋過程n解釋程序先將源程序轉解釋程序先將源程序轉換成一棵樹換成一棵樹n遍歷該樹，執(zhí)行結點上所遍歷該樹，執(zhí)行結點上所規(guī)定的動作。規(guī)定的動作。調用一個過程，執(zhí)行右邊的表達式，調用一個過程，執(zhí)行右邊的表達式，計算結果送入計算結果送入total的存儲單元的存儲單元遞歸調用過程，對表遞歸調用過程，對表達式進行計算達式進行計

8、算Wensheng Li BUPTJavaJava語言語言處理器：處理器：編譯編譯+ +解釋解釋12編譯編譯：用用javac 把把源源代碼代碼編譯成編譯成 .class 文件文件（平臺無關的（平臺無關的字節(jié)碼）。字節(jié)碼）。解釋解釋：Java虛擬機對字節(jié)碼解釋虛擬機對字節(jié)碼解釋執(zhí)行。執(zhí)行。Wensheng Li BUPT13JavaJava語言語言處理器（續(xù)）處理器（續(xù)）nJITJIT（Just-in-timeJust-in-time）即時編譯）即時編譯u在運行中，程序處理輸入的前一刻首先把字節(jié)碼翻譯成為在運行中，程序處理輸入的前一刻首先把字節(jié)碼翻譯成為機器語言，然后再執(zhí)行程序。機器語言，然后再

9、執(zhí)行程序。u可以加快可以加快javajava程序的啟動速度程序的啟動速度u代碼的執(zhí)行效率相對差些代碼的執(zhí)行效率相對差些nHotSpotHotSpot VM VM中的中的JITJITu組合組合了編譯、性能分析以及動態(tài)了編譯、性能分析以及動態(tài)編譯編譯。u只編譯只編譯“熱門熱門”代碼代碼，即，即執(zhí)行執(zhí)行最頻繁的最頻繁的代碼代碼。uclientclient版和版和serverserver版版兩個兩個編譯器編譯器。默認默認：用用clientclient版的版的。啟動時啟動時，指定指定-server-server參數參數，啟動啟動serverserver版的編譯器版的編譯器。ServerServer版版適

10、用于需要長期運行的服務器適用于需要長期運行的服務器應用程序應用程序，針對最大峰值針對最大峰值操作速度進行了優(yōu)化操作速度進行了優(yōu)化。Wensheng Li BUPT141.2 1.2 編譯的階段和任務編譯的階段和任務一、分析階段一、分析階段 根據源語言的定義，分析源程序的結構根據源語言的定義，分析源程序的結構1.1.詞法分析詞法分析2.2.語法分析語法分析3.3.語義分析語義分析二、綜合階段二、綜合階段 根據分析結果構造出所要求的目標程序根據分析結果構造出所要求的目標程序4.4.中間代碼生成中間代碼生成5.5.代碼優(yōu)化代碼優(yōu)化6.6.目標代碼生成目標代碼生成三、符號表的管理三、符號表的管理 四、

11、錯誤診斷和處理四、錯誤診斷和處理Wensheng Li BUPT15編譯程序的典型結構編譯程序的典型結構Wensheng Li BUPT16一、分析階段一、分析階段n任務：根據源語言的定義，對源程序進行結構分析任務：根據源語言的定義，對源程序進行結構分析和語義分析，從而把源程序正文轉換為某種內部表和語義分析，從而把源程序正文轉換為某種內部表示。示。n分析階段是對源程序結構的靜態(tài)分析。分析階段是對源程序結構的靜態(tài)分析。n任務劃分：任務劃分：1.1.詞法分析詞法分析2.2.語法分析語法分析3.3.語義分析語義分析Wensheng Li BUPT171. 1. 詞法分析詞法分析n掃描，線性分析掃描，

12、線性分析n詞法分析器：詞法分析器：u依次讀入源程序中的每個字符，對構成源程序的字符串依次讀入源程序中的每個字符，對構成源程序的字符串進行分解，識別出每個具有獨立意義的字符串（即單進行分解，識別出每個具有獨立意義的字符串（即單詞），將其轉換成記號（詞），將其轉換成記號（token），并組織成記號流。），并組織成記號流。u把需要存放的單詞放到符號表中，如變量名，標號，常把需要存放的單詞放到符號表中，如變量名，標號，常量等。量等。n形成記號的字符串叫做該記號的形成記號的字符串叫做該記號的單詞單詞（lexeme）。）。n工作依據：源語言的構詞工作依據：源語言的構詞規(guī)則（即詞法），規(guī)則（即詞法），也稱為

13、也稱為模式模式（pattern）。）。uC語言的標識符的模式是：以字母或下劃線開頭，由字母、語言的標識符的模式是：以字母或下劃線開頭，由字母、數字或下劃線組成的符號串。數字或下劃線組成的符號串。Wensheng Li BUPT18對對 total:=total+ratetotal:=total+rate* *4 4 的詞法分析的詞法分析(1) 標識符標識符 total(2) 賦值號賦值號 :=(3) 標識符標識符 total(4) 加號加號 +(5) 標識符標識符 rate(6) 乘號乘號 *(7) 整常數整常數 4Wensheng Li BUPT19空格、注釋的處理及其他空格、注釋的處理及其

14、他n分隔分隔單詞單詞的空格：被跳過的空格：被跳過n源程序中的注釋：被跳源程序中的注釋：被跳過過n識別出來的標識符要放入符號表。識別出來的標識符要放入符號表。n某些記號還要具有某些記號還要具有“屬性值屬性值”u如發(fā)現標識符如發(fā)現標識符total時，詞法分析器不僅產生一個單詞時，詞法分析器不僅產生一個單詞符號的類別標記如符號的類別標記如id，還把它的單詞，還把它的單詞total填入符號表填入符號表（如果（如果total在表中不存在的話），則在表中不存在的話），則total的記號就包的記號就包括兩部分：單詞符號的類別標記括兩部分：單詞符號的類別標記id、屬性值（即指向、屬性值（即指向符符號表號表中中

15、R條目的指針）條目的指針）。u如如發(fā)現常數發(fā)現常數3.14時時，詞法分析，詞法分析器產生器產生一一個類別個類別標記標記如如num，這樣，這樣，3.14的的記號就包括兩部分：單詞符號的記號就包括兩部分：單詞符號的類別類別標記標記num、屬性值屬性值（3.14）。）。Wensheng Li BUPT202. 語法分析語法分析n層次結構的分析層次結構的分析n把記號流按語言的語法結構層次地分組，以形成語把記號流按語言的語法結構層次地分組，以形成語法短語。法短語。n源程序的語法短語常用分析樹表示源程序的語法短語常用分析樹表示n工作依據：源語言的語法規(guī)則工作依據：源語言的語法規(guī)則n程序的層次結構通常由遞歸

16、的規(guī)則表示，如表達式程序的層次結構通常由遞歸的規(guī)則表示，如表達式的定義如下：的定義如下：(1) 任何一個標識符是一個表達式任何一個標識符是一個表達式(2) 任何一個數是一個表達式任何一個數是一個表達式(3) 如果如果expr1和和expr2是表達式，是表達式，expr1+expr2、expr1*expr2、(expr1)也都是表達式。也都是表達式。Wensheng Li BUPT21total:=total+ratetotal:=total+rate* *4 4 的分析樹的分析樹Wensheng Li BUPT22語句的遞歸定義語句的遞歸定義n如果如果id是一個標識符，是一個標識符，expr是

17、一個表達式，則是一個表達式，則id:=expr 是一個語句。是一個語句。n如果如果expr是表達式，是表達式，stmt是語句，則是語句，則while (expr) do stmt 是是語句語句if (expr) then stmt 是是語句。語句。Wensheng Li BUPT233. 3. 語義分析語義分析n對語句的意義進行檢查分析對語句的意義進行檢查分析n收集類型等必要信息收集類型等必要信息n用語法分析確定的層次結構表示各語法成份用語法分析確定的層次結構表示各語法成份n工作依據：源語言的語義規(guī)則工作依據：源語言的語義規(guī)則n一個重要任務：類型檢查一個重要任務：類型檢查u根據規(guī)則檢查每個運算

18、符及其運算對象是否符合要求；根據規(guī)則檢查每個運算符及其運算對象是否符合要求；u數組的下標是否合法；數組的下標是否合法；u過程調用時，形參與實參個數、類型是否匹配等過程調用時，形參與實參個數、類型是否匹配等Wensheng Li BUPT24賦值語句賦值語句 total:=total+ratetotal:=total+rate* *4 4插入轉換符的語法樹插入轉換符的語法樹Wensheng Li BUPT25total:=total+ratetotal:=total+rate* *4 4 的各分析步驟及其中間結果的各分析步驟及其中間結果total:=total+rate*4詞法分析語法分析id2

19、4:=id1+id1*語義分析:=id1+id1*id2inttoreal4id1:=id1+id2*4Wensheng Li BUPT26二、綜合階段二、綜合階段n任務：根據所制定的源語言到目標語言的對應關系，任務：根據所制定的源語言到目標語言的對應關系，對分析階段所產生的中間形式進行綜合加工，從而對分析階段所產生的中間形式進行綜合加工，從而得到與源程序等價的目標程序。得到與源程序等價的目標程序。n任務劃分：任務劃分：(4) (4) 中間代碼生成中間代碼生成(5) (5) 代碼優(yōu)化代碼優(yōu)化(6) (6) 目標代碼生成目標代碼生成Wensheng Li BUPT274. 4. 中間代碼生成中間

20、代碼生成n中間代碼：一種抽象的機器程序中間代碼：一種抽象的機器程序n中間代碼應具有兩個重要的特點：中間代碼應具有兩個重要的特點：u易于產生易于產生u易于翻譯成目標代碼易于翻譯成目標代碼n中間代碼有多種形式中間代碼有多種形式n三地址代碼三地址代碼具有的特點：具有的特點：u每條指令除了賦值號之外，最多還有一個運算符。每條指令除了賦值號之外，最多還有一個運算符。u編譯程序必須生成臨時變量名，以便保留每條指令的計算編譯程序必須生成臨時變量名，以便保留每條指令的計算結果。結果。u有些有些“三地址三地址”指令少于三個操作數指令少于三個操作數Wensheng Li BUPT28total:=total+ra

21、tetotal:=total+rate* *4 4 的三地址代碼的三地址代碼temptemp1 1:=inttoreal(4):=inttoreal(4)temptemp2 2:=id:=id2 2* *temptemp1 1temptemp3 3:=id:=id1 1+temp+temp2 2idid1 1:=temp:=temp3 3Wensheng Li BUPT5. 5. 代碼優(yōu)化代碼優(yōu)化n代碼優(yōu)化：代碼優(yōu)化：對對代碼進行改進，使之占用的空間少、運行速度代碼進行改進，使之占用的空間少、運行速度快?？?。n代碼優(yōu)化首先是在中間代碼上進行的代碼優(yōu)化首先是在中間代碼上進行的。temptemp1

22、 1:=:=inttorealinttoreal(4)(4)temptemp2 2:=id:=id2 2* *temptemp1 1temptemp3 3:=id:=id1 1+temp+temp2 2idid1 1:=:=temptemp3 3n優(yōu)化編譯程序：能夠優(yōu)化編譯程序：能夠完成大多數優(yōu)化的完成大多數優(yōu)化的編譯程序。編譯程序。29temp1:=id2*4.0temp2:=id1+temp1id1:=temp2 Wensheng Li BUPT306. 6. 目標代碼生成目標代碼生成n生成的目標代碼一般是可以重定位的機器代碼或匯生成的目標代碼一般是可以重定位的機器代碼或匯編語言代碼。編語

23、言代碼。n涉及到的兩個重要問題：涉及到的兩個重要問題：u對程序中使用的每個變量要指定存儲單元對程序中使用的每個變量要指定存儲單元u對變量進行寄存器分配對變量進行寄存器分配Wensheng Li BUPT31total:=total+ratetotal:=total+rate* *4 4 的目標代碼的目標代碼 MOVF MOVF R R0 0, id, id2 2 MULF MULF R R0 0, #4.0, #4.0 MOVF MOVF R R1 1, id, id1 1 ADDF ADDF R R0 0, R, R1 1 MOVF MOVF idid1 1, , R R0 0Wenshen

24、g Li BUPT32賦值語句賦值語句total:=total+ratetotal:=total+rate* *4 4的各綜合步驟及結果的各綜合步驟及結果中間代碼生成代碼優(yōu)化目標代碼生成temp1:=inttoreal(4)temp2:=id2*temp1temp3:=id1+temp2id1:=temp3 temp1:=id2*4.0temp2:= id1+trmp1id1:= temp2MOVF R0, id2MULF R0, #4.0MOVF R1, id1ADDF R0, R1MOVF id1, R0Wensheng Li BUPT33total:=total+ratetotal:=t

25、otal+rate* *4 4 的翻譯過程的翻譯過程total:=total+rate*4詞法分析語法分析id24:=id1+id1*語義分析:=id1+id1*id2inttoreal4中間代碼生成代碼優(yōu)化目標代碼生成temp1:=inttoreal(4)temp2:=id2*temp1temp3:=id1+temp2id1:=temp3 temp1:=id2*4.0temp2:= id1+trmp1id1:= temp2MOVF R0, id2MULF R0, #4.0MOVF R1, id1ADDF R0, R1MOVF id1, R0 id1:=id1+id2*4Wensheng Li

26、 BUPT34三、符號表管理三、符號表管理n編譯程序的一項重要工作：編譯程序的一項重要工作：u記錄源程序中使用的標識符記錄源程序中使用的標識符u收集每個標識符的各種屬性信息收集每個標識符的各種屬性信息n符號表是由若干記錄組成的數據結構符號表是由若干記錄組成的數據結構u每個標識符在表中有一條記錄每個標識符在表中有一條記錄u記錄的域是標識符的屬性記錄的域是標識符的屬性n對符號表結構的要求：對符號表結構的要求：u應允許快速地找到標識符的記錄應允許快速地找到標識符的記錄u可在其中存取數據可在其中存取數據n標識符的各種屬性是在編譯的各個不同階段填入符標識符的各種屬性是在編譯的各個不同階段填入符號表的。號

27、表的。Wensheng Li BUPT35聲明語句：聲明語句：float total, rate; float total, rate; n詞法分析器：詞法分析器：ufloat是關鍵字是關鍵字utotal、rate是標識符是標識符u在符號表中創(chuàng)建這兩個標識符的記錄在符號表中創(chuàng)建這兩個標識符的記錄n語義分析器：語義分析器：utotal、rate都表示變量都表示變量ufloat表示這兩個變量的類型表示這兩個變量的類型u可以把這兩種屬性及存儲分配信息填入符號表?？梢园堰@兩種屬性及存儲分配信息填入符號表。n在語義分析和生成中間代碼時，還要在符號表中在語義分析和生成中間代碼時，還要在符號表中填入對這個填

28、入對這個float型變量進行存儲分配的信息。型變量進行存儲分配的信息。Wensheng Li BUPT36四、錯誤處理四、錯誤處理n在編譯的每個階段都可能檢測到源程序中存在的錯在編譯的每個階段都可能檢測到源程序中存在的錯誤誤u詞法分析詞法分析程序可以檢測出非法字符錯誤。程序可以檢測出非法字符錯誤。u語法分析語法分析程序能夠發(fā)現記號流不符合語法規(guī)則的錯誤。程序能夠發(fā)現記號流不符合語法規(guī)則的錯誤。u語義分析語義分析程序試圖檢測出具有正確的語法結構，但對所程序試圖檢測出具有正確的語法結構，但對所涉及的操作無意義的結構。涉及的操作無意義的結構。u代碼生成代碼生成程序可能發(fā)現目標程序區(qū)超出了允許范圍的錯

29、程序可能發(fā)現目標程序區(qū)超出了允許范圍的錯誤。誤。u由于計算機由于計算機容量的限制容量的限制，編譯程序的處理能力受到限制，編譯程序的處理能力受到限制而引起的錯誤而引起的錯誤。n處理與恢復處理與恢復u判斷位置和性質判斷位置和性質u適當的恢復適當的恢復Wensheng Li BUPT371.3 1.3 編譯有關的其他概念編譯有關的其他概念一、前端和后端一、前端和后端二、二、“遍遍”Wensheng Li BUPT38一、前端和后端一、前端和后端n前端主要由與源語言有關而與目標機器無關的那些前端主要由與源語言有關而與目標機器無關的那些部分組成部分組成 u詞法分析、語法分析、符號表的建立、語義分析和中間

30、詞法分析、語法分析、符號表的建立、語義分析和中間代碼生成代碼生成u與機器無關的代碼優(yōu)化工作與機器無關的代碼優(yōu)化工作u相應的錯誤處理工作和符號表操作相應的錯誤處理工作和符號表操作n后端由編譯程序中與目標機器有關的部分組成后端由編譯程序中與目標機器有關的部分組成u與機器有關的代碼優(yōu)化、目標代碼的生成與機器有關的代碼優(yōu)化、目標代碼的生成u相應的錯誤處理和符號表操作相應的錯誤處理和符號表操作n把編譯程序劃分成前端和后端的優(yōu)點：把編譯程序劃分成前端和后端的優(yōu)點：u便于移植、便于編譯程序的構造便于移植、便于編譯程序的構造。Wensheng Li BUPT39二、遍二、遍n一一“遍遍”是指對源程序或其中間形

31、式從頭到尾掃描是指對源程序或其中間形式從頭到尾掃描一遍，并作相關的加工處理，生成新的中間形式或一遍，并作相關的加工處理，生成新的中間形式或目標程序。目標程序。n編譯程序的結構受編譯程序的結構受“遍遍”的影響的影響u遍數遍數u分遍方式分遍方式一遍掃描的編譯程序一遍掃描的編譯程序多遍編譯程序多遍編譯程序Wensheng Li BUPT40一遍掃描的編譯程序一遍掃描的編譯程序語法分析器語法分析器取記號取記號詞法分析器詞法分析器源程序源程序記號記號語法成分語法成分語義分析及代碼生成語義分析及代碼生成目標程序目標程序返回返回控制流控制流數據流數據流開始開始結束結束整理目標程序整理目標程序Wensheng

32、 Li BUPT41多遍編譯程序多遍編譯程序編譯程序總控詞法分析器語法分析器語義分析器中間代碼生成代碼優(yōu)化目標代碼生成源程序中間語言1，表中間語言2，表中間語言3，表中間語言4，表優(yōu)化代碼，表目標代碼符號表管理錯誤處理Wensheng Li BUPT42編譯程序分遍的優(yōu)缺點編譯程序分遍的優(yōu)缺點n分遍的主要好處：分遍的主要好處：u可以減少對主存容量的要求可以減少對主存容量的要求u可使各遍編譯程序功能獨立、單純，相互聯系簡單，編譯可使各遍編譯程序功能獨立、單純，相互聯系簡單，編譯程序結構清晰。程序結構清晰。u能夠實現更充分的優(yōu)化工作，獲得高質量目標程序。能夠實現更充分的優(yōu)化工作，獲得高質量目標程序

33、。u通過分遍將編譯程序的前端和后端分開，可以為編譯程序通過分遍將編譯程序的前端和后端分開，可以為編譯程序的移植創(chuàng)造條件。的移植創(chuàng)造條件。n分遍的缺點：分遍的缺點：u增加了不少重復性的工作。增加了不少重復性的工作。Wensheng Li BUPT431.4 1.4 編譯程序的伙伴工具編譯程序的伙伴工具框架源程序預處理器標準源程序編譯程序目標匯編程序匯編程序可重定位機器代碼連接裝配程序絕對機器代碼庫，可重定位目標文件 Wensheng Li BUPT44一、預處理器一、預處理器二、匯編程序二、匯編程序三、連接裝配程序三、連接裝配程序編譯程序的前后處理器編譯程序的前后處理器Wensheng Li B

34、UPT45一、預處理器一、預處理器n預處理器的主要功能：預處理器的主要功能：1.1.宏處理宏處理2.2.文件包含文件包含3.3.語言擴充語言擴充Wensheng Li BUPT461. 1. 宏理器宏理器n預處理器允許用戶在源程序中定義宏。預處理器允許用戶在源程序中定義宏。nC C語言源程序中的一個宏定義：語言源程序中的一個宏定義： #define prompt(s) fprintf(stderr, s)#define prompt(s) fprintf(stderr, s)n宏處理器處理兩類語句，即宏定義和宏調用。宏處理器處理兩類語句，即宏定義和宏調用。u宏定義宏定義通常用統(tǒng)一的字符或關鍵字

35、表示，如通常用統(tǒng)一的字符或關鍵字表示，如definedefine或或macromacro，宏定義由宏名字及宏體組成，通常宏處理器允許，宏定義由宏名字及宏體組成，通常宏處理器允許在宏定義中使用形參。在宏定義中使用形參。u宏調用宏調用由調用宏的命令名（宏名）和所提供的實參組成。由調用宏的命令名（宏名）和所提供的實參組成。宏處理器用實參代替宏體中的形參，再用變換后的宏體替宏處理器用實參代替宏體中的形參，再用變換后的宏體替換宏調用本身。換宏調用本身。Wensheng Li BUPT472. 2. 文件包含文件包含n預處理器把文件的包含聲明擴展為程序正文。預處理器把文件的包含聲明擴展為程序正文。nC C

36、語言程序中的語言程序中的“頭文件頭文件”包含聲明行：包含聲明行： #include #include n預處理器處理到該語句時，就用文件預處理器處理到該語句時，就用文件stdio.hstdio.h的內的內容替換此語句。容替換此語句。Wensheng Li BUPT483. 3. 語言擴充語言擴充n有些預處理器用更先進的控制流和數據結構來增強有些預處理器用更先進的控制流和數據結構來增強原來的語言。原來的語言。n例如：例如：u預處理器可以將類似于預處理器可以將類似于whilewhile或或if-then-elseif-then-else語句結構的語句結構的內部宏提供給用戶使用，而這些結構在原來的程

37、序設計語內部宏提供給用戶使用，而這些結構在原來的程序設計語言中是沒有的。言中是沒有的。u當程序中使用了這樣的結構時，由預處理器通過宏調用實當程序中使用了這樣的結構時，由預處理器通過宏調用實現語言功能的擴充?，F語言功能的擴充。Wensheng Li BUPT49二、匯編程序二、匯編程序n匯編語言用助記符表示操作碼，用標識符表示存儲匯編語言用助記符表示操作碼，用標識符表示存儲地址。地址。n賦值語句賦值語句b:=a+2b:=a+2相應的匯編語言程序為相應的匯編語言程序為：MOV MOV R R1 1, , a aADD ADD R R1 1, #, #2 2MOV MOV b, b, R R1 1n

38、最簡單的匯編程序對輸入作兩遍掃描。最簡單的匯編程序對輸入作兩遍掃描。Wensheng Li BUPT50第一遍第一遍n找出標志存貯單元的所有標識符，并將它們存貯到找出標志存貯單元的所有標識符，并將它們存貯到匯編符號表匯編符號表中。中。u匯編符號表獨立于編譯程序的符號表匯編符號表獨立于編譯程序的符號表n在符號表中指定該標識符所對應的存儲單元地址，在符號表中指定該標識符所對應的存儲單元地址，此地址是在首次遇到該標識符時確定的。此地址是在首次遇到該標識符時確定的。n假定一個字包括假定一個字包括4 4個字節(jié)，每個變量占一個字，完成個字節(jié)，每個變量占一個字，完成第一遍掃描后，得到匯編符號表：第一遍掃描后

39、，得到匯編符號表： 標識符標識符 地址地址 a 0a 0 b 4 b 4Wensheng Li BUPT51第二遍第二遍n把每個用助記符表示的操作碼翻譯為二進制表示的把每個用助記符表示的操作碼翻譯為二進制表示的機器代碼。機器代碼。n把用標識符表示的存儲地址翻譯為匯編符號表中該把用標識符表示的存儲地址翻譯為匯編符號表中該標識符所對應的地址。標識符所對應的地址。n輸出通常是可重定位的機器代碼。輸出通常是可重定位的機器代碼。u起始地址為起始地址為0 0，各條指令及其所訪問的地址都是相對于，各條指令及其所訪問的地址都是相對于0 0的的邏輯地址。邏輯地址。u當裝入內存時，可以指定任意的地址當裝入內存時，

40、可以指定任意的地址L L作為開始單元。作為開始單元。n輸出中要對那些需要重定位的指令做出標記輸出中要對那些需要重定位的指令做出標記u標記供裝入程序識別，以便計算相應的物理地址。標記供裝入程序識別，以便計算相應的物理地址。Wensheng Li BUPT52可重定位機器代碼可重定位機器代碼n假定機器指令的格式為：假定機器指令的格式為： 操作符操作符 寄存器寄存器 尋址模式尋址模式 地址地址n假定假定： 0001 0001 代表代表 MOV MOV R R， S S 0011 0011 代表代表 ADDADD 0010 0010 代表代表 MOV MOV D D， R Rn第二第二遍輸出的可重定位

41、機器代碼：遍輸出的可重定位機器代碼： 0001 01 00 000000000001 01 00 00000000* * 0011 01 10 00000010 0011 01 10 00000010 0010 01 00 00000100 0010 01 00 00000100* *b:=a+2的匯編代碼的匯編代碼 MOV R1, a ADD R1, #2 MOV b, R1Wensheng Li BUPT53絕對機器代碼絕對機器代碼n假如裝入內存的起始地址為假如裝入內存的起始地址為L=00001111L=00001111n則則a a和和b b的地址分別是的地址分別是1515和和1919n則

42、裝入后的機器代碼為：則裝入后的機器代碼為： 0001 01 00 000011110001 01 00 00001111 0011 01 10 00000010 0011 01 10 00000010 0010 01 00 00010011 0010 01 00 00010011可重定位機器代碼：可重定位機器代碼： 0001 01 00 00000000* 0011 01 10 00000010 0010 01 00 00000100*Wensheng Li BUPT54三、連接裝配程序三、連接裝配程序n可重定位目標程序可重定位目標程序的的組成組成：u正文，目標程序的主要部分，包括指令代碼和數

43、據；正文，目標程序的主要部分，包括指令代碼和數據；u外部符號表外部符號表( (也稱全局符號表也稱全局符號表) )，記錄有本程序段引用的名，記錄有本程序段引用的名字和被其他程序段引用的名字；字和被其他程序段引用的名字；u重定位信息表，記錄有重定位所需要的有關信息。重定位信息表，記錄有重定位所需要的有關信息。n連接連接裝配程序裝配程序u作用：作用：把把多個經過編譯或匯編的目標模塊連接裝配成一個多個經過編譯或匯編的目標模塊連接裝配成一個完整的可執(zhí)行程序。完整的可執(zhí)行程序。u連接編輯程序連接編輯程序：掃描掃描外部符號表，尋找所連接的程序段，外部符號表，尋找所連接的程序段，根據重定位信息表解決外部引用和

44、重定位，最終將整個程根據重定位信息表解決外部引用和重定位，最終將整個程序涉及到的目標模塊逐個調入內存并連接在一起，組合成序涉及到的目標模塊逐個調入內存并連接在一起，組合成一個待裝入的程序一個待裝入的程序。u重定位重定位裝配裝配程序程序：把把目標模塊的相對地址轉換成絕對地址。目標模塊的相對地址轉換成絕對地址。Wensheng Li BUPT551.5 1.5 編譯原理的應用編譯原理的應用n語法制導的結構化編輯器語法制導的結構化編輯器n程序格式化工具程序格式化工具n軟件測試工具軟件測試工具n程序理解工具程序理解工具n高級語言的翻譯工具高級語言的翻譯工具Wensheng Li BUPT56語法制導的結構化編輯器語法制導的結構化編輯器n具有通常的正文編輯和修改功能具有通常的正文編輯和修改功能n能象編譯程序那樣對源程序進行分析，把恰當的層能象編譯程序那樣對源程序進行分析，把恰當的層次結構加在程序上。次結構加在程序上。n可以保證源程序可以保證源程序u無語法錯誤無語法錯誤u有統(tǒng)一的可讀性好的程序格式有統(tǒng)一的可讀性好的程序格式n結構化編輯器能夠執(zhí)行一些對編制源程序有用的附結構化編輯器能夠執(zhí)行一些對編制源程序有用的附加任務，如