1、第1章 引論2v 教材 程序設計語言編譯原理(第3版) 陳火旺 國防工業出版社v 課程內容 程序設計語言編譯程序構造的基本原理和基本實現技術v 課程地位：編譯理論與方法 計算機科學與技術中理論和實踐相結合的最好典范 ACM圖靈獎，授予在計算機技術領域作出突出貢獻的科學家 程序設計語言、編譯理論與方法約占1/33v 自20世紀50年代以來，世界上公布的程序設計語言已有上千種之多，但是只有很小一部分得到了廣泛的應用。v 從發展歷程來看，程序設計語言可以分為4代：v 第一代語言(機器語言)1. 機器語言是由二進制0、1代碼指令構成，不同的CPU具有不同的指令系統。機器語言程序難編寫、難修改、難維護，

2、需要用戶直接對存儲空間進行分配，編程效率極低。目前，這種語言已經被淘汰4v 第二代語言(匯編語言) 匯編語言指令是機器指令的符號化，與機器指令存在著直接的對應關系，所以匯編語言同樣存在著難學難用、容易出錯、維護困難等缺點 但是匯編語言也有自己的優點：可直接訪問系統接口，匯編程序翻譯成的機器語言程序的效率高 從軟件工程角度來看，只有在高級語言不能滿足設計要求，或不具備支持某種特定功能的技術性能(如特殊的輸入輸出)時，匯編語言才被使用5v 第三代語言(高級語言) 高級語言是面向用戶的、基本上獨立于計算機種類和結構的語言 其最大的優點是：形式上接近于算術語言和自然語言，概念上接近于人們通常使用的概念

3、。高級語言的一個命令可以代替幾條、幾十條甚至幾百條匯編語言的指令。因此，高級語言易學易用，通用性強，應用廣泛。 高級語言種類繁多，可以從以下兩方面對其進一步分類： 從應用角度分類 從客觀系統的描述分類6v 第三代語言(高級語言) 從應用角度分類 可以分為基礎語言、結構化語言和專用語言 基礎語言 基礎語言也稱通用語言。它歷史悠久，流傳很廣，有大量的已開發的軟件庫，擁有眾多的用戶，為人們所熟悉和接受。屬于這類語言的有 BASIC、FORTRAN、COBOL、ALGOL等 BASIC 語言是在 20 世紀 60 年代初為適應分時系統而研制的一種交互式語言，可用于一般的數值計算與事務處理。BASIC

4、語言結構簡單，易學易用，并且具有交互能力，成為許多初學者學習程序設計的入門語言7v 第三代語言(高級語言) 從應用角度分類 基礎語言 FORTRAN（FORmula TRANslation，公式翻譯程序設計語言，20世紀50年代）是世界上最早出現的計算機高級程序設計語言，廣泛地應用于數值計算領域，積累了大量高效而可靠的源程序。Fortran語言與JAVA、C#等語言相比缺乏創造力。但是，像ANSYS和Marc等優秀的工程計算軟件都運用Fortran語言編寫，MATLAB的早期版本主要是為兩個著名的Fortran函數包提供程序接口，因此Fortran在工程計算領域長期處于統治地位8v 第三代語言

5、(高級語言) 從應用角度分類 基礎語言 COBOL(COmmon Business Oriented Language)是數據處理領域最為廣泛的程序設計語言 COBOL主要是應用于銀行、金融和會計行業等非常重要的商業數據處理領域。 在企業管理中，數值計算并不復雜，但數據處理信息量卻很大 世界上70%的數據都是用COBOL語言處理的，并且90%的ATM事務處理用的都是COBOL語言。500強中有492家使用了COBOL語言，目前在COBOL方面的投資已經超過3萬億美元。據稱用COBOL書寫的程序超過了1000億行，并以每年約50億行代碼的速度增長 只要大型機存在，COBOL就不會消失9v 第三代

6、語言(高級語言) 從應用角度分類 結構化語言 20世紀70年代以來，結構化程序設計和軟件工程的思想日益為人們所接受。出現了一些很有影響的結構化語言，如PASCAL、C、Ada就是它們的突出代表 PASCAL的取名是為了紀念十七世紀法國數學家Blaise Pascal。PASCAL是第一個系統地體現結構化程序設計概念的現代高級語言。IOI(國際奧林匹克信息學競賽)和NOI(全國奧林匹克信息學競賽)都指定C，C+，Free Pascal作為三種程序設計語言。在大學中Pascal語言也常常被用作學習數據結構與算法的教學語言10v 第三代語言(高級語言) 從應用角度分類 結構化語言 C語言功能豐富，表

