《編譯程序概論》PPT課件.ppt

1、1,編譯原理,主講： 馬 力 單位： 計(jì)通學(xué)院 計(jì)算機(jī)科學(xué)系 Email: 電話:考核：平時(shí)考勤、表現(xiàn)： 10% 平時(shí)作業(yè)： 20% 期末考試（閉卷）： 70%,2,前 言,課程內(nèi)容 課程特點(diǎn) 教學(xué)安排 學(xué)習(xí)章節(jié) 考試安排,3,課程內(nèi)容,主要闡述編譯程序的基本結(jié)構(gòu)、編譯技術(shù)的一般理論和常用的有效方法與技術(shù)。 包括: 文法和形式語言 自動(dòng)機(jī)理論 詞法分析 語法分析 語義分析 中間語言 代碼生成,4,理論與實(shí)踐的結(jié)合 理論： 編譯基礎(chǔ)理論 實(shí)踐： 自己編寫編譯器（專門課程設(shè)計(jì)課） 涉及的知識(shí)面廣 形式語言 自動(dòng)機(jī)理論 離散數(shù)學(xué) 數(shù)據(jù)結(jié)構(gòu) 算 法,課程特點(diǎn),有,點(diǎn),難,?,

2、5,教學(xué)安排,教學(xué): 48課時(shí) 主要采用幻燈片輔導(dǎo)教學(xué) 課后作業(yè)：從第3章起一般每章交1次，大約5-6次 課終復(fù)習(xí)、串講一次 要求：課前預(yù)習(xí)、課后認(rèn)真作業(yè),6,學(xué)習(xí)章節(jié),第一章 編譯程序概論(一般了解) 第二章 PL/0編譯程序的實(shí)現(xiàn)(一般了解) 第三章 文法和語言 第四章 詞法分析 第五章 自頂向下語法分析 - LL（1）文法 第六章 自底向上語法分析 -優(yōu)先分析法 第七章 自底向上語法分析 -LR分析法 第八章 語法制導(dǎo)翻譯及代碼生成,7,考試安排,考核范圍:重點(diǎn)考察編譯原理中的基本概念，編譯基礎(chǔ)理論以及編譯過程的各個(gè)階段的功能和實(shí)現(xiàn)方法。 考核方式：期末考核與平時(shí)成績相結(jié)合的方式。 1）

3、期末考核： 筆試、閉卷，答題時(shí)限120分鐘，占70%； 2）平時(shí)成績： 視平時(shí)考勤、表現(xiàn)、課堂提問、作業(yè)完成情況等給分，占30%。 以上成績累計(jì)60分以上（包括60分）算考核通過。,8,參考書,1編譯原理（第二版），張素琴、呂映芝、蔣維杜、戴桂蘭編著，清華大學(xué)出版社，2011年 (教材) 2程序設(shè)計(jì)語言編譯原理（第三版），陳火旺、劉春林等編著，國防工業(yè)出版社，2000年 3編譯原理與編譯程序構(gòu)造，高仲儀等編著，北京航空航天大學(xué)出版社，2001年 4編譯原理，胡倫駿、徐蘭芳、劉建農(nóng)編，電子工業(yè)出版社，2002年,9,5、龍書（Dragon book）英文名：Compilers: Principl

4、es,Techniques,and Tools作者：Alfred V.Aho,Ravi Sethi,Jeffrey D.Ullman中文名：編譯原理技術(shù)和工具6、虎書（Tiger book）英文名：Modern Compiler Implementation in C作者：Andrew W.Appel,with Jens Palsberg中文名：現(xiàn)代編譯原理-C語言描述7、鯨書（Whale book）英文名：Advanced Compiler Design and Implementation作者：Steven S.Muchnick中文名：高級(jí)編譯器設(shè)計(jì)與實(shí)現(xiàn),10,第一章 編譯程序概論,1.

5、1 什么是編譯程序 1.2 編譯過程概述 1.3 編譯程序的結(jié)構(gòu) 1.4 編譯技術(shù)的發(fā)展和應(yīng)用,11,1.1 什么是編譯程序(compiler),一、基本概念 1. 編譯程序 編譯程序是現(xiàn)代計(jì)算機(jī)系統(tǒng)的基本組成部分。 從功能上看，一個(gè)編譯程序就是一個(gè)語言翻譯程序，它把一種語言(稱作源語言)書寫的程序翻譯成另一種語言(稱作目標(biāo)語言)的等價(jià)的程序。,12,程序設(shè) 計(jì)語言,低級(jí)語言,高級(jí)語言,匯編語言,機(jī)器語言,翻譯 程序,翻譯 程序,2.程序設(shè)計(jì)語言及其翻譯,源程序,目標(biāo)程序,翻譯程序,13,翻譯程序Translator,匯編程序 Assembler,編譯程序 Compiler,解釋程序 Inte

