編譯原理01匯編

1、1編 譯 原 理西安電子科技大學(xué) 軟件工程研究所張立勇2題外話 一、本課程討論的領(lǐng)域和希望達到的目的12 CCC 2002 中國計算機科學(xué)與技術(shù)學(xué)科教程（China Computing Curricula 2002，CCC2002）提出的計算機科學(xué)與技術(shù)學(xué)科的知識體系，包括了14個基本的知識領(lǐng)域。與本課程相關(guān)的： 1程序設(shè)計基礎(chǔ)（PF）：程序設(shè)計基本結(jié)構(gòu)、算法與問題求解、基本數(shù)據(jù)結(jié)構(gòu)、遞歸、事件驅(qū)動程序設(shè)計。（PLA） 2程序設(shè)計語言（PL）：程序設(shè)計語言概論、虛擬機、語言翻譯簡介、聲明和類型、抽象機制、面向?qū)ο蟪绦蛟O(shè)計（以上是核心）；函數(shù)程序設(shè)計、語言翻譯系統(tǒng)、類型系統(tǒng)、程序設(shè)計語言的語義、

2、程序設(shè)計語言的設(shè)計（以上是選修）。（PLA、PLT、PLD） 11 領(lǐng)域程序設(shè)計語言的應(yīng)用程序設(shè)計（PLA）程序設(shè)計語言的翻譯編譯器的構(gòu)造（PLT）程序設(shè)計語言的設(shè)計語法、語義（PLD）3題外話（續(xù)1）13 目的1了解PL的基本要素、工作原理、語言翻譯的基本方法；2用不同的PL進行程序設(shè)計，即自學(xué)計算機語言的能力；3具備語言翻譯的基本技能。二、學(xué)習(xí)方法 21 本課程的特點理論與實踐并重理論學(xué)習(xí)要嚴謹、方法掌握要靈活提高自學(xué)能力（push與pull）22 理論與技術(shù)的關(guān)系適應(yīng)飛速變化的技術(shù)的根本是注重基礎(chǔ)理論學(xué)習(xí)理論的演變是緩慢的、理論基礎(chǔ)是相通的相同的原理可以應(yīng)用于不同的技術(shù)4題外話（續(xù)2）2

3、3 勤動手、多實踐、提高學(xué)習(xí)能力 學(xué)到的知識是死的，總有過時的時候。只有通過學(xué)習(xí)知識提高學(xué)習(xí)能力，才是立于不敗之地的保證。記筆記：好記性不如爛筆頭，通過動手加深理解和記憶。做作業(yè)、做上機題：自己動手為主，參考“解答”為輔。 24 如何使用習(xí)題與上機題解答合理利用“解答”有助于課程學(xué)習(xí)?！敖獯稹奔炔煌耆_也不是最好的。習(xí)題解答：先做作業(yè)，后看解答。如不符，思考原因，找出最好答案。上機解答：先看題目要求，根據(jù)要求自己設(shè)計并實現(xiàn)。如有困難，部分參考解答。提倡學(xué)生獨立思考，對發(fā)現(xiàn)解答錯誤并給出正確解法、做出選做題和上機題擴充部分者，給予加分獎勵。（只給第一組，寫明姓名、日期。加分按人平分）根據(jù)需要上

4、習(xí)題課。5題外話（續(xù)3）三、其他31 課代表與輔導(dǎo)課代表的職責：收繳作業(yè)；安排上機時間、聯(lián)系上機事宜；反映同學(xué)意見；監(jiān)督老師的工作。輔導(dǎo)時間：每周一次，課代表與同學(xué)商量后確定。32 作業(yè)與上機作業(yè) 第二、五章收繳一次，第三、四章收繳兩次。有獨立見解的可直接交給主講老師，包括指出解答的錯誤并給出正確答案、選做題答案等。（僅以第一個收到的為準，包括上屆）驗收上機題，并收繳上機報告。報告內(nèi)容根據(jù)個人對題目要求的理解寫。6題外話（續(xù)4）中文：清華大學(xué)出版社，呂映芝等，“編譯原理”國防工業(yè)出版社，陳火旺等，“程序設(shè)計語言編譯原理”（第三版）西北工業(yè)大學(xué)出版社，蔣立源等，“編譯原理”33 參考書目英文：人

