1、編 譯 原 理清華大學出版社 呂映芝 張素琴 蔣維杜 編著第1章 概述第2章 PL/0編譯系統第3章詞法分析程序的自動構造第4章文法和語言第5章自頂向下語法分析LL（1）文法目 錄第6章自底向上語法分析、LR分析程序及其自動構造第7章 語法制導翻譯和中間代碼生成第8章 運行時的存儲組織和管理 第9章 代碼優化第10章代碼生成第1章 概 述1.1什么是編譯程序1.2編譯過程和編譯程序的結構1.3 編譯技術的發展和應用 參考書什么是編譯程序(compiler) 編譯程序是現代計算機系統的基本組成部分. 從功能上看，一個編譯程序就是一個語言翻譯程序,它把一種語言(稱作源語言)書寫的程序翻譯成另一種語

2、言(稱作目標語言)的等價的程序. 1.1功能術語編譯程序的源語言(源程序)編譯程序的目標語言(目標程序)編譯程序的實現語言S OI 高級語言書寫的程序 編譯程序低級語言程序S TI 什么是編譯程序軟件分類軟件系統軟件語言處理系統操作系統編譯系統裸機分類軟件：計算機系統中的程序及其文檔系統軟件：居于計算機系統中最靠近硬件的一層，其他軟件一般都通過系統軟件發揮作用。他和具體的應用領域無關，如編譯系統和操作系統等。語言處理系統：把軟件語言書寫的各種程序處理成可在計算機上執行的程序。軟件語言：用于書寫軟件的語言。它主要包括需求定義語言，功能性語言，設計性語言，程序設計語言以及文檔語言。預處理器編譯器匯

3、編器裝配連接編輯骨架程序 源程序 目標匯編程序 可重定位機器代碼 絕對機器碼可重定位目標文件庫語言處理過程什么是編譯程序語言轉(變）換系統C+編譯器C+CJavaBytecodeJava編譯器術語編譯程序(compiler)編譯程序的源語言(源程序) (source language)(source program)編譯程序的目標語言(目標程序) (object or target language)(object or target program) 編譯程序的實現語言(implementation language)語言處理程序(language processor)語言轉（變）換(lan

4、guage transformation)1.2 編譯過程和編譯程序的結構編譯邏輯過程詞法分析語法分析語義分析中間代碼生成代碼優化目標代碼生成詞法分析從左至右讀字符流的源程序、識別(拼)單詞例： position := initial + rate * 60;position := initial + rate * 60;單詞類型單詞值 標識符1(id1) position 算符(賦值) := 標識符2(id2) initial 算符(加) + 標識符3(id3) rate 算符(乘) * 整數 60 分號 ；又如一個C源程序片斷： int a; a = a + 2;詞法分析后可能返回:單詞類

5、型單詞值 保留字 int標識符(變量名) a界符 ;標識符(變量名) a算符(賦值) =標識符(變量名) a 算符(加) +整數 2界符 ；有關術語詞法分析(lexical analysis or scanning) -The stream of characters making up a source program is read from left to right and grouped into tokens,which are sequences of characters that have a collective meaning.單詞-token保留字-reserved w

6、ord標識符 -identifier(user-defined name)語法分析功能:層次分析.依據源程序的語法規則把源程序的單詞序列組成語法短語(表示成語法樹).position := initial + rate * 60 ;規則 :=“:=” :=“+” :=“*” :=“(”“)” := := := 賦值語句標識符表達式表達式+表達式表達式標識符整數標識符:=表達式*id1:=id2+id3*N:=+N 60*id1 Positionid2 initialid3 rate術語語法分析(syntax analysis or parsing)The purpose of syntax a

7、nalysis is to determine the source programs phrase structure.This process is also called parsing.The source program is parsed to check whether it conforms to the source languages syntax,and to construct a suitable representation of its phrase structure.語法樹(推導樹)(parse tree or derivation tree)語義分析語義審查

8、(靜態語義)上下文相關性類型匹配類型轉換例:Program p();Var rate:real;procedure initial;position := initial + rate * 60 /* error */ /* error */ /* warning */;又如: int arr 2,abc; abc = arr * 10;Program p();Var rate:real; Var initial :real; Var position :real ; position := initial + rate * 60語義分析60:=+*Id1 positionId2 initia

9、lId3 rateinttoreal術語語義分析(semantic analysis) The parsed program is further analyzed to determine whether it conforms to the source languages contextual constraints:scope rules, type rulese.g. To relate each applied occurrence of an identifier in the source program to the corresponding declaration. 中間

10、代碼生成源程序的內部(中間)表示三元式、四元式、P-Code、C-Code、U-Code、bytecode( * id3t1t2)t2 = id3 * t1t2 := id3 * t1id1:= id2 + id3 * 60(1)(inttoreal,60-t1)(2)(*,id3t1t2)(3)(+,id2t2t3)(4)(:=,t3-id1)中間代碼生成(intermediate code generation)This is where the intermediate representation of the source program is created.We want thi

11、s representation to be easy to generate,and easy to translate into the target program.The representation can have a variety of forms,but a common one is called three-address code or 4- tuple code.代碼優化id1:= id2 + id3 * 60(1)(inttoreal60-t1)(2)( * id3t1t2)(3)( +id2t2t3)(4)( :=t3-id1) 變換 （1） ( *id360.0

12、t1) ( 2）（ + id2 t1id1)代碼優化t1 = b* c t1 = b* c t2 = t1+ 0 t2 = t1 + t1t3 = b* c a = t2t4 = t2 + t3a = t4代碼優化(code optimization)Intermediate code optimizationThe optimizer accepts input in the intermediate representation and output a version still in the intermediate representation .In this phase,the

13、compiler attempts to produce the smallest,fastest and most efficient running result by applying various techniques.Object code optimization目標代碼生成(*,id360.0t1)(+,id2t1id1)movfid3,R2mulf#60.0,R2movfid2,R1addfR2,R1movfR1,id1符號表管理記錄源程序中使用的名字收集每個名字的各種屬性信息類型、作用域、分配存儲信息Const1常量值：35Var1變量類型：實層次：2符號表(symbol

14、table)Symbol table is a data structure which is employed to associate identifiers with their attributes .An identifiers attribute consists of information relevant to contextual analysis,and is obtained from the identifiers declaration.出錯處理檢查錯誤、報告出錯信息、排錯、恢復編譯工作出錯處理(error handling)(error reporting and

15、 error recovery)The compiler should report the location of each error,together with some explanation. The major categories of compile-time error: syntax error, scope error, type error.After detecting and reporting an error,the compiler should attempt error recovery,means that the compiler should try

