編譯原理劉善梅第1章緒論2

1、編譯原理2自我介紹自我介紹n姓名：劉善梅姓名：劉善梅nqq qq ： 3068353030683530n辦公室：逸夫樓辦公室：逸夫樓c427c427n 郵箱：郵箱： 3課程介紹課程介紹n兩門獨立的課程：理論（兩門獨立的課程：理論（4848學時）學時） 實驗（實驗（1616學時）學時）n考試成績組成考試成績組成 理論：理論：平時作業(yè)和考勤占平時作業(yè)和考勤占20%20%，期末結業(yè)，期末結業(yè)考試占考試占80%80%； 實驗：實驗：根據(jù)實驗報告和程序源代碼評分，根據(jù)實驗報告和程序源代碼評分，實驗報告占實驗報告占40%, 40%, 程序源代碼占程序源代碼占60%60%。n課程特點：課程特點：難！難！4開

2、課目的：開課目的：介紹設計與構造程序設計語言介紹設計與構造程序設計語言編譯程序編譯程序的的原理與方法原理與方法源程序源程序編譯編譯程序程序目標程序目標程序連接連接可執(zhí)行程序可執(zhí)行程序預備知識：預備知識：形式語言與自動機、形式語言與自動機、兩門以上的高兩門以上的高級程序設計語級程序設計語言言匯編語言匯編語言數(shù)據(jù)結構等數(shù)據(jù)結構等how?5教學要求教學要求 通過課程的學習和實驗的完成，通過課程的學習和實驗的完成， 應該應該清楚的理解一個編譯程序是如何工作的；清楚的理解一個編譯程序是如何工作的； 如果在以后遇到了任何一個程序設計語言，如果在以后遇到了任何一個程序設計語言，應該應該知道如何實現(xiàn)這個語言的