7、達能力強，有豐富的運算符和數據類型，使用靈活方便，應用面廣，移植能力強，編譯質量高，目標程序效率高，具有高級語言的優點。同時，C語言還具有低級語言的許多特點，如允許直接訪問物理地址，能進行位操作，能實現匯編語言的大部分功能，可以直接對硬件進行操作等。用C語言編譯程序產生的目標程序，其質量可以與匯編語言產生的目標程序相媲美，具有“可移植的匯編語言”的美稱，成為編寫應用軟件、操作系統和編譯程序的重要語言之一11v 第三代語言(高級語言) 從應用角度分類 專用語言 是為某種特殊應用而專門設計的語言，通常具有特殊的語法形式。一般來說，這種語言的應用范圍狹窄，移植性和可維護性不如結構化程序設計語言 目前

8、使用的專業語言已有數百種，應用比較廣泛的有APL語言、Forth語言、LISP語言12v 第三代語言(高級語言) 從客觀系統的描述分類 可分為面向過程語言和面向對象語言 面向過程語言 以“數據結構+算法”程序設計范式構成的程序設計語言，稱為面向過程語言。前面介紹的程序設計語言大多為面向過程語言 面向對象語言 以“對象+消息”程序設計范式構成的程序設計語言，稱為面向對象語言。目前比較流行的面向對象語言有Java、C+、Delphi、Visual Basic等13v 第四代語言(簡稱4GL) 4GL是非過程化語言，編碼時只需說明“做什么”，不需描述算法細節 數據庫查詢和應用程序生成器是 4GL 的

9、兩個典型應用： 用戶可以用數據庫查詢語言(SQL)對數據庫中的信息進行復雜的操作。 用戶只需將要查找的內容在什么地方、 據什么 根條件進行查找等信息告訴 SQL，SQL 將自動完成查找過程 應用程序生成器則是根據用戶的需求“自動生成”滿足需求的高級語言程序 真正的第四代程序設計語言應該說還沒有出現。目前，所謂的第四代語言大多是指基于某種語言環境上具有4GL特征的軟件工具產品14v 語言特性 強語言與弱語言分類： 是否要強制類型轉化 靈活與規范 如： 強類型語言：JAVA、C+ 弱類型語言：大多數的腳本語言 安全與效率： JAVA與C 指針申請回收 堆、棧等內存空間分配 數組越界檢查15v 1

10、什么叫編譯程序v 2 編譯過程概述v 3 編譯程序結構v 4 編譯程序與程序設計環境v 5 編譯程序的生成16v 編譯程序與程序員的關系？v 回顧程序執行的方式 解釋型，如：BASIC 編譯型，如：C 混合型，如：JAVAv 其中后兩種都要使用編譯程序（編譯器）1 什么叫編譯程序17v JAVA語言 Java編譯器把Java代碼翻譯成獨立于機器的Java“字節代碼” 運行時，目標裝置中的校驗器便分析這些字節代碼以確保代碼的安全執行 在目標裝置中，內置一個JVM（Java虛擬機）。該虛擬機用一個解釋器或一個JIT（適時）編譯器把字節代碼翻譯成目標處理器能夠識別的機器語言 Java的傳統環境如下圖

11、所示：1 什么叫編譯程序18v JAVA語言1 什么叫編譯程序COMPILE-TIMEENVIRONMENTJAVASOURCE(.java)JAVACOMPILERJAVABYTE CODES(.class)RUNTIME ENVIRONMENT (JAVA PLATFORM)CLASS LOADERBYTE-CODEVERIFIERJAVA CLASSLIBRARIESJAVA VIRTUAL MACHIMEJAVAINTERPTETERJUST-IN-TIMECOMPILERHARDWAREJAVABYTE CODESMOVE LOCALLYOR THROUGHNETWORK19v 在計

12、算機上執行一個高級語言程序一般分兩步： 用編譯程序把高級語言翻譯成機器語言程序 運行所得的機器語言程序求得計算結果1 什么叫編譯程序20v 翻譯程序 把某一種語言程序(稱為源語言程序)等價地轉換成另一種語言程序(稱為目標語言程序)的程序1 什么叫編譯程序源語言程序目標語言程序翻譯程序翻譯21v 編譯程序(compiler) 把某一種高級語言程序等價地轉換成另一種低級語言程序(如匯編語言或機器語言程序)的程序1 什么叫編譯程序高級語言程序機器語言程序結果編譯程序翻譯運行22v 編譯程序(compiler) 根據不同用途和側重，編譯程序的類型可分為： 診斷編譯程序（Diagnostic Compi

13、ler) 專門用于幫助程序開發和調試 優化編譯程序（Optimizing Compiler) 著重提高代碼效率 交叉編譯程序(Cross Compiler) 產生不同于其宿主主機的機器代碼 可變目標編譯程序(Retargetable Compiler) 不需重寫編譯程序中與機器無關的部分就能改變目標機1 什么叫編譯程序23v 解釋程序 把源語言寫的源程序作為輸入，但不產生目標程序，而是邊解釋邊執行源程序本身1 什么叫編譯程序源程序結果解釋程序解釋執行24v 1 什么叫編譯程序v 2 編譯過程概述v 3 編譯程序結構v 4 編譯程序與程序設計環境v 5 編譯程序的生成25v 把英文翻譯為中文 識

