編譯原理(第1章)

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

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

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

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

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

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

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

8、按機(jī)器指令的工作方式來(lái)思考問(wèn)題按機(jī)器指令的工作方式來(lái)思考問(wèn)題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è)計(jì)語(yǔ)言高級(jí)語(yǔ)言（面向人類(lèi)的語(yǔ)言）：高級(jí)語(yǔ)言（面向人類(lèi)的語(yǔ)言）：便于人類(lèi)的理解和使用語(yǔ)言的結(jié)構(gòu)符合人的思維方式：如直接使用表達(dá)式

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

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

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

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

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

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

15、立意義的單詞單詞( 也稱(chēng)單詞符號(hào)單詞符號(hào), 簡(jiǎn)稱(chēng)符號(hào) )。2022-2-1編 譯 原 理24 詞法規(guī)則詞法規(guī)則是單詞符號(hào)的形成規(guī)則,它規(guī)定了哪樣的字符串構(gòu)成一個(gè)單詞符號(hào)。 float r，h，s； s = 2*3.1416*r*(hr);例如2022-2-1編 譯 原 理25 上述源程序通過(guò)詞法分析識(shí)別出如下單詞符號(hào)： 關(guān)鍵字 float 標(biāo)識(shí)符 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)識(shí)符，sum)(賦值號(hào)，=)(左括號(hào)， ( )(整常數(shù)，10)(加號(hào)，+ )(整常數(shù)，20)(右括號(hào)， ) )(乘號(hào)，* )(左括號(hào)， ( )(標(biāo)識(shí)符，num)(加號(hào)，+ )(標(biāo)識(shí)符，square)(右括號(hào)， ) )(分號(hào)，; ) B. 語(yǔ)法分析2022-2-1編 譯 原 理27 語(yǔ)法分析的任務(wù)是在詞法分析的基 礎(chǔ)上, 根據(jù)語(yǔ)言的語(yǔ)法規(guī)則語(yǔ)法規(guī)則從單詞符單詞符 號(hào)串號(hào)串中識(shí)別出各種語(yǔ)法單位語(yǔ)法單位 ( 如表 達(dá)式、說(shuō)明、語(yǔ)句等 ) ,并進(jìn)行語(yǔ)法語(yǔ)法 檢查檢查,即檢查各種語(yǔ)法單位在語(yǔ)法結(jié) 構(gòu)上的正確性。 2022-2-1編 譯 原 理28 語(yǔ)言的語(yǔ)法規(guī)則語(yǔ)法規(guī)則規(guī)定了如何從單詞符號(hào)形成語(yǔ)法單位

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

18、另一種語(yǔ)言形式 (比源語(yǔ)言更接近于目標(biāo)語(yǔ)言的一種中間代碼或直接用目標(biāo)語(yǔ)言 ) 來(lái)描述這種語(yǔ)義。 例如：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運(yùn)算符運(yùn)算對(duì)象1運(yùn)算對(duì)象2結(jié)果id1id2id3t1，t2，t3是臨時(shí)變量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ù)是對(duì)前階段產(chǎn)生的中間代碼進(jìn)行等價(jià)變換，以期獲得更為高效即 省 時(shí) 間 和 空 間 的 目 標(biāo) 代 碼 。將s = 2*3.1416 * r *(hr)翻譯成如下形式的四元式經(jīng)局部?jī)?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)局部?jī)?yōu)化后得：（1） ( * id3 60.0 t1 )（2）（ + id2 t1 id1) E. E.目標(biāo)代碼生成 2022-2-1編 譯 原 理37主要任務(wù)：將中間代碼變換成特定機(jī)器上的絕對(duì)指令代碼或可重定位的匯編指令代碼。主要與硬件系統(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記號(hào)：記號(hào)：token語(yǔ)法樹(shù)：語(yǔ)法樹(shù)：syntax tree：symbol table注釋樹(shù)注釋樹(shù)2022-2-139編譯程序總體結(jié)構(gòu)表格與表格管理作用：作用： 登記登記源程序的各類(lèi)信息源程序的各類(lèi)信息和和編譯各階編譯各階段的進(jìn)展情況段的進(jìn)展情況。 最重要的是最重要的是符號(hào)表，符號(hào)表，它用來(lái)登記源它用來(lái)登記源程序中出現(xiàn)的每一個(gè)名字以及名字的各種屬性程序中出現(xiàn)的每一個(gè)名字以及名字的各種屬性（類(lèi)型、作用域、分配存儲(chǔ)信息等）（類(lèi)型、作用域、分配存儲(chǔ)信息等）如：Const1常量 值：35Var1變量 類(lèi)型：實(shí) 層次：2出錯(cuò)處理錯(cuò)誤可發(fā)生在編譯的各個(gè)階段，錯(cuò)誤處理也是錯(cuò)誤可發(fā)生在編譯的各個(gè)階段，錯(cuò)誤處理也是貫穿編譯全過(guò)程。貫穿編譯全過(guò)程。編譯程序應(yīng)