西安電子科技大學(xué)編譯原理.ppt

《西安電子科技大學(xué)編譯原理.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《西安電子科技大學(xué)編譯原理.ppt（24頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、編 譯 原 理,西安電子科技大學(xué) 軟件工程研究所 劉 堅(jiān),2,題外話,一、本課程討論的領(lǐng)域和希望達(dá)到的目的 11 領(lǐng)域 程序設(shè)計(jì)語(yǔ)言的應(yīng)用程序設(shè)計(jì)（PLA） 程序設(shè)計(jì)語(yǔ)言的翻譯編譯器的構(gòu)造（PLT） 程序設(shè)計(jì)語(yǔ)言的設(shè)計(jì)語(yǔ)法、語(yǔ)義（PLD）,12 CCC 2002 中國(guó)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科教程（China Computing Curricula 2002，CCC2002）提出的計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科的知識(shí)體系，包括了14個(gè)基本的知識(shí)領(lǐng)域。與本課程相關(guān)的： 1程序設(shè)計(jì)基礎(chǔ)（PF）：程序設(shè)計(jì)基本結(jié)構(gòu)、算法與問題求解、基本數(shù)據(jù)結(jié)構(gòu)、遞歸、事件驅(qū)動(dòng)程序設(shè)計(jì)。（PLA） 2程序設(shè)計(jì)語(yǔ)言（PL）：程序設(shè)計(jì)

2、語(yǔ)言概論、虛擬機(jī)、語(yǔ)言翻譯簡(jiǎn)介、聲明和類型、抽象機(jī)制、面向?qū)ο蟪绦蛟O(shè)計(jì)（以上是核心）；函數(shù)程序設(shè)計(jì)、語(yǔ)言翻譯系統(tǒng)、類型系統(tǒng)、程序設(shè)計(jì)語(yǔ)言的語(yǔ)義、程序設(shè)計(jì)語(yǔ)言的設(shè)計(jì)（以上是選修）。（PLA、PLT、PLD）,3,題外話（續(xù)1）,13 目的 1了解PL的基本要素、工作原理、語(yǔ)言翻譯的基本方法； 2用不同的PL進(jìn)行程序設(shè)計(jì)，即自學(xué)計(jì)算機(jī)語(yǔ)言的能力； 3具備語(yǔ)言翻譯的基本技能。,二、學(xué)習(xí)方法 21 本課程的特點(diǎn) 理論與實(shí)踐并重 理論學(xué)習(xí)要嚴(yán)謹(jǐn)、方法掌握要靈活 提高自學(xué)能力（push與pull）,22 理論與技術(shù)的關(guān)系 適應(yīng)飛速變化的技術(shù)的根本是注重基礎(chǔ)理論學(xué)習(xí) 理論的演變是緩慢的、理論基礎(chǔ)是相通的

3、相同的原理可以應(yīng)用于不同的技術(shù),例1 質(zhì)能守恒、物質(zhì)不滅、借貸 內(nèi)存與外存速度的差異：虛存 虛盤,4,題外話（續(xù)2）,23 勤動(dòng)手、多實(shí)踐、提高學(xué)習(xí)能力 1 學(xué)到的知識(shí)是死的，總有過時(shí)的時(shí)候。只有通過學(xué)習(xí)知識(shí)提高學(xué)習(xí)能力，才是立于不敗之地的保證。 2記筆記：好記性不如爛筆頭，通過動(dòng)手加深理解和記憶。 3做作業(yè)、做上機(jī)題：自己動(dòng)手為主，參考“解答”為輔。,24 如何使用習(xí)題與上機(jī)題解答 合理利用“解答”有助于課程的學(xué)習(xí)?！敖獯稹奔炔煌耆_也不是最好的。 1習(xí)題解答：先做作業(yè)，后看解答。如不符，思考原因，找出最好的答案。 2上機(jī)解答：先看題目要求，根據(jù)要求自己設(shè)計(jì)并實(shí)現(xiàn)。如有困難，可部分參考

