1、2020/7/25,編譯原理,1,編譯原理 Compiler Principles,授課教師：賀輝 619412,課程簡(jiǎn)介,教學(xué)方式：理論(40)+實(shí)驗(yàn)(14) 考核方式：期中考試(20%)+平時(shí)成績(jī)(30%) +期末考試（40）+平時(shí)考核（10%） 課程學(xué)分：3 答 疑： 勵(lì)耘樓A209 周一 5-6節(jié) 教材及參考書(shū)籍： 編譯原理（本科教學(xué)版） 趙建華等（譯），機(jī)械工業(yè)出版社 Compilers: Principles,Techniques, 編譯原理課程的學(xué)習(xí)有利于加深對(duì)程序語(yǔ)言的理解,可以幫助你更加快速的掌握新的語(yǔ)言工具; 課程中包含了很多軟件技術(shù),程序設(shè)計(jì)語(yǔ)言編譯程序構(gòu)造的基本原理和實(shí)

2、現(xiàn)方法是軟件的核心技術(shù)之一,這對(duì)于以后從事軟件設(shè)計(jì)是很有幫助的.,2020/7/25,編譯原理,4,為什么要學(xué)習(xí)編譯原理,與課程有關(guān)的問(wèn)題,先修課程： 編程語(yǔ)言、離散數(shù)學(xué)、匯編語(yǔ)言、數(shù)據(jù)結(jié)構(gòu) 、形式語(yǔ)言與自動(dòng)機(jī) 應(yīng)用 編譯器的設(shè)計(jì) 一般軟件的設(shè)計(jì) 文本編輯器、信息檢索系統(tǒng)、模式識(shí)別器 排版、繪圖等 本課程的基本要求 通過(guò)對(duì)本課程的學(xué)習(xí)，對(duì)形式語(yǔ)言有初步了解，并能對(duì)編譯程序的整個(gè)結(jié)構(gòu)有較清楚地了解，熟悉和掌握幾種主要編譯方法。 修養(yǎng)“問(wèn)題形式化描述計(jì)算機(jī)化” 的問(wèn)題求解過(guò)程,2020/7/25,編譯原理,5,實(shí)驗(yàn)要求,實(shí)驗(yàn)形式 分析、設(shè)計(jì)、編寫(xiě)、調(diào)試、測(cè)試程序 撰寫(xiě)實(shí)驗(yàn)報(bào)告 答辯 實(shí)驗(yàn)內(nèi)容 程序

3、設(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í),2020/7/25,6,學(xué)習(xí)中應(yīng)注意的問(wèn)題,一定要預(yù)習(xí)，每人都請(qǐng)準(zhǔn)備一個(gè)筆記本！ 認(rèn)真聽(tīng)課，積極思考，積極發(fā)言，認(rèn)真理解 重視習(xí)題：按時(shí)完成課堂作業(yè)及課堂的測(cè)試 在理解的基礎(chǔ)上記憶，把編譯的每個(gè)階段放到整個(gè)編譯程序背景中學(xué)習(xí) 理論結(jié)合實(shí)踐，重視實(shí)驗(yàn) 要敢于犯錯(cuò)誤 學(xué)習(xí)的一種方法，經(jīng)常還是唯一的方法，就在于首先犯錯(cuò)誤。我們?cè)趯W(xué)習(xí)，多數(shù)時(shí)間在通過(guò)犯錯(cuò)誤學(xué)習(xí)。 急功近利是學(xué)習(xí)的一大敵人！,2020/7/25,編譯原理,7,寄語(yǔ),要主動(dòng)學(xué)習(xí) 不要苛求課程、老師和環(huán)境，他/她/它們

4、只是資源 目標(biāo)確定后要善于利用各種資源 注重對(duì)自己能力的培養(yǎng) 學(xué)會(huì)做人,樂(lè)于助人,多為別人著想,可以獲取友誼 朋友是資源，可以終生受益 學(xué)會(huì)安排自己的時(shí)間 時(shí)間就像海綿里的水，只要肯擠，總會(huì)有的。貴在恒。 學(xué)會(huì)利用各種資源提高自己 學(xué)校的、家庭的、社會(huì)的 上學(xué)期間利用資源的唯一目的就是提高自己 不要沉迷于網(wǎng)絡(luò)聊天（微信 微博）與游戲,2020/7/25,8,各章節(jié)內(nèi)容安排,第一章引論 第二章高級(jí)語(yǔ)言及其語(yǔ)法描述 第三章詞法分析 第四章語(yǔ)法分析【自頂向下（遞歸下降語(yǔ)法分析、LL(1)）、自底向上（LR（1）】 第五章語(yǔ)義分析【語(yǔ)法制導(dǎo)的翻譯】 第六章中間代碼及目標(biāo)代碼生成,2020/7/25,編

