程序設(shè)計(jì)語言編譯原理第三版第1章

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 什么叫編譯程序什么叫編譯程序翻譯程序翻譯程序：一種語言程序：一種語言程序-另一種語言程序另一種語言程序源語言源語言目標(biāo)語言目標(biāo)語言編譯程序編譯程序：高級(jí)語言程序：高級(jí)語言程序-低級(jí)語言程序低級(jí)語言程序匯編程序匯編程序：匯編語言程序：匯編語言程序-機(jī)器語言程序機(jī)器語言程序解

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

3、ran fortran編譯程序編譯程序目前：目前：編譯原理與技術(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.2 編譯過程概述編譯過程概述the elephant ate an banana.什么是語言？for k : = 1 to 100 dobeginm

4、: = i + 10 * k ;n : = j + 10 * kend一一. .類比自然語言翻譯和編譯過程類比自然語言翻譯和編譯過程英英漢漢 編譯的工作過程編譯的工作過程1)1)識(shí)別單詞識(shí)別單詞詞法分析詞法分析2)2)分析句子語法結(jié)構(gòu)分析句子語法結(jié)構(gòu)語法分析語法分析3)3)根據(jù)句子含義初步翻譯根據(jù)句子含義初步翻譯語義分析與中間代碼產(chǎn)生語義分析與中間代碼產(chǎn)生4)4)修飾譯文修飾譯文優(yōu)化優(yōu)化5)5)寫出最后譯文寫出最后譯文目標(biāo)代碼生成目標(biāo)代碼生成1.2 編譯過程概述編譯過程概述1.詞法分析詞法分析for k : = 1 to 100 dobeginm : = i + 10 * k ;n : = j

5、 + 10 * kend 基本字基本字 forfor 標(biāo)識(shí)符標(biāo)識(shí)符 k k 賦值號(hào)賦值號(hào) :=:= 常數(shù)常數(shù) 1 1 基本字基本字 toto 常數(shù)常數(shù) 100100 基本字基本字 dodo 基本字基本字 beginbegin . . . .1.2 編譯過程概述編譯過程概述詞法分析詞法分析 規(guī)則：規(guī)則：規(guī)則描述工具：規(guī)則描述工具：任務(wù)：任務(wù)：依循詞法規(guī)則依循詞法規(guī)則.正規(guī)式和有限自動(dòng)機(jī)（正規(guī)式和有限自動(dòng)機(jī)（fafa）. .輸入源程序輸入源程序，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，分解，識(shí)別出一個(gè)個(gè)的單詞符號(hào)識(shí)別出一個(gè)個(gè)的單詞符號(hào)，如基本字、標(biāo)，如基本字、標(biāo)識(shí)符、常

6、數(shù)、算符、界符等。識(shí)符、常數(shù)、算符、界符等。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ī)則，對(duì)單詞在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，對(duì)單詞符號(hào)串進(jìn)行語法分析，識(shí)別出各類語法單位，最終判符號(hào)串進(jìn)行語法分析，識(shí)別出各類語法單位，最終判斷輸入串是否構(gòu)成語法上正確的斷輸入串是否構(gòu)成語法上正確的“程序程序”。1.2 編

7、譯過程概述編譯過程概述3.語義分析和中間代碼產(chǎn)生語義分析和中間代碼產(chǎn)生規(guī)則：規(guī)則：規(guī)則描述工具：規(guī)則描述工具：任務(wù)：任務(wù)：語義規(guī)則語義規(guī)則屬性文法屬性文法兩部分工作：兩部分工作：1.1.對(duì)每種語法范疇進(jìn)行對(duì)每種語法范疇進(jìn)行靜態(tài)語義檢查靜態(tài)語義檢查; ;2.2.若語義正確，則進(jìn)行若語義正確，則進(jìn)行中間代碼翻譯中間代碼翻譯. .對(duì)語法分析器識(shí)別出的各類語法單位，分析對(duì)語法分析器識(shí)別出的各類語法單位，分析其含義并進(jìn)行初步翻譯（產(chǎn)生其含義并進(jìn)行初步翻譯（產(chǎn)生中間代碼中間代碼）。）。 中間代碼：一種獨(dú)立于中間代碼：一種獨(dú)立于具體硬件的記號(hào)系統(tǒng)，具體硬件的記號(hào)系統(tǒng)，更接近于機(jī)器代碼更接近于機(jī)器代碼 1.2