4、解答。 3提倡學(xué)生獨(dú)立思考，對(duì)發(fā)現(xiàn)解答錯(cuò)誤并給出正確解法、做出選做題、做出上機(jī)題擴(kuò)充部分者，給予加分獎(jiǎng)勵(lì)。（只給第一組，寫明姓名、日期。加分按人平分） 4根據(jù)需要，可適當(dāng)上一、兩次習(xí)題課（學(xué)生預(yù)先提題目，若課時(shí)緊張則不占正課時(shí)間）。,5,題外話（續(xù)3）,三、其他 31 課代表與輔導(dǎo) 1課代表的職責(zé)：收繳作業(yè)；安排上機(jī)時(shí)間、聯(lián)系上機(jī)事宜；反映同學(xué)意見；監(jiān)督輔導(dǎo)老師的工作。 2輔導(dǎo)時(shí)間：每周一次，課代表與同學(xué)商量后確定。,32 作業(yè)與上機(jī)作業(yè) 1第二、五章收繳一次，第三、四章收繳兩次。有獨(dú)立見解的可直接交給主講老師，包括，指出解答的錯(cuò)誤并給出正確答案、選做題答案等。（僅以第一個(gè)收到的為準(zhǔn)，包括上屆

5、） 2驗(yàn)收上機(jī)題，并收繳上機(jī)報(bào)告。報(bào)告內(nèi)容根據(jù)個(gè)人對(duì)題目要求的理解寫。,33 參考書目（重點(diǎn)） 1人民郵電出版社（影印本，編譯原理 技術(shù)與工具）Aho等，Compilers - Principles, Techniques, and Tools，1986 2清華大學(xué)出版社，呂映芝等，“編譯原理” 3清華大學(xué)出版社（影印版）Hopcroft等，Introduction to Automata Theory, Languages, and Computation(Second Edition),6,第一章 引言,1.1 從面向機(jī)器的語(yǔ)言到面向人類的語(yǔ)言 面向機(jī)器的語(yǔ)言：機(jī)器指令、匯編語(yǔ)言 面向人類

6、的語(yǔ)言：通用程序設(shè)計(jì)語(yǔ)言、非過程式語(yǔ)言，等等, 計(jì)算機(jī)語(yǔ)言舉例 例2 通用程序設(shè)計(jì)語(yǔ)言與匯編語(yǔ)言（包括機(jī)器指令） Pascal語(yǔ)句：x := a+b； 匯編指令：十六進(jìn)制代碼匯編指令 A10002 MOV AX, A 8B1E0202 MOV BX, B 01D8 ADD AX, BX A30402 MOV X, AX,7, 計(jì)算機(jī)語(yǔ)言舉例（續(xù)）,給出003號(hào)學(xué)生所選課程與成績(jī)： Select 學(xué)號(hào),姓名,課程名,成績(jī) from 學(xué)生,選課 where 學(xué)生.學(xué)號(hào)=“003” ;,例4 LEX的正規(guī)式： a-za-z0-9* return id; YACC的產(chǎn)生式：E : E +

7、 E | E * E | id;,例3 SQL 學(xué)生： 選課：,,,8, 按范型劃分的程序設(shè)計(jì)語(yǔ)言,CCC2002PL： 1過程式語(yǔ)言、面向?qū)ο笳Z(yǔ)言：通用程序設(shè)計(jì)語(yǔ)言，包括FORTRAN、Pascal、C/C++、Ada83/Ada95、Java等； 2函數(shù)語(yǔ)言：面向特點(diǎn)領(lǐng)域的、遞歸特性，典型代表：Lisp； 3說(shuō)明性、非算法式語(yǔ)言：濃厚的數(shù)學(xué)特征，典型代表：LEX/YACC、SQL； 4腳本式語(yǔ)言：僅是一種安排，沒有復(fù)雜的邏輯關(guān)系，典型代表：shell語(yǔ)言。,PROGRAMMING LANGUAGES Design and Implementation(影印，清華) (

8、Terrence W.Pratt and Marvin V.Zelkowitz) 1. Simple Procedural Languages：FORTRAN C 2. Block-Structured Procedural Languages：Pascal 3. Object-Based Languages：Ada C++ Smalltalk 4. Functional Languages：LISP ML 5. Logic Programming Languages：Prolog,9, 其他面向特定應(yīng)用領(lǐng)域的語(yǔ)言,1互連網(wǎng)應(yīng)用：HTML、XML 2計(jì)算機(jī)輔助設(shè)計(jì)：MATLAB 3集成電路設(shè)計(jì)

