編譯概述精品課件

1、編譯概述第1頁，共54頁，2022年，5月20日，20點35分，星期二編譯原理-課前思考為什么有些語言規(guī)定標(biāo)識符不能超過8個字符？而有些語言對標(biāo)識符的長度無限制？ 為什么有些語言能實現(xiàn)遞歸，而有些語言不能？ C語言規(guī)定數(shù)組下界為0，上界為聲明的數(shù)減1，為什么？ 嵌套的IF語句規(guī)定ELSE與上面最近的IF配對，為什么？為什么有些程序運行一段時間后會導(dǎo)致內(nèi)存溢出？為什么Java實現(xiàn)了“一次編寫，到處運行”？ 第2頁，共54頁，2022年，5月20日，20點35分，星期二學(xué)習(xí)目的 了解和掌握設(shè)計和構(gòu)造編譯程序的基本原理、基本技術(shù)及其實現(xiàn)方法，加深對計算機系統(tǒng)的了解，培養(yǎng)和提高計算（機）思維能力。第3

2、頁，共54頁，2022年，5月20日，20點35分，星期二各章節(jié)內(nèi)容第1章 編譯概述（2課時）第2章 文法和語言（6課時）第3章 詞法分析（6+4課時）第4章 語法分析-自頂向下分析（6+4課時）第5章 語法分析-自底向上分析（6課時）第6章 語法制導(dǎo)翻譯技術(shù)（6課時）第7章 符號表管理技術(shù) （2課時）第8章 程序運行時的存儲組織及管理 （2課時）第9章 語義分析和代碼生成（6+4課時）第10章 代碼優(yōu)化（2課時）第4頁，共54頁，2022年，5月20日，20點35分，星期二學(xué)習(xí)要求認(rèn)真聽課積極練習(xí)課后復(fù)習(xí)編譯原理好難！第5頁，共54頁，2022年，5月20日，20點35分，星期二參考書目張幸

3、兒編，計算機編譯原理編譯程序構(gòu)造實踐(第二版)，科學(xué)出版社，2009年劉磊等編，編譯程序的設(shè)計與實現(xiàn)，高等教育出版社，2004年趙克佳等譯，現(xiàn)代編譯原理C語言描述，人民郵電出版社，2006年張素琴，呂映芝等編，編譯原理（第2版），清華大學(xué)出版社，2005年趙建華等譯，編譯原理(第2版)，機械工業(yè)出版社，2009年第6頁，共54頁，2022年，5月20日，20點35分，星期二編譯原理(原書第2版)作者： (美)Alfred V.Aho Monica S.Lam Ravi Sethi Jeffrey D.Ullman 譯者： 趙建華 鄭滔 戴新宇 出版社：機械工業(yè)出版社 編譯領(lǐng)域里程碑式的經(jīng)典著作

4、龍書原版封面中文版封面第7頁，共54頁，2022年，5月20日，20點35分，星期二課程學(xué)習(xí)網(wǎng)站清華大學(xué)北京航空航天大學(xué)武漢大學(xué)第8頁，共54頁，2022年，5月20日，20點35分，星期二題 外 話基本：完成課程學(xué)習(xí)，通過考試，獲得學(xué)分。提高：能夠?qū)⑺鶎W(xué)知識和內(nèi)容用于解決實際問題。飛躍：通過編譯原理的學(xué)習(xí)，改進(jìn)思維方式，為將來的工作打好基礎(chǔ)，終身受益。第9頁，共54頁，2022年，5月20日，20點35分，星期二考試成績評定方法平時（30%） 作業(yè)、課堂練習(xí)和出勤(25%) 上機編程(15%)期考（70%） 考試方式：筆試（閉卷） 考試題型：填空題 判斷題 選擇題 綜合應(yīng)用題第10頁，共54