5、譯原理,9,程序設(shè)計(jì)語(yǔ)言,機(jī)器語(yǔ)言： 能夠被計(jì)算機(jī)的硬件系統(tǒng)直接執(zhí)行的指令程序。 由二進(jìn)制(0、1序列)組成 難讀、難寫(xiě)、易出錯(cuò)。 匯編語(yǔ)言：用記憶符表示指令的操作碼。,面向機(jī)器語(yǔ)言（低級(jí)語(yǔ)言）,按機(jī)器指令的工作方式來(lái)思考問(wèn)題,assume cs:code, ds:data data segment dw 1234h,5678h data ends code segment start:mov ax, data mov ds, ax mov ax, ds:0 mov bx, ds:2 mov cx, 0 add cx, ax add cx, bx mov cx, ds:4 mov ax, 4c

6、00h int 21h code ends end start,程序設(shè)計(jì)語(yǔ)言,高級(jí)語(yǔ)言（面向人類(lèi)的語(yǔ)言）： 便于人類(lèi)的理解和使用 語(yǔ)言的結(jié)構(gòu)符合人的思維方式：如直接使用表達(dá)式進(jìn)行計(jì)算. 具有高抽象度：如 類(lèi) 等機(jī)制 強(qiáng)調(diào)邏輯過(guò)程，事情的前因后果，不僅是做什么，而且是怎么做？,int main int a,b,c; a=1234h; b=5678h; c=a+b; return 0; ,翻譯程序,機(jī)器只能理解和執(zhí)行機(jī)器語(yǔ)言高級(jí)語(yǔ)言需轉(zhuǎn)換成機(jī)器語(yǔ)言才能執(zhí)行如何轉(zhuǎn)換？ 翻譯 解釋 翻譯程序：是指能夠把某種語(yǔ)言的程序（源語(yǔ)言程序）轉(zhuǎn)換成另一種語(yǔ)言的程序（目標(biāo)語(yǔ)言程序），而后者與前者在邏輯上是等價(jià)的。

7、編譯程序：源語(yǔ)言程序?yàn)楦呒?jí)語(yǔ)言程序，目標(biāo)語(yǔ)言程序是低級(jí)語(yǔ)言程序的翻譯程序。 匯編程序：源語(yǔ)言程序?yàn)閰R編語(yǔ)言程序，目標(biāo)語(yǔ)言程序?yàn)闄C(jī)器語(yǔ)言程序的翻譯程序。,如何執(zhí)行一個(gè)源程序,先編譯后執(zhí)行-編譯程序編譯出目標(biāo)程序，系統(tǒng)執(zhí)行。,交叉編譯程序：宿主機(jī)和目標(biāo)機(jī)的指令系統(tǒng)不同,診斷編譯程序：側(cè)重于幫助程序開(kāi)發(fā)和調(diào)試 優(yōu)化編譯程序：著重于提高目標(biāo)代碼的效率 ,運(yùn)行編譯程序的計(jì)算機(jī),運(yùn)行產(chǎn)生的目標(biāo)代碼的計(jì)算機(jī),如何執(zhí)行一個(gè)源程序,邊解釋邊執(zhí)行-解釋程序邊解釋邊執(zhí)行源程序本身，不產(chǎn)生目標(biāo)程序。,什么是編譯程序,2020/7/25,編譯原理,15,編譯原理這門(mén)課程主要介紹設(shè)計(jì)和構(gòu)造編譯程序的基本原理和常用的技術(shù)和

