計算機科學(xué)與技術(shù)編譯原理考試重點課件

1、計算機科學(xué)與技術(shù)編譯原理考試重點,1,編譯原理compilers principles,學(xué)時安排 上課：48學(xué)時（415周） 實驗：12學(xué)時（1015周 ）,計算機科學(xué)與技術(shù)編譯原理考試重點,2,課程內(nèi)容,第一章 引論 第二章 形式語言概論 第三章 有窮自動機 第四章 詞法分析 第五章 自上而下語法分析 第六章 自下而上分析和優(yōu)先分析方法 第七章 自下而上的LR(k)分析方法,計算機科學(xué)與技術(shù)編譯原理考試重點,3,成績：,平時 實驗 期中考查 期末考試,計算機科學(xué)與技術(shù)編譯原理考試重點,4,與課程有關(guān)的問題：,本課程的性質(zhì)、目的和任務(wù) ： 編譯原理是計算機類專業(yè)的專業(yè)課，目的是使學(xué)生了解并掌握

2、編譯程序的基本理論和方法，具有分析和實現(xiàn)編譯程序的初步能力。 本課程的基本要求 ： 通過對本課程的學(xué)習(xí)，對形式語言有初步了解，對編譯程序的整個結(jié)構(gòu)有較清楚的了解，熟悉和掌握幾種主要編譯方法。 課程內(nèi)容的重點、深度與廣度 ： 文法和形式語言、詞法分析和有窮自動機、語法分析 語義分析、目標代碼的生成，了解符號表的構(gòu)造、存儲分配與管理、代碼優(yōu)化和錯誤校正,計算機科學(xué)與技術(shù)編譯原理考試重點,5,第一章 引 論,本節(jié)內(nèi)容： 翻譯程序 為什么需要編譯程序 編譯程序的工作過程 編譯程序的結(jié)構(gòu) 編譯程序的組織方式 編譯程序的其它有關(guān)技術(shù) 編譯程序編寫系統(tǒng) 并行編譯程序,計算機科學(xué)與技術(shù)編譯原理考試重點,6,編

3、譯程序在計算機系統(tǒng)中的位置,分類 軟件 系統(tǒng)軟件 語言處理系統(tǒng),計算機科學(xué)與技術(shù)編譯原理考試重點,7,1.1 程序的翻譯,1.1.1 程序設(shè)計語言 機器語言 0 匯編語言 add R1 2 高級語言 begin x:=9+2 end 問題: 計算機只能識別二進制數(shù)0、1表示的指令和數(shù)構(gòu)成的本計算機系統(tǒng)的機器語言。如何讓計算機執(zhí)行高級語言程序呢？,計算機科學(xué)與技術(shù)編譯原理考試重點,8,1.1 程序的翻譯,1.1.2 翻譯程序 所謂翻譯程序，是指這樣一種程序，它能將用甲語言（源語言）編寫的程序翻譯成與之等價的用乙語言（目標語言）書寫的程序。 程序的翻譯通常有兩種方式：一是“編譯”方式，二是“解釋”

4、方式。 如口譯和筆譯,計算機科學(xué)與技術(shù)編譯原理考試重點,9,1.1 程序的翻譯,1.1.3 編譯方式 一種分階段進行的方式 1.翻譯階段： 高級語言或匯編語言源程序 機器語言目標程序 2.運行階段 目標程序、運行子程序、數(shù)據(jù) 運行結(jié)果,計算機科學(xué)與技術(shù)編譯原理考試重點,10,1.1 程序的翻譯,3.編譯方式的特點 在編譯方式下，源程序的執(zhí)行需要分階段。 如果目標程序是機器語言程序， 則源程序的執(zhí)行分為兩大階段：編譯階段和運行階段。 如果目標程序是匯編語言程序， 則源程序的執(zhí)行分為三大階段：編譯階段、匯編階段和運行階段。 編譯方式下，生成了目標代碼，且可多次執(zhí)行。,計算機科學(xué)與技術(shù)編譯原理考試重

5、點,11,1.1 程序的翻譯,4.關(guān)于編譯程序的幾點說明 編譯程序生成的目標程序不一定是機器語言的程序，也有可能是匯編語言程序； 編譯程序與具體的機器和語言有關(guān)，即任何一個具體的編譯程序都是某一特定類型的計算機系統(tǒng)中關(guān)于某一特定語言的編譯程序； 對編譯程序而言，源程序是輸入數(shù)據(jù)，目標程序是輸出結(jié)果。,計算機科學(xué)與技術(shù)編譯原理考試重點,12,1.1 程序的翻譯,1.1.4 解釋方式 完成解釋工作的解釋程序?qū)丛闯绦蛑姓Z句的動態(tài)順序，逐句地進行分析解釋，并立即予以執(zhí)行，給出執(zhí)行結(jié)果。 執(zhí)行歷程為：,計算機科學(xué)與技術(shù)編譯原理考試重點,13,1.1 程序的翻譯,源程序解釋執(zhí)行的歷程 源程序 （高級語言

6、）、初始數(shù)據(jù) 解釋程序 計 算 結(jié) 果 在解釋方式下，并不生成目標代碼，而是直接執(zhí)行源程序本身。這是編譯方式與解釋方式的根本區(qū)別。,計算機科學(xué)與技術(shù)編譯原理考試重點,14,1.2 為什么需要編譯程序,編譯程序具有以下特點： 模塊性 靜態(tài)解釋和動態(tài)解釋 機器無關(guān)性 語言標準化 程序語言特征,計算機科學(xué)與技術(shù)編譯原理考試重點,15,1.3 編譯程序的工作過程,詞法分析 語法分析 語義分析和中間代碼生成 中間代碼優(yōu)化 目標代碼生成,計算機科學(xué)與技術(shù)編譯原理考試重點,16,1.3 編譯程序的工作過程,1.3.1 詞法分析 依據(jù)語言詞法規(guī)則，分析由字符組成的源程序，把它識別為一個一個具有獨立意義的最小語

7、法單位，即“單詞”，并識別出與其相關(guān)的屬性(如是標識符，是界限符，還是數(shù)，等等)，再轉(zhuǎn)換成長度上統(tǒng)一的標準形式(這種統(tǒng)一的標準形式既刻畫了單詞本身，又刻畫了它所具有的屬性，稱為屬性字)，以供其它部分使用。,計算機科學(xué)與技術(shù)編譯原理考試重點,17,詞法分析,讀字符流的源程序、識別單詞 例： position = initial + rate * 60,計算機科學(xué)與技術(shù)編譯原理考試重點,18,詞法分析,單詞類型單詞值 標識符1(id1)position 算符(賦值) = 標識符2(id2) initial 算符(加) + 標識符3(id3) rate 算符(乘) * 整數(shù) 60 分號 ；,計算機科

8、學(xué)與技術(shù)編譯原理考試重點,19,1.3 編譯程序的工作過程,1.3.2 語法分析 依據(jù)語法規(guī)則，逐一分析詞法分析時得到的單詞，把單詞串分解成各類語法單位，即確定它們是怎樣組成說明和語句，以及說明和語句又是怎樣組成程序的。分析時如發(fā)現(xiàn)有不合語法規(guī)則的地方，便將出錯的位置及出錯性質(zhì)打印報告給程序員；如無語法錯誤，則用另一種中間形式給出正確的語法結(jié)構(gòu)，供下一階段分析使用。,計算機科學(xué)與技術(shù)編譯原理考試重點,20,語法分析,功能:層次分析,把源程序的單詞序列組成語法短語(表示成語法樹). 例: :=“=” :=“+” :=“*” :=“(”“)” := := :=,計算機科學(xué)與技術(shù)編譯原理考試重點,2

9、1,賦值語句,標識符,表達式,表達式,+,表達式,表達式,整數(shù),實數(shù),標識符,=,表達式,*,計算機科學(xué)與技術(shù)編譯原理考試重點,22,語法分析id1=id2+id3*N,計算機科學(xué)與技術(shù)編譯原理考試重點,23,1.3 編譯程序的工作過程,1.3.3 語義分析 依據(jù)語言的語義規(guī)則對語法分析得到的語法結(jié)構(gòu)進行靜態(tài)語義檢查(確定類型、類型和運算合法性檢查、識別含義與相應(yīng)的語義處理及其它一些靜態(tài)語義檢查)，并用另一種內(nèi)部形式表示出來，或者直接用目標語言表示出來。 凡在編譯時可以確定的內(nèi)容稱為“靜態(tài)”的；凡必須推遲到程序運行時才能確定的內(nèi)容稱為“動態(tài)”的。,計算機科學(xué)與技術(shù)編譯原理考試重點,24,語義分

10、析,語義審查(靜態(tài)語義) 上下文相關(guān)性 類型匹配 類型轉(zhuǎn)換,例:Program p(); Var rate:real; procedure initial; position := initial + rate * 60 /* error */ /* error */ /* warning */; ,計算機科學(xué)與技術(shù)編譯原理考試重點,25,Program p(); Var rate:real; Var initial :real; Var position :real ; position := initial + rate * 60 ,計算機科學(xué)與技術(shù)編譯原理考試重點,26,語義分析,計算機

11、科學(xué)與技術(shù)編譯原理考試重點,27,中間代碼生成,源程序的內(nèi)部(中間)表示 逆波蘭式、三元式、四元式、樹型表示 逆波蘭式也是后綴表達式 2-34+5 2 3 4 - 5 + 優(yōu)勢在于只用兩種簡單操作，入棧和出棧就可以搞定任何普通表達式的運算 運算方式如下： 如果當(dāng)前字符為變量或者為數(shù)字，則壓棧，如果是運算符，則將棧頂兩個元素彈出作相應(yīng)運算，結(jié)果再入棧，最后當(dāng)表達式掃描完后，棧里的就是結(jié)果。,計算機科學(xué)與技術(shù)編譯原理考試重點,28,中間代碼生成,id1= id2 + id3 * 60 (1)(inttoreal,60-t1) (2)(*,id3t1t2) (3)(+,id2t2t3) (4)(=,

12、t3-id1),計算機科學(xué)與技術(shù)編譯原理考試重點,29,1.3 編譯程序的工作過程,1.3.4 代碼優(yōu)化 依據(jù)程序的等價變換規(guī)則，盡量壓縮目標程序運行所需的時間和所占的存儲空間，以提高目標程序的質(zhì)量。,計算機科學(xué)與技術(shù)編譯原理考試重點,30,代碼優(yōu)化,id1= id2 + id3 * 60 (1)(inttoreal60-t1) (2)( * id3t1t2) (3)( +id2t2t3) (4)( :=t3-id1) 變換 （1） ( *id360.0t1) ( 2）（ + id2 t1id1),計算機科學(xué)與技術(shù)編譯原理考試重點,31,1.3 編譯程序的工作過程,1.3.5 代碼生成 如果語

13、義分析時把源程序表示成中間形式而不是表示成目標指令，則由本部分完成從中間形式到目標指令的轉(zhuǎn)換。如果語義分析時，已直接生成目標指令，則無需另外再做代碼生成工作。 目標指令可能是絕對指令代碼，或可重新定位的指令代碼或匯編指令代碼。該階段的工作有賴于硬件系統(tǒng)結(jié)構(gòu)和機器指令含義。,計算機科學(xué)與技術(shù)編譯原理考試重點,32,目標代碼生成,(*,id360.0t1) (+,id2t1id1),movfid3,R2 mulf#60.0,R2 movfid2,R1 addfR2,R1 movfR1,id1,計算機科學(xué)與技術(shù)編譯原理考試重點,33,1.3 編譯程序的工作過程,1.3.6 表格管理 登記源程序中出現(xiàn)

14、的每個名字以及名字的各種屬性。有些名字的屬性需要在各個階段才能填入。,計算機科學(xué)與技術(shù)編譯原理考試重點,34,符號表管理,記錄源程序中使用的名字 收集每個名字的各種屬性信息 類型、作用域、分配存儲信息,Const1常量值：35 Var1變量類型：實層次：2,計算機科學(xué)與技術(shù)編譯原理考試重點,35,1.3 編譯程序的工作過程,1.3.7 出錯處理 源程序中的錯誤有語法錯誤和語義錯誤兩種。 1.語法錯誤：源程序中不符合語法(或詞法)規(guī)則的錯誤，它們可在詞法分析或語法分析時檢測出來。 2.語義錯誤：源程序中不符合語義規(guī)則的錯誤，一般在語義分析時檢測出來，有的語義錯誤要在運行時才能檢測出來。通常包括：

15、說明錯誤、作用域錯誤、類型不一致等等,計算機科學(xué)與技術(shù)編譯原理考試重點,36,出錯處理,檢查錯誤、報告出錯信息、排錯、恢復(fù)編譯工作,計算機科學(xué)與技術(shù)編譯原理考試重點,37,1.4 編譯程序的結(jié)構(gòu),計算機科學(xué)與技術(shù)編譯原理考試重點,38,1.4 編譯程序的結(jié)構(gòu),計算機科學(xué)與技術(shù)編譯原理考試重點,39,1.4 編譯程序的結(jié)構(gòu),1.4.1 遍(趟，趟程) 所謂一趟或一遍是指一個編譯程序在編譯時刻把源程序或源程序的等價物(中間程序)從頭到尾掃描一遍并轉(zhuǎn)換成另一緊鄰的等價物的全過程。 根據(jù)編譯程序在完成翻譯任務(wù)的過程中需要對源程序或其中間等價物掃描的遍數(shù)，可以把編譯程序分為單遍掃描的編譯程序(只需掃描一

16、遍)和多遍掃描的編譯程序(需掃描多遍)。,計算機科學(xué)與技術(shù)編譯原理考試重點,40,單遍掃描的編譯程序,計算機科學(xué)與技術(shù)編譯原理考試重點,41,1.4 編譯程序的結(jié)構(gòu),1.4.2 編譯的前端和后端 前端主要由與源語言有關(guān)但與目標機器無關(guān)的那些部分組成，如詞法分析、語法分析、語義分析與中間代碼生成及部分代碼優(yōu)化工作。 后端主要包括編譯中與目標機器有關(guān)的那些部分，如與目標機有關(guān)的代碼優(yōu)化和目標代碼生成等。后端不依賴于源語言而僅依賴于中間語言。 可以通過改變編譯程序的后端來實現(xiàn)編譯程序的移植。,計算機科學(xué)與技術(shù)編譯原理考試重點,42,1.5 編譯程序的組織方式,課本 圖1.7 Page10,計算機科學(xué)

17、與技術(shù)編譯原理考試重點,43,1.6 編譯程序的其它有關(guān)技術(shù),1.6.1 高級語言的自展技術(shù) 構(gòu)造編譯程序可以用機器言語、匯編語言和高級語言。 高級語言的自編譯性：一個語言可以用來編寫自己的編譯程序。,計算機科學(xué)與技術(shù)編譯原理考試重點,44,1.6 編譯程序的其它有關(guān)技術(shù),1.6.1 編譯的自展技術(shù) 通過一系列自展途徑而形成編譯程序的過程。 先對語言的核心部分構(gòu)造一個小小編譯程序(可用低級語言實現(xiàn))，再以它為工具構(gòu)造一個能夠編譯更多語言成分的較大編譯程序。如此擴展下去，越滾越大，最后形成所期望的整個編譯程序。滾雪球！ 課本 圖1.8 Page10,計算機科學(xué)與技術(shù)編譯原理考試重點,45,1.6

18、 編譯程序的其它有關(guān)技術(shù),1.6.2 編譯的移植技術(shù) 將一個機器（宿主機）上的一個具有自編譯性的高級語言編譯程序移植到另一個機器（目標機）上。 利用A機器上的高級語言L編寫能在B機器上運行的高級語言L的編譯程序。 如下圖：,計算機科學(xué)與技術(shù)編譯原理考試重點,46,1.6 編譯程序的其它有關(guān)技術(shù),1.6.2 編譯的移植技術(shù) 將一個機器（宿主機）上的一個具有自編譯性的高級語言編譯程序移植到另一個機器（目標機）上。 利用A機器上的高級語言L編寫能在B機器上運行的高級語言L的編譯程序。,計算機科學(xué)與技術(shù)編譯原理考試重點,47,1.6 編譯程序的其它有關(guān)技術(shù),1.6.3 編譯程序自動化 1.詞法分析生成器 如：LEX （接