編譯原理(第1章)

1、2022-2-1編 譯 原 理1授課教師：賀輝授課教師：賀輝 619412課程簡介教學(xué)方式：教學(xué)方式：理論理論(40)+(40)+實驗實驗(14)(14)考核方式：考核方式：期中考試期中考試(20%)+(20%)+平時成績平時成績(30%)(30%) + +期末考試（期末考試（4040）+ +平時平時考核（考核（10%10%）課程學(xué)分：課程學(xué)分：3 3答答 疑：疑： 勵耘樓勵耘樓A209 A209 周一周一 5-65-6節(jié)節(jié)教材及參考書籍：教材及參考書籍：編譯原理編譯原理（本科教學(xué)版）（本科教學(xué)版） 趙建華等（譯），機械趙建華等（譯），機械工業(yè)出版社工業(yè)出版社Compilers: Princi

2、ples,Techniques,&Tools (編譯原理 技術(shù)與工具) ，Aho，A.V. ，機械工業(yè)出版社 Compiler Construction Principle and Pratice ( 編譯原理及實踐 )， Kenneth C.Louden ， 機械工業(yè)出版社為什么要學(xué)習(xí)編譯原理編譯程序構(gòu)造是計算機學(xué)科中一個非常成功的分支，也是最早獲得成功的分支；編譯原理蘊涵著計算機學(xué)科中解決問題的思路、抽象問題和解決問題的方法; ;編譯原理課程的學(xué)習(xí)有利于加深對程序語言的理解, ,可以幫助你更加快速的掌握新的語言工具; ;課程中包含了很多軟件技術(shù), ,程序設(shè)計語言編譯程序構(gòu)造的基本原

3、理和實現(xiàn)方法是軟件的核心技術(shù)之一,這對于以后從事軟件設(shè)計是很有幫助的. .2022-2-1編 譯 原 理4為什么要學(xué)習(xí)編譯原理為什么要學(xué)習(xí)編譯原理與課程有關(guān)的問題u 先修課程：先修課程：u編程語言、離散數(shù)學(xué)、匯編語言、數(shù)據(jù)結(jié)構(gòu)編程語言、離散數(shù)學(xué)、匯編語言、數(shù)據(jù)結(jié)構(gòu) 、形式語言與、形式語言與自自動機動機u 應(yīng)用應(yīng)用p編譯器的設(shè)計編譯器的設(shè)計p一般軟件的設(shè)計一般軟件的設(shè)計a)a) 文本編輯器、信息檢索系統(tǒng)、模式識別器文本編輯器、信息檢索系統(tǒng)、模式識別器b)b) 排版、繪圖等排版、繪圖等p 本本課程的基本要求課程的基本要求 通過對本課程的學(xué)習(xí)，對形式語言有初步了解，并能對編譯通過對本課程的學(xué)習(xí)，對形

4、式語言有初步了解，并能對編譯程序的整個結(jié)構(gòu)有較清楚地了解，熟悉和掌握幾種主要編譯程序的整個結(jié)構(gòu)有較清楚地了解，熟悉和掌握幾種主要編譯方法方法。 修養(yǎng)修養(yǎng)“問題問題形式化描述形式化描述計算機化計算機化” 的問題求解過程的問題求解過程 2022-2-1編 譯 原 理5實驗要求實驗形式實驗形式分析、設(shè)計、編寫、調(diào)試、測試程序撰寫實驗報告答辯實驗內(nèi)容實驗內(nèi)容程序設(shè)計復(fù)習(xí) 2學(xué)時編碼完成掃描程序（詞法分析）2學(xué)時語法分析器的設(shè)計與實現(xiàn) 4學(xué)時使用Lex自動生成一個編譯器 6學(xué)時2022-2-16學(xué)習(xí)中應(yīng)注意的問題l 一定要預(yù)習(xí)，一定要預(yù)習(xí)，每人都請準(zhǔn)備一個筆記本！每人都請準(zhǔn)備一個筆記本！l 認(rèn)真認(rèn)真聽課

