Chapter 01--編譯概述

1、LI Wensheng, SCS, BUPT 第第1 1章章 編譯概述編譯概述知識(shí)點(diǎn)：知識(shí)點(diǎn)：翻譯、解釋、編譯翻譯、解釋、編譯 編譯的階段、任務(wù)、及典型結(jié)構(gòu)編譯的階段、任務(wù)、及典型結(jié)構(gòu) 編譯程序的伙伴工具編譯程序的伙伴工具Wensheng Li BUPT2編譯概述編譯概述 簡介簡介1.1 1.1 翻譯和解釋翻譯和解釋1.2 1.2 編譯的階段和任務(wù)編譯的階段和任務(wù)1.3 1.3 編譯有關(guān)的其他概念編譯有關(guān)的其他概念1.4 1.4 編譯程序的伙伴工具編譯程序的伙伴工具1.5 1.5 編譯原理的編譯原理的應(yīng)用應(yīng)用 小結(jié)小結(jié)Wensheng Li BUPT3簡介簡介n什么是編譯？什么是編譯？u把源程

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

3、高級(jí)語言u(píng)過程性語言過程性語言面向用戶的語言面向用戶的語言 如：如：C C、PascalPascalu專用語言專用語言面向問題的語言面向問題的語言 如：如：SQLSQLu面向?qū)ο蟮恼Z言面向?qū)ο蟮恼Z言 如：如：JavaJava、C+C+Wensheng Li BUPT6高級(jí)語言的優(yōu)點(diǎn)高級(jí)語言的優(yōu)點(diǎn)n高級(jí)語言獨(dú)立于機(jī)器。所編程序移植性比較好。高級(jí)語言獨(dú)立于機(jī)器。所編程序移植性比較好。n不必考慮不必考慮存儲(chǔ)存儲(chǔ)空間空間的的分配問題分配問題，不需要了解數(shù)據(jù)，不需要了解數(shù)據(jù)從從外部外部形式轉(zhuǎn)換成形式轉(zhuǎn)換成機(jī)器內(nèi)部形式的細(xì)節(jié)機(jī)器內(nèi)部形式的細(xì)節(jié)。u用變量描述存儲(chǔ)單元用變量描述存儲(chǔ)單元n具有豐富的數(shù)據(jù)結(jié)構(gòu)和控

4、制結(jié)構(gòu)。具有豐富的數(shù)據(jù)結(jié)構(gòu)和控制結(jié)構(gòu)。u數(shù)據(jù)結(jié)構(gòu)：數(shù)組、記錄等數(shù)據(jù)結(jié)構(gòu)：數(shù)組、記錄等u控制結(jié)構(gòu)：循環(huán)、分支、過程調(diào)用等。控制結(jié)構(gòu)：循環(huán)、分支、過程調(diào)用等。n更接近于自然語言。更接近于自然語言。u可讀性好，便于維護(hù)?？勺x性好，便于維護(hù)。n編程效率高。編程效率高。Wensheng Li BUPT7二、翻譯程序二、翻譯程序n翻譯程序掃描所輸入的源程序，并將其轉(zhuǎn)換為目標(biāo)翻譯程序掃描所輸入的源程序，并將其轉(zhuǎn)換為目標(biāo)程序，程序，或?qū)⒃闯绦蛑苯臃g成結(jié)果或?qū)⒃闯绦蛑苯臃g成結(jié)果。翻譯程序翻譯程序源程序源程序目標(biāo)程序或執(zhí)行結(jié)果目標(biāo)程序或執(zhí)行結(jié)果n翻譯程序分為兩大類：翻譯程序分為兩大類：1.1.編譯程序編譯程序

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