5、頁，2022年，5月20日，20點35分，星期二No man is born wise or learned. 沒有生而知之者第1章 編譯概述第11頁，共54頁，2022年，5月20日，20點35分，星期二學(xué)習(xí)內(nèi)容：1.1 程序設(shè)計語言1.2 翻譯程序1.3 編譯程序的組成1.4 編譯程序的結(jié)構(gòu)1.5 編譯程序的前后處理器1.6 TEST語言與編譯器第12頁，共54頁，2022年，5月20日，20點35分，星期二第1章 編譯概述學(xué)習(xí)重點：1、編譯程序2、編譯程序與解釋程序的根本區(qū)別3、典型的編譯程序模型及其各組成 部分的功能第13頁，共54頁，2022年，5月20日，20點35分，星期二回顧：

6、程序與程序設(shè)計語言程序：為實現(xiàn)特定目標(biāo)或解決特定問題而用計算機語言編寫的指令序列的集合。常見的程序設(shè)計語言： C+, Java, C, FORTRAN, Pascal, Lisp, Basic, ML等程序輸入程序輸出高級語言機器語言第14頁，共54頁，2022年，5月20日，20點35分，星期二1.1 程序設(shè)計語言(p1) 1、機器語言（最低形式，屬低級語言） 特點：程序中的每條指令都是用二進(jìn)制代碼直接表示的，由它構(gòu)成機器的指令系統(tǒng)，機器能直接識別和直接執(zhí)行，但機器語言程序難寫、難讀、難修改，編程的工作量大，對程序員的要求高。 機器語言程序示例： 00111110 00011010 1111

7、1110 00100100 11010011 00101111 01110110 第15頁，共54頁，2022年，5月20日，20點35分，星期二2、匯編語言（屬低級語言） 特點：它是機器語言的符號表示，例如用ADD表示加法，可讀性等方面較機器語言有一定的改進(jìn)，但還依賴于具體的機器，機器不能直接識別和直接執(zhí)行。匯編語言程序示例：LD A，26 /把26送到變量AADD A，36 /加上36 OUT (48)，A /輸出到48號端口 HALT /暫停第16頁，共54頁，2022年，5月20日，20點35分，星期二 3、高級語言 特點：它獨立于機器，比較接近自然語言，因而容易學(xué)習(xí)和掌握，且編寫程序

8、效率高，編寫出的程序易讀、易理解、易修改、易移植，但機器不能直接識別和直接執(zhí)行。C語言程序示例：int a,c=2; a=16+c*2; printf(a=%d,a); 第17頁，共54頁，2022年，5月20日，20點35分，星期二高 匯級 編語 語言 言程 程序 序翻譯程序第18頁，共54頁，2022年，5月20日，20點35分，星期二1.2 翻譯程序(p2)1、除機器語言程序外，用其它語言編寫的程序都必須翻譯才能被計算機識別和執(zhí)行。2、翻譯程序的定義： 翻譯程序是這樣的一種程序，它能將用甲語言（源語言）編寫的程序（源程序）翻譯成與之等價的乙語言（目標(biāo)語言）編寫的程序（目標(biāo)程序）。第19頁

9、，共54頁，2022年，5月20日，20點35分，星期二3、翻譯程序在計算機系統(tǒng)中的所在層翻譯程序?qū)儆谙到y(tǒng)軟件 ! 第20頁，共54頁，2022年，5月20日，20點35分，星期二4、翻譯方式（1）解釋方式（相當(dāng)口譯） 特點：源程序的翻譯到執(zhí)行只有一個階段解釋執(zhí)行階段，即：解釋程序?qū)丛闯绦蛑姓Z句的動態(tài)順序，逐句地進(jìn)行分析解釋，并立即予以執(zhí)行。在這種翻譯方式下，不生成目標(biāo)代碼。第21頁，共54頁，2022年，5月20日，20點35分，星期二（2）編譯方式（相當(dāng)筆譯） 特點：源程序的翻譯和目標(biāo)程序的運行是分階段進(jìn)行的，它先將高級語言編寫的源程序翻譯成匯編語言程序或機器語言程序，然后再運行目標(biāo)程序

