編譯原理_第一章

1、編譯原理編譯原理于靜洋于靜洋 程序設(shè)計(jì)語言程序設(shè)計(jì)語言第一章第一章 引論引論1.1 1.1 什么叫編譯程序什么叫編譯程序1.2 1.2 編譯過程概述編譯過程概述1.3 1.3 編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu)1.4 1.4 編譯程序與程序設(shè)計(jì)環(huán)境（略）編譯程序與程序設(shè)計(jì)環(huán)境（略）1.5 1.5 編譯程序的生成編譯程序的生成1.1 1.1 什么叫編譯程序什么叫編譯程序翻譯程序翻譯程序：一種語言程序：一種語言程序-另一種語言程序另一種語言程序源語言源語言目標(biāo)語言目標(biāo)語言編譯程序編譯程序：高級語言程序：高級語言程序-低級語言程序低級語言程序匯編程序匯編程序：匯編語言程序：匯編語言程序-機(jī)器語言程序機(jī)器語

2、言程序解釋程序解釋程序：源語言程序：源語言程序-邊解釋邊執(zhí)行邊解釋邊執(zhí)行（1 1）編譯方式：先編譯后執(zhí)行。）編譯方式：先編譯后執(zhí)行。（2 2）解釋方式：）解釋方式：以源程序作為輸入，但以源程序作為輸入，但不產(chǎn)生目標(biāo)代碼不產(chǎn)生目標(biāo)代碼，而，而 是是邊解釋邊執(zhí)行邊解釋邊執(zhí)行源程序本身。源程序本身。 1.1 1.1 什么叫編譯程序什么叫編譯程序編譯和解釋的主要區(qū)別：是否產(chǎn)生目標(biāo)代碼！“編譯程序編譯程序”在計(jì)在計(jì)算機(jī)系統(tǒng)中的位算機(jī)系統(tǒng)中的位置較接近于置較接近于“硬硬件件”1.1 1.1 什么叫編譯程序什么叫編譯程序2020世紀(jì)世紀(jì)5050年代年代 第一個(gè)編譯程序第一個(gè)編譯程序 FORTRAN FORT

3、RAN編譯程序編譯程序目前：編譯原理與技術(shù)得到迅速發(fā)展，現(xiàn)已形成一套比目前：編譯原理與技術(shù)得到迅速發(fā)展，現(xiàn)已形成一套比較成熟的系統(tǒng)化的理論與方法，并開發(fā)出了一些好的編譯較成熟的系統(tǒng)化的理論與方法，并開發(fā)出了一些好的編譯程序的實(shí)現(xiàn)語言、環(huán)境與工具。程序的實(shí)現(xiàn)語言、環(huán)境與工具。當(dāng)時(shí)普遍認(rèn)為設(shè)計(jì)和實(shí)當(dāng)時(shí)普遍認(rèn)為設(shè)計(jì)和實(shí)現(xiàn)編譯程序是一件十分現(xiàn)編譯程序是一件十分困難、令人生畏的事情困難、令人生畏的事情1.1 1.1 什么叫編譯程序什么叫編譯程序1.2 1.2 編譯過程概述編譯過程概述The elephant ate an banana.The elephant ate an banana.什么是語言？f

4、or K : = 1 to 100 dofor K : = 1 to 100 dobeginbeginM : = I + 10 M : = I + 10 * * K ; K ;N : = J + 10 N : = J + 10 * * K Kendend一一. .類比自然語言翻譯和編譯過程類比自然語言翻譯和編譯過程英英漢漢 編譯的工作過程編譯的工作過程1)1)識別單詞識別單詞詞法分析詞法分析2)2)分析句子語法結(jié)構(gòu)分析句子語法結(jié)構(gòu)語法分析語法分析3)3)根據(jù)句子含義初步翻譯根據(jù)句子含義初步翻譯語義分析與中間代碼產(chǎn)生語義分析與中間代碼產(chǎn)生4)4)修飾譯文修飾譯文優(yōu)化優(yōu)化5)5)寫出最后譯文寫出最

