編譯原理講義精品課件

1、編譯原理講義第1頁(yè)，共19頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二第一章緒論程序設(shè)計(jì)語(yǔ)言分低級(jí)語(yǔ)言和高級(jí)語(yǔ)言兩類低級(jí)語(yǔ)言:機(jī)器語(yǔ)言、匯編語(yǔ)言及其它面向機(jī)器的程序設(shè)計(jì)語(yǔ)言；其特點(diǎn)對(duì)計(jì)算機(jī)的依賴性強(qiáng)、直觀性差、編寫程序的工作量大，對(duì)程序設(shè)計(jì)人員要求較高。高級(jí)語(yǔ)言：有幾百種之多，常用的有BASIC、FORTRAN、PASCAL、C、JAVA等，高級(jí)語(yǔ)言在算法描述能力、編寫和調(diào)試效率上均比低級(jí)語(yǔ)言優(yōu)越。但高級(jí)語(yǔ)言與機(jī)器之間有一“鴻溝”：機(jī)器不能理解高級(jí)語(yǔ)言！因此，要在計(jì)算機(jī)上實(shí)現(xiàn)高級(jí)語(yǔ)言，需使該語(yǔ)言能讓計(jì)算機(jī)所理解。方法：對(duì)程序進(jìn)行翻譯或進(jìn)行解釋。翻譯：在計(jì)算機(jī)中放置一能由計(jì)算機(jī)直接執(zhí)行的翻譯

2、程序，它將某程序設(shè)計(jì)語(yǔ)言（源語(yǔ)言）所編寫的程序（源程序）作為加工對(duì)象，將其翻譯成為與之等價(jià)的另一種語(yǔ)言（目標(biāo)語(yǔ)言）的程序（目標(biāo)程序）可見，計(jì)算機(jī)執(zhí)行某高級(jí)語(yǔ)言程序，需經(jīng)兩個(gè)階段，即編譯階段和運(yùn)行階段。在執(zhí)行時(shí)，一般應(yīng)有一些輔助子程序配合。如：數(shù)據(jù)格式轉(zhuǎn)換子程序、標(biāo)準(zhǔn)函數(shù)、動(dòng)態(tài)存儲(chǔ)分配子程序等等，由它們構(gòu)成的子程序庫(kù)稱為運(yùn)行系統(tǒng)。編譯系統(tǒng)=編譯程序+運(yùn)行系統(tǒng)第2頁(yè)，共19頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二計(jì)算機(jī)執(zhí)行高級(jí)語(yǔ)言程序的步驟源程序P目標(biāo)程序P運(yùn)行結(jié)果S編譯程序數(shù)據(jù)運(yùn)行程序計(jì)算機(jī)A計(jì)算機(jī)B編譯階段運(yùn)行階段第3頁(yè)，共19頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二編譯程序與

3、解釋程序高級(jí)語(yǔ)言程序也可通過解釋程序來執(zhí)行解釋程序：以源程序?yàn)檩斎耄趫?zhí)行過程中不再產(chǎn)生目標(biāo)程序，而是邊解釋邊執(zhí)行。解釋程序運(yùn)行效率不高目前，純粹的解釋程序已不多見，通常是將編譯和解釋作某種程度的結(jié)合。編譯程序是現(xiàn)今任何計(jì)算機(jī)系統(tǒng)的最重要的系統(tǒng)程序。本課程的目的，在于向大家介紹設(shè)計(jì)和構(gòu)造編譯程序的基本原理和基本方法，其中許多方法也適用于構(gòu)造解釋程序或匯編程序。第4頁(yè)，共19頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二1.1編譯過程概述翻譯外文書刊與編譯工作比較第5頁(yè)，共19頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二編譯程序的構(gòu)成編譯程序主要由八個(gè)部分構(gòu)成：1.詞法分析程序（掃描器 s

4、canner）2.語(yǔ)法分析程序（分析器 parser）3.語(yǔ)義分析程序4.中間代碼生成程序5.代碼優(yōu)化程序6.目標(biāo)代碼生成程序7.錯(cuò)誤檢查和處理程序8.各種信息表格的管理程序第6頁(yè)，共19頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二1.2 編譯程序的邏輯結(jié)構(gòu)詞法分析程序語(yǔ)法分析程序語(yǔ)義分析程序中間代碼生成代碼優(yōu)化程序目標(biāo)代碼生成信息表管理程序錯(cuò)誤檢查和處理程序源程序目標(biāo)代碼第7頁(yè)，共19頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二一個(gè)微型PASCAL語(yǔ)言的定義為了便于說明，我們引入一個(gè)微型PASCAL語(yǔ)言（PASCAL/M）的定義。它只有如下四種語(yǔ)句：1）PROGRAM語(yǔ)句；2）說明語(yǔ)