8、 編譯過程概述編譯過程概述for k : = 1 to 100 do begin m : = i + 10 * k ; n : = j + 10 * k end； k:=1l1: if 100k goto l2 t1:=10*k m:=i+t1 t2:=10*k n:=j+t2 k:=k+1 goto l1l2:語義分析后產(chǎn)生的中間代碼：語義分析后產(chǎn)生的中間代碼：三地址代碼三地址代碼具體實(shí)現(xiàn)：具體實(shí)現(xiàn)：三元式，四元式，間接三元式三元式，四元式，間接三元式1.2 編譯過程概述編譯過程概述 k:=1k:=1l l1 1:if 100k goto l:if 100k goto l2 2 t t1 1

9、:=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: :序號(hào)oparg1arg2result(1)(2)(3)(4)(5)(6)(7)(8)(9):=j*+*+j110010i10jkkkt1kt21k(9)t1mt2nk(2)四元式序列：四元式序列：1.2 1.2 編譯過程概述編譯過程概述任務(wù)：任務(wù)：對(duì)中間代碼進(jìn)行加工變換，以期在最后階段能產(chǎn)生出對(duì)中間代碼進(jìn)行加工變換，以期在最后階段能產(chǎn)生出 更為更為高效（省時(shí)間和空間）高效（省時(shí)間和

10、空間）的目標(biāo)代碼。的目標(biāo)代碼。 4.4.優(yōu)化優(yōu)化包括：公共子表達(dá)式的提取、包括：公共子表達(dá)式的提取、循環(huán)優(yōu)化、刪除無用代碼等循環(huán)優(yōu)化、刪除無用代碼等1.2 1.2 編譯過程概述編譯過程概述序號(hào)序號(hào) opoparg1arg1 arg2arg2 resultresult(1)(2)(3)(4)(5)(6)(7)(8)(9):=j*+*+j110010i10jkkkt1kt21k(9)t1mt2nk(2)序號(hào)序號(hào) opoparg1arg1 arg2arg2 resultresult(1)(2)(3)(4)(5)(6)(7)(8)(9):=:=:=j+jii1100mnk k10101mnk(9)mn

11、k(2)優(yōu)化前優(yōu)化前優(yōu)化后優(yōu)化后1.2 1.2 編譯過程概述編譯過程概述任務(wù)：任務(wù)：把中間代碼變換成把中間代碼變換成特定機(jī)器上特定機(jī)器上的低級(jí)語言代碼，的低級(jí)語言代碼， 實(shí)現(xiàn)最后的翻譯。實(shí)現(xiàn)最后的翻譯。5.5.目標(biāo)代碼生成目標(biāo)代碼生成絕對(duì)指令代碼絕對(duì)指令代碼/ /可重定位的可重定位的指令代碼指令代碼/ /匯編指令代碼匯編指令代碼有賴于硬件系統(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)造、

12、查找或 更新有關(guān)表格更新有關(guān)表格 。表格的作用：表格的作用： 登記源程序的登記源程序的各類信息各類信息和編譯和編譯各階段的進(jìn)展?fàn)顩r各階段的進(jìn)展?fàn)顩r。符號(hào)表：符號(hào)表： 用來登記源程序中出現(xiàn)的每個(gè)用來登記源程序中出現(xiàn)的每個(gè)名字名字以及以及名字的各種屬性名字的各種屬性。 舉例：舉例：名字名字變量名變量名/ /常量名常量名/ /過程名過程名？變量名變量名類型？類型？/ /內(nèi)存？?jī)?nèi)存？/ /地址？地址？1.3 1.3 編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu)2.2.出錯(cuò)處理出錯(cuò)處理 每一階段都可能檢測(cè)出錯(cuò)誤，絕大多每一階段都可能檢測(cè)出錯(cuò)誤，絕大多 數(shù)錯(cuò)誤可在前三階段檢測(cè)出來數(shù)錯(cuò)誤可在前三階段檢測(cè)出來 . .任務(wù)：任

13、務(wù)：設(shè)法發(fā)現(xiàn)錯(cuò)誤，并把有關(guān)錯(cuò)誤信息報(bào)告給用戶設(shè)法發(fā)現(xiàn)錯(cuò)誤，并把有關(guān)錯(cuò)誤信息報(bào)告給用戶. . 語法錯(cuò)誤語法錯(cuò)誤：源程序中不符合語法：源程序中不符合語法/ /詞法規(guī)則的錯(cuò)誤。詞法規(guī)則的錯(cuò)誤。詞法詞法/ /語法分析時(shí)檢測(cè)語法分析時(shí)檢測(cè)語義錯(cuò)誤語義錯(cuò)誤：源程序中不符合語義規(guī)則的錯(cuò)誤。：源程序中不符合語義規(guī)則的錯(cuò)誤。語義分析語義分析/ /運(yùn)行時(shí)檢測(cè)出來運(yùn)行時(shí)檢測(cè)出來1.3 1.3 編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu)二二. .遍遍1.1.編譯過程的劃分：編譯過程的劃分： 上述劃分的五個(gè)階段僅僅是上述劃分的五個(gè)階段僅僅是邏輯功能邏輯功能上的一種劃分上的一種劃分2.2.遍（遍（passpass） 對(duì)源程序或源程序的