5、，積極思考，積極發(fā)言，認(rèn)真聽課，積極思考，積極發(fā)言，認(rèn)真理解理解l 重視習(xí)題：按時完成重視習(xí)題：按時完成課堂作業(yè)及課堂的課堂作業(yè)及課堂的測試測試l 在在理解的基礎(chǔ)上理解的基礎(chǔ)上記憶，記憶，把把編譯的每個階段放到整編譯的每個階段放到整個編譯程序背景中個編譯程序背景中學(xué)習(xí)學(xué)習(xí)l 理論結(jié)合理論結(jié)合實踐，實踐，重視重視實驗實驗要敢于犯錯誤要敢于犯錯誤學(xué)習(xí)的一種方法，經(jīng)常還是唯一的方法，就在于首學(xué)習(xí)的一種方法，經(jīng)常還是唯一的方法，就在于首先犯錯誤。我們在學(xué)習(xí)，多數(shù)時間在通過犯錯誤先犯錯誤。我們在學(xué)習(xí)，多數(shù)時間在通過犯錯誤學(xué)習(xí)。學(xué)習(xí)。急功近利急功近利是學(xué)習(xí)的一大敵人！是學(xué)習(xí)的一大敵人！ 2022-2-1編

6、 譯 原 理7寄語要主動學(xué)習(xí)要主動學(xué)習(xí)不要苛求課程、老師和環(huán)境，他/她/它們只是資源目標(biāo)確定后要善于利用各種資源注重對自己能力的培養(yǎng)注重對自己能力的培養(yǎng)學(xué)會學(xué)會做人做人,樂于助人樂于助人,多為別人著想多為別人著想,可以獲取友誼可以獲取友誼朋友是資源，可以終生受益學(xué)會安排自己的時間學(xué)會安排自己的時間時間就像海綿里的水，只要肯擠，總會有的。貴在恒。學(xué)會利用各種資源學(xué)會利用各種資源提高自己提高自己學(xué)校的、家庭的、社會的上學(xué)期間利用資源的唯一目的就是提高自己不要沉迷于網(wǎng)絡(luò)聊天（微信不要沉迷于網(wǎng)絡(luò)聊天（微信 微博微博）與游戲）與游戲2022-2-18各章節(jié)內(nèi)容安排第一章引論第一章引論第二章高級語言及其語

7、法描述第二章高級語言及其語法描述第三章詞法分析第三章詞法分析第四章語法分析第四章語法分析【自頂向下（遞歸自頂向下（遞歸下降語法分析、下降語法分析、LL(1)LL(1)）、自底向上）、自底向上（LRLR（1 1）】第五章語義分析第五章語義分析【語法制導(dǎo)的翻譯語法制導(dǎo)的翻譯】第六章中間代碼及目標(biāo)代碼生成第六章中間代碼及目標(biāo)代碼生成2022-2-1編 譯 原 理9程序設(shè)計語言機器語言：機器語言：能夠被計算機的硬件系統(tǒng)直接執(zhí)行的指令程序。由二進制(0、1序列)組成難讀、難寫、易出錯。匯編語言：匯編語言：用用記憶符記憶符表示指令的操作碼。表示指令的操作碼。面向機器語面向機器語言（低級語言（低級語言）言）

8、按機器指令的工作方式來思考問題按機器指令的工作方式來思考問題assume cs:code, ds:datadata segmentdw 1234h,5678hdata endscode segmentstart:mov ax, datamov ds, ax mov ax, ds:0mov bx, ds:2mov cx, 0add cx, axadd cx, bxmov cx, ds:4mov ax, 4c00hint 21h code endsend start 程序設(shè)計語言高級語言（面向人類的語言）：高級語言（面向人類的語言）：便于人類的理解和使用語言的結(jié)構(gòu)符合人的思維方式：如直接使用表達式