5、句；3）BEGIN-END語(yǔ)句；4）賦值語(yǔ)句；每個(gè)PASCAL/M語(yǔ)句都以PROGRAM語(yǔ)句開頭，后跟說明語(yǔ)句，再跟以一個(gè)BEGIN-END語(yǔ)句，在其內(nèi)部可以有若干賦值語(yǔ)句。右邊是一個(gè)該語(yǔ)言程序的例子。程序1-1 一個(gè)PASCAL源程序sourcePROGRAM source;This little source program is used to illustrate compiling procedure VAR x,y,z:integer;a:integer;BEGIN This program has only 4 statement x:=23+5;z:=x DIV -3;y:=z

6、+18*3;a:=x+(y-2) DIV 4;END.第8頁(yè)，共19頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二1.2.1 詞法分析程序（掃描器）詞法分析程序的任務(wù)是：1）識(shí)別出源程序的各個(gè)基本語(yǔ)法單位（單詞或語(yǔ)法符號(hào)）2）刪除無用的空白字符及其它與輸入介質(zhì)相關(guān)的非實(shí)質(zhì)性字符（空格、回車等）3）刪除注釋4）進(jìn)行詞法檢查，報(bào)告所發(fā)現(xiàn)的錯(cuò)誤掃描器依次查看緩沖區(qū)中源程序的各字符，根據(jù)當(dāng)前正查看的字符之種類，并參考掃描過程中已得到的信息，就能判斷出該字符在源程序中所處地位。一般它是下述幾種情況之一：1）正處理的注釋中的一個(gè)字符；2）無用字符；3）下一個(gè)單詞的首字符；4）正識(shí)別的單詞中的一個(gè)字符；5

7、）不合法的字符。掃描器輸出以單詞為單位的單詞流例如，以特殊符號(hào)“#”分隔的單詞流： # PROGRAM # source # ; # VAR # x # , # y # , # z # : # integer # ; # a # : # integer # ; # BEGIN # x # := # 23 # + # 5 # ; # z # := # x # DIV # - # 3 # ; # y # := # z # + # 18 # * # 3 # ; # a # := # x # + # ( # y # - # 2 # ) # DIV # 4 # ; # END # . #第9頁(yè)，共19頁(yè)

8、，2022年，5月20日，20點(diǎn)33分，星期二單詞流的內(nèi)部表示注意，前面的單詞流形式只是我們?yōu)檎f明原理便于閱讀而假定的形式。為了讓計(jì)算機(jī)能夠方便地識(shí)別和使用，在實(shí)際中的常用方法是將單詞計(jì)算機(jī)內(nèi)部表示為一個(gè)有序?qū)?Class,Value)。Class為一整型數(shù)，用于標(biāo)識(shí)該單詞的類別；Value用于存放單詞的值。例如對(duì)于source程序，可將其單詞分為四類：（1）保留字（2）專用符號(hào)（3）標(biāo)識(shí)符（4）整數(shù)。這樣，source程序相應(yīng)的單詞流為：(1,PAROGRAM) (3,source) (2,;) (1,VAR) (.) (2,;) (1,END) (2, .)第10頁(yè)，共19頁(yè)，2022年，

9、5月20日，20點(diǎn)33分，星期二1.2.2 語(yǔ)法分析程序（分析器）語(yǔ)法分析程序以詞法分析程序輸出的單詞流為輸入，分析源程序的結(jié)構(gòu)，判斷它是否為相應(yīng)程序設(shè)計(jì)語(yǔ)言的合法程序。方法：試圖為源程序構(gòu)造一個(gè)語(yǔ)法樹。分析工作是在相應(yīng)程序設(shè)計(jì)語(yǔ)言的語(yǔ)法規(guī)則指導(dǎo)下進(jìn)行的。語(yǔ)法規(guī)則描述了該語(yǔ)言的各種語(yǔ)成份的組成結(jié)構(gòu)。所謂語(yǔ)法樹只是邏輯概念上的，并不是在機(jī)器內(nèi)真要存儲(chǔ)一個(gè)樹形結(jié)構(gòu)。第11頁(yè)，共19頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二1.2.3 語(yǔ)義分析程序一程序設(shè)計(jì)語(yǔ)言具有語(yǔ)法和語(yǔ)義兩個(gè)特征。語(yǔ)法特征描述各成份的形式或結(jié)構(gòu)；語(yǔ)義特征描述各語(yǔ)法成份的含義與功能，即規(guī)定它們的屬性或在執(zhí)行應(yīng)進(jìn)行的運(yùn)算或操作