10、。 第22頁，共54頁，2022年，5月20日，20點35分，星期二編譯程序 vs. 解釋程序編譯解釋第23頁，共54頁，2022年，5月20日，20點35分，星期二a.當(dāng)目標(biāo)程序是機器語言程序時，源程序從編譯到被執(zhí)行的過程分為兩個階段： 第24頁，共54頁，2022年，5月20日，20點35分，星期二b.當(dāng)目標(biāo)程序是匯編語言程序時，源程序從編譯到被執(zhí)行的過程分為三個階段：第25頁，共54頁，2022年，5月20日，20點35分，星期二看起來，編譯器似乎完全能代替匯編??！回答是No。Why?高級語言通過編譯器轉(zhuǎn)化成的機器語言，受限于高級語言，其效率和功能上都有限制。比如不能過分操作內(nèi)存。但通過

11、匯編器轉(zhuǎn)化過來的機器語言，效率高，且用匯編語言，可直接和CPU對話！ 匯編可以反匯編（逆向編譯），即： 程序（二進(jìn)制機器語言）通過反匯編器（compiler），可轉(zhuǎn)化為匯編代碼（文本） 但永遠(yuǎn)不能轉(zhuǎn)化為高級語言的源代碼！ 第26頁，共54頁，2022年，5月20日，20點35分，星期二預(yù)處理器源程序標(biāo)準(zhǔn)源程序 可重定位機器代碼可重定位目標(biāo)文件庫文件編譯程序匯編程序目標(biāo)匯編程序連接加載程序絕對機器代碼C語言編譯系統(tǒng)（見p9）宏處理文件包含條件編譯第27頁，共54頁，2022年，5月20日，20點35分，星期二5、兩種翻譯方式的比較編譯方式與解釋方式的根本區(qū)別在于是否生成目標(biāo)代碼。 在解釋方式下執(zhí)

12、行源程序，易于查錯，在程序執(zhí)行中可以修改程序(代表有BASIC語言) 。但和編譯方式相比，執(zhí)行效率太低?，F(xiàn)在有些語言的集成開發(fā)環(huán)境提供了兩種方式，如Visual Basic，調(diào)試期間可解釋執(zhí)行源程序，而調(diào)好的程序可以編譯生成目標(biāo)程序。 第28頁，共54頁，2022年，5月20日，20點35分，星期二編譯過程自然語言的翻譯（如把英文翻譯為中文 ）識別出句子中的一個個單詞；分析句子的語法結(jié)構(gòu)；根據(jù)句子的含義進(jìn)行初步翻譯；對譯文進(jìn)行修飾；寫出最后的譯文。 詞法分析語法分析中間代碼產(chǎn)生優(yōu)化目標(biāo)代碼產(chǎn)生例 The monkey ate the banana.例 A compiler is a compu

13、ter program that transforms source code written in a programming language into another computer language. 第29頁，共54頁，2022年，5月20日，20點35分，星期二一個平滑的字符流變成一個單詞序列得到語法成分更接近機器語言更高的效率達(dá)到目標(biāo)走向目標(biāo)1走向目標(biāo)2走向目標(biāo)3走向目標(biāo)4走向目標(biāo)51.3 編譯程序的組成(p3)第30頁，共54頁，2022年，5月20日，20點35分，星期二第31頁，共54頁，2022年，5月20日，20點35分，星期二1、詞法分析程序（又稱掃描器） 詞法分析