14、中間結(jié)果對(duì)源程序或源程序的中間結(jié)果從頭到尾從頭到尾掃描一次，并掃描一次，并作有關(guān)的加工處理，生成作有關(guān)的加工處理，生成新的新的中間結(jié)果或目標(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)生語義分析與

15、中間代碼產(chǎn)生一遍一遍優(yōu)化優(yōu)化 若干遍若干遍單遍代碼單遍代碼不太有效不太有效。根據(jù)系統(tǒng)資源的狀況、運(yùn)行目標(biāo)根據(jù)系統(tǒng)資源的狀況、運(yùn)行目標(biāo)的要求等，可以將一個(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)行的 。例如：例如：識(shí)別出一個(gè)語識(shí)別出一個(gè)語法單位時(shí)法單位時(shí)語法分析器語法分析器詞法分析器詞法分析器語義分析和中間代碼產(chǎn)生器語義分析和中間代碼產(chǎn)生器識(shí)別語法結(jié)構(gòu)需識(shí)別語

16、法結(jié)構(gòu)需要下一個(gè)單詞時(shí)要下一個(gè)單詞時(shí)單單詞詞符符號(hào)號(hào)1.3 1.3 編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu)三三. .編譯前端與后端編譯前端與后端1.1.前端：前端： 由與源語言由與源語言有關(guān)有關(guān)但與目標(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)代碼生成等。不依賴于源語言而僅僅不依賴于源語言而僅僅依

17、賴于中間語言依賴于中間語言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í)行速度快編譯程序小，執(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è)高級(jí)語言的編譯程序是怎樣構(gòu)造的？歷史上第一個(gè)高級(jí)語言的編譯程序是怎樣構(gòu)造的？ -自編譯技術(shù)（自展技術(shù)）自編譯技

18、術(shù)（自展技術(shù)）（2 2）已有已有a a機(jī)器上的機(jī)器上的l1l1語言（如：語言（如：c c語言）的編譯程序，如何語言）的編譯程序，如何構(gòu)造構(gòu)造a a機(jī)器上的機(jī)器上的l2l2語言（如：語言（如：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形圖形

19、圖1.5 1.5 編譯程序的生成編譯程序的生成 問題：?jiǎn)栴}：已知已知a a機(jī)上有一個(gè)用機(jī)上有一個(gè)用a a代碼實(shí)現(xiàn)的高級(jí)語言代碼實(shí)現(xiàn)的高級(jí)語言l1l1的編的編譯程序，可以用譯程序，可以用l1l1實(shí)現(xiàn)在實(shí)現(xiàn)在a a機(jī)上能運(yùn)行一個(gè)新語言機(jī)上能運(yùn)行一個(gè)新語言l2l2編編寫的程序。寫的程序。 l1aa已知條件目標(biāo)l2l1a二二. . 多級(jí)編譯程序多級(jí)編譯程序 1.1.本機(jī)編譯器利用本機(jī)編譯器利用 分析：分析：1.5 1.5 編譯程序的生成編譯程序的生成 條件目標(biāo)l2l1al1aal2aal l1 1語言寫成的語言寫成的l l2 2語言語言的編譯程序的編譯程序a a代碼寫成的代碼寫成的l l1 1語語言的

20、編譯程序言的編譯程序得到得到a a代碼寫成的代碼寫成的l l2 2語言的編譯程序語言的編譯程序p p0 0p p1 1p p2 2說明：說明：p p0 0l l2 2語言的編譯程序，用語言的編譯程序，用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 編譯程序的生成編譯程序的生成 問題：?jiǎn)栴}：已知已知a a機(jī)上有一個(gè)用機(jī)上有一個(gè)用a a代碼實(shí)現(xiàn)的高級(jí)語言代碼實(shí)現(xiàn)的高級(jí)語言l l的的編譯程序（即編譯程序（即a a機(jī)上可直接運(yùn)行機(jī)上可直接運(yùn)行l(wèi) l語言程序），是否可語言程序），是否可利用該編譯程序?qū)崿F(xiàn)在利用該編譯程序?qū)崿F(xiàn)在b b機(jī)上運(yùn)行機(jī)上運(yùn)行l(wèi) l語言程序？語言程序？ laa條件目標(biāo)llb2. 2. 交叉編譯交叉編譯/ /移植移植（思考思考）1.5