14、別出句子中的一個個單詞 詞法分析 分析句子的語法結構 語法分析 根據句子的含義進行初步翻譯 語義分析與中間代碼產生 對譯文進行修飾 優化 寫出最后的譯文1. 目標代碼生成2 編譯過程概述26v 編譯程序的工作一般分為五個階段：v 詞法分析v 語法分析v 語義分析與中間代碼產生v 優化v 目標代碼產生2 編譯過程概述27v 詞法分析v 任務： 輸入源程序，對構成源程序的字符串進行掃描和分解，識別出一個個單詞符號v 依循的原則： 詞法規則v 描述工具： 正規式和有限自動機v 舉例：2 編譯過程概述FOR保留字I標識符:=賦值號1整常數TO保留字100整常數DO保留字28v 語法分析v 任務： 在詞

15、法分析的基礎上，根據語言的語法規則，把單詞符號串分解成各類語法單位v 依循的原則： 語法規則v 描述工具： 上下文無關文法、語法樹和抽象語法樹v 舉例： Z:=X+0.618*Y 賦值語句 其中X+0.618*Y 算術表達式2 編譯過程概述:=Z+*X0.618Y:=+*IDEEEIDEEIDnumE29v 語義分析與中間代碼產生v 任務： 對各類不同語法范疇按語言的語義進行初步翻譯（產生中間代碼）。工作包括：靜態語義檢查和中間代碼翻譯v 依循的原則： 語義規則v 描述工具： 屬性文法v 舉例： Z:=(X+0.418)*Y/W翻譯成四元式序列為：2 編譯過程概述ZWT2/(3)T2YT1*(

16、2)T10.418X+(1)結果右操作數左操作數算符序號30v 優化v 任務： 對前階段產生的中間代碼進行加工變換，以期在最后階段產生更高效（節省時間和空間）的目標代碼。優化的主要方面：公共子表達式提取、循環優化和刪除無用代碼等v 依循的原則： 程序的等價變換規則v 舉例：FOR K:=1 TO 100 DOBEGINM := I + 10 * K;N := J + 10 * K;END2 編譯過程概述31v 優化v 舉例： 優化前中間代碼：循環中需做300次加法和200次乘法2 編譯過程概述(9)goto (2)(2)j(8)K:=K+1K1K+(7)N:=J+T2NT2J+(6)T2:=1

17、0*K；T2為臨時變量T2K10*(5)M:=I+T1MT1I+(4)T1:=10*K；T1為臨時變量T1K10*(3)if (100K) goto (9)(9)K100j(2)K:=1K1:=(1)注釋RESULTARG2ARG1OP序號32v 優化v 舉例： 優化后中間代碼：循環中僅需做300次加法，無乘法2 編譯過程概述(9)goto (4)(4)j(8)K:=K+1K1K+(7)N:=N+10N10N+(6)M:=M+10M10M+(5)if (100K) goto (9)(9)K100j(4)K:=1K1:=(3)N:=JNJ:=(2)M:=IMI:=(1)注釋RESULTARG2A

18、RG1OP序號33v 目標代碼產生v 任務： 把中間代碼變換成特定機器上的目標代碼，依賴于硬件系統結構和機器指令的含義。涉及到硬件系統功能部件的運用、機器指令的選擇、存儲空間分配和寄存器調度等v 目標代碼三種形式： 絕對指令代碼 可直接運行 匯編指令代碼 需要進行匯編 可重新定位指令代碼 需要連接裝配2 編譯過程概述34v 目標代碼產生 可重新定位指令代碼 在運行前必須借助一個連接裝配程序把各個目標模塊（包括系統提供的庫模塊）連接在一起，確定程序變量（或常數）在主存中的位置，裝入內存中指定的起始地址，使之成為一個可以運行的絕對指令代碼程序2 編譯過程概述模塊Aa模塊Bb模塊Cc模塊Aa模塊Bb

19、模塊Cc模塊Aa模塊D模塊Cc35v 目標代碼產生v 舉例： b=a+2v 翻譯成匯編指令： MOV a，R1 ADD #2，R1 MOV R1，bv 把匯編指令翻譯成機器代碼： 0001 01 00 00000000 * 0011 01 10 00000010 0100 01 00 00000100 *2 編譯過程概述36v 目標代碼產生v 把匯編指令翻譯成機器代碼： 指令字的前4位：指令代碼 0001、0011和0100分別代表裝入、加和存儲 5，6位：01為指定寄存器R1 7，8位：標志位，說明尋址方式 00：直接尋址，后8位為內存地址 10：立即數，后8位為操作數 星號*：重定位標志