9、進行計算.具有高抽象度：如 類 等機制強調(diào)邏輯過程，事情的前因后果，不僅是做什么，而且是怎么做？int mainint a,b,c;a=1234h;b=5678h;c=a+b;return 0; 翻譯程序機器只能理解和執(zhí)行機器語言高級語言需轉(zhuǎn)換成機器機器只能理解和執(zhí)行機器語言高級語言需轉(zhuǎn)換成機器語言才能執(zhí)行如何轉(zhuǎn)換？語言才能執(zhí)行如何轉(zhuǎn)換？翻譯解釋翻譯程序：翻譯程序：是指能夠把某種語言的程序是指能夠把某種語言的程序（源語言程序）（源語言程序）轉(zhuǎn)換成另一種語言的程序轉(zhuǎn)換成另一種語言的程序（目標(biāo)語言程序），（目標(biāo)語言程序），而后者而后者與前者在邏輯上是等價的。與前者在邏輯上是等價的。編譯程序：編譯程

10、序：源語言程序為高級語言程序，目標(biāo)語言程序源語言程序為高級語言程序，目標(biāo)語言程序是低級語言程序的翻譯程序。是低級語言程序的翻譯程序。匯編程序：匯編程序：源語言程序為匯編語言程序，目標(biāo)語言程序源語言程序為匯編語言程序，目標(biāo)語言程序為機器語言程序的翻譯程序。為機器語言程序的翻譯程序。如何執(zhí)行一個源程序先編譯后執(zhí)行先編譯后執(zhí)行-編譯程序編譯程序編譯出目標(biāo)程序，編譯出目標(biāo)程序，系統(tǒng)執(zhí)行。系統(tǒng)執(zhí)行。目標(biāo)機目標(biāo)機宿主機宿主機編譯程序編譯程序運行系統(tǒng)運行系統(tǒng)目標(biāo)程序目標(biāo)程序P輸入數(shù)據(jù)輸入數(shù)據(jù)計算結(jié)果計算結(jié)果源程序源程序P交叉編譯程序：交叉編譯程序：宿主機和目標(biāo)機的指令系統(tǒng)不同宿主機和目標(biāo)機的指令系統(tǒng)不同診斷

11、編譯程序診斷編譯程序：側(cè)重于幫助程序開發(fā)和調(diào)試側(cè)重于幫助程序開發(fā)和調(diào)試優(yōu)化編譯程序：優(yōu)化編譯程序：著重于提高目標(biāo)代碼的效率著重于提高目標(biāo)代碼的效率運行編譯程序的計算機運行編譯程序的計算機運行產(chǎn)生的目標(biāo)代碼的計算機運行產(chǎn)生的目標(biāo)代碼的計算機如何執(zhí)行一個源程序邊解釋邊執(zhí)行邊解釋邊執(zhí)行-解釋程序解釋程序邊解釋邊執(zhí)邊解釋邊執(zhí)行源程序本身，不產(chǎn)生目標(biāo)程序。行源程序本身，不產(chǎn)生目標(biāo)程序。解釋程序解釋程序源程序源程序輸入數(shù)據(jù)輸入數(shù)據(jù)計算結(jié)果計算結(jié)果什么是編譯程序什么是編譯程序2022-2-1編 譯 原 理15 編譯原理這門課程主要介紹設(shè)計和構(gòu)造編譯程序的基本原理和常用的技術(shù)和方法。本章重點介紹編譯程序的基本

12、概念。1.1 什么是編譯程序2022-2-1編 譯 原 理16 翻譯程序翻譯程序是指這樣一個程序,它把一種語言(稱作源語言)所寫的程序(源程序)翻譯成等價的另一種語言(稱作目標(biāo)語言)的程序(目標(biāo)程序)。世界上世界上第一個編譯程序第一個編譯程序FORTRANFORTRAN是在是在2020世紀(jì)世紀(jì)5050年代中期研制成功的?；ㄙM了年代中期研制成功的?；ㄙM了1818年的年的時間。時間。 高級語言程序機器語言程序翻譯程序2022-2-1編 譯 原 理17 編譯程序編譯程序是一種翻譯程序，它將高級語言所寫的源程序翻譯成等價的機器語言或匯編語言的目標(biāo)程序。 源程序高級語言程序編譯程序目標(biāo)程序匯編語言或者機