10、。因此，只有進(jìn)行了語(yǔ)義分析，才能讓計(jì)算機(jī)知道，應(yīng)進(jìn)行何操作或運(yùn)算。在進(jìn)行語(yǔ)義分析時(shí)還應(yīng)進(jìn)行相應(yīng)的語(yǔ)義檢查（類型匹配、矛盾說明、參數(shù)匹配等）。語(yǔ)義處理尚無公認(rèn)的方法來系統(tǒng)地描述。當(dāng)前較通用的方法是半機(jī)械化的“語(yǔ)法制導(dǎo)翻譯”方法。第12頁(yè)，共19頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 中間代碼生成為了處理方便和便于代碼優(yōu)化，在語(yǔ)義分析后通常并不直接產(chǎn)生目標(biāo)代碼，而是生成介于二者之間的中間代碼。常見的有：逆波蘭式、三元式、四元式及樹形結(jié)構(gòu)等。例如，source程序中的第四條賦值語(yǔ)句相應(yīng)的逆波蘭式可寫成：a x y 2 - div + :=source程序相應(yīng)的四元式表示為：(prologu

11、e,source)(add,23,5,T)(store,T, ,x)(div,x,-3,T)(store,T, ,z)(mult, 18,3,T)(add,z,T,T)(store,T, ,y)(sub,y,2,T)(div,T,4,T)(add,x,T,T)(store,T, ,a)(epilogue)第13頁(yè)，共19頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二1.2.5 代碼優(yōu)化程序代碼優(yōu)化的目的是生成質(zhì)量較高的目標(biāo)代碼衡量質(zhì)量的標(biāo)準(zhǔn)：空間指標(biāo)和時(shí)間指標(biāo)優(yōu)化方法分類：與機(jī)器有關(guān)和無關(guān)兩類優(yōu)化指標(biāo)有時(shí)是相互矛盾的，應(yīng)根據(jù)具體情況進(jìn)行取舍和側(cè)重source程序優(yōu)化后結(jié)果：(prologue

12、,source)(store,28, ,x)(div,x,-3,T)(store,T, ,z)(add,z,54,T)(store,T, ,y)(sub,y,2,T)(div,T,4,T)(add,x,T,T)(store,T, ,a)(epilogue)第14頁(yè)，共19頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二1.2.6 目標(biāo)代碼生成程序任務(wù)：將中間代碼翻譯成為目標(biāo)程序首先確定源語(yǔ)言各種語(yǔ)法成份的目標(biāo)代碼結(jié)構(gòu)；再根據(jù)需要制定中間代碼到目標(biāo)代碼的翻譯策略這部分程序?qū)唧w機(jī)器的依賴性很強(qiáng)，需具體情況具體分析通常，目標(biāo)代碼的三種形式：（1）具有絕對(duì)地址的機(jī)器指令代碼；（2）匯編語(yǔ)言形式的目標(biāo)

13、程序；（3）模塊結(jié)構(gòu)的機(jī)器指令（浮動(dòng)地址）。Source程序?qū)?yīng)的80386匯編程序見書中P9第15頁(yè)，共19頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二1.2.7 錯(cuò)誤檢查和處理程序程序中出現(xiàn)錯(cuò)誤是難免的。一完善的編譯程序應(yīng)具有很強(qiáng)的查錯(cuò)能力，并能準(zhǔn)確地報(bào)告源程序中錯(cuò)誤的種類及位置。除報(bào)錯(cuò)外，編譯程序還可生成一些另外的注釋信息，它有助于程序設(shè)計(jì)人員調(diào)試程序。常見的輔助手段根據(jù)請(qǐng)求輸出“對(duì)照?qǐng)D”和各變量的值。Source程序的對(duì)照?qǐng)D，見P10表1-2第16頁(yè)，共19頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二1.2.8 信息表管理程序編譯過程中，需經(jīng)常收集、記錄或查詢程序中所出現(xiàn)的各種量的有關(guān)屬性（信息）。為此，編譯程序需要建立一批不同用途的表格（常數(shù)表、變量表、關(guān)鍵字表等）除此之外，根據(jù)不同的分析方法，編譯程序還保持一些專用的表格（LL分