6、rpreter,高級(jí)語言,3.翻譯程序,14,4. 高級(jí)語言程序處理的兩種方法,(1) 編譯途徑 方法一：,源程序,運(yùn)行程序,目標(biāo)程序,編譯程序,結(jié)果,初始數(shù)據(jù),編譯階段,運(yùn)行階段,15,4.高級(jí)語言程序處理的兩種方法,(1) 編譯途徑 方法二：,源程 序,運(yùn)行程序,目標(biāo) 代碼,編譯程序,結(jié) 果,初始數(shù)據(jù),編譯階段,運(yùn)行階段,匯編語言,匯編程序,匯編階段,16,(2) 解釋途徑,源程序,結(jié)果,解釋程序,初始數(shù)據(jù),直接解釋執(zhí)行、中間代碼,與編譯的主要區(qū)別：解釋程序不產(chǎn)生目標(biāo)代碼,4.高級(jí)語言程序處理的兩種方法,17,編譯程序 vs. 解釋程序,編譯,解釋,18,二、編譯程序的功能,功能,術(shù)語 編

7、譯程序的源語言(源程序S) 編譯程序的目標(biāo)語言(目標(biāo)程序O、T) 編譯程序的實(shí)現(xiàn)語言(I),高級(jí)語言 書寫的程序,編譯程序,低級(jí)語言程序,19,三、編譯程序在軟件中的地位,軟件 系統(tǒng)軟件 語言處理系統(tǒng),1.屬于系統(tǒng)軟件類,20,2.計(jì)算機(jī)軟件相關(guān)概念 (1) 軟件：計(jì)算機(jī)系統(tǒng)中的程序及其文檔 (2)系統(tǒng)軟件：居于計(jì)算機(jī)系統(tǒng)中最靠近硬件的一層，其他軟件一般都通過系統(tǒng)軟件發(fā)揮作用。他和具體的應(yīng)用領(lǐng)域無關(guān)，如編譯系統(tǒng)和操作系統(tǒng)等。 (3)語言處理系統(tǒng)：把軟件語言書寫的各種程序處理成可在計(jì)算機(jī)上執(zhí)行的程序。 (4)軟件語言：用于書寫軟件的語言。它主要包括需求定義語言，功能性語言，設(shè)計(jì)性語言，程序設(shè)計(jì)語

8、言以及文檔語言。,21,預(yù)處理器,編譯器,匯編器,裝配連接編輯,骨架程序,源程序,目標(biāo)匯編程序,可重定位機(jī)器代碼,絕對(duì)機(jī)器碼,可重定位目標(biāo)文件庫,3.語言處理過程,22,編譯工作重要貢獻(xiàn)者,Grace Hopper ，計(jì)算機(jī)軟件的第一夫人 Hopper“全美技術(shù)獎(jiǎng) 。1952年，世界上第一個(gè)將高級(jí)符號(hào)語言轉(zhuǎn)變?yōu)闄C(jī)器語言的編譯，COBOL語言和編譯器。 John Cocke ，“IBM小子” 1987圖靈獎(jiǎng)，高性能計(jì)算機(jī)的體系結(jié)構(gòu)方面（RISC） ，編譯器的優(yōu)化方面的貢獻(xiàn)。 A.J. Perlis 1966圖靈獎(jiǎng)，獲獎(jiǎng)原因：在先進(jìn)編程技術(shù)和編譯架構(gòu)方面的貢獻(xiàn)。,23,1.2 編譯過程概述,24,

9、把英文翻譯為中文 識(shí)別出句子中的一個(gè)個(gè)單詞； 分析句子的語法結(jié)構(gòu)； 根據(jù)句子的含義進(jìn)行初步翻譯； 對(duì)譯文進(jìn)行修飾； 寫出最后的譯文。,詞法分析,語法分析（含語義）,中間代碼生成,優(yōu)化,目標(biāo)代碼產(chǎn)生,舉例,25,編譯邏輯過程: 詞法分析 語法分析 語義分析 中間代碼生成 代碼優(yōu)化 目標(biāo)代碼生成 編譯輔助工作: 表格管理 出錯(cuò)處理,26,1. 詞法分析,掃描源程序的ASCII碼序列,拼出每一個(gè)單詞,并把每個(gè)單詞的ASCII碼序列替換為所謂的機(jī)內(nèi)表示TOKEN形式，這時(shí)還檢查詞法錯(cuò)誤。但詞法分析階段不依靠語法關(guān)系。 簡單地說，就是從左至右讀字符流的源程序、識(shí)別(拼)單詞。 例： position =