5、民郵電出版社， Aho等， “編譯原理 技術(shù)與工具”（影印版）高等教育出版社，Andrew W.Appel，“現(xiàn)代編譯程序?qū)崿F(xiàn)Java語言”（影印版）機械工業(yè)出版社，Steven S.Muchnick，“高級編譯器設(shè)計與實現(xiàn)” （影印版）清華大學(xué)出版社，Hopcroft等，“自動機理論、語言和計算機導(dǎo)論”（影印版）7第一章 引言 1.1 從面向機器的語言到面向人類的語言面向機器的語言：機器指令、匯編語言面向人類的語言：通用程序設(shè)計語言、非過程式語言，等等例1 :通用程序設(shè)計語言與匯編語言（包括機器指令） Pascal語句：x := a+b；C+語句： x = a+b；匯編指令：十六進制代碼匯編

6、指令A(yù)10002 MOV AX, A 8B1E0202 MOV BX, B 01D8 ADD AX, BX A30402 MOV X, AX 計算機語言舉例8 計算機語言舉例（續(xù)1）給出003號學(xué)生所選課程與成績:Select 學(xué)號,姓名,課程名,成績 from 學(xué)生,選課 where 學(xué)生.學(xué)號=“003” ;例2 SQL 學(xué)生： 選課：學(xué)號姓名性別001 張梧男002 李煦 男003 王沁 女004劉荔女學(xué)號課程代碼課程名成績0010104離散數(shù)學(xué)800010205數(shù)據(jù)結(jié)構(gòu)900030104離散數(shù)學(xué)850030205數(shù)據(jù)結(jié)構(gòu)95學(xué)號姓名課程名成績003王沁離散數(shù)學(xué)85003王沁數(shù)據(jù)結(jié)構(gòu)95

7、9 計算機語言舉例（續(xù)2）例3： LEX的正規(guī)式：char(char|digit)* return idYacc的產(chǎn)生式：E : E + E | E * E | id 例4：Unix的shell命令SHELL=/bin/sh# include env_precomp.mkCPDIR = /u/pbsrc/chpORAHOME = /oracle/app/oracle/product/734.10 按范型劃分的程序設(shè)計語言CCC2002PL：Simple Procedural Languages：FORTRAN C Block-Structured Procedural Languages：Pa

8、scalObject-Based Languages：Ada C+ SmalltalkFunctional Languages：LISP ML Haskell OCamlLogic Programming Languages：Prolog 清華大學(xué)出版社， Terrence W.Pratt等，PROGRAMMING LANGUAGES Design and Implementation(影印版)過程式語言、面向?qū)ο笳Z言：通用程序設(shè)計語言，包括FORTRAN、Pascal、C/C+、Ada83/Ada95、Java等；函數(shù)語言：面向特點領(lǐng)域的、遞歸特性，典型代表：Lisp；說明性、非算法式語言：

9、濃厚的數(shù)學(xué)特征，典型代表：LEX/YACC、SQL；腳本式語言：僅是一種安排，沒有復(fù)雜的邏輯關(guān)系，典型代表：shell語言。11 其他面向特定應(yīng)用領(lǐng)域的語言1互連網(wǎng)應(yīng)用：HTML、XML2計算機輔助設(shè)計：MATLAB3集成電路設(shè)計：VHDL、Verilog4虛擬現(xiàn)實與人機交互：VRML問題： 如何將形形色色的語言翻譯成可以在計算機上運行的0、1串121.2 語言之間的翻譯 習(xí)慣稱法： 匯編語言機器指令：匯編（或交叉匯編） 程序設(shè)計語言匯編語言或機器指令：編譯（或解釋） 高級語言之間：轉(zhuǎn)換（或預(yù)編譯） 逆向：反匯編、反編譯131.3 編譯器與解釋器 語言翻譯的兩種基本形態(tài)1.先翻譯后執(zhí)行 2.