16、 to get itself into a state where analysis of the source program can continue as normally as possible.編譯程序結構(components)詞法分析程序語法分析程序語義分析程序中間代碼生成程序代碼優化程序目標代碼生成程序符號表管理程序出錯處理程序出錯處理語法分析程序語義分析程序目標代碼生成程序詞法分析程序中間代碼生成程序代碼優化程序表格管理編譯階段的組合分析，綜合(synthesis)源程序的分析線性分析層次分析語義分析目標程序的綜合編譯的前端（front end）編譯的后端（back end）

17、遍（趟）從頭到尾掃描源程序（各種形式）一遍(pass)高級語言解釋系統(interpreter)功能 讓計算機執行高級語言（basic,lisp,prolog)與編譯程序的不同 1）不生成目標代碼 2）能支持交互環境源 程 序 初始數據 解釋程序計算結果 解釋系統直接對源程序中的語句進行分析，執行其隱含的操作。如： b := 2 ; a := b+2 ; 編譯程序 write a ; 解釋程序直接將4的值輸出（顯示）Int 2St bLd badd 2St a生成代碼 編譯階段和運行階段存儲結構 編譯時 運行時 名字表目標代碼緩沖區編譯用源程序中間表示各種表格目標代碼區數據區源程序緩沖區解釋系

18、統存儲結構解釋系統源程序工作單元名字表標號表緩沖區(輸入輸出)棧區1.3 編譯技術的發展和應用功能：程序 集成環境實現方式手工機器語言匯編系統程序設計語言自動構造工具lex yacc gccS OI 編譯程序的發展Human-orientedlanguageComputer-orientedlanguage計算模式，語言范式語言應用領域編譯程序萬諾曼機體系結構并行體系結構嵌入系統 編譯程序的發展語言范型(paradigms)命令式(imperative language)應用式(applicative)基于規則的（rule-based）面向對象的（object-oriented）編譯程序執行環

19、境批處理交互環境嵌入系統環境 語言范型（支持的計算模式） 命令式：程序特點： 語言執行的解釋： 編譯技術發展快：語句1； 改變機器狀態 系統語言語句2； 內存 自動化生成技術語句3； 各種寄存器 的內容 外存 與萬諾曼機的 體系結構一般 應用式（函數式）：程序特點： Function n(funetion2(funetion1(data)程序執行： 執行一個個函數施用在數據上的變換最終得到的結果編譯： 語法分析容易； 語義處理復雜； 基于規則的語言（prolog,yacc)：程序特點： 使能條件1 動作1 使能條件2 動作2 使能條件3 動作3 面向對象語言： 抽象數據類型，繼承機制編譯： 動

20、態綁定； 執行環境批處理環境： 將源程序作為整體處理 排除程序錯誤不能依靠用戶的外部幫助交互環境： 解釋 增量式編譯嵌入式系統環境：交叉編譯分布并行環境：并行編譯程序創建和測試環境： 獨立編譯 編譯和調試同時設計考慮 編譯技術的發展和應用結構化編譯器程序分析工具 靜態分析 動態分析 度量工具 結構度量 模塊接口復雜度 分析工具(source insight) 廣泛的語言領域 數據庫系統查詢 腳本語言 置標語言(SGML.HTML.XML)研究領域并行編譯技術交叉編譯技術硬件描述語言及其編譯技術 并行化編譯技術目的：提高并行計算機體系結構的性能。超大規模計算的日益增長的需求 高性能計算機 并行軟

21、件并行體系結構單機速度并行體系結構途徑1途徑2 并行體系結構 編譯技術支持 串行程序并行化編譯技術支持 并行程序設計語言編譯 依賴于目標機的優化（低層） 性能發揮 并行算法復雜，難掌握，難編程 開發并行 軟件的困難 并行程序的不確定行為，難調試，驗證設計新的并行算法 修改已有串行程序盡量（直接用并行程序 并行化（研究算法和設計語言和并行程 應用的人同時工作）序庫實現。). . PVM 途徑12嵌入式交叉編譯器由于目標機指令系統與宿主機的指令系統不同，編譯時將應用程序的源程序在宿主機上生成目標機代碼，稱為交叉編譯。SOIOAB編譯程序生成以匯編語言和機器語言為工具優點: 可以針對具體的機器，充分發揮計算機的系統功能。生成的程序效率高。缺點: 程序難讀、難寫、易出錯、難維護、生產的效率低。編譯程序生成高級語言書寫優點: 程序易讀、易理解、容易維護、生產的效率高。缺點: 難以充分發揮計算機的系統功能，生成的程序