5、后譯文目標(biāo)代碼生成目標(biāo)代碼生成1.2 1.2 編譯過程概述編譯過程概述1.詞法分析詞法分析for K : = 1 to 100 dobeginM : = I + 10 * K ;N : = J + 10 * Kend 基本字基本字 forfor 標(biāo)識符標(biāo)識符 K K 賦值號賦值號 :=:= 常數(shù)常數(shù) 1 1 基本字基本字 toto 常數(shù)常數(shù) 100100 基本字基本字 dodo 基本字基本字 beginbegin . . . .1.2 1.2 編譯過程概述編譯過程概述詞法分析詞法分析 規(guī)則：規(guī)則：規(guī)則描述工具：規(guī)則描述工具：任務(wù)：任務(wù)：依循詞法規(guī)則依循詞法規(guī)則.正規(guī)式和有限自動機(jī)（正規(guī)式和有限

6、自動機(jī)（FAFA）. .輸入源程序輸入源程序，對構(gòu)成源程序的字符串進(jìn)行掃，對構(gòu)成源程序的字符串進(jìn)行掃描和分解，描和分解，識別出一個(gè)個(gè)的單詞符號識別出一個(gè)個(gè)的單詞符號，如基，如基本字、標(biāo)識符、常數(shù)、算符、界符等。本字、標(biāo)識符、常數(shù)、算符、界符等。1.2 1.2 編譯過程概述編譯過程概述2. 語法分析語法分析for K : = 1 to 100 dobeginM : = I + 10 * K ;N : = J + 10 * Kend規(guī)則：規(guī)則：規(guī)則描述工具：規(guī)則描述工具：任務(wù)：任務(wù)：依循語法規(guī)則依循語法規(guī)則.上下文無關(guān)文法上下文無關(guān)文法. .在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，對單詞符在詞法分

7、析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，對單詞符號串進(jìn)行語法分析，識別出各類語法單位，最終判斷輸號串進(jìn)行語法分析，識別出各類語法單位，最終判斷輸入串是否構(gòu)成語法上正確的入串是否構(gòu)成語法上正確的“程序程序”。1.2 1.2 編譯過程概述編譯過程概述3.語義分析和中間代碼產(chǎn)生語義分析和中間代碼產(chǎn)生規(guī)則：規(guī)則：規(guī)則描述工具：規(guī)則描述工具：任務(wù)：任務(wù)：語義規(guī)則語義規(guī)則屬性文法屬性文法兩部分工作：兩部分工作：1.1.對每種語法范疇進(jìn)行對每種語法范疇進(jìn)行靜態(tài)語義檢查靜態(tài)語義檢查; ;2.2.若語義正確，則進(jìn)行若語義正確，則進(jìn)行中間代碼翻譯中間代碼翻譯. .對語法分析器識別出的各類語法單位，分析對語法分析器識別出的

8、各類語法單位，分析其含義并進(jìn)行初步翻譯（產(chǎn)生其含義并進(jìn)行初步翻譯（產(chǎn)生中間代碼中間代碼）。）。 中間代碼：一種獨(dú)立于中間代碼：一種獨(dú)立于具體硬件的記號系統(tǒng)，具體硬件的記號系統(tǒng)，更接近于機(jī)器代碼更接近于機(jī)器代碼 1.2 1.2 編譯過程概述編譯過程概述for K : = 1 to 100 dofor K : = 1 to 100 do begin begin M : = I + 10 M : = I + 10 * * K ; K ; N : = J + 10 N : = J + 10 * * K K end end； K:=1K:=1L L1 1:if 100K goto L:if 100K g

9、oto L2 2 T T1 1:=10:=10* *K K M:=I+T M:=I+T1 1 T T2 2:=10:=10* *K K N:=J+T N:=J+T2 2 K:=K+1K:=K+1 goto L goto L1 1L L2 2: :語義分析后產(chǎn)生的中間代碼：語義分析后產(chǎn)生的中間代碼：三地址代碼三地址代碼具體實(shí)現(xiàn)：具體實(shí)現(xiàn)：三元式，四元式，間接三元式三元式，四元式，間接三元式1.2 1.2 編譯過程概述編譯過程概述 K:=1K:=1L L1 1:if 100K goto L:if 100K goto L2 2 T T1 1:=10:=10* *K K M:=I+T M:=I+T1

