編譯原理ppt40099164

1、編譯原理 Compiler Principles 彭彭 源源Email: 課件下載：課件下載： 密碼：密碼：bianyi課程簡(jiǎn)介課程簡(jiǎn)介u 教學(xué)方式：教學(xué)方式：理論理論(40)+實(shí)驗(yàn)實(shí)驗(yàn)(11)u 考核方式：考核方式：考試考試(70%)+平時(shí)成績(jī)平時(shí)成績(jī)(30%)u 課程學(xué)分：課程學(xué)分：3u 答疑答疑: 每周一中午每周一中午 信息安全實(shí)驗(yàn)室信息安全實(shí)驗(yàn)室u 參考書(shū)籍：參考書(shū)籍：p編譯原理編譯原理呂映芝等，清華大學(xué)出版社呂映芝等，清華大學(xué)出版社p Compiler Construction Principle and Pratice ( 編編譯原理及實(shí)踐譯原理及實(shí)踐 )， Kenneth C.L

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

3、這對(duì)于以后從事軟件設(shè)計(jì)是很有幫助的.課程要求課程要求u 上課認(rèn)真聽(tīng)講上課認(rèn)真聽(tīng)講 , 課后鞏固課后鞏固u 思想上重視思想上重視u 認(rèn)真完成作業(yè)認(rèn)真完成作業(yè) , 保證學(xué)習(xí)時(shí)間保證學(xué)習(xí)時(shí)間第 一章 引 論本章學(xué)習(xí)內(nèi)容本章學(xué)習(xí)內(nèi)容內(nèi)容：內(nèi)容： 什么是編譯程序什么是編譯程序編譯過(guò)程概述編譯過(guò)程概述編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu)編譯程序的構(gòu)造編譯程序的構(gòu)造要求：要求：p 理解編譯程序、解釋程序和遍的概念；理解編譯程序、解釋程序和遍的概念；p 掌握編譯過(guò)程各階段的任務(wù)和編譯程序邏輯結(jié)構(gòu)掌握編譯過(guò)程各階段的任務(wù)和編譯程序邏輯結(jié)構(gòu)及其各部分的基本功能。及其各部分的基本功能。程序設(shè)計(jì)語(yǔ)言程序設(shè)計(jì)語(yǔ)言u(píng) 機(jī)器語(yǔ)言：

4、機(jī)器語(yǔ)言：p 能夠被計(jì)算機(jī)的硬件系統(tǒng)直接執(zhí)行的指令能夠被計(jì)算機(jī)的硬件系統(tǒng)直接執(zhí)行的指令程序。程序。p 由由二進(jìn)制二進(jìn)制(0、1序列序列)組成組成p 難讀、難寫(xiě)、易出錯(cuò)。難讀、難寫(xiě)、易出錯(cuò)。u 匯編語(yǔ)言：匯編語(yǔ)言：用用記憶符記憶符表示指令的操作表示指令的操作碼。碼。面向機(jī)器語(yǔ)面向機(jī)器語(yǔ)言（低級(jí)語(yǔ)言（低級(jí)語(yǔ)言）言）按機(jī)器指令的工作方式來(lái)思考問(wèn)題按機(jī)器指令的工作方式來(lái)思考問(wèn)題程序設(shè)計(jì)語(yǔ)言程序設(shè)計(jì)語(yǔ)言u(píng) 高級(jí)語(yǔ)言（面向人類的語(yǔ)言）：高級(jí)語(yǔ)言（面向人類的語(yǔ)言）：p 便于人類的理解和使用便于人類的理解和使用p 語(yǔ)言的結(jié)構(gòu)符合人的思維方式：如直接使用表語(yǔ)言的結(jié)構(gòu)符合人的思維方式：如直接使用表達(dá)式進(jìn)行計(jì)算達(dá)式

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