9、：VHDL、Verilog 4虛擬現(xiàn)實(shí)：VRML ,問題： 如何將形形色色的語(yǔ)言翻譯成可以在計(jì)算機(jī)上運(yùn)行的0、1串,10,1.2 語(yǔ)言之間的翻譯,習(xí)慣稱法： 匯編語(yǔ)言機(jī)器指令：匯編（或交叉匯編） 程序設(shè)計(jì)語(yǔ)言匯編語(yǔ)言或機(jī)器指令：編譯（或解釋） 高級(jí)語(yǔ)言之間：轉(zhuǎn)換（或預(yù)編譯） 逆向：反匯編、反編譯,11,1.3 編譯器與解釋器,語(yǔ)言翻譯的兩種基本形態(tài) 1.先翻譯后執(zhí)行 2. 邊翻譯邊執(zhí)行,例5 假設(shè)有源程序：read(x); write(x=, x);,12,1.3 編譯器與解釋器（續(xù)）,特點(diǎn)： 1編譯器：工作效率高，即時(shí)間快、空間??；交互性與動(dòng)態(tài)特性差、可移植性差。大多數(shù)PL采用此種方法翻譯

10、； 2解釋器：工作效率低，即時(shí)間慢、空間費(fèi)；交互性與動(dòng)態(tài)特性好、可移植性好。早期的Basic和現(xiàn)在的Java等。 基本功能：二者相同； 所采用的技術(shù)：從翻譯的角度來(lái)講，兩種方式所涉及的原理、方法、技術(shù)相似。,13,1.4 編譯器的工作原理與基本組成1.4.1 通用程序設(shè)計(jì)語(yǔ)言的主要成份,1從語(yǔ)言抽象的演變看： 過程抽象數(shù)據(jù)類型（ADT，程序包） 類 2共同特點(diǎn)：兩大部分組成：聲明操作完整定義 3以過程式語(yǔ)言為例：,聲明性語(yǔ)句：提供操作對(duì)象的性質(zhì)，如數(shù)據(jù)類型、值、作用域等； 操作性語(yǔ)句：確定操作的計(jì)算次序，完成實(shí)際操作。 過程頭過程體過程定義,4編譯器對(duì)兩類語(yǔ)句的翻譯： 聲明：生成相應(yīng)的環(huán)境，

11、一般是配置存儲(chǔ)空間。 操作：生成可執(zhí)行的代碼序列。 例6 一個(gè)Pascal過程,14,1.4.2 以階段劃分編譯器,1自然語(yǔ)言的翻譯過程： 識(shí)別單詞 識(shí)別句子結(jié)構(gòu) 理解意思 譯成中文并修飾,2編譯器的工作過程： 詞法分析 語(yǔ)法分析 語(yǔ)義分析 目標(biāo)代碼生成 3編譯器的階段（邏輯模塊劃分）,4中間代碼的重要作用,15,1.4.3 編譯器各階段的工作,例7 Pascal源程序語(yǔ)句如下： var x, y, z : real; x := y + z * 60;,（源程序）var x, y, z : real; x := y + z * 60;,（記號(hào)流）var id1, id2, id3 : r

12、eal; id1 := id2+id3*60;,16,1.4.3 編譯器各階段的工作（續(xù)1）,中間代碼的形式與作用： (序號(hào))(op， arg1, arg2, result) result := arg1 op arg2,(1) (itr, 60, , T1) (2) (*, id3, T1, T2) (3) (+, id2, T2, T3) (4) (:=, T3, , id1),17,1.4.3 編譯器各階段的工作（續(xù)2）,(1) (itr, 60, , T1) (2) (*, id3, T1, T2) (3) (+, id2, T2, T3) (4) (:=, T3, , id1),(1

13、) (*, id3, 60.0, T1) (2) (+, id2, T1, id1),MOVF id3, R2 MULF#60.0, R2 MOVF id2, R1 ADDF R2, R1 MOVF R1, id1,R2 := id3 R2 := R2 * 60.0 R1 := id2 R1 := R1 + R2 id1 := R1 id1 := id2 + id3 * 60.0 x := y + z * 60;,18,1.4.3 編譯器各階段的工作（續(xù)3）,各階段工作的歸納, 詞法分析：識(shí)別單詞，至少分以下幾大類：關(guān)鍵字（保留字）、標(biāo)識(shí)符、字面量、特殊符號(hào)； 語(yǔ)法分析：得到語(yǔ)言結(jié)構(gòu)并以樹