8、方法。,本章重點(diǎn)介紹編譯程序的基本概念。,編譯的過(guò)程,編譯程序的結(jié)構(gòu),1.1 什么是編譯程序,2020/7/25,編譯原理,16,翻譯程序是指這樣一個(gè)程序,它把一種語(yǔ)言(稱(chēng)作源語(yǔ)言)所寫(xiě)的程序(源程序)翻譯成等價(jià)的另一種語(yǔ)言(稱(chēng)作目標(biāo)語(yǔ)言)的程序(目標(biāo)程序)。世界上第一個(gè)編譯程序FORTRAN是在20世紀(jì)50年代中期研制成功的?；ㄙM(fèi)了18年的時(shí)間。,高級(jí)語(yǔ)言程序,機(jī)器語(yǔ)言程序,翻譯程序,2020/7/25,編譯原理,17,編譯程序是一種翻譯程序，它將高級(jí)語(yǔ)言所寫(xiě)的源程序翻譯成等價(jià)的機(jī)器語(yǔ)言或匯編語(yǔ)言的目標(biāo)程序。,源程序,高級(jí)語(yǔ)言程序,編譯程序,目標(biāo)程序,匯編語(yǔ)言或者機(jī)器語(yǔ)言程序,(*.C /

9、*.PAS),(*.OBJ / *.EXE),2020/7/25,編譯原理,18,采用編譯方式在計(jì)算機(jī)上執(zhí)行用高級(jí)語(yǔ)言編寫(xiě)的程序，需分階段進(jìn)行。,第一種情況：,高級(jí)語(yǔ)言 程序,2020/7/25,編譯原理,19,第二種情況：,高級(jí)語(yǔ)言 程序,1.2 編譯程序的基本結(jié)構(gòu),2020/7/25,編譯原理,20,例：將英文句子 “I wish you success ”翻譯成中文句子的大致過(guò)程是：,詞法分析,語(yǔ)法分析,語(yǔ)義分析,修飾工作,翻譯成文,2020/7/25,編譯原理,21,編譯程序是將一種語(yǔ)言形式翻譯成另一種語(yǔ)言形式，因此，其工作過(guò)程一般可劃分為如下五個(gè)階段：,詞法分析,語(yǔ)法分析,語(yǔ)義分析和

10、中間代碼生成,代碼優(yōu)化,目標(biāo)代碼生成,2020/7/25,編譯原理,22,float r，h，s； s = 2*3.1416 * r *(rh);,例如 計(jì)算圓柱體表面積的程序 片斷如下：,a. 詞法分析,2020/7/25,編譯原理,23,詞法分析階段的任務(wù)是對(duì)構(gòu)成源程序的字符串從左到右進(jìn)行掃描和分解，根據(jù)語(yǔ)言的詞法規(guī)則，識(shí)別出一個(gè)一個(gè)具有獨(dú)立意義的單詞( 也稱(chēng)單詞符號(hào), 簡(jiǎn)稱(chēng)符號(hào) )。,2020/7/25,編譯原理,24,詞法規(guī)則是單詞符號(hào)的形成規(guī)則,它規(guī)定了哪樣的字符串構(gòu)成一個(gè)單詞符號(hào)。,float r，h，s； s = 2*3.1416*r*(hr);,例如,2020/7/25,編譯原

11、理,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);,2020/7/25,26,練一練,sum=(10+20)*(num+square); 詞法分析結(jié)果？,結(jié)果 (標(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)，; )

12、,b. 語(yǔ)法分析,2020/7/25,編譯原理,27,語(yǔ)法分析的任務(wù)是在詞法分析的基 礎(chǔ)上, 根據(jù)語(yǔ)言的語(yǔ)法規(guī)則從單詞符 號(hào)串中識(shí)別出各種語(yǔ)法單位 ( 如表 達(dá)式、說(shuō)明、語(yǔ)句等 ) ,并進(jìn)行語(yǔ)法 檢查,即檢查各種語(yǔ)法單位在語(yǔ)法結(jié) 構(gòu)上的正確性。,2020/7/25,編譯原理,28,語(yǔ)言的語(yǔ)法規(guī)則規(guī)定了如何從單詞符號(hào)形成語(yǔ)法單位，語(yǔ)法規(guī)則是語(yǔ)法單位的形成規(guī)則。,float r，h，s； s = 2*3.1416*r*(hr);,例如,2020/7/25,編譯原理,29,單詞符號(hào)串 s=2*3.1416 * r *(hr)中，“s” 是，單詞符號(hào)串 “2 * 3.1416 * r *(hr)” 組

13、合成這樣的語(yǔ)法單位 , 由=構(gòu)成這樣的語(yǔ)法單位。,2020/7/25,30,語(yǔ)法分析,sum=(10+20)*(num+square);,語(yǔ)法樹(shù),c. 語(yǔ)義分析和中間代碼生成,2020/7/25,編譯原理,31,語(yǔ)義分析的任務(wù)是首先對(duì)每種語(yǔ)法單位進(jìn)行靜態(tài)的語(yǔ)義審查，然后分析其含義，并用另一種語(yǔ)言形式 (比源語(yǔ)言更接近于目標(biāo)語(yǔ)言的一種中間代碼或直接用目標(biāo)語(yǔ)言 ) 來(lái)描述這種語(yǔ)義。,例如：,2020/7/25,編譯原理,32,將s = 2*3.1416 * r *(hr)翻譯成如下形式的四元式中間代碼：,(1) ( *, 2, 3.1416, T1 ),(2) ( *, T1, r, T2 ),(

14、3) ( +, h, r, T3 ),(4) ( *, T2, T3, T4 ),(5) ( =, T4, _, s ),2020/7/25,編譯原理,33,再例如：中間代碼生成：,如：position：initialrate60 生成四元式序列： （inttoreal 60 t1 ） （ id3 t1 t2） （ id2 t2 t3） （： t3 id1）,運(yùn)算符,運(yùn)算對(duì)象1,運(yùn)算對(duì)象2,結(jié)果,id1,id2,id3,t1，t2，t3是臨時(shí)變量,2020/7/25,34,練一練,sum=(10+20)*(num+square); 中間代碼(intermediate Code)？,四元式表示