10、1 T T2 2:=10:=10* *K K N:=J+T N:=J+T2 2 K:=K+1K:=K+1 goto L goto L1 1L L2 2: :序號OPARG1ARG2RESULT(1)(2)(3)(4)(5)(6)(7)(8)(9):=j*+*+j110010I10JKKKT1KT21K(9)T1MT2NK(2)四元式序列：四元式序列：1.2 1.2 編譯過程概述編譯過程概述任務(wù)：任務(wù)：對中間代碼進(jìn)行加工變換，以期在最后階段對中間代碼進(jìn)行加工變換，以期在最后階段 能產(chǎn)生出更為能產(chǎn)生出更為高效（省時(shí)間和空間）高效（省時(shí)間和空間）的目標(biāo)的目標(biāo) 代碼。代碼。 4.4.優(yōu)化優(yōu)化包括：公共

11、子表達(dá)式的提取、包括：公共子表達(dá)式的提取、循環(huán)優(yōu)化、刪除無用代碼等循環(huán)優(yōu)化、刪除無用代碼等1.2 1.2 編譯過程概述編譯過程概述序號OP ARG1 ARG2RESULT(1)(2)(3)(4)(5)(6)(7)(8)(9):=j*+*+j110010I10JKKKT1KT21K(9)T1MT2NK(2)序號OP ARG1 ARG2RESULT(1)(2)(3)(4)(5)(6)(7)(8)(9):=:=:=j+jII1100MNK K10101MNK(9)MNK(2)優(yōu)化前優(yōu)化前優(yōu)化后優(yōu)化后1.2 1.2 編譯過程概述編譯過程概述任務(wù)：任務(wù)：把中間代碼變換成把中間代碼變換成特定機(jī)器上特定機(jī)器

12、上的低級語言代碼，的低級語言代碼， 實(shí)現(xiàn)最后的翻譯。實(shí)現(xiàn)最后的翻譯。5.5.目標(biāo)代碼生成目標(biāo)代碼生成絕對指令代碼絕對指令代碼/ /可重定位的可重定位的指令代碼指令代碼/ /匯編指令代碼匯編指令代碼有賴于硬件系統(tǒng)結(jié)構(gòu)和機(jī)器指令含義有賴于硬件系統(tǒng)結(jié)構(gòu)和機(jī)器指令含義1.2 1.2 編譯過程概述編譯過程概述1.3 1.3 編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu)一一. .編譯程序總框圖編譯程序總框圖1.1.表格管理表格管理 編譯各階段都要涉及到構(gòu)造、查找或編譯各階段都要涉及到構(gòu)造、查找或 更新有關(guān)表格更新有關(guān)表格 。表格的作用：表格的作用： 登記源程序的登記源程序的各類信息各類信息和編譯和編譯各階段的進(jìn)展?fàn)顩r各階

13、段的進(jìn)展?fàn)顩r。符號表：符號表： 用來登記源程序中出現(xiàn)的每個(gè)用來登記源程序中出現(xiàn)的每個(gè)名字名字以及以及名字的各種屬性名字的各種屬性。 舉例：舉例：名字名字變量名變量名/ /常量名常量名/ /過程名過程名？變量名變量名類型？類型？/ /內(nèi)存？內(nèi)存？/ /地址？地址？1.3 1.3 編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu)2.2.出錯(cuò)處理出錯(cuò)處理 每一階段都可能檢測出錯(cuò)誤，絕大多每一階段都可能檢測出錯(cuò)誤，絕大多 數(shù)錯(cuò)誤可在前三階段檢測出來數(shù)錯(cuò)誤可在前三階段檢測出來 . .任務(wù)：任務(wù)：設(shè)法發(fā)現(xiàn)錯(cuò)誤，并把有關(guān)錯(cuò)誤信息報(bào)告給用戶設(shè)法發(fā)現(xiàn)錯(cuò)誤，并把有關(guān)錯(cuò)誤信息報(bào)告給用戶. . 語法錯(cuò)誤語法錯(cuò)誤：源程序中不符合語法：源程

14、序中不符合語法/ /詞法規(guī)則的錯(cuò)誤。詞法規(guī)則的錯(cuò)誤。詞法詞法/ /語法分析時(shí)檢測語法分析時(shí)檢測語義錯(cuò)誤語義錯(cuò)誤：源程序中不符合語義規(guī)則的錯(cuò)誤。：源程序中不符合語義規(guī)則的錯(cuò)誤。語義分析語義分析/ /運(yùn)行時(shí)檢測出來運(yùn)行時(shí)檢測出來1.3 1.3 編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu)二二. .遍遍1.1.編譯過程的劃分：編譯過程的劃分： 上述劃分的五個(gè)階段僅僅是上述劃分的五個(gè)階段僅僅是邏輯功能邏輯功能上的一種劃分上的一種劃分2.2.遍（遍（PassPass） 對源程序或源程序的中間結(jié)果對源程序或源程序的中間結(jié)果從頭到尾從頭到尾掃描一次，并掃描一次，并作有關(guān)的加工處理，生成作有關(guān)的加工處理，生成新的新的中間結(jié)果