6、。u 編譯程序：編譯程序：源語(yǔ)言程序?yàn)楦呒?jí)語(yǔ)言程序，目標(biāo)語(yǔ)言源語(yǔ)言程序?yàn)楦呒?jí)語(yǔ)言程序，目標(biāo)語(yǔ)言程序是低級(jí)語(yǔ)言程序的翻譯程序。程序是低級(jí)語(yǔ)言程序的翻譯程序。u 匯編程序：匯編程序：源語(yǔ)言程序?yàn)閰R編語(yǔ)言程序，目標(biāo)語(yǔ)言源語(yǔ)言程序?yàn)閰R編語(yǔ)言程序，目標(biāo)語(yǔ)言程序?yàn)闄C(jī)器語(yǔ)言程序的翻譯程序。程序?yàn)闄C(jī)器語(yǔ)言程序的翻譯程序。如何執(zhí)行一個(gè)源程序如何執(zhí)行一個(gè)源程序u 先編譯后執(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)

7、機(jī)的指令系統(tǒng)不同宿主機(jī)和目標(biāo)機(jī)的指令系統(tǒng)不同診斷編譯程序診斷編譯程序：側(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í)行一個(gè)源程序u 邊解釋邊執(zhí)行邊解釋邊執(zhí)行-解釋程序解釋程序邊解釋邊執(zhí)行源程邊解釋邊執(zhí)行源程序本身，不產(chǎn)生目標(biāo)程序。序本身，不產(chǎn)生目標(biāo)程序。解釋程序解釋程序源程序源程序輸入數(shù)據(jù)輸入數(shù)據(jù)計(jì)算結(jié)果計(jì)算結(jié)果編譯過(guò)程編譯的過(guò)程與自然語(yǔ)言間的翻譯過(guò)程有相似之處：編譯的過(guò)程與自然語(yǔ)言間的翻譯過(guò)程有相似之

8、處：1.識(shí)別出每個(gè)單詞（含義，性識(shí)別出每個(gè)單詞（含義，性質(zhì)等）質(zhì)等）2.分析語(yǔ)法結(jié)構(gòu)分析語(yǔ)法結(jié)構(gòu)3.初步翻譯句子的含義，得到初步翻譯句子的含義，得到草稿草稿4.譯文修飾譯文修飾5.寫(xiě)出最后譯文寫(xiě)出最后譯文1.詞法分析詞法分析2.語(yǔ)法分析語(yǔ)法分析3.語(yǔ)義分析中間代碼生成語(yǔ)義分析中間代碼生成4.優(yōu)化優(yōu)化5.目標(biāo)代碼生成目標(biāo)代碼生成英文翻譯成中文英文翻譯成中文編譯過(guò)程編譯過(guò)程詞法分析詞法分析(線性分析)u 輸入源程序，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，依據(jù)詞法規(guī)則(或構(gòu)詞規(guī)則)識(shí)別出一個(gè)個(gè)的單詞(基本字、標(biāo)識(shí)符、常數(shù)、運(yùn)算符、基本字、標(biāo)識(shí)符、常數(shù)、運(yùn)算符、界限符界限符) 。u 描述詞法規(guī)則的有效工