10、 initial + rate * 60;,27,詞法分析 position = initial + rate * 60;,單詞類型單詞值 標(biāo)識(shí)符1(id1) position 算符(賦值) = 標(biāo)識(shí)符2(id2) initial 算符(加) + 標(biāo)識(shí)符3(id3) rate 算符(乘) * 整數(shù) 60 分號(hào) ；,28,又如一個(gè)C源程序片斷： int a; a = a + 2; 詞法分析后可能返回: 單詞類型單詞值 保留字 int 標(biāo)識(shí)符(變量名) a 界符 ; 標(biāo)識(shí)符(變量名) a 算符(賦值) = 標(biāo)識(shí)符(變量名) a 算符(加) + 整數(shù) 2 界符 ；,29,2. 語法分析,功能：層次分

11、析。依據(jù)源程序的語法規(guī)則把源程序的單詞序列組成語法短語(表示成語法樹). 掃描對(duì)象可能是源程序的ASCII碼序列，也可能是詞法分析后的TOKEN序列。主要任務(wù)是檢查源程序的形式語法錯(cuò)誤,每當(dāng)發(fā)現(xiàn)錯(cuò)誤時(shí)將輸出有關(guān)信息。 position = initial + rate * 60 ; 規(guī)則 :=“=” :=“+” :=“*” :=“(”“)” := := :=,30,賦值語句,標(biāo)識(shí)符,表達(dá)式,表達(dá)式,+,表達(dá)式,表達(dá)式,標(biāo)識(shí)符,整數(shù),標(biāo)識(shí)符,=,表達(dá)式,*,31,id1=id2+id3*N,32,3.語義分析,語義審查(靜態(tài)語義) 上下文相關(guān)性 類型匹配 類型轉(zhuǎn)換,例:main p(); flo

12、at rate; void initial; position = initial + rate * 60; /* error */ /* error */ /* warning */; ,33,又如: int arr 2,abc; abc = arr * 10; main p(); float rate; float initial; float position ; position = initial + rate * 60;,34,語義分析例：,35,4.中間代碼生成,掃描對(duì)象通常是語法分析后的結(jié)果，這部分把源程序的TOKEN序列轉(zhuǎn)換成更接近目標(biāo)代碼的中間代碼三元式或四元式的序列。 源

13、程序的內(nèi)部(中間)表示： 后綴式、三元式、四元式、樹、波蘭式、逆波蘭式等 例如： 后綴式：ab+c* 表示(a+b)*c 三元式： ( *，id3，t1) 四元式： ( *，id3，t1，t2),36,中間代碼生成例：,id1= id2 + id3 * 60 (1)(inttoreal,60-t1) (2)(*,id3t1t2) (3)(+,id2t2t3) (4)(=,t3-id1),37,5.代碼優(yōu)化,按代碼級(jí)別，可分成源代碼優(yōu)化、中間代碼優(yōu)化和目標(biāo)代碼優(yōu)化三種。 其中：中間代碼優(yōu)化掃描對(duì)象是中間代碼,任務(wù)是把優(yōu)化前的中間代碼轉(zhuǎn)換成可產(chǎn)生高質(zhì)量目標(biāo)代碼的中間代碼。 優(yōu)化工作包括表達(dá)式優(yōu)化、

14、公共子表達(dá)式優(yōu)化、不便表達(dá)式外提和削減運(yùn)算強(qiáng)度等。,38,代碼優(yōu)化例：,t1 = b* c t1 = b* c t2 = t1+ 0 優(yōu)化后： a= t1 + t1 t3 = b* c t4 = t2 + t3 a = t4,39,6.目標(biāo)代碼生成,(*,id3，60.0，t1) (+,id2，t1，id1),movfid3,R2 mulf#60.0,R2 movfid2,R1 addfR2,R1 movfR1,id1,掃描對(duì)象是中間代碼，任務(wù)是從中間代碼產(chǎn)生目標(biāo)代碼，這一部分的工作與目標(biāo)機(jī)緊密相關(guān)，其它部分的工作幾乎與目標(biāo)機(jī)無關(guān)。,40,7.表格管理,較大的編譯程序用到很多表格，甚至可達(dá)幾十

15、種表。不少編譯程序都設(shè)立一些專門子程序（稱為表格管理程序），它們專門負(fù)責(zé)管理表格。 記錄源程序中使用的名字 收集每個(gè)名字的各種屬性信息，包括： 類型、作用域、分配存儲(chǔ)信息， 例如： Const1常量值：35 Var1變量類型：實(shí),41,8.出錯(cuò)處理,出錯(cuò)處理包括詞法錯(cuò)誤、語法錯(cuò)誤、靜態(tài)語義錯(cuò)誤、動(dòng)態(tài)語義錯(cuò)誤等； 出錯(cuò)處理模塊的作用是：檢查錯(cuò)誤、報(bào)告出錯(cuò)信息、排錯(cuò)、恢復(fù)編譯工作。,42,1.3 編譯程序的結(jié)構(gòu) (components),詞法分析程序 語法分析程序 語義分析程序 中間代碼生成程序 代碼優(yōu)化程序 目標(biāo)代碼生成程序 符號(hào)表管理程序 出錯(cuò)處理程序,43,出 錯(cuò) 處 理,表 格 管 理,4