13、器語言程序(*.C / *.PAS)(*.OBJ / *.EXE)2022-2-1編 譯 原 理18 采用編譯方式在計算機上執(zhí)行用高級語言編寫的程序，需分階段進行。第一種情況：第一種情況：源程序編譯程序機器語言目標(biāo)程序初始數(shù)據(jù)運行系統(tǒng)結(jié)果編 譯 階 段運 行 階 段高級語言 程序2022-2-1編 譯 原 理19第二種情況第二種情況：源程序編譯程序機器語言目標(biāo)程序初始數(shù)據(jù)運行系統(tǒng)結(jié)果編 譯 階 段運行階段匯編程序匯編語言目標(biāo)程序匯 編 階 段高級語言 程序1.2 編譯程序的基本結(jié)構(gòu) 2022-2-1編 譯 原 理20例例：將英文句子 “I wish you success ”翻譯成中文句子的大

14、致過程是：q 詞法分析q 語法分析q 語義分析q 修飾工作q 翻譯成文 2022-2-1編 譯 原 理21 編譯程序是將一種語言形式翻譯成另一種語言形式，因此，其工作過程一般可劃分為如下五個階段： q 詞法分析 q 語法分析 q 語義分析和中間代碼生成 q 代碼優(yōu)化 q 目標(biāo)代碼生成2022-2-1編 譯 原 理22 float r，h，s； s = 2*3.1416 * r *(rh);例如 計算圓柱體表面積的程序 片斷如下：A. 詞法分析2022-2-1編 譯 原 理23 詞法分析階段的任務(wù)是對構(gòu)成源程序的字符串字符串從左到右進行掃描和分解，根據(jù)語言的詞法規(guī)則詞法規(guī)則，識別出一個一個具有獨

15、立意義的單詞單詞( 也稱單詞符號單詞符號, 簡稱符號 )。2022-2-1編 譯 原 理24 詞法規(guī)則詞法規(guī)則是單詞符號的形成規(guī)則,它規(guī)定了哪樣的字符串構(gòu)成一個單詞符號。 float r，h，s； s = 2*3.1416*r*(hr);例如2022-2-1編 譯 原 理25 上述源程序通過詞法分析識別出如下單詞符號： 關(guān)鍵字 float 標(biāo)識符 r、h、s 常數(shù) 3.1416、2 算符 * 、 界符 （、 ）、 ；、 ，、= float r，h，s； s = 2*3.1416*r*(hr);2022-2-126練一練sum=(10+20)*(num+square);詞法分析結(jié)果？ 結(jié)果結(jié)果(

16、標(biāo)識符，sum)(賦值號，=)(左括號， ( )(整常數(shù)，10)(加號，+ )(整常數(shù)，20)(右括號， ) )(乘號，* )(左括號， ( )(標(biāo)識符，num)(加號，+ )(標(biāo)識符，square)(右括號， ) )(分號，; ) B. 語法分析2022-2-1編 譯 原 理27 語法分析的任務(wù)是在詞法分析的基 礎(chǔ)上, 根據(jù)語言的語法規(guī)則語法規(guī)則從單詞符單詞符 號串號串中識別出各種語法單位語法單位 ( 如表 達式、說明、語句等 ) ,并進行語法語法 檢查檢查,即檢查各種語法單位在語法結(jié) 構(gòu)上的正確性。 2022-2-1編 譯 原 理28 語言的語法規(guī)則語法規(guī)則規(guī)定了如何從單詞符號形成語法單位