20、代碼生成n中間代碼：一種抽象的機(jī)器程序中間代碼：一種抽象的機(jī)器程序n中間代碼應(yīng)具有兩個(gè)重要的特點(diǎn)：中間代碼應(yīng)具有兩個(gè)重要的特點(diǎn)：u易于產(chǎn)生易于產(chǎn)生u易于翻譯成目標(biāo)代碼易于翻譯成目標(biāo)代碼n中間代碼有多種形式中間代碼有多種形式n三地址代碼三地址代碼具有的特點(diǎn)：具有的特點(diǎn)：u每條指令除了賦值號(hào)之外，最多還有一個(gè)運(yùn)算符。每條指令除了賦值號(hào)之外，最多還有一個(gè)運(yùn)算符。u編譯程序必須生成臨時(shí)變量名，以便保留每條指令的計(jì)算編譯程序必須生成臨時(shí)變量名，以便保留每條指令的計(jì)算結(jié)果。結(jié)果。u有些有些“三地址三地址”指令少于三個(gè)操作數(shù)指令少于三個(gè)操作數(shù)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)化：對(duì)對(duì)代碼進(jìn)行改進(jìn)，使之占用的空間少、運(yùn)行速度代碼進(jìn)行改進(jìn)，使之占用的空間少、運(yùn)行速度快?？?。n代碼優(yōu)化首先是在中間代碼上進(jìn)行的代碼優(yōu)化首先是在中間代碼上進(jìn)行的。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)化編譯程序：能夠完成大多數(shù)優(yōu)化的完成大多數(shù)優(yōu)化的編譯程序。編譯程序。29temp1:=id2*4.0temp2:=id1+temp1id1:=temp2 Wensheng Li BUPT306. 6. 目標(biāo)代碼生成目標(biāo)代碼生成n生成的目標(biāo)代碼一般是可以重定位的機(jī)器代碼或匯生成的目標(biāo)代碼一般是可以重定位的機(jī)器代碼或匯編語言代碼。編語

23、言代碼。n涉及到的兩個(gè)重要問題：涉及到的兩個(gè)重要問題：u對(duì)程序中使用的每個(gè)變量要指定存儲(chǔ)單元對(duì)程序中使用的每個(gè)變量要指定存儲(chǔ)單元u對(duì)變量進(jìn)行寄存器分配對(duì)變量進(jìn)行寄存器分配Wensheng Li BUPT31total:=total+ratetotal:=total+rate* *4 4 的目標(biāo)代碼的目標(biāo)代碼 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的各綜合步驟及結(jié)果的各綜合步驟及結(jié)果中間代碼生成代碼優(yōu)化目標(biāo)代碼生成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)化目標(biāo)代碼生成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三、符號(hào)表管理三、符號(hào)表管理n編譯程序的一項(xiàng)重要工作：編譯程序的一項(xiàng)重要工作：u記錄源程序中使用的標(biāo)識(shí)符記錄源程序中使用的標(biāo)識(shí)符u收集每個(gè)標(biāo)識(shí)符的各種屬性信息收集每個(gè)標(biāo)識(shí)符的各種屬性信息n符號(hào)表是由若干記錄組成的數(shù)據(jù)結(jié)構(gòu)符號(hào)表是由若干記錄組成的數(shù)據(jù)結(jié)構(gòu)u每個(gè)標(biāo)識(shí)符在表中有一條記錄每個(gè)標(biāo)識(shí)符在表中有一條記錄u記錄的域是標(biāo)識(shí)符的屬性記錄的域是標(biāo)識(shí)符的屬性n對(duì)符號(hào)表結(jié)構(gòu)的要求：對(duì)符號(hào)表結(jié)構(gòu)的要求：u應(yīng)允許快速地找到標(biāo)識(shí)符的記錄應(yīng)允許快速地找到標(biāo)識(shí)符的記錄u可在其中存取數(shù)據(jù)可在其中存取數(shù)據(jù)n標(biāo)識(shí)符的各種屬性是在編譯的各個(gè)不同階段填入符標(biāo)識(shí)符的各種屬性是在編譯的各個(gè)不同階段填入符號(hào)表的。號(hào)

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

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

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

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

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