16、4,1.4 編譯技術(shù)的發(fā)展和應(yīng)用,一、實(shí)現(xiàn)方式 手工 機(jī)器語言 匯 編 系統(tǒng)程序設(shè)計(jì)語言 自動(dòng)構(gòu)造工具 lex yacc 分類：命令行 集成環(huán)境,45,二、程序設(shè)計(jì)語言范型,1. 命令式（過程式）： 程序特點(diǎn)： 語句1； 語句2； 語句3； 與馮諾曼機(jī)的體系結(jié)構(gòu)一致,46,2.應(yīng)用式（函數(shù)式） 程序特點(diǎn)： Function n(funetion2(funetion1(data) 程序執(zhí)行： 執(zhí)行一個(gè)個(gè)函數(shù)施用在數(shù)據(jù)上的變換最終得到的結(jié)果 編譯： 語法分析容易； 語義處理復(fù)雜。,二、程序設(shè)計(jì)語言范型,47,3.基于規(guī)則的語言（prolog, yacc)： 程序特點(diǎn)： 使能條件1 動(dòng)作1 使能條件

17、2 動(dòng)作2 使能條件3 動(dòng)作3 4. 面向?qū)ο笳Z言： 抽象數(shù)據(jù)類型，繼承機(jī)制 編譯： 動(dòng)態(tài)綁定；,二、程序設(shè)計(jì)語言范型,48,三、執(zhí)行環(huán)境,批處理環(huán)境：將源程序作為整體處理 排除程序錯(cuò)誤不能依靠用戶的外部幫助 交互環(huán)境：解釋 增量式編譯 嵌入式系統(tǒng)環(huán)境：交叉編譯 分布并行環(huán)境： 并行編譯 程序創(chuàng)建和測試環(huán)境： 獨(dú)立編譯 編譯和調(diào)試同時(shí)設(shè)計(jì)考慮,49,高級(jí)語言的實(shí)現(xiàn) 高級(jí)編程語言易于編程，但程序運(yùn)行較慢 低級(jí)語言編程時(shí)可實(shí)施更有效的控制方式，得到更有效的代碼，但難編寫、易出錯(cuò)、難維護(hù) 流行編程語言的大多數(shù)演變都是朝著提高抽象級(jí)別的方向 每一輪編程語言新特征的出現(xiàn)都刺激編譯器優(yōu)化的新研究,四、編譯

18、技術(shù)的應(yīng)用,50,高級(jí)語言的實(shí)現(xiàn) 每一輪編程語言新特征的出現(xiàn)都刺激編譯器優(yōu) 化的新研究 支持用戶定義的聚合數(shù)據(jù)類型和高級(jí)控制流，如數(shù)組和記錄、循環(huán)和過程調(diào)用：C、Fortran 面向?qū)ο蟮闹饕拍钍菙?shù)據(jù)抽象和性質(zhì)繼承，使得程序更加模塊化并易于維護(hù)：Smalltalk、C+、C#、Java 類型安全的語言：Java沒有指針，也不允許指針?biāo)阈g(shù)。它用無用單元收集機(jī)制來自動(dòng)地釋放那些不再使用的變量占據(jù)的內(nèi)存 Java設(shè)計(jì)來支持代碼移植和代碼移動(dòng),四、編譯技術(shù)的應(yīng)用,51,針對(duì)計(jì)算機(jī)體系結(jié)構(gòu)的優(yōu)化 計(jì)算機(jī)體系結(jié)構(gòu)的迅速演化引起對(duì)新的編譯器技術(shù)一種不知足的需要 并行化 編譯器重新整理指令，使得指令級(jí)并行更有效 編譯器從傳統(tǒng)的串行程序自動(dòng)生成并行代碼，使之運(yùn)行于多處理器上 內(nèi)存分層 編譯器優(yōu)化歷來集中在優(yōu)化處理器的執(zhí)行上，但是現(xiàn)在更強(qiáng)調(diào)要使內(nèi)存分層更有效,四、編譯技術(shù)的應(yīng)用,52,新計(jì)算機(jī)體系結(jié)構(gòu)的設(shè)計(jì) 現(xiàn)在計(jì)算機(jī)系統(tǒng)