9、具是描述詞法規(guī)則的有效工具是正規(guī)式正規(guī)式和和有限自有限自動(dòng)機(jī)動(dòng)機(jī)例：源程序 for I:=1 to 100 do經(jīng)詞法分析被分析成一個(gè)個(gè)的單詞經(jīng)詞法分析被分析成一個(gè)個(gè)的單詞基本字for 標(biāo)識(shí)符I賦值符:=整常數(shù)1基本字to整常數(shù)100基本字do語(yǔ)法分析語(yǔ)法分析（層次分析）（層次分析）u 在詞法分析的基礎(chǔ)上，根據(jù)語(yǔ)言的在詞法分析的基礎(chǔ)上，根據(jù)語(yǔ)言的語(yǔ)法規(guī)則語(yǔ)法規(guī)則(文法規(guī)則）文法規(guī)則），把單詞符號(hào)組成各類，把單詞符號(hào)組成各類語(yǔ)法單位語(yǔ)法單位（語(yǔ)法范疇語(yǔ)法范疇），如），如“短語(yǔ)短語(yǔ)”、 “子句子句”、 “句子句子”、“程序段程序段” 、“程序程序” 等。等。u 通過(guò)語(yǔ)法分析，確定整個(gè)輸入串是否構(gòu)成

10、通過(guò)語(yǔ)法分析，確定整個(gè)輸入串是否構(gòu)成語(yǔ)語(yǔ)法上正確的法上正確的“程序程序”。position := initial + rate * 60 語(yǔ)法規(guī)則 “:=” “+” “*” “(”“)” 賦值語(yǔ)句標(biāo)識(shí)符表達(dá)式表達(dá)式+表達(dá)式表達(dá)式標(biāo)識(shí)符整數(shù)標(biāo)識(shí)符:=表達(dá)式*position:=initial+rate*60語(yǔ)法分析表達(dá)式表達(dá)式position:=initial+rate*60:=+N 60*id1 Positionid2 initialid3 rate語(yǔ)義分析語(yǔ)義分析u 對(duì)各種語(yǔ)法范疇進(jìn)行靜態(tài)語(yǔ)義檢查對(duì)各種語(yǔ)法范疇進(jìn)行靜態(tài)語(yǔ)義檢查p 上下文相關(guān)性上下文相關(guān)性p 類型匹配類型匹配p 類型轉(zhuǎn)換類型轉(zhuǎn)

11、換依據(jù)：語(yǔ)義規(guī)則。依據(jù)：語(yǔ)義規(guī)則。使用使用屬性文法屬性文法描述描述例:int p();double rate;position := initial + rate * 60 /* error */ /* error */ /* warning */ position := initial + rate * 6060:=+*Id1 positionId2 initialId3 rateInttoreal中間代碼生成中間代碼生成p 將源程序翻譯成中間代碼。將源程序翻譯成中間代碼。 所謂所謂“中間代碼中間代碼”是一種不依賴于機(jī)器，含是一種不依賴于機(jī)器，含義明確，便于處理的記號(hào)系統(tǒng)。如義明確，便于處理

12、的記號(hào)系統(tǒng)。如“四元式四元式”，其形式如下：其形式如下：算符算符左操作數(shù)左操作數(shù)右操作數(shù)右操作數(shù)結(jié)果結(jié)果id1:= id2 + id3 * 60(1) (inttoreal 60-t1)(2) (* id3t1t2)(3) (+ id2t2t3)(4) (:= t3-id1)60:=+*Id1 positionId2 initialId3 rateInttoreal中間代碼生成中間代碼生成例：例：Z=(X+0.418)*Y/W序號(hào)算符 左操作數(shù)右操作數(shù)結(jié)果(1)+X0.418T1(2)*T1YT2(3)/T2WZ 常用的中間代碼出了四元式外，還有三常用的中間代碼出了四元式外，還有三元式、間接三

13、元式和逆波蘭記號(hào)等等。元式、間接三元式和逆波蘭記號(hào)等等。1.2.4 優(yōu)化優(yōu)化任務(wù)：任務(wù)： 對(duì)前段產(chǎn)生的中間代碼進(jìn)行加工，以期對(duì)前段產(chǎn)生的中間代碼進(jìn)行加工，以期在最后階段產(chǎn)生更為高效（省在最后階段產(chǎn)生更為高效（省時(shí)間時(shí)間和和空間空間）的代碼的代碼依據(jù)：依據(jù)： 程序的程序的等價(jià)變換規(guī)則等價(jià)變換規(guī)則。其方法有：。其方法有：公共子表公共子表達(dá)式的提取達(dá)式的提取、循環(huán)優(yōu)化循環(huán)優(yōu)化、刪除無(wú)用代碼、并刪除無(wú)用代碼、并行化處理行化處理等。等。id1:= id2 + id3 * 60(1)(inttoreal60-t1)(2)( * id3 t1t2)(3)( +id2t2t3)(4)( :=t3-id1) 變

14、換變換 （1） ( *id360.0 t1) ( 2）（ + id2 t1id1)1.2.5 目標(biāo)代碼生成目標(biāo)代碼生成任務(wù)：任務(wù)： 把中間代碼（或經(jīng)優(yōu)化處理后）變換成把中間代碼（或經(jīng)優(yōu)化處理后）變換成特定機(jī)器上的特定機(jī)器上的低級(jí)語(yǔ)言代碼低級(jí)語(yǔ)言代碼（一般是（一般是機(jī)器機(jī)器代代碼或碼或匯編匯編代碼，稱為代碼，稱為目標(biāo)代碼目標(biāo)代碼）。它有賴于）。它有賴于硬件系統(tǒng)結(jié)構(gòu)和機(jī)器指令含義。硬件系統(tǒng)結(jié)構(gòu)和機(jī)器指令含義。目標(biāo)代碼的形式：目標(biāo)代碼的形式：p 絕對(duì)指令代碼絕對(duì)指令代碼-可以放在內(nèi)存的固定地方并且立可以放在內(nèi)存的固定地方并且立即執(zhí)行即執(zhí)行 p 可重定位的指令代碼可重定位的指令代碼-連接裝配程序連接各

15、目標(biāo)連接裝配程序連接各目標(biāo)模塊，確定程序變量在內(nèi)存中的位置，裝入內(nèi)存模塊，確定程序變量在內(nèi)存中的位置，裝入內(nèi)存中指定的起始地址，變成絕對(duì)指令代碼程序。中指定的起始地址，變成絕對(duì)指令代碼程序。p 匯編指令代碼匯編指令代碼-通過(guò)匯編器匯編后執(zhí)行通過(guò)匯編器匯編后執(zhí)行(*,id3 60.0 t1)(+,id2 t1id1 )movfid3, R2mulf #60.0, R2movfid2, R1addf R2, R1 movfR1, id1編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu)語(yǔ)義語(yǔ)義分析分析與中與中間代間代碼生碼生成器成器詞詞法法分分析析器器語(yǔ)語(yǔ)法法分分析析器器優(yōu)優(yōu)化化器器目目標(biāo)標(biāo)代代碼碼生生成成器器表格管理

16、錯(cuò)誤處理編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu)源程序源程序單詞符號(hào)單詞符號(hào)語(yǔ)法單位語(yǔ)法單位中間代碼中間代碼中間代碼中間代碼目標(biāo)代碼目標(biāo)代碼表格與表格管理表格與表格管理作用：作用： 登記登記源程序的各類信息源程序的各類信息和和編譯各階段的進(jìn)編譯各階段的進(jìn)展情況展情況。 最重要的是最重要的是符號(hào)表，符號(hào)表，它用來(lái)登記源程序中它用來(lái)登記源程序中出現(xiàn)的每一個(gè)名字以及名字的各種屬性（類出現(xiàn)的每一個(gè)名字以及名字的各種屬性（類型、作用域、分配存儲(chǔ)信息等）型、作用域、分配存儲(chǔ)信息等）如：Const1常量 值：35Var1變量 類型：實(shí) 層次：2出錯(cuò)處理出錯(cuò)處理u 錯(cuò)誤可發(fā)生在編譯的各個(gè)階段，錯(cuò)誤處理也是貫穿錯(cuò)誤可發(fā)生在