15、或目標(biāo)程序。中間結(jié)果或目標(biāo)程序。具體實(shí)現(xiàn)時(shí)，受各方具體實(shí)現(xiàn)時(shí)，受各方面（如源語言、設(shè)計(jì)面（如源語言、設(shè)計(jì)要求等）限制，往往要求等）限制，往往組織成若干遍組織成若干遍1.3 1.3 編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu)3.3.注意：注意：既可以將幾個(gè)不同階段合為一遍，也可以把一個(gè)階段的既可以將幾個(gè)不同階段合為一遍，也可以把一個(gè)階段的工作分為若干遍工作分為若干遍例如：例如：詞法分析詞法分析+ +語法分析語法分析 一遍一遍語法分析語法分析+ +語義分析與中間代碼產(chǎn)生語義分析與中間代碼產(chǎn)生一遍一遍優(yōu)化優(yōu)化 若干遍若干遍單遍代碼單遍代碼不太有效不太有效。根據(jù)系統(tǒng)資源的狀況、運(yùn)行目標(biāo)根據(jù)系統(tǒng)資源的狀況、運(yùn)行目標(biāo)的

16、要求等，可以將一個(gè)編譯程序的要求等，可以將一個(gè)編譯程序設(shè)計(jì)形成多遍掃描的形式，在每設(shè)計(jì)形成多遍掃描的形式，在每一遍掃描中完成不同的任務(wù)。一遍掃描中完成不同的任務(wù)。1.3 1.3 編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu)當(dāng)一遍中包含若干階段時(shí)，各階段的工作是穿插進(jìn)行的當(dāng)一遍中包含若干階段時(shí)，各階段的工作是穿插進(jìn)行的 。例如：例如：識別出一個(gè)語法單位時(shí)語法分析器語法分析器詞法分析器詞法分析器語義分析和中間代碼產(chǎn)生器語義分析和中間代碼產(chǎn)生器識別語法結(jié)構(gòu)需要下一個(gè)單詞時(shí)單詞符號1.3 1.3 編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu)三三. .編譯前端與后端編譯前端與后端1 1、前端：、前端： 由與源語言由與源語言有關(guān)有關(guān)但與

17、目標(biāo)機(jī)但與目標(biāo)機(jī)無關(guān)無關(guān)的那些部分組成的那些部分組成 包括包括詞法分析、語法分析、語義分析與中間代碼詞法分析、語法分析、語義分析與中間代碼 產(chǎn)生、部分代碼優(yōu)化工作產(chǎn)生、部分代碼優(yōu)化工作 2 2、后端：、后端： 包括編譯程序中與目標(biāo)機(jī)包括編譯程序中與目標(biāo)機(jī)有關(guān)有關(guān)的那些部分，如與的那些部分，如與 目標(biāo)機(jī)有關(guān)的代碼優(yōu)化和目標(biāo)代碼生成等。目標(biāo)機(jī)有關(guān)的代碼優(yōu)化和目標(biāo)代碼生成等。不依賴于源語言而僅僅不依賴于源語言而僅僅依賴于中間語言依賴于中間語言1.3 1.3 編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu)1.5 1.5 編譯程序的生成編譯程序的生成 一一. . 設(shè)計(jì)目標(biāo)設(shè)計(jì)目標(biāo) 目標(biāo)程序小，執(zhí)行速度快目標(biāo)程序小，執(zhí)行速