32、 Li BUPT41多遍編譯程序多遍編譯程序編譯程序總控詞法分析器語法分析器語義分析器中間代碼生成代碼優(yōu)化目標(biāo)代碼生成源程序中間語言1，表中間語言2，表中間語言3，表中間語言4，表優(yōu)化代碼，表目標(biāo)代碼符號(hào)表管理錯(cuò)誤處理Wensheng Li BUPT42編譯程序分遍的優(yōu)缺點(diǎn)編譯程序分遍的優(yōu)缺點(diǎn)n分遍的主要好處：分遍的主要好處：u可以減少對(duì)主存容量的要求可以減少對(duì)主存容量的要求u可使各遍編譯程序功能獨(dú)立、單純，相互聯(lián)系簡單，編譯可使各遍編譯程序功能獨(dú)立、單純，相互聯(lián)系簡單，編譯程序結(jié)構(gòu)清晰。程序結(jié)構(gòu)清晰。u能夠?qū)崿F(xiàn)更充分的優(yōu)化工作，獲得高質(zhì)量目標(biāo)程序。能夠?qū)崿F(xiàn)更充分的優(yōu)化工作，獲得高質(zhì)量目標(biāo)程序

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

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

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

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

37、序設(shè)計(jì)語內(nèi)部宏提供給用戶使用，而這些結(jié)構(gòu)在原來的程序設(shè)計(jì)語言中是沒有的。言中是沒有的。u當(dāng)程序中使用了這樣的結(jié)構(gòu)時(shí)，由預(yù)處理器通過宏調(diào)用實(shí)當(dāng)程序中使用了這樣的結(jié)構(gòu)時(shí)，由預(yù)處理器通過宏調(diào)用實(shí)現(xiàn)語言功能的擴(kuò)充?，F(xiàn)語言功能的擴(kuò)充。Wensheng Li BUPT49二、匯編程序二、匯編程序n匯編語言用助記符表示操作碼，用標(biāo)識(shí)符表示存儲(chǔ)匯編語言用助記符表示操作碼，用標(biāo)識(shí)符表示存儲(chǔ)地址。地址。n賦值語句賦值語句b:=a+2b:=a+2相應(yīng)的匯編語言程序?yàn)橄鄳?yīng)的匯編語言程序?yàn)椋篗OV MOV R R1 1, , a aADD ADD R R1 1, #, #2 2MOV MOV b, b, R R1 1n

38、最簡單的匯編程序?qū)斎胱鲀杀閽呙?。最簡單的匯編程序?qū)斎胱鲀杀閽呙?。Wensheng Li BUPT50第一遍第一遍n找出標(biāo)志存貯單元的所有標(biāo)識(shí)符，并將它們存貯到找出標(biāo)志存貯單元的所有標(biāo)識(shí)符，并將它們存貯到匯編符號(hào)表匯編符號(hào)表中。中。u匯編符號(hào)表獨(dú)立于編譯程序的符號(hào)表匯編符號(hào)表獨(dú)立于編譯程序的符號(hào)表n在符號(hào)表中指定該標(biāo)識(shí)符所對(duì)應(yīng)的存儲(chǔ)單元地址，在符號(hào)表中指定該標(biāo)識(shí)符所對(duì)應(yīng)的存儲(chǔ)單元地址，此地址是在首次遇到該標(biāo)識(shí)符時(shí)確定的。此地址是在首次遇到該標(biāo)識(shí)符時(shí)確定的。n假定一個(gè)字包括假定一個(gè)字包括4 4個(gè)字節(jié)，每個(gè)變量占一個(gè)字，完成個(gè)字節(jié)，每個(gè)變量占一個(gè)字，完成第一遍掃描后，得到匯編符號(hào)表：第一遍掃描后

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

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

41、機(jī)器代碼：遍輸出的可重定位機(jī)器代碼： 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絕對(duì)機(jī)器代碼絕對(duì)機(jī)器代碼n假如裝入內(nèi)存的起始地址為假如裝入內(nèi)存的起始地址為L=00001111L=00001111n則則a a和和b b的地址分別是的地址分別是1515和和1919n則

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

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

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