14、依次讀入源程序中的每個字符，依據(jù)語言的構(gòu)詞規(guī)則，識別出一個個具有獨立意義的最小語法單位，即“單詞”，并用整數(shù)碼或有意義的記號來表示每個單詞的詞性是保留字、標(biāo)識符、分界符、運算符或常數(shù)。例如，表達(dá)式a=10+c*20的詞法分析結(jié)果如右表所示。整數(shù)碼記號單詞100IDa21=200NUM1022+100IDc25*200NUM20第32頁，共54頁，2022年，5月20日，20點35分，星期二2、語法分析程序 依據(jù)語言的語法規(guī)則，逐一地分析詞法分析時得到的單詞，以確定它們是怎樣組成說明和語句的，以及說明和語句是怎樣組成程序的。 分析時如發(fā)現(xiàn)有不合語法規(guī)則的地方，則報告出錯位置和性質(zhì)；如無語法錯誤，

15、則以另一種內(nèi)部表示（如語法分析樹或其它中間表示）給出正確的語法結(jié)構(gòu)，供下一階段分析使用?！昂镒映韵憬丁钡恼Z法分析樹第33頁，共54頁，2022年，5月20日，20點35分，星期二a=10+c*20的語法分析樹第34頁，共54頁，2022年，5月20日，20點35分，星期二3、語義分析程序 依據(jù)語言的語義規(guī)則對語法分析得到的語法結(jié)構(gòu)進(jìn)行靜態(tài)語義檢查（即確定類型、類型和運算合法性檢查、識別含義與相應(yīng)的語義處理及其它一些靜態(tài)語義檢查），并用另一種內(nèi)部形式表示出來，供下一階段使用。4、中間代碼生成程序（可有可無） 根據(jù)語法成分的語義對其進(jìn)行翻譯，用另一種接近于計算機的指令形式（中間代碼）表示出來，供下

16、一階段使用。第35頁，共54頁，2022年，5月20日，20點35分，星期二語義分析及中間代碼生成示例第36頁，共54頁，2022年，5月20日，20點35分，星期二5、中間代碼優(yōu)化程序(可有可無)第37頁，共54頁，2022年，5月20日，20點35分，星期二6、目標(biāo)代碼生成程序 將中間代碼或優(yōu)化之后的中間代碼轉(zhuǎn)換為等價的目標(biāo)代碼。 目標(biāo)代碼的形式可以是絕對指令代碼、可重定位的機器指令代碼或匯編指令代碼。目標(biāo)代碼依賴于具體的計算機的硬件系統(tǒng)結(jié)構(gòu)和指令系統(tǒng)。第38頁，共54頁，2022年，5月20日，20點35分，星期二7、符號表處理程序 編譯過程中要記錄源程序中出現(xiàn)的標(biāo)識符，并收集每個標(biāo)識符

17、的各種屬性信息。符號表是由若干記錄組成的數(shù)據(jù)結(jié)構(gòu)，每個標(biāo)識符在表中有一條記錄。 標(biāo)識符的各種屬性是在編譯的不同階段填入符號表的。詞法分析階段只能分析出標(biāo)識符名，語法分析階段只能判斷標(biāo)識符在語句中出現(xiàn)是否合法，語義分析階段將標(biāo)識符的各種屬性填入符號表并使用這些屬性生成中間代碼。 標(biāo)識符名標(biāo)識符類型 類型 地址 aaa1（表示變量） 1（表示整型） 0001 第39頁，共54頁，2022年，5月20日，20點35分，星期二8、出錯處理程序 編譯的各個階段都可能發(fā)現(xiàn)源程序中的錯誤。任意時刻發(fā)現(xiàn)錯誤，都應(yīng)該報告錯誤信息，包括錯誤出現(xiàn)的位置、錯誤性質(zhì)等，為程序員調(diào)試程序提供方便，從而使編譯能繼續(xù)進(jìn)行。