18、度快編譯程序小，執(zhí)行速度快編譯程序小，執(zhí)行速度快診斷能力強(qiáng)，可靠性強(qiáng)診斷能力強(qiáng)，可靠性強(qiáng)可移植性，可擴(kuò)充性可移植性，可擴(kuò)充性 如何實(shí)現(xiàn)編譯器？如何實(shí)現(xiàn)編譯器？直接用可運(yùn)行直接用可運(yùn)行的代碼編制的代碼編制太費(fèi)力！太費(fèi)力！1.5 1.5 編譯程序的生成編譯程序的生成 2 2、問題、問題 （1 1）歷史上第一個(gè)高級語言的編譯程序是怎樣構(gòu)造的？）歷史上第一個(gè)高級語言的編譯程序是怎樣構(gòu)造的？ -自編譯技術(shù)（自展技術(shù)）自編譯技術(shù)（自展技術(shù)）（2 2）已有）已有A A機(jī)器上的機(jī)器上的L1L1語言（如：語言（如：C C語言）的編譯程序，如何語言）的編譯程序，如何構(gòu)造構(gòu)造A A機(jī)器上的機(jī)器上的L2L2語言（如：

19、語言（如：PASCALPASCAL語言）的編譯程序？語言）的編譯程序？（3 3）已有）已有A A機(jī)器上的機(jī)器上的L L語言的編譯程序，如何構(gòu)造語言的編譯程序，如何構(gòu)造B B機(jī)器上的機(jī)器上的L L語言的編譯程序？語言的編譯程序？ -交叉編譯交叉編譯 / /移植移植STI源語言源語言編譯程序編譯程序?qū)崿F(xiàn)語言實(shí)現(xiàn)語言目標(biāo)語言目標(biāo)語言一般采用基于一般采用基于T T形圖的方式：形圖的方式：表現(xiàn)語言翻譯的表現(xiàn)語言翻譯的T T形圖形圖1.5 1.5 編譯程序的生成編譯程序的生成 問題：問題：已知已知A A機(jī)上有一個(gè)用機(jī)上有一個(gè)用A A代碼實(shí)現(xiàn)的高級語言代碼實(shí)現(xiàn)的高級語言L1L1的編的編譯程序，可以用譯程序，

20、可以用L1L1實(shí)現(xiàn)在實(shí)現(xiàn)在A A機(jī)上能運(yùn)行一個(gè)新語言機(jī)上能運(yùn)行一個(gè)新語言L2L2編編寫的程序。寫的程序。 L1AA已知條件目標(biāo)L2L1A二二. . 多級編譯程序多級編譯程序 1 1、本機(jī)編譯器利用、本機(jī)編譯器利用 分析：分析：1.5 1.5 編譯程序的生成編譯程序的生成 條件目標(biāo)L2L1AL1AAL2AAL L1 1語言寫成的語言寫成的L L2 2語言語言的編譯程序的編譯程序A A代碼寫成的代碼寫成的L L1 1語語言的編譯程序言的編譯程序得到得到A A代碼寫成的代碼寫成的L L2 2語言的編譯程序語言的編譯程序P P0 0P P1 1P P2 2說明：說明：P P0 0L L2 2語言的編譯

21、程序，用語言的編譯程序，用L L1 1語言實(shí)現(xiàn)語言實(shí)現(xiàn) P P1 1L L1 1語言的編譯程序，用語言的編譯程序，用A A代碼實(shí)現(xiàn)代碼實(shí)現(xiàn) P P2 2L L2 2語言的編譯程序，用語言的編譯程序，用A A代碼實(shí)現(xiàn)代碼實(shí)現(xiàn) 1.5 1.5 編譯程序的生成編譯程序的生成 問題：問題：已知已知A A機(jī)上有一個(gè)用機(jī)上有一個(gè)用A A代碼實(shí)現(xiàn)的高級語言代碼實(shí)現(xiàn)的高級語言L L的的編譯程序（即編譯程序（即A A機(jī)上可直接運(yùn)行機(jī)上可直接運(yùn)行L L語言程序），是否可語言程序），是否可利用該編譯程序?qū)崿F(xiàn)在利用該編譯程序?qū)崿F(xiàn)在B B機(jī)上運(yùn)行機(jī)上運(yùn)行L L語言程序？語言程序？ LAA條件目標(biāo)LLB2. 2. 交叉編譯交叉編譯/ /移植（移植（思考思考）1.5 1.5 編譯程序的生成編譯程序的生成 LAA條件LLB目標(biāo)LLBLAALABLLBLBB說明：說明：過程過程在在A A機(jī)上運(yùn)行的產(chǎn)生機(jī)上運(yùn)行的產(chǎn)生B B代碼的代碼的L L編譯程序源程序（編譯程序源程序（L