10、邊翻譯邊執(zhí)行 例5 假設(shè)有源程序：read(x); write(x=, x); 141.3 編譯器與解釋器（續(xù)）特點：編譯器：工作效率高，即時間快、空間?。唤换バ耘c動態(tài)特性差、可移植性差。大多數(shù)PL采用此方法翻譯；解釋器：工作效率低，即時間慢、空間費；交互性與動態(tài)特性好、可移植性好。早期的Basic和Java等；基本功能：二者相同；所采用的技術(shù)：從翻譯的角度來講，兩種方式所涉及的原理、方法、技術(shù)相似。 151.4 編譯器的工作原理與基本組成1.4.1 通用程序設(shè)計語言的主要成份1從語言抽象的演變看：過程抽象數(shù)據(jù)類型（ADT，程序包） 類2共同特點：兩大部分組成：聲明操作完整定義3以過程式語言為

11、例：聲明性語句：提供操作對象的性質(zhì)，如數(shù)據(jù)類型、值、作用域等；操作性語句：確定操作的計算次序，完成實際操作。過程頭過程體過程定義 4編譯器對兩類語句的翻譯： 聲明：生成相應(yīng)的環(huán)境，一般是配置存儲空間。 操作：生成可執(zhí)行的代碼序列。例6 一個Pascal過程 161.4.2 以階段劃分編譯器 1自然語言的翻譯過程：識別單詞識別句子結(jié)構(gòu)理解意思譯成中文并修飾 2編譯器的工作過程：詞法分析 語法分析語義分析目標代碼生成3編譯器的階段（邏輯模塊劃分）4中間代碼的重要作用171.4.3 編譯器各階段的工作例例7 7 Pascal源程序語句如下： var x, y, z : real; x := y +

12、z * 60;（源程序）var x, y, z : real; x := y + z * 60; （記號流）var id1, id2, id3 : real; id1 := id2+id3*60; （語法樹）181.4.3 編譯器各階段的工作（續(xù)1） 中間代碼的形式與作用：(序號)(op， arg1, arg2, result)result := arg1 op arg2 (1) (itr, 60, , T1)(2) (*, id3, T1, T2)(3) (+, id2, T2, T3)(4) (:=, T3, , id1) 191.4.3 編譯器各階段的工作（續(xù)2）(1) (itr, 60

13、, , T1)(2) (*, id3, T1, T2)(3) (+, id2, T2, T3)(4) (:=, T3, , id1) (1) (*, id3, 60.0, T1)(2) (+, id2, T1, id1) MOVF id3, R2MULF#60.0, R2MOVF id2, R1ADDF R2, R1MOVF R1, id1 R2 := id3R2 := R2 * 60.0R1 := id2R1 := R1 + R2id1 := R1id1 := id2 + id3 * 60.0 x := y + z * 60;201.4.3 編譯器各階段的工作（續(xù)3）各階段工作的歸納 詞法分

14、析：識別單詞，至少分以下幾大類：關(guān)鍵字（保留字）、標識符、字面量、特殊符號；語法分析：得到語言結(jié)構(gòu)并以樹的形式表示；語義分析：考察結(jié)構(gòu)正確的句子是否語義合法，修改樹結(jié)構(gòu)；中間代碼生成（可選）：生成一種既接近目標語言，又與具體機器無關(guān)的表示，便于優(yōu)化與代碼生成；（到目前為止，編譯器與解釋器可以一致） 中間代碼優(yōu)化（可選）:局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化等；優(yōu)化實際上是一個等價變換，變換前后的指令序列完成同樣的功能，但在占用的空間上和程序執(zhí)行的時間上都更省、更有效。目標代碼生成：不同形式的目標代碼匯編、可重定位、內(nèi)存形式（Load-and-Go）;符號表管理：合理組織符號，便于各階段查找、填寫等；出