18、詞法分析可以檢測出源程序中的非法符號。語法分析能夠發(fā)現(xiàn)程序語句中的各種語法錯誤，如括號不匹配等等。語義分析能判斷運算對象的類型是否匹配、變量是否重復(fù)聲明或沒聲明就使用等錯誤。 例 int a,b; a= 2*)12+b);第40頁，共54頁，2022年，5月20日，20點35分，星期二C編譯器不同的編譯器，其結(jié)構(gòu)也不一定相同！FORTRAN 編譯器第41頁，共54頁，2022年，5月20日，20點35分，星期二1.4 編譯程序的結(jié)構(gòu)(p7)1、遍（趟，趟程） 所謂一遍是指一個編譯程序在編譯時把源程序或其中間代碼從頭到尾掃描一遍并完成相應(yīng)工作的全過程。在一遍處理中，可完成編譯程序六個任務(wù)中的一個

19、或幾個。2、單遍與多遍編譯程序 根據(jù)編譯程序在完成翻譯任務(wù)的過程中需要對源程序或其中間代碼掃描的遍數(shù)，可以把編譯程序分為單遍編譯程序(只需掃描一遍)和多遍編譯程序（需掃描多遍）。第42頁，共54頁，2022年，5月20日，20點35分，星期二（1）單遍編譯程序舉例 編譯程序?qū)υ闯绦蛑贿M(jìn)行一遍掃描，就完成編譯的各項任務(wù)，其典型結(jié)構(gòu)是：以語法分析程序為主程序，詞法分析程序作為語法分析的一個子程序，當(dāng)語法分析需要一個新單詞時，便調(diào)用詞法分析程序，當(dāng)它識別出一個語法成分時，就調(diào)用語義分析程序。第43頁，共54頁，2022年，5月20日，20點35分，星期二 具體做法：將整個編譯程序劃分為若干個相繼執(zhí)行

20、的模塊，每一模塊都對它前一模塊的輸出掃描一遍，并完成相應(yīng)工作，然后將工作結(jié)果送給下一模塊加工。 （2）多遍編譯程序舉例 例如，三遍編譯程序：把詞法分析作為第一遍，語法分析和語義分析作為第二遍，代碼生成作為第三遍。有：第44頁，共54頁，2022年，5月20日，20點35分，星期二3、遍的劃分依據(jù)源語言的繁簡宿主機的存儲容量的大小編譯程序功能的強弱目標(biāo)程序優(yōu)化的程度實現(xiàn)工具的先進(jìn)程度設(shè)計人員的素質(zhì)和數(shù)量 當(dāng)源語言較繁、編譯程序功能很強、目標(biāo)程序優(yōu)化程度較高且宿主機存儲容量較小時，宜采用多遍掃描方式。第45頁，共54頁，2022年，5月20日，20點35分，星期二4、前端和后端(p8)第46頁，共

21、54頁，2022年，5月20日，20點35分，星期二 把編譯程序分為前端和后端的優(yōu)點是便于編譯程序的構(gòu)造和移植。 例如，有K種高級語言、L種目標(biāo)機器，如果不分前端和后端，就需要建立K*L套編譯程序，而分成前端和后端，只需要建立K（前端）+L（后端）套編譯程序。CPBAB中間語言第47頁，共54頁，2022年，5月20日，20點35分，星期二1.6 TEST語言與編譯器（p10）一、TEST語言 TEST語言程序是由一對花括號括起來的語句序列，它在語法上相當(dāng)于C語言的函數(shù)體。 聲明語句：只能是簡單的整型變量 控制語句：if、while和for語句 表達(dá)式語句：布爾表達(dá)式和算術(shù)表達(dá)式 算術(shù)運算符： +、*、/ 比較運算符： 、=、=和!= 輸入語句：read語句 輸出語句：write語句 注釋語句：用“/*”和“*/”括起來，但注釋不能嵌套。 第48頁，共54頁，2022年，5月20日，20點35分，星期二一個TEST語言程序 int i; int n; int j; j=1; read n; /*輸入語句*/ for (i=1;i=n;i=i+1) j=j*i; write j; /*輸出語句*/第49頁，共54頁，2022年，5月20日，20點35分，星期二二、TEST編譯器TEST編譯器包括以下3個C文件：1、TESTmain.c：主程序，先后調(diào)用詞法分析、語法分析及語義分