3、多數(shù)機制；知道如何實現(xiàn)這個語言的多數(shù)機制； 應應具有一定的使用編譯構造工具開發(fā)編譯程序的具有一定的使用編譯構造工具開發(fā)編譯程序的經(jīng)驗；經(jīng)驗； 會會將所學的常用技術和算法應用于類似的軟件的將所學的常用技術和算法應用于類似的軟件的設計和實現(xiàn)中。設計和實現(xiàn)中。理論課內(nèi)容簡介：理論課內(nèi)容簡介：第一章：緒論 第二章：編譯基礎(形式語言 、有窮自動機等）第三章：詞法分析 第四章：語法分析第五章：語法制導翻譯和中間代碼生成第七章：程序運行時的存貯分配問題第八章：代碼優(yōu)化第九章：目標代碼生成 第六章：符號表實驗課內(nèi)容簡介：實驗課內(nèi)容簡介：第一次課：詞法分析 （4學時）第二次課：語法分析 （4學時）第三次課：詞

4、義分析、代碼生成 （4學時）第四次課：小型c語言編譯器設計（4學時）詳細實驗內(nèi)容請見實驗要求和實驗指導書8教材：教材：編譯原理編譯原理（第（第2版），張素琴、呂映芝、蔣維杜、戴桂版），張素琴、呂映芝、蔣維杜、戴桂 蘭，清華大學出版社蘭，清華大學出版社 2004參考書：參考書：教材及主要參考書教材及主要參考書 compilers: principles, technigues, and tools alfred v.aho, ravi sethi, jeffrey d.ullman, addison-wesley,1986. 譯著版：機械工業(yè)出版社，譯著版：機械工業(yè)出版社，2003，李建中，姜守

5、旭譯。，李建中，姜守旭譯。(龍書）龍書） 中文名：編譯原理技術和工具中文名：編譯原理技術和工具 modern compiler implementation in java modern compiler implementation in c andrew w.appel，人民郵電出版社影印，人民郵電出版社影印，2005 （虎書）（虎書） 中文名：現(xiàn)代編譯原理中文名：現(xiàn)代編譯原理 advanced compiler design and implementation steven s. muchnick, 1997. 機械工業(yè)出版社影印機械工業(yè)出版社影印，2003 （鯨書）（鯨書） 中文名：

6、高級編譯器設計與實現(xiàn)中文名：高級編譯器設計與實現(xiàn)內(nèi)地內(nèi)地 陳火旺（國防科大版）陳火旺（國防科大版） 陳意云（中國科技大學版）陳意云（中國科技大學版） 王生原等（人民郵電版）王生原等（人民郵電版） 王生原等（清華大學第三版）王生原等（清華大學第三版） 主要參考書主要參考書10第一章緒論第一章緒論n編譯器就是一個編譯器就是一個程序程序，它，它讀入讀入用某種語言用某種語言編寫的源程序，并編寫的源程序，并翻譯翻譯成一個成一個與之等價與之等價的的另一種語言編寫的源程序。另一種語言編寫的源程序。編譯器編譯器源程序源程序目標程序目標程序錯誤信息錯誤信息fortran、pascal、java、 c .另一種程

7、序另一種程序設計語言、設計語言、匯編語匯編語言、機言、機器語言器語言1.1什么是編譯程序什么是編譯程序什么是編譯程序什么是編譯程序 編譯程序編譯程序通常通常是是從較高級語言的程序翻譯從較高級語言的程序翻譯 至較低級語言的程序至較低級語言的程序，如，如c 代碼匯編代碼a c compilerc+ 代碼匯編代碼a c+ compilerc+ 代碼c代碼another c+ compilerjava 代碼bytecode代碼a java compiler121.2編譯過程概述編譯過程概述編譯程序的工作，從輸入源程序開始，到輸出目編譯程序的工作，從輸入源程序開始，到輸出目標程序結束，與自然語言之間的翻

8、譯有很多相似之處。標程序結束，與自然語言之間的翻譯有很多相似之處。 一段英文翻譯成中文，一段英文翻譯成中文，需經(jīng)下列步驟：需經(jīng)下列步驟：識別出句子中的單詞識別出句子中的單詞分析句子的語法結構分析句子的語法結構根據(jù)句子的含義進行初步分析根據(jù)句子的含義進行初步分析對譯文進行修飾對譯文進行修飾寫出最后的譯文寫出最后的譯文編譯程序編譯程序詞法分析詞法分析代碼優(yōu)化代碼優(yōu)化語法分析語法分析語義分析及中語義分析及中間代碼生成間代碼生成目標代碼生成目標代碼生成構成編譯程構成編譯程序各個階段序各個階段i am a teacher.13編譯器的各個階段：編譯器的各個階段：編譯器是分編譯器是分階段執(zhí)行的。階段執(zhí)行的

9、。每個階段將源程每個階段將源程序從一種表示轉序從一種表示轉換成另一種表示換成另一種表示源程序源程序詞法分析器詞法分析器錯錯誤誤處處理理器器符符號號管管理理表表語法分析器語法分析器語義分析器語義分析器中間代碼生成器中間代碼生成器代碼優(yōu)化器代碼優(yōu)化器代碼生成器代碼生成器編譯的各編譯的各個階段個階段14各分析階段各分析階段隨著編譯器各個階段的進展，源程序的內(nèi)部表示不隨著編譯器各個階段的進展，源程序的內(nèi)部表示不斷地發(fā)生變化。斷地發(fā)生變化。以以a=b+c *d為例為例1。詞法分析。詞法分析讀入源程序讀入源程序完成的任務：完成的任務：識別出單詞：識別出單詞： a、=、b、+、c 、 *、 d并用記號方式表

10、示識別出的單詞并用記號方式表示識別出的單詞關鍵字、標識關鍵字、標識符、常數(shù)、算符、常數(shù)、算符和界符符和界符例：例：25表示表示a、b、c、d；36：；：；2：；：；31：*記號表示邏輯記號表示邏輯上相關的字符上相關的字符序列，常用整序列，常用整數(shù)來表示數(shù)來表示上述單詞表示為：上述單詞表示為：(25,a),(36,=),(25,b),(32,+),(25,c),(31,*),(25,d)n程序文本程序文本if x = y then z := 1 else z := 2; 經(jīng)詞法分析，變成一個個單詞經(jīng)詞法分析，變成一個個單詞nif, x, =, y, then, z, :=, 1, else, z

11、, :=, 2, ;n語言的單詞符號是由語言的單詞符號是由詞法規(guī)則詞法規(guī)則所確定的。所確定的。詞法詞法規(guī)則規(guī)則規(guī)定了字母表中哪樣的字符串是一個單詞規(guī)定了字母表中哪樣的字符串是一個單詞符號。符號。又例，又例， 從左至右掃描字符流的源程序從左至右掃描字符流的源程序、分解構成源、分解構成源程序的字符串，程序的字符串，識別出識別出(拼拼)一個個的一個個的單詞單詞（符號）（符號） 單詞符號是語言中具有獨立意義的最基本單詞符號是語言中具有獨立意義的最基本結構。多數(shù)程序語言中，結構。多數(shù)程序語言中，單詞單詞符號一般符號一般包括包括 各類型的各類型的常數(shù)、保留字、標識符常數(shù)、保留字、標識符、運算符、界符、運算

12、符、界符等等。等等。 詞法分析詞法分析第一步識別單詞第一步識別單詞position := initial + rate * 60;單詞類型單詞類型單詞值單詞值 標識符標識符1(id1) position 算符算符(賦值賦值) := 標識符標識符2(id2) initial 算符算符(加加) + 標識符標識符3(id3) rate 算符算符(乘乘) * 整數(shù)整數(shù) 60 分號分號 ；詞法分析詞法分析18語法分析語法分析在詞法分析的基礎上，根據(jù)語言的語法規(guī)則，在詞法分析的基礎上，根據(jù)語言的語法規(guī)則，把單詞符號串組成各類語法單位把單詞符號串組成各類語法單位.具體的說，語法分析是在單詞流的基礎上建立具體

13、的說，語法分析是在單詞流的基礎上建立一個層次結構一個層次結構-建立語法樹建立語法樹賦值語句賦值語句標識符標識符=表達式表達式 id1表達式表達式標識符標識符 id2 +表達式表達式表達式表達式*標識符標識符 id3表達式表達式 整數(shù)整數(shù) 60語法分析語法分析 舉例舉例id1 := id2 + id3 * 60 ;（pascal）語法規(guī)則）語法規(guī)則 :=“:=” :=“+” :=“*” :=“(”“)” := := := 賦值語句賦值語句標識符標識符表達式表達式表達式表達式+表達式表達式表達式表達式標識符標識符整數(shù)整數(shù)標識符標識符:=表達式表達式*id1:=id2+id3*60:=+60*id1

14、id2id322語義分析階段語義分析階段語義分析利用語法分析階段確定的層次結構來識別語義分析利用語法分析階段確定的層次結構來識別表達式和語句中的操作信息及類型信息表達式和語句中的操作信息及類型信息= + a b*c dtemp1=c*dtemp2=b+temp1 temp1 temp2a=temp2語義分析語義分析n 句子的結構理解了，句子的結構理解了，撲捉它的撲捉它的“含義含義” 如：杰克說杰瑞把他的作業(yè)落在了家里。如：杰克說杰瑞把他的作業(yè)落在了家里。 “他的他的”是誰的？是誰的？ 又：杰克說杰克把他的作業(yè)落在了家里。又：杰克說杰克把他的作業(yè)落在了家里。 幾個杰克？幾個杰克？n杰克把她的作業(yè)

15、落在了家里。杰克把她的作業(yè)落在了家里。（杰克是男生）（杰克是男生）“杰克杰克”和和“她的她的”不一致。不一致。 “杰克杰克”和和“他的他的”才匹配才匹配語義分析語義分析25中間代碼生成階段中間代碼生成階段本階段將產(chǎn)生源程序的一個顯式中間表示本階段將產(chǎn)生源程序的一個顯式中間表示這種中間表示可以看成是某種抽象的程這種中間表示可以看成是某種抽象的程序，通常是與平臺無關的序，通常是與平臺無關的其重要性質：其重要性質：1.易于產(chǎn)生易于產(chǎn)生2.易于翻譯成目標程序易于翻譯成目標程序下面是用下面是用三地址碼三地址碼（四元式）（四元式）表示的例子：表示的例子：temp1=c*dtemp2=b+temp1a=te

16、mp2（* , c , d , tempt1) (+ , b, tempt1 , tempt2) (= , tempt2 , , a)id1:= id2 + id3 * 60(1)(inttoreal, 60, ,t1)(2)(*,id3,t1,t2)(3)(+,id2,t2,t3)(4)(:=,t3,id1)27代碼優(yōu)化階段代碼優(yōu)化階段對代碼進行變換對代碼進行變換以使得編譯產(chǎn)生的目標代碼更高效以使得編譯產(chǎn)生的目標代碼更高效（執(zhí)行速度更快）（執(zhí)行速度更快）。對上面中間代碼進行優(yōu)化處理后，產(chǎn)生如對上面中間代碼進行優(yōu)化處理后，產(chǎn)生如下的代碼：下的代碼：temp1=c*da=b+temp1temp1

17、=c*dtemp2=b+temp1a=temp2如下程序 語法分析結果j = 2 * i + 1;if (j = n) j = 2 * i + 3;return aj;t1 = 2 * it2 = t1 + 1j = t2t3 = j nif t3 goto l0t4 = 2 * it5 = t4 + 3j = t5l0: t6 = ajreturn t6t1 = 2 * it2 = t1 + 1j = t2t3 = j nif t3 goto l0t4 = 2 * it5 = t4 + 3j = t5l0: t6 = ajreturn t6t1 = 2 * ij = t1 + 1t3 = j

18、 nif t3 goto l0 j = t1 + 3l0: t6 = ajreturn t6代碼優(yōu)化代碼優(yōu)化代碼優(yōu)化代碼優(yōu)化id1:= id2 + id3 * 60(1)(inttoreal60-t1)(2)( * id3 t1t2)(3)( +id2t2t3)(4)( :=t3-id1) 變換變換 （1） ( *id360.0 t1) ( 2）（）（ + id2 t1id1)31代碼生成階段代碼生成階段生成目標機機器代碼或匯編代碼生成目標機機器代碼或匯編代碼(*,id360.0 t1)(+,id2t1id1)movf id3,r2mulf #60.0,r2movf id2,r1addf r2

19、,r1movf r1,id1nexample: a in r0, i in r1, n in r2t1 = 2 * ij = t1 + 1t3 = j nif t3 goto l0 j = t1 + 3l0: t6 = ajreturn t6sll r1, 1, r1add r1, 1, jcmp j,r2blt .ll3add r1, 3, j.ll3: ld r0+j, rt retr代碼生成代碼生成n記錄記錄源程序中使用的源程序中使用的標識符標識符n收集收集每個標識符的各種每個標識符的各種屬性信息屬性信息n普通變量：普通變量：類型、作用域、分配存儲信息類型、作用域、分配存儲信息n函數(shù)或過

20、程：函數(shù)或過程：參數(shù)個數(shù)、類型、傳遞方法參數(shù)個數(shù)、類型、傳遞方法 返回值類型返回值類型符號表管理符號表管理(登錄，查找）登錄，查找）1.3 符號表符號表34符號表管理符號表管理int a,b;float e,fchar ch1,ch2;為什么要先說明為什么要先說明? 定義了變量的類型，也就規(guī)定了變量定義了變量的類型，也就規(guī)定了變量在內(nèi)存中的存放形式，在其上所能進行的在內(nèi)存中的存放形式，在其上所能進行的運算運算解決符號地址到存貯地址上的映射解決符號地址到存貯地址上的映射35編譯器的一個基本功能是編譯器的一個基本功能是記錄源程序中使用記錄源程序中使用的標識符的標識符并將它們并將它們記載到符號表中記

21、載到符號表中。符號表是一個數(shù)據(jù)結構。符號表是一個數(shù)據(jù)結構。 每個標識符在符號表中都有每個標識符在符號表中都有一條記錄一條記錄名字名字記號記號類型類型種屬種屬 addrid1(25)id2(25) b a例：例：int a,b;int簡變簡變 0 4 并并收集與每個標識符相關的各種屬收集與每個標識符相關的各種屬性信息，性信息，int簡變簡變36在編譯的各個階段都會發(fā)現(xiàn)源程序中的錯誤，在編譯的各個階段都會發(fā)現(xiàn)源程序中的錯誤，1.4錯誤檢測與報告錯誤檢測與報告為了使編譯器能繼續(xù)運行，以檢測出源程序中為了使編譯器能繼續(xù)運行，以檢測出源程序中更多的錯誤，在檢測到錯誤后，必須以合適的方式更多的錯誤，在檢測

22、到錯誤后，必須以合適的方式進行錯誤處理。進行錯誤處理。error37小結：小結：編譯器編譯器的各個的各個階段階段源程序源程序詞法分析器詞法分析器錯錯誤誤處處理理器器符符號號管管理理表表語法分析器語法分析器語義分析器語義分析器中間代碼生成器中間代碼生成器代碼優(yōu)化器代碼優(yōu)化器代碼生成器代碼生成器38編譯的前端和后端編譯的前端和后端 前端包括詞法分析、語法分析、語前端包括詞法分析、語法分析、語義分析，以及相關的錯誤處理和符號表義分析，以及相關的錯誤處理和符號表的建立的建立 前端依賴于源程序并在很大程度上前端依賴于源程序并在很大程度上獨立于目標機器。獨立于目標機器。39 后端主要包括代碼優(yōu)化、代碼生成

23、和相后端主要包括代碼優(yōu)化、代碼生成和相關錯誤處理。關錯誤處理。 后端依賴于目標機器。后端依賴于目標機器。 后端處理對象是由前端產(chǎn)生的結果，即中后端處理對象是由前端產(chǎn)生的結果，即中間代碼間代碼 前端生成與平臺無關的字節(jié)碼前端生成與平臺無關的字節(jié)碼 后端是由與平臺有關的解釋器對所生成后端是由與平臺有關的解釋器對所生成的字節(jié)碼文件進行解釋執(zhí)行的字節(jié)碼文件進行解釋執(zhí)行java語言的編譯采用的是前端后端方式。語言的編譯采用的是前端后端方式。編譯程序的組織編譯程序的組織 編譯程序的遍編譯程序的遍（passes / phases）- 對一種代碼形式從頭到尾掃描一遍對一種代碼形式從頭到尾掃描一遍- 將一個代碼

24、空間變換到另一個代碼空間將一個代碼空間變換到另一個代碼空間- 代碼空間代碼空間 = 代碼代碼 + 符號表符號表 + 其他有用信息其他有用信息 編譯程序的組織取決于各遍的組織編譯程序的組織取決于各遍的組織- 單遍單遍編譯程序，編譯程序，多遍多遍編譯程序編譯程序- 多個遍之間有邏輯上的先后關系多個遍之間有邏輯上的先后關系- 多個遍的實現(xiàn)可采用順序結構或并發(fā)結構多個遍的實現(xiàn)可采用順序結構或并發(fā)結構 （后者不常用）（后者不常用）編譯程序的組織編譯程序的組織 例：一個以語法、語義分析程序為中心的例：一個以語法、語義分析程序為中心的 單遍編譯程序單遍編譯程序組織組織source programtarget

25、 program語法、語義語法、語義分析程序分析程序詞法分詞法分析程序析程序代碼生代碼生成程序成程序編譯程序的伙伴程序編譯程序的伙伴程序 解釋程序解釋程序（interpreter）- 不產(chǎn)生目標程序文件不產(chǎn)生目標程序文件- 不區(qū)別翻譯階段和執(zhí)行階段不區(qū)別翻譯階段和執(zhí)行階段- 翻譯源程序的每條語句后直接執(zhí)行翻譯源程序的每條語句后直接執(zhí)行- 程序執(zhí)行期間一直有解釋程序守候程序執(zhí)行期間一直有解釋程序守候- 常用于實現(xiàn)虛擬機常用于實現(xiàn)虛擬機 比較比較編譯程序和解釋程序編譯程序和解釋程序源程序源程序編譯程序編譯程序目標程序目標程序輸入輸入目標程序目標程序輸出輸出解釋程序解釋程序輸出輸出輸入輸入源程序源程序 預處理程序預處理程序（preprocessor）- 支持宏定義支持宏定義（macro definition） 如c源程序中 #define 行的處理- 支持文件包含支持文件包含（file inclusion） 如c源程序中 #include 行的處理- 支持其他更復雜的源程序擴展信息支持其他更復雜