17、編譯的各個(gè)階段，錯(cuò)誤處理也是貫穿編譯全過(guò)程。編譯全過(guò)程。u 編譯程序應(yīng)設(shè)法發(fā)現(xiàn)源程序的錯(cuò)誤，把有關(guān)錯(cuò)誤報(bào)編譯程序應(yīng)設(shè)法發(fā)現(xiàn)源程序的錯(cuò)誤，把有關(guān)錯(cuò)誤報(bào)告給用戶。這部分的工作是由專門(mén)的一組程序（叫告給用戶。這部分的工作是由專門(mén)的一組程序（叫做做出錯(cuò)處理程序出錯(cuò)處理程序）完成的。）完成的。錯(cuò)誤的類型：錯(cuò)誤的類型：p語(yǔ)法錯(cuò)誤：語(yǔ)法錯(cuò)誤：指源程序中不合語(yǔ)法（或詞法）規(guī)則的錯(cuò)誤。指源程序中不合語(yǔ)法（或詞法）規(guī)則的錯(cuò)誤。如：非法字符。如：非法字符。p語(yǔ)義錯(cuò)誤：語(yǔ)義錯(cuò)誤：指不合語(yǔ)義規(guī)則的錯(cuò)誤，如：說(shuō)明錯(cuò)誤、作用指不合語(yǔ)義規(guī)則的錯(cuò)誤，如：說(shuō)明錯(cuò)誤、作用域錯(cuò)誤、類型不一致等。有些在語(yǔ)義分析時(shí)檢測(cè)出來(lái)，有域錯(cuò)誤、類