17、，語法規(guī)則語法規(guī)則是語法單位的形成規(guī)則。 float r，h，s； s = 2*3.1416*r*(hr);例如2022-2-1編 譯 原 理29 單詞符號串 s=2*3.1416 * r *(hr)中，“s” 是，單詞符號串 “2 * * 3.1416 * * r * *(hr)”組合成組合成這樣的語法單位這樣的語法單位 , 由=構(gòu)成這樣的語法單位。2022-2-130語法分析語法分析sum=(10+20)*(num+square);語語法法樹樹 C. 語義分析和中間代碼生成2022-2-1編 譯 原 理31 語義分析語義分析的任務(wù)是首先對每種語法單位進行靜態(tài)的語義審查，然后分析其含義，并用

18、另一種語言形式 (比源語言更接近于目標(biāo)語言的一種中間代碼或直接用目標(biāo)語言 ) 來描述這種語義。 例如：2022-2-1編 譯 原 理32 將s = 2*3.1416 * r *(hr)翻譯成如下形式的四元式四元式中間代碼：(1) ( *, 2, 3.1416, T1 ) (2) ( *, T1, r, T2 )(3) ( +, h, r, T3 )(4) ( *, T2, T3, T4 )(5) ( =, T4, _, s )2022-2-1編 譯 原 理33運算符運算對象1運算對象2結(jié)果id1id2id3t1，t2，t3是臨時變量2022-2-134練一練sum=(10+20)*(num+s

19、quare); 中間代碼中間代碼(intermediate Code)？(三地址碼三地址碼)(+，10，20，T1)(+，num，square，T2)(*， T1， T2， T3)(=， T3 ， ， sum) (+，10，20)(+，num，square)(*，)(=， sum，) D. 代碼優(yōu)化2022-2-1編 譯 原 理35 代碼優(yōu)化的任務(wù)是對前階段產(chǎn)生的中間代碼進行等價變換，以期獲得更為高效即 省 時 間 和 空 間 的 目 標(biāo) 代 碼 。將s = 2*3.1416 * r *(hr)翻譯成如下形式的四元式經(jīng)局部優(yōu)化后得： (1) ( *, 6.28, r, T2 )(2) ( +,

20、 h, r, T3 )(3) ( *, T2, T3, T4 )(4) ( =, T4, _, s )2022-2-1編 譯 原 理36例如：id1:= id2 + id3 * 60(1) (inttoreal 60 - t1 )(2) (* id3 t1 t2 )(3) (+ id2 t2 t3 )(4) (:= t3 - id1)四元式經(jīng)局部優(yōu)化后得：（1） ( * id3 60.0 t1 )（2）（ + id2 t1 id1) E. E.目標(biāo)代碼生成 2022-2-1編 譯 原 理37主要任務(wù)：將中間代碼變換成特定機器上的絕對指令代碼或可重定位的匯編指令代碼。主要與硬件系統(tǒng)結(jié)構(gòu)和指令含義

21、有關(guān)。(*id3 60.0 t1)(+id2 t1 id1)MOVid3,R2MUL #60.0,R2 MOVid2,R1ADDR2,R1MOVR1,id12022-2-1編 譯 原 理38記號：記號：token語法樹：語法樹：syntax tree：symbol table注釋樹注釋樹2022-2-139編譯程序總體結(jié)構(gòu)表格與表格管理作用：作用： 登記登記源程序的各類信息源程序的各類信息和和編譯各階編譯各階段的進展情況段的進展情況。 最重要的是最重要的是符號表，符號表，它用來登記源它用來登記源程序中出現(xiàn)的每一個名字以及名字的各種屬性程序中出現(xiàn)的每一個名字以及名字的各種屬性（類型、作用域、分配存儲信息等）（類型、作用域、分配存儲信息等）如：Const1常量 值：35Var1變量 類型：實 層次：2出錯處理錯誤可發(fā)生在編譯的各個階段，錯誤處理也是錯誤可發(fā)生在編譯的各個階段，錯誤處理也是貫穿編譯全過程。貫穿編譯全過程。編譯程序應(yīng)