編譯原理及實現(xiàn),任課教師：韋艷艷 聯(lián)系電話E-mail：,編譯原理-課前思考,為什么有些語言規(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)了“一次編寫，到處運行”？ ,學(xué)習(xí)目的,了解和掌握設(shè)計和構(gòu)造編譯程序的基本原理、基本技術(shù)及其實現(xiàn)方法，加深對計算機系統(tǒng)的了解，培養(yǎng)和提高計算（機）思維能力。,各章節(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課時）,學(xué)習(xí)要求,認(rèn)真聽課 積極練習(xí) 課后復(fù)習(xí),編譯原理好難！,參考書目,張幸兒編，計算機編譯原理編譯程序構(gòu)造實踐(第二版)，科學(xué)出版社，2009年 劉磊等編，編譯程序的設(shè)計與實現(xiàn)，高等教育出版社，2004年 趙克佳等譯，現(xiàn)代編譯原理C語言描述，人民郵電出版社，2006年 張素琴，呂映芝等編，編譯原理（第2版），清華大學(xué)出版社，2005年 趙建華等譯，編譯原理(第2版)，機械工業(yè)出版社，2009年,編譯原理(原書第2版) 作者： (美)Alfred V.Aho Monica S.Lam Ravi Sethi Jeffrey D.Ullman 譯者： 趙建華 鄭滔 戴新宇 出版社：機械工業(yè)出版社,編譯領(lǐng)域里程碑式的經(jīng)典著作龍書,原版封面,中文版封面,課程學(xué)習(xí)網(wǎng)站,清華大學(xué) /courses/jsj/GD_jsj_009b/index.htm 北京航空航天大學(xué)/compile/ 武漢大學(xué) /jpkc2005/byyl/index.html,題 外 話,基本：完成課程學(xué)習(xí)，通過考試，獲得學(xué)分。 提高：能夠?qū)⑺鶎W(xué)知識和內(nèi)容用于解決實際問題。 飛躍：通過編譯原理的學(xué)習(xí)，改進思維方式，為將來的工作打好基礎(chǔ)，終身受益。,考試成績評定方法,平時（30%） 作業(yè)、課堂練習(xí)和出勤(25%) 上機編程(15%) 期考（70%） 考試方式：筆試（閉卷） 考試題型：填空題 判斷題 選擇題 綜合應(yīng)用題,No man is born wise or learned. 沒有生而知之者,第1章 編譯概述,學(xué)習(xí)內(nèi)容： 1.1 程序設(shè)計語言 1.2 翻譯程序 1.3 編譯程序的組成 1.4 編譯程序的結(jié)構(gòu) 1.5 編譯程序的前后處理器 1.6 TEST語言與編譯器,第1章 編譯概述,學(xué)習(xí)重點： 1、編譯程序 2、編譯程序與解釋程序的根本區(qū)別 3、典型的編譯程序模型及其各組成 部分的功能,回顧：程序與程序設(shè)計語言,程序：為實現(xiàn)特定目標(biāo)或解決特定問題而用計算機語言編寫的指令序列的集合。 常見的程序設(shè)計語言： C+, Java, C, FORTRAN, Pascal, Lisp, Basic, ML等,程序輸入,程序輸出,高級語言,機器語言,1.1 程序設(shè)計語言(p1),1、機器語言（最低形式，屬低級語言） 特點：程序中的每條指令都是用二進制代碼直接表示的，由它構(gòu)成機器的指令系統(tǒng)，機器能直接識別和直接執(zhí)行，但機器語言程序難寫、難讀、難修改，編程的工作量大，對程序員的要求高。 機器語言程序示例： 00111110 00011010 11111110 00100100 11010011 00101111 01110110,2、匯編語言（屬低級語言） 特點：它是機器語言的符號表示，例如用ADD表示加法，可讀性等方面較機器語言有一定的改進，但還依賴于具體的機器，機器不能直接識別和直接執(zhí)行。,匯編語言程序示例： LD A，26 /把26送到變量A ADD A，36 /加上36 OUT (48)，A /輸出到48號端口 HALT /暫停,3、高級語言 特點：它獨立于機器，比較接近自然語言，因而容易學(xué)習(xí)和掌握，且編寫程序效率高，編寫出的程序易讀、易理解、易修改、易移植，但機器不能直接識別和直接執(zhí)行。,C語言程序示例： int a,c=2; a=16+c*2; printf(a=%d,a);,高 匯 級 編 語 語 言 言 程 程 序 序,翻譯程序,1.2 翻譯程序(p2),1、除機器語言程序外，用其它語言編寫的程序都必須翻譯才能被計算機識別和執(zhí)行。 2、翻譯程序的定義： 翻譯程序是這樣的一種程序，它能將用甲語言（源語言）編寫的程序（源程序）翻譯成與之等價的乙語言（目標(biāo)語言）編寫的程序（目標(biāo)程序）。,3、翻譯程序在計算機系統(tǒng)中的所在層,翻譯程序?qū)儆谙到y(tǒng)軟件 !,4、翻譯方式 （1）解釋方式（相當(dāng)口譯） 特點：源程序的翻譯到執(zhí)行只有一個階段解釋執(zhí)行階段，即：解釋程序?qū)丛闯绦蛑姓Z句的動態(tài)順序，逐句地進行分析解釋，并立即予以執(zhí)行。在這種翻譯方式下，不生成目標(biāo)代碼。,（2）編譯方式（相當(dāng)筆譯） 特點：源程序的翻譯和目標(biāo)程序的運行是分階段進行的，它先將高級語言編寫的源程序翻譯成匯編語言程序或機器語言程序，然后再運行目標(biāo)程序。,編譯程序 vs. 解釋程序,編譯,解釋,a.當(dāng)目標(biāo)程序是機器語言程序時，源程序從編譯到被執(zhí)行的過程分為兩個階段：,b.當(dāng)目標(biāo)程序是匯編語言程序時，源程序從編譯到被執(zhí)行的過程分為三個階段：,看起來，編譯器似乎完全能代替匯編?。?回答是No。 Why? 高級語言通過編譯器轉(zhuǎn)化成的機器語言，受限于高級語言，其效率和功能上都有限制。比如不能過分操作內(nèi)存。但通過匯編器轉(zhuǎn)化過來的機器語言，效率高，且用匯編語言，可直接和CPU對話！ 匯編可以反匯編（逆向編譯），即： 程序（二進制機器語言）通過反匯編器（compiler），可轉(zhuǎn)化為匯編代碼（文本） 但永遠不能轉(zhuǎn)化為高級語言的源代碼！,C 語 言 編 譯 系 統(tǒng),（見p9）,5、兩種翻譯方式的比較 編譯方式與解釋方式的根本區(qū)別在于是否生成目標(biāo)代碼。 在解釋方式下執(zhí)行源程序，易于查錯，在程序執(zhí)行中可以修改程序(代表有BASIC語言) 。但和編譯方式相比，執(zhí)行效率太低。 現(xiàn)在有些語言的集成開發(fā)環(huán)境提供了兩種方式，如Visual Basic，調(diào)試期間可解釋執(zhí)行源程序，而調(diào)好的程序可以編譯生成目標(biāo)程序。,編譯過程,自然語言的翻譯（如把英文翻譯為中文 ） 識別出句子中的一個個單詞； 分析句子的語法結(jié)構(gòu)； 根據(jù)句子的含義進行初步翻譯； 對譯文進行修飾； 寫出最后的譯文。,詞法分析,語法分析,中間代碼產(chǎn)生,優(yōu)化,目標(biāo)代碼產(chǎn)生,例 The monkey ate the banana. 例 A compiler is a computer program that transforms source code written in a programming language into another computer language.,一個平滑的字符流,變成一個單詞序列,得到語法成分,更接近機器語言,更高的效率,達到目標(biāo),走向目標(biāo)1,走向目標(biāo)2,走向目標(biāo)3,走向目標(biāo)4,走向目標(biāo)5,1.3 編譯程序的組成(p3),1、詞法分析程序（又稱掃描器） 詞法分析依次讀入源程序中的每個字符，依據(jù)語言的構(gòu)詞規(guī)則，識別出一個個具有獨立意義的最小語法單位，即“單詞”，并用整數(shù)碼或有意義的記號來表示每個單詞的詞性是保留字、標(biāo)識符、分界符、運算符或常數(shù)。 例如，表達式a=10+c*20的詞法分析結(jié)果如右表所示。,2、語法分析程序 依據(jù)語言的語法規(guī)則，逐一地分析詞法分析時得到的單詞，以確定它們是怎樣組成說明和語句的，以及說明和語句是怎樣組成程序的。 分析時如發(fā)現(xiàn)有不合語法規(guī)則的地方，則報告出錯位置和性質(zhì)；如無語法錯誤，則以另一種內(nèi)部表示（如語法分析樹或其它中間表示）給出正確的語法結(jié)構(gòu)，供下一階段分析使用。,“猴子吃香蕉”的 語法分析樹,a=10+c*20的語法分析樹,3、語義分析程序 依據(jù)語言的語義規(guī)則對語法分析得到的語法結(jié)構(gòu)進行靜態(tài)語義檢查（即確定類型、類型和運算合法性檢查、識別含義與相應(yīng)的語義處理及其它一些靜態(tài)語義檢查），并用另一種內(nèi)部形式表示出來，供下一階段使用。 4、中間代碼生成程序（可有可無） 根據(jù)語法成分的語義對其進行翻譯，用另一種接近于計算機的指令形式（中間代碼）表示出來，供下一階段使用。,語義分析及中間代碼生成示例,5、中間代碼優(yōu)化程序(可有可無),6、目標(biāo)代碼生成程序 將中間代碼或優(yōu)化之后的中間代碼轉(zhuǎn)換為等價的目標(biāo)代碼。 目標(biāo)代碼的形式可以是絕對指令代碼、可重定位的機器指令代碼或匯編指令代碼。目標(biāo)代碼依賴于具體的計算機的硬件系統(tǒng)結(jié)構(gòu)和指令系統(tǒng)。,7、符號表處理程序 編譯過程中要記錄源程序中出現(xiàn)的標(biāo)識符，并收集每個標(biāo)識符的各種屬性信息。符號表是由若干記錄組成的數(shù)據(jù)結(jié)構(gòu)，每個標(biāo)識符在表中有一條記錄。 標(biāo)識符的各種屬性是在編譯的不同階段填入符號表的。詞法分析階段只能分析出標(biāo)識符名，語法分析階段只能判斷標(biāo)識符在語句中出現(xiàn)是否合法，語義分析階段將標(biāo)識符的各種屬性填入符號表并使用這些屬性生成中間代碼。,8、出錯處理程序 編譯的各個階段都可能發(fā)現(xiàn)源程序中的錯誤。任意時刻發(fā)現(xiàn)錯誤，都應(yīng)該報告錯誤信息，包括錯誤出現(xiàn)的位置、錯誤性質(zhì)等，為程序員調(diào)試程序提供方便，從而使編譯能繼續(xù)進行。 詞法分析可以檢測出源程序中的非法符號。語法分析能夠發(fā)現(xiàn)程序語句中的各種語法錯誤，如括號不匹配等等。語義分析能判斷運算對象的類型是否匹配、變量是否重復(fù)聲明或沒聲明就使用等錯誤。 例 int a,b; a= 2*)12+b);,C編譯器,不同的編譯器，其結(jié)構(gòu)也不一定相同！,FORTRAN 編譯器,1.4 編譯程序的結(jié)構(gòu)(p7),1、遍（趟，趟程） 所謂一遍是指一個編譯程序在編譯時把源程序或其中間代碼從頭到尾掃描一遍并完成相應(yīng)工作的全過程。在一遍處理中，可完成編譯程序六個任務(wù)中的一個或幾個。 2、單遍與多遍編譯程序 根據(jù)編譯程序在完成翻譯任務(wù)的過程中需要對源程序或其中間代碼掃描的遍數(shù)，可以把編譯程序分為單遍編譯程序(只需掃描一遍)和多遍編譯程序（需掃描多遍）。,（1）單遍編譯程序舉例 編譯程序?qū)υ闯绦蛑贿M行一遍掃描，就完成編譯的各項任務(wù)，其典型結(jié)構(gòu)是：以語法分析程序為主程序，詞法分析程序作為語法分析的一個子程序，當(dāng)語法分析需要一個新單詞時，便調(diào)用詞法分析程序，當(dāng)它識別出一個語法成分時，就調(diào)用語義分析程序。,具體做法：將整個編譯程序劃分為若干個相繼執(zhí)行的模塊，每一模塊都對它前一模塊的輸出掃描一遍，并完成相應(yīng)工作，然后將工作結(jié)果送給下一模塊加工。,（2）多遍編譯程序舉例,例如，三遍編譯程序：把詞法分析作為第一遍，語法分析和語義分析作為第二遍，代碼生成作為第三遍。有：,3、遍的劃分依據(jù) 源語言的繁簡 宿主機的存儲容量的大小 編譯程序功能的強弱 目標(biāo)程序優(yōu)化的程度 實現(xiàn)工具的先進程度 設(shè)計人員的素質(zhì)和數(shù)量 當(dāng)源語言較繁、編譯程序功能很強、目標(biāo)程序優(yōu)化程度較高且宿主機存儲容量較小時，宜采用多遍掃描方式。,4、前端和后端(p8),把編譯程序分為前端和后端的優(yōu)點是便于編譯程序的構(gòu)造和移植。 例如，有K種高級語言、L種目標(biāo)機器，如果不分前端和后端，就需要建立K*L套編譯程序，而分成前端和后端，只需要建立K（前端）+L（后端）套編譯程序。,C,P,B,A,B,中 間 語 言,1.6 TEST語言與編譯器（p10）,一、TEST語言 TEST語言程序是由一對花括號括起來的語句序列，它在語法上相當(dāng)于C語言的函數(shù)體。 聲明語句：只能是簡單的整型變量 控制語句：if、while和for語句 表達式語句：布爾表達式和算術(shù)表達式 算術(shù)運算符： +、*、/ 比較運算符： 、=、=和!= 輸入語句：read語句 輸出語句：write語句 注釋語句：用“/*”和“*/”括起來，但注釋不能嵌套。,一個TEST語言程序 int i; int n; int j; j=1; read n; /*輸入語句*/ for (i=1;i=n;i=i+1) j=j*i; write j; /*輸出語句*/ ,二、TEST編譯器,TEST編譯器包括以下3個C文件： 1、TESTmain.c：主程序，先后調(diào)用詞法分析、語法分析及語義分析和代碼生成子程序。 2、TESTscan.c：詞法分析子程序，接收用TEST語言編寫的程序，輸出的單詞符號程序?qū)⒆鳛檎Z法分析的輸入。 3、TESTparse.c：語法、語義分析及TEST機的匯編代碼生成子程序，如果有錯誤，報告錯誤。,詞 法 分 析,語法分析 語義分析 代碼生成,TEST程序,TEST單詞,TEST機匯編代碼,三、TEST機,用一個抽象機的匯編語言作為TEST編譯器的目標(biāo)語言。TEST機的指令僅能作為TEST語言的目標(biāo)。TEST機的模擬程序直接從一個文件中讀取匯編代碼并執(zhí)行它，因此避免了由匯編語言翻譯為機器代碼的過程。但是，這個模擬程序并非是一個真正的匯編程序，它沒有符號地址或標(biāo)號。,TEST編譯器,TEST