15、錯處理：錯誤的種類詞法錯、語法錯、靜態(tài)語義錯、動態(tài)語義錯。211.4.4 編譯器的分析/綜合模式 前端：語言結(jié)構(gòu)和意義的分析； 后端：語言意義處理； 中間代碼：前端與后端的分界；221.4.4 編譯器的分析/綜合模式（續(xù)1）4編譯器基礎(chǔ)架構(gòu)（Infrastructure） ：源代碼的中間表示、一組前端、一組后端；23第次課 結(jié)束241.4.2 以階段劃分編譯器 1自然語言的翻譯過程：識別單詞識別句子結(jié)構(gòu)理解意思譯成中文并修飾 2編譯器的工作過程：詞法分析 語法分析語義分析目標代碼生成3編譯器的階段（邏輯模塊劃分）4中間代碼的重要作用251.4.3 編譯器各階段的工作例例7 7 Pascal源程

16、序語句如下： var x, y, z : real; x := y + z * 60;（源程序）var x, y, z : real; x := y + z * 60; （記號流）var id1, id2, id3 : real; id1 := id2+id3*60; （語法樹）261.4.3 編譯器各階段的工作（續(xù)1） 中間代碼的形式與作用：(序號)(op， arg1, arg2, result)result := arg1 op arg2 (1) (itr, 60, , T1)(2) (*, id3, T1, T2)(3) (+, id2, T2, T3)(4) (:=, T3, , id

17、1) 271.4.3 編譯器各階段的工作（續(xù)2）(1) (itr, 60, , T1)(2) (*, id3, T1, T2)(3) (+, id2, T2, T3)(4) (:=, T3, , id1) (1) (*, id3, 60.0, T1)(2) (+, id2, T1, id1) MOVF id3, R2MULF#60.0, R2MOVF id2, R1ADDF R2, R1MOVF R1, id1 R2 := id3R2 := R2 * 60.0R1 := id2R1 := R1 + R2id1 := R1id1 := id2 + id3 * 60.0 x := y + z *

18、60;281.4.3 編譯器各階段的工作（續(xù)3）各階段工作的歸納 詞法分析：識別單詞，至少分以下幾大類：關(guān)鍵字（保留字）、標識符、字面量、特殊符號；語法分析：得到語言結(jié)構(gòu)并以樹的形式表示；語義分析：考察結(jié)構(gòu)正確的句子是否語義合法，修改樹結(jié)構(gòu)；中間代碼生成（可選）：生成一種既接近目標語言，又與具體機器無關(guān)的表示，便于優(yōu)化與代碼生成；（到目前為止，編譯器與解釋器可以一致） 中間代碼優(yōu)化（可選）:局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化等；優(yōu)化實際上是一個等價變換，變換前后的指令序列完成同樣的功能，但在占用的空間上和程序執(zhí)行的時間上都更省、更有效。目標代碼生成：不同形式的目標代碼匯編、可重定位、內(nèi)存形式（Loa

19、d-and-Go）;符號表管理：合理組織符號，便于各階段查找、填寫等；出錯處理：錯誤的種類詞法錯、語法錯、靜態(tài)語義錯、動態(tài)語義錯。291.4.4 編譯器的分析/綜合模式 前端：語言結(jié)構(gòu)和意義的分析； 后端：語言意義處理； 中間代碼：前端與后端的分界；301.4.4 1.4.4 編譯器的分析編譯器的分析/ /綜合模式（續(xù)綜合模式（續(xù)1 1）4編譯器基礎(chǔ)架構(gòu)（Infrastructure） ：源代碼的中間表示、一組前端、一組后端；311.4.5 編譯器掃描的遍數(shù) 每個階段將程序完整分析一遍的工作模式稱為一遍掃描。早期編譯器的一遍定義為從外存讀入內(nèi)存再寫到外存；確定掃描遍數(shù)的因素：軟、硬件條件，如內(nèi)存太小，或全局優(yōu)化語言結(jié)構(gòu)，如規(guī)定標識符的先聲明后引用x := f(a, b, c);function f(a:integer; b:integer):integer; 編譯技術(shù)，如拉鏈回填goto lab1;lab1: