編譯原理第一講

1、編譯原理教師教師：劉丁劉丁計算機科學(xué)與技術(shù)系計算機科學(xué)與技術(shù)系2014-20152014-2015學(xué)年學(xué)年寫在課程之前 課程難度 權(quán)利和義務(wù) 考核學(xué)時與參考教材學(xué)時與參考教材學(xué)時：學(xué)時：4 45 5學(xué)時學(xué)時周五（周五（1-141-14周）周）周一（周一（2,4,62,4,6周）周）參考參考教材：教材：1、Alfred Aho ect. 編譯原理，趙建華等譯，機械工業(yè)出版社，2009.10.Modern Compiler Implementation in C ，中文名現(xiàn)代編譯原理-C語言描述，作者Andrew W. AppelAdvanced Compiler Design and Imple

2、mentation，中文名高級編譯器設(shè)計與實現(xiàn)，作者 Steven S.Muchnick編譯原理講什么？編譯原理講什么？q編譯系統(tǒng)及其設(shè)計概述編譯系統(tǒng)及其設(shè)計概述（總體結(jié)構(gòu)、設(shè)計方法總體結(jié)構(gòu)、設(shè)計方法）q語言與文法語言與文法（文法、推導(dǎo)、歸約、分類、分析樹文法、推導(dǎo)、歸約、分類、分析樹）q詞法分析詞法分析（詞法分析、正規(guī)式與正規(guī)文法、詞法分析、正規(guī)式與正規(guī)文法、DFADFA的狀態(tài)轉(zhuǎn)移圖的狀態(tài)轉(zhuǎn)移圖）q語法分析語法分析（自頂向下：自頂向下：LL(1)LL(1)、遞歸子程序；自底向上：遞歸子程序；自底向上：LRLR）q語義分析語義分析（屬性文法、各種語句的語法制導(dǎo)翻譯屬性文法、各種語句的語法制導(dǎo)翻

3、譯）q運行環(huán)境運行環(huán)境（存儲分配、過程調(diào)用、符號表管理存儲分配、過程調(diào)用、符號表管理）q代碼優(yōu)化代碼優(yōu)化（基本塊的優(yōu)化、循環(huán)優(yōu)化等基本塊的優(yōu)化、循環(huán)優(yōu)化等）q代碼生成代碼生成（目標(biāo)機器模型、基本塊和流圖、寄存器分配、基本塊的目標(biāo)機器模型、基本塊和流圖、寄存器分配、基本塊的DAG表示、從表示、從 DAG生成目標(biāo)代碼生成目標(biāo)代碼）應(yīng)用開發(fā)計算機維護編譯原理離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)算法分析形式語言自動機數(shù)據(jù)庫程序設(shè)計操作系統(tǒng)組成原理編譯原理重要嗎？從從編譯原理能編譯原理能學(xué)學(xué)到什么？到什么？ 掌握編譯程序掌握編譯程序總體結(jié)構(gòu)總體結(jié)構(gòu) 在在系統(tǒng)級系統(tǒng)級上認識算法、系統(tǒng)的設(shè)計上認識算法、系統(tǒng)的設(shè)計 具有把握系統(tǒng)

4、的能力具有把握系統(tǒng)的能力 學(xué)習(xí)有關(guān)的原理、實現(xiàn)方法和技術(shù)，了解計算學(xué)科的基本方法、思想學(xué)習(xí)有關(guān)的原理、實現(xiàn)方法和技術(shù)，了解計算學(xué)科的基本方法、思想 掌握典型方法。掌握典型方法。 “在每一個計算機科技工作者的職業(yè)生涯中，這些原理和技在每一個計算機科技工作者的職業(yè)生涯中，這些原理和技術(shù)都被反復(fù)用到。術(shù)都被反復(fù)用到。” 兼顧語言的描述方法、設(shè)計、應(yīng)用兼顧語言的描述方法、設(shè)計、應(yīng)用形式化形式化 能形式化就能自動化能形式化就能自動化 進一步培養(yǎng)進一步培養(yǎng)“計算思維能力計算思維能力”編譯原理怎么學(xué)？編譯原理怎么學(xué)？ 讀世界上最好的教材讀世界上最好的教材 龍書龍書 虎書虎書 鯨書鯨書 充分利用網(wǎng)絡(luò)資源充分利

5、用網(wǎng)絡(luò)資源 MOOCMOOC EdxEdx 讀源碼讀源碼 Get your hands dirty!Get your hands dirty!第第1 1章章 引論引論 1.1 1.1 計算機語言的發(fā)展計算機語言的發(fā)展 1.2 1.2 翻譯、編譯、解釋翻譯、編譯、解釋 1.1.3 3 編譯程序總體結(jié)構(gòu)編譯程序總體結(jié)構(gòu) 1.1.4 4 編譯程序的生成編譯程序的生成 1.1.5 5 編譯技術(shù)的應(yīng)用編譯技術(shù)的應(yīng)用1.1 計算機語言的發(fā)展計算機語言的發(fā)展 機器語言機器語言( (Machine Language)Machine Language)與匯編語言與匯編語言( (Assemble Language

6、)Assemble Language) 0 0、1 1代碼與助記符：更接近于計算機硬件指令系統(tǒng)的工代碼與助記符：更接近于計算機硬件指令系統(tǒng)的工作作 高級語言高級語言( (High Level Language)High Level Language) 其表示方法更接近于待解問題的表示方法其表示方法更接近于待解問題的表示方法 定義數(shù)據(jù)、描述運算、控制流程、傳輸數(shù)據(jù)定義數(shù)據(jù)、描述運算、控制流程、傳輸數(shù)據(jù) 如：如：C C、FORTRANFORTRAN、PASCALPASCAL、C+C+、JAVAJAVA、SQL(SQL(數(shù)據(jù)定義、數(shù)據(jù)數(shù)據(jù)定義、數(shù)據(jù)操作操作) ) 命令語言命令語言( (Command

7、 Language)Command Language) 控制系統(tǒng)的工作控制系統(tǒng)的工作以功能封裝為特征以功能封裝為特征 如如UNIXUNIX上的上的shellshell1.2 1.2 翻譯系統(tǒng)翻譯系統(tǒng)翻譯程序翻譯程序( (Translator)Translator)將某一種語言描述的程序?qū)⒛骋环N語言描述的程序( (源程序源程序Source Source Program)Program)翻譯成等價的另一種語言描述的程翻譯成等價的另一種語言描述的程序序( (目標(biāo)程序目標(biāo)程序Object Program)Object Program)的程序。的程序。翻譯程序翻譯程序源程序源程序目標(biāo)程序目標(biāo)程序1.2

8、1.2 編譯系統(tǒng)編譯系統(tǒng)編譯程序編譯程序( (Compiler)Compiler) 高級語言程序高級語言程序匯編匯編/ /機器語言機器語言程序程序 匯編語言更容易輸出、調(diào)試匯編語言更容易輸出、調(diào)試程序設(shè)計語言程序設(shè)計語言目標(biāo)程序目標(biāo)程序1.2 1.2 編譯系統(tǒng)編譯系統(tǒng)SPCompilerS-SourceO-ObjectOPP-ProgramInputRSRS-Run Sys. Output1.2 1.2 解釋解釋系統(tǒng)系統(tǒng)解釋程序解釋程序( (Interpreter)Interpreter) 口譯與筆譯（單句提交與整篇提交）口譯與筆譯（單句提交與整篇提交）源程序源程序輸入數(shù)據(jù)輸入數(shù)據(jù)計算結(jié)果計算

9、結(jié)果知識點 編譯器和解釋器之間的區(qū)別是什么？舉例說明 在編譯系統(tǒng)中，編譯器產(chǎn)生匯編語言而不是機器語言的好處是什么？1.4 1.4 編譯程序總體結(jié)構(gòu)編譯程序總體結(jié)構(gòu)1 1、詞法分析、詞法分析 詞法分析由詞法分析器完成詞法分析由詞法分析器完成( (Lexical Analyzer)Lexical Analyzer)，詞法分析詞法分析器又叫做掃描器器又叫做掃描器( (Scanner)Scanner) 詞法分析器從左到右掃描源程序詞法分析器從左到右掃描源程序發(fā)現(xiàn)一個字符串，則將發(fā)現(xiàn)一個字符串，則將該字符串轉(zhuǎn)換成單詞該字符串轉(zhuǎn)換成單詞( (記號記號Token)Token)串；同時要：查詞法錯串；同時要：

10、查詞法錯誤，進行標(biāo)識符登記誤，進行標(biāo)識符登記符號表管理。符號表管理。 輸入：字符串輸入：字符串 輸出：輸出：( (種別碼，屬性值種別碼，屬性值) )序?qū)π驅(qū)?屬性值屬性值tokentoken的機內(nèi)表示的機內(nèi)表示1. 1. 詞法分析詞法分析 例：例：main( ) main( ) printf( printf(“hellohello”);); 結(jié)果結(jié)果IDNmain()IDNprintf (STRhello);2 2、語法分析、語法分析 語法分析由語法分析器語法分析由語法分析器( (Syntax Analyzer)Syntax Analyzer)完成，完成，語法分析器又叫語法分析器又叫Parse

11、rParser。 功能：功能： ParserParser實現(xiàn)實現(xiàn)“組詞成句組詞成句” 將詞組成各類語法成分：表達式、因子、項，語句，子程序?qū)⒃~組成各類語法成分：表達式、因子、項，語句，子程序 構(gòu)造分析樹構(gòu)造分析樹 指出語法錯誤指出語法錯誤 指導(dǎo)翻譯指導(dǎo)翻譯 輸入：輸入：TokenToken序列序列 輸出：語法成分輸出：語法成分2. 2. 語法分析語法分析res=fact*(term1+term2);3. 3. 語義分析語義分析 功能：分析由語法分析器識別出的語法單位的語功能：分析由語法分析器識別出的語法單位的語義義 獲取標(biāo)識符的屬性：獲取標(biāo)識符的屬性：類型檢查、類型檢查、作用域等作用域等 語義

12、檢查：運算的合法性語義檢查：運算的合法性、類型轉(zhuǎn)換、取、類型轉(zhuǎn)換、取值值范圍等范圍等 子程序的靜態(tài)綁定：代碼的相對地址子程序的靜態(tài)綁定：代碼的相對地址 變量的靜態(tài)綁定：數(shù)據(jù)的相對地址變量的靜態(tài)綁定：數(shù)據(jù)的相對地址4. 4. 中間代碼生成中間代碼生成 中間代碼的特點中間代碼的特點 簡單規(guī)范簡單規(guī)范 與機器無關(guān)與機器無關(guān) 易于優(yōu)化與轉(zhuǎn)換易于優(yōu)化與轉(zhuǎn)換4 4. . 中間代碼生成中間代碼生成中間代碼中間代碼( (intermediate Code)intermediate Code)例例: :id1+id2*id3T1=id2*id3T2=id1*T15. 5. 代碼優(yōu)化代碼優(yōu)化對中間代碼的優(yōu)化處理對

13、中間代碼的優(yōu)化處理: :對代碼進行等對代碼進行等價變換以求提高執(zhí)行效率價變換以求提高執(zhí)行效率提高運提高運行速度和節(jié)省存儲空間行速度和節(jié)省存儲空間 與機器無關(guān)的優(yōu)化與機器無關(guān)的優(yōu)化 與機器有關(guān)的優(yōu)化與機器有關(guān)的優(yōu)化與機器無關(guān)的優(yōu)化與機器無關(guān)的優(yōu)化局部優(yōu)化局部優(yōu)化 常量合并：常數(shù)運算在編譯期間完成，如常量合并：常數(shù)運算在編譯期間完成，如8+98+9* *4 4 公共子表達式的提取公共子表達式的提取: :基本塊內(nèi)基本塊內(nèi)循環(huán)優(yōu)化循環(huán)優(yōu)化 強度削減強度削減 用較快的操作代替較慢的操作用較快的操作代替較慢的操作 代碼外提代碼外提 將循環(huán)不變計算移出循環(huán)將循環(huán)不變計算移出循環(huán)與機器有關(guān)的優(yōu)化與機器有關(guān)的優(yōu)

14、化 寄存器的利用寄存器的利用 將常用量放入寄存器，以減少訪問內(nèi)存的次數(shù)將常用量放入寄存器，以減少訪問內(nèi)存的次數(shù) 體系結(jié)構(gòu)體系結(jié)構(gòu) MIMDMIMD、SIMDSIMD、SPMDSPMD、向量機、流水機向量機、流水機 存儲策略存儲策略 根據(jù)算法訪存的要求安排：根據(jù)算法訪存的要求安排：CacheCache、并行存儲體系并行存儲體系減減少訪問沖突少訪問沖突 任務(wù)劃分任務(wù)劃分 按運行的算法及體系結(jié)構(gòu)，劃分子任務(wù)按運行的算法及體系結(jié)構(gòu)，劃分子任務(wù)( (MPMD)MPMD)6. 6. 目標(biāo)代碼生成（目標(biāo)代碼生成（Code GeneratorCode Generator） 將中間代碼轉(zhuǎn)換成目標(biāo)機上的機器指令代

15、碼或匯編將中間代碼轉(zhuǎn)換成目標(biāo)機上的機器指令代碼或匯編代碼代碼 確定源語言的各種語法成分的目標(biāo)代碼結(jié)構(gòu)（機器指令確定源語言的各種語法成分的目標(biāo)代碼結(jié)構(gòu)（機器指令組組/ /匯編語句組）匯編語句組） 制定從中間代碼到目標(biāo)代碼的翻譯策略或算法制定從中間代碼到目標(biāo)代碼的翻譯策略或算法 目標(biāo)代碼的形式目標(biāo)代碼的形式 具有絕對地址的機器指令具有絕對地址的機器指令 匯編語言形式的目標(biāo)程序匯編語言形式的目標(biāo)程序 模塊結(jié)構(gòu)的機器指令（需要鏈接程序）模塊結(jié)構(gòu)的機器指令（需要鏈接程序）7 7、表格管理、表格管理 管理各種符號表（常數(shù)、標(biāo)號、變量、過程、結(jié)管理各種符號表（常數(shù)、標(biāo)號、變量、過程、結(jié)構(gòu)構(gòu)），查、填（登記、

16、查找）源程序中出現(xiàn)），查、填（登記、查找）源程序中出現(xiàn)的符號和編譯程序生成的符號，為編譯的各個階的符號和編譯程序生成的符號，為編譯的各個階段提供信息。段提供信息。 輔助語法檢查、語義檢查輔助語法檢查、語義檢查 完成靜態(tài)綁定、管理編譯過程完成靜態(tài)綁定、管理編譯過程 HashHash表、鏈表等各種查、填表技術(shù)表、鏈表等各種查、填表技術(shù)8 8、錯誤處理、錯誤處理進行各種錯誤的檢查、報告、糾正，以及相應(yīng)進行各種錯誤的檢查、報告、糾正，以及相應(yīng)的續(xù)編譯處理（如：錯誤的定位與局部化）的續(xù)編譯處理（如：錯誤的定位與局部化）詞法：拼寫詞法：拼寫語法：語句結(jié)構(gòu)、表達式結(jié)構(gòu)語法：語句結(jié)構(gòu)、表達式結(jié)構(gòu)語義：類型不匹

17、配語義：類型不匹配詞法分析器語法分析器語義分析器中間代碼生成器代碼優(yōu)化器代碼生成器position:= initial + rate * 60idid1 := idid2 + idid3 * 60:=+*idid1idid2idid360:=+*idid1idid2idid360inttorealinttorealtemp1 := inttoreal(60)temp2 := id3 *temp1temp3 := id2 +temp2id1 := temp3temp1 := id3 *60.0id1 := id2 + temp1MOVF id3, R2MULF #60.0, R2MOVF id2

18、, R1ADDF R2, R1MOVF R1, id1符號表 position initial rate 1234例例 一個語句的翻譯一個語句的翻譯9 9 編譯的遍（編譯的遍（PassPass） 根據(jù)系統(tǒng)資源的狀況、運行目標(biāo)的要求根據(jù)系統(tǒng)資源的狀況、運行目標(biāo)的要求等，等，可以將一個編譯程序設(shè)計成多遍掃描的形式，在可以將一個編譯程序設(shè)計成多遍掃描的形式，在每一遍掃描中，完成不同的任務(wù)。每一遍掃描中，完成不同的任務(wù)。 如：首遍構(gòu)造語法樹，二遍處理中間表示，增加信息如：首遍構(gòu)造語法樹，二遍處理中間表示，增加信息等。等。 遍可以和階段相對應(yīng)，也可無關(guān)遍可以和階段相對應(yīng)，也可無關(guān) 單遍代碼不太有效單遍代碼不太有效1010、編譯的前端與后端、編譯的前端與后端 前端前端 與源語言有關(guān)、與目標(biāo)機無關(guān)的部分與源語言有關(guān)、與目標(biāo)機無關(guān)的部分 詞法分析、語法分析、語義分析與中間代碼生成、與詞法分析、語法分析、語義分析與中間代碼生成、與機器無關(guān)的代碼優(yōu)化機器無關(guān)的代碼優(yōu)化 后端后端 與目標(biāo)機有關(guān)的部分與目標(biāo)機有關(guān)的部