14、的形式表示； 語(yǔ)義分析：考察結(jié)構(gòu)正確的句子是否語(yǔ)義合法，可修改樹結(jié)構(gòu)； 中間代碼生成（可選）：生成一種既接近目標(biāo)語(yǔ)言，又與具體機(jī)器無(wú)關(guān)的表示，便于優(yōu)化與代碼生成； （到目前為止，編譯器與解釋器可以一致）, 中間代碼優(yōu)化（可選）：局部?jī)?yōu)化、循環(huán)優(yōu)化、全局優(yōu)化等；優(yōu)化實(shí)際上是一個(gè)等價(jià)變換，變換前后的指令序列完成同樣的功能，但是，在占用的空間上和程序執(zhí)行的時(shí)間上都更省、更有效。 目標(biāo)代碼生成：不同形式的目標(biāo)代碼匯編、可重定位、內(nèi)存形式（Load-and-Go）; 符號(hào)表管理：合理組織符號(hào)，便于各階段查找、填寫等； 出錯(cuò)處理：錯(cuò)誤的種類詞法錯(cuò)、語(yǔ)法錯(cuò)、靜態(tài)語(yǔ)義錯(cuò)、動(dòng)態(tài)語(yǔ)義錯(cuò)。,

15、19,1.4.4 編譯器的分析/綜合模式,1前端：語(yǔ)言結(jié)構(gòu)的分析； 2后端：語(yǔ)言意義的分析與處理； 3中間代碼：前端與后端的分界；,4編譯器基礎(chǔ)架構(gòu)（Infrastructure） ：源代碼的中間表示、一組前端、一組后端；,20,1.4.5 編譯器掃描的遍數(shù),1每個(gè)階段將程序完整分析一遍的工作模式稱為一遍掃描。早期編譯器的一遍定義為從外存讀入內(nèi)存再寫到外存； 2確定掃描遍數(shù)的因素： (a) 軟、硬件條件，如內(nèi)存太小，或全局優(yōu)化 (b) 語(yǔ)言結(jié)構(gòu)，如規(guī)定標(biāo)識(shí)符的先聲明后引用, x := f(a, b, c); function f(a:integer; b:integer): int

16、eger;,(c)編譯技術(shù)，如拉鏈回填, goto lab1; lab1: ,21,1.5 編譯器的編寫,1直接使用匯編語(yǔ)言和程序設(shè)計(jì)語(yǔ)言； 2利用編譯器編寫工具：詞/語(yǔ)法、語(yǔ)法制導(dǎo)翻譯、代碼生成、數(shù)據(jù)流分析等； 3基于編譯器基礎(chǔ)架構(gòu)的編譯器構(gòu)造系統(tǒng)（開放式編譯器，如GCC、SUIF等）。,GCC Home Page. http://gcc.gnu.org. Gasta Homepage. SUIF Compiler System Home Page. http://suif.stanford.edu,22,1.6 本章小結(jié),1語(yǔ)言與語(yǔ)言的翻譯 2編譯器的基本組成（工作） 3編譯器的分析/綜合

17、模式，編譯器基礎(chǔ)架構(gòu) 4掃描遍數(shù) 5編譯器的編寫,其它 作業(yè)：教材中除標(biāo)記*的全做；根據(jù)課程進(jìn)度做；第二、五章交一次，第三、四章交兩次； 課代表：收繳作業(yè)、聯(lián)系上機(jī)、反映同學(xué)意見，等 答疑：每周一次，課代表與輔導(dǎo)教師商討確定； 上機(jī)作業(yè)：交上機(jī)報(bào)告，作業(yè)由輔導(dǎo)教師驗(yàn)收。,23,第一章 結(jié)束,24,例6 有一Pascal的過程如下所示,(1) procedure sample(y: integer);過程頭 (2) var x : integer;過程體（開始） (3) begin x := y; (4) if x100 then x := 0 (5) end;過程體（結(jié)束）,(1)是過程頭，它是一個(gè)聲明性的語(yǔ)句，為使用者提供調(diào)用信息，包括過程名、參數(shù)、返回值（如果有的話）等。（接口） (2)至(5)是過程體，它是一個(gè)語(yǔ)句序列。語(yǔ)句序列中既包括聲明性語(yǔ)句也包括操作性語(yǔ)句。（實(shí)現(xiàn)） (2)是聲明性語(yǔ)句，而(3)至(5)是操作性語(yǔ)句。 對(duì)于編譯器來(lái)講，它對(duì)聲明性語(yǔ)句的處理一般是生成相應(yīng)的環(huán)境（存儲(chǔ)空間），而對(duì)操作性語(yǔ)句則是生成此環(huán)境中的可執(zhí)行代碼序列。 為了便于編譯器的處理，操作性語(yǔ)句中使用的每個(gè)操作對(duì)象，均應(yīng)在使用前聲明，即符合先聲明后引用的原則。,返回,