18、型不一致等。有些在語(yǔ)義分析時(shí)檢測(cè)出來(lái)，有些要在運(yùn)行的時(shí)候才能檢測(cè)出來(lái)些要在運(yùn)行的時(shí)候才能檢測(cè)出來(lái)遍遍(Pass)遍：遍：對(duì)源程序?qū)υ闯绦?或其中間形式或其中間形式)從頭至尾掃描一次并從頭至尾掃描一次并進(jìn)行有關(guān)加工處理，生成新的中間形式或最終目標(biāo)進(jìn)行有關(guān)加工處理，生成新的中間形式或最終目標(biāo)程序，稱為程序，稱為一遍一遍。 即可將幾個(gè)不同階段合為一遍，也可以把各個(gè)即可將幾個(gè)不同階段合為一遍，也可以把各個(gè)階段的工作分成若干遍。階段的工作分成若干遍。分遍的原則：分遍的原則： 目標(biāo)質(zhì)量高低，機(jī)器內(nèi)存大小，源語(yǔ)言簡(jiǎn)繁等。目標(biāo)質(zhì)量高低，機(jī)器內(nèi)存大小，源語(yǔ)言簡(jiǎn)繁等。編譯前端與后端編譯前端與后端從概念上劃分：從概念上劃分： 編譯程序可分為編譯程序可分為編譯前端編譯前端和和編譯后端編譯后端。p 編譯前端：編譯前端：指與源語(yǔ)言有關(guān)但與目標(biāo)機(jī)無(wú)關(guān)的編指與源語(yǔ)言有關(guān)但與目標(biāo)機(jī)無(wú)關(guān)的編譯程序部分。包括詞法分析、語(yǔ)法分析、語(yǔ)義分譯程序部分。包括詞法分析、語(yǔ)法分析、語(yǔ)義分析、中間代碼產(chǎn)生和部分優(yōu)化。析、中間代碼產(chǎn)生和部分優(yōu)化。p 編譯后端：編譯后端：指與目標(biāo)機(jī)有關(guān)的編譯程序部分。包指與目標(biāo)機(jī)有關(guān)的編譯程序部分。包括與代目標(biāo)機(jī)有關(guān)的代碼優(yōu)化和目標(biāo)代碼生成等。括與代目標(biāo)機(jī)有關(guān)的代碼優(yōu)化和目標(biāo)代碼生成等。一般后端只依賴于中間語(yǔ)言。一般后端只依賴于中間語(yǔ)言。1.4 編譯程序與程序設(shè)計(jì)環(huán)境編譯程序與程