20、假設裝載起始地址L=00001111，最終目標代碼為 0001 01 00 00001111 0011 01 10 00000010 0100 01 00 000100112 編譯過程概述37v 上述編譯過程的五個階段是一種典型分法。事實上，并非所有編譯程序都分成這五階段 有些編譯程序對優化沒什么要求，優化階段就可以省去 在某些情況下，為了加快編譯速度，中間代碼產生階段也可以去掉 有些最簡單的編譯程序實在語法分析階段的同時產生代碼v 但是，多數實用編譯程序的工作過程大致都像上述編譯過程的五個階段2 編譯過程概述38v 1 什么叫編譯程序v 2 編譯過程概述v 3 編譯程序結構v 4 編譯程序與

21、程序設計環境v 5 編譯程序的生成39v 編譯程序總框3 編譯程序結構四元式單詞符號語法單位四元式目標代碼詞法分析器語法分析器語義分析與中間代碼生成器優化段源程序表格管理出錯處理目標代碼生成器40v 表格與表格管理v 常見的表格： 符號名表，常數表，標號表，入口名表，過程引用表v 格式：v 舉例： PASCAL程序段PROCEDURE INCWAP(M，N:INTEGER);LABEL START;VAR K:INTEGER;BEGINSTART: K:=M+1; M:=N+4; N:=K;END.3 編譯程序結構名字信息413 編譯程序結構v 表格與表格管理423 編譯程序結構v 表格與表格

22、管理43v 出錯處理v 出錯處理程序：發現源程序中的錯誤，把有關錯誤信息報告給用戶v 語法錯誤 不符合語法（或詞法）規則的錯誤，在詞法分析或語法分析時發現，如： 詞法分析階段檢查出：非法字符 語法分析階段檢查出：括號不匹配，缺少“；”等v 語義錯誤 不符合語義規則的錯誤，有的可以在語義分析階段檢查出，有的只能在運行時檢查出。如：說明錯誤、作用域錯誤、類型不一致等3 編譯程序結構44v 遍(pass)v 所謂“遍”，就是對源程序或源程序的中間表示從頭到尾掃描一次，并完成相應處理，生成新的中間結果或目標程序。v 階段與遍是不同的概念。一遍可以由若干段組成，一個階段也可以分若干遍來完成v 詞法分析可

23、以單獨一遍，但常作為語法分析的子程序，與其安排在同一遍v 可以單遍編譯，也可以多遍編譯v 允許符號先使用后定義的語言至少需要2遍v 優化層次越深，所需遍數越多v 遍數越多，花的時間就越多3 編譯程序結構45v 編譯前端與后端v 編譯前端： 與源語言有關。如詞法分析，語法分析，語義分析與中間代碼產生，優化階段中與機器無關的優化v 編譯后端： 與目標機有關。如與目標機有關的優化，目標代碼產生v 編譯區分前后端的優點： 減少對內存容量的要求，程序邏輯結構清晰 優化更充分，有利于移植v 編譯區分前后端的不足： 編譯程序運行的效率低3 編譯程序結構源語言中間語言目標語言前端后端46v 編譯前端與后端v

24、編譯區分前后端的優點方便移植： 不同源語言，編譯成相同的中間語言，即為不同前端，配以相同的后端，可生成在同一目標機器上的不同語言的編譯程序 同一編譯程序的前端，配以不同的后端，可生成在不同目標機器上的相同語言的編譯程序 如：JAVA語言的操作平臺無關性 JAVA定義一種虛擬機代碼Bytecode 只要操作平臺上實現了執行Bytecode的JAVA解釋器，就可以執行各種Java程序3 編譯程序結構47v 1 什么叫編譯程序v 2 編譯過程概述v 3 編譯程序結構v 4 編譯程序與程序設計環境v 5 編譯程序的生成48v 程序設計環境 編輯程序 編譯程序 連接程序 調試工具v 集成化的程序設計環境

25、4 編譯程序與程序設計環境49v 編譯器的上下文環境4 編譯程序與程序設計環境預處理器編譯器裝配/連接器匯編器源程序骨架源程序目標匯編程序可重定位的機器代碼絕對機器代碼庫、可重定位目標文件50v 預處理器的功能 產生編譯器的輸入 宏擴展 #define PI 3.1415926 加入頭文件 如：C語言的#include “理性”預處理器 把現代控制流和數據結構機制添加到比較老式的語言中 語言擴充 通過大量的內部宏定義來增強語言的能力 如：嵌套在C語言中的數據庫查詢語言Equel4 編譯程序與程序設計環境51v .NET Framework與VS.NET4 編譯程序與程序設計環境Operating SystemCommon Language RuntimeADO.NET: Data and XMLASP.NET: Web Services & Web FormsWindowsFormsCommon Language SpecificationVisual Stud