15、(三地址碼) (+，10，20，T1) (+，num，square，T2) (*， T1， T2， T3) (=， T3 ， ， sum),三元式表示 (+，10，20) (+，num，square) (*，) (=， sum，),語(yǔ)法樹(shù),d. 代碼優(yōu)化,2020/7/25,編譯原理,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) ( +, h, r, T3 ),(3) ( *, T2, T3, T4 )

16、,(4) ( =, T4, _, s ),2020/7/25,編譯原理,36,例如： position：initialrate60 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.目標(biāo)代碼生成,2020/7/25,編譯原理,37,主要任務(wù)：將中間代碼變換成特定機(jī)器上的絕對(duì)指令代碼或可重定位的匯編指令代碼。主要與硬件系統(tǒng)結(jié)構(gòu)和指令含義有關(guān)

17、。,(*id360.0 t1) (+id2t1 id1),MOVid3,R2 MUL #60.0,R2 MOVid2,R1 ADDR2,R1 MOVR1,id1,2020/7/25,編譯原理,38,記號(hào)：token,語(yǔ)法樹(shù)：syntax tree,：symbol table,注釋樹(shù),2020/7/25,39,編譯程序總體結(jié)構(gòu),目標(biāo)代碼生成器,代碼優(yōu)化器,語(yǔ)義分析與中間代碼生成器,語(yǔ)法分析器,目標(biāo)代碼,表格與表格管理,作用： 登記源程序的各類(lèi)信息和編譯各階段的進(jìn)展情況。 最重要的是符號(hào)表，它用來(lái)登記源程序中出現(xiàn)的每一個(gè)名字以及名字的各種屬性（類(lèi)型、作用域、分配存儲(chǔ)信息等）,如：Const1常量

18、值：35 Var1變量 類(lèi)型：實(shí) 層次：2,出錯(cuò)處理,錯(cuò)誤可發(fā)生在編譯的各個(gè)階段，錯(cuò)誤處理也是貫穿編譯全過(guò)程。 編譯程序應(yīng)設(shè)法發(fā)現(xiàn)源程序的錯(cuò)誤，把有關(guān)錯(cuò)誤報(bào)告給用戶(hù)。這部分的工作是由專(zhuān)門(mén)的一組程序（叫做出錯(cuò)處理程序）完成的。 錯(cuò)誤的類(lèi)型： 語(yǔ)法錯(cuò)誤：指源程序中不合語(yǔ)法（或詞法）規(guī)則的錯(cuò)誤。如：非法字符。 語(yǔ)義錯(cuò)誤：指不合語(yǔ)義規(guī)則的錯(cuò)誤，如：說(shuō)明錯(cuò)誤、作用域錯(cuò)誤、類(lèi)型不一致等。有些在語(yǔ)義分析時(shí)檢測(cè)出來(lái)，有些要在運(yùn)行的時(shí)候才能檢測(cè)出來(lái),遍(Pass),遍： 對(duì)源程序(或其中間形式)從頭至尾掃描一次并進(jìn)行有關(guān)加工處理，生成新的中間形式或最終目標(biāo)程序，稱(chēng)為一遍。 即可將幾個(gè)不同階段合為一遍，也可以把各個(gè)階段的工作分成若干遍。 分遍的原則： 目標(biāo)質(zhì)量高低，機(jī)器內(nèi)存大小，源語(yǔ)言簡(jiǎn)繁等。,編譯前端與后端,從概念上劃分： 編譯程序可分為編譯前端和編譯后端。 編譯前端：指與源語(yǔ)言有關(guān)但與目標(biāo)機(jī)無(wú)關(guān)的編譯程序部分。包括詞法分析、語(yǔ)法分析、語(yǔ)義分析、中間代碼產(chǎn)生和部分優(yōu)化。 編譯后端：指與目標(biāo)機(jī)有關(guān)的編譯