編譯原理講義

編譯原理講義第一頁(yè)，共十九頁(yè)，2022年，8月28日第一章 緒論程序設(shè)計(jì)語(yǔ)言分低級(jí)語(yǔ)言和高級(jí)語(yǔ)言兩類低級(jí)語(yǔ)言:機(jī)器語(yǔ)言、匯編語(yǔ)言及其它面向機(jī)器的程序設(shè)計(jì)語(yǔ)言；其特點(diǎn)對(duì)計(jì)算機(jī)的依賴性強(qiáng)、直觀性差、編寫(xiě)程序的工作量大，對(duì)程序設(shè)計(jì)人員要求較高。高級(jí)語(yǔ)言：有幾百種之多，常用的有BASIC、FORTRAN、PASCAL、C、JAVA等，高級(jí)語(yǔ)言在算法描述能力、編寫(xiě)和調(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í)行的翻譯程序，它將某程序設(shè)計(jì)語(yǔ)言（源語(yǔ)言）所編寫(xiě)的程序（源程序）作為加工對(duì)象，將其翻譯成為與之等價(jià)的另一種語(yǔ)言（目標(biāo)語(yǔ)言）的程序（目標(biāo)程序）可見(jiàn)，計(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)第二頁(yè)，共十九頁(yè)，2022年，8月28日計(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)行階段第三頁(yè)，共十九頁(yè)，2022年，8月28日編譯程序與解釋程序高級(jí)語(yǔ)言程序也可通過(guò)解釋程序來(lái)執(zhí)行解釋程序：以源程序?yàn)檩斎?，在?zhí)行過(guò)程中不再產(chǎn)生目標(biāo)程序，而是邊解釋邊執(zhí)行。解釋程序運(yùn)行效率不高目前，純粹的解釋程序已不多見(jiàn)，通常是將編譯和解釋作某種程度的結(jié)合。編譯程序是現(xiàn)今任何計(jì)算機(jī)系統(tǒng)的最重要的系統(tǒng)程序。本課程的目的，在于向大家介紹設(shè)計(jì)和構(gòu)造編譯程序的基本原理和基本方法，其中許多方法也適用于構(gòu)造解釋程序或匯編程序。第四頁(yè)，共十九頁(yè)，2022年，8月28日1.1編譯過(guò)程概述翻譯外文書(shū)刊與編譯工作比較第五頁(yè)，共十九頁(yè)，2022年，8月28日編譯程序的構(gòu)成編譯程序主要由八個(gè)部分構(gòu)成：1.詞法分析程序（掃描器scanner）2.語(yǔ)法分析程序（分析器parser）3.語(yǔ)義分析程序4.中間代碼生成程序5.代碼優(yōu)化程序6.目標(biāo)代碼生成程序7.錯(cuò)誤檢查和處理程序8.各種信息表格的管理程序第六頁(yè)，共十九頁(yè)，2022年，8月28日1.2編譯程序的邏輯結(jié)構(gòu)詞法分析程序語(yǔ)法分析程序語(yǔ)義分析程序中間代碼生成代碼優(yōu)化程序目標(biāo)代碼生成信息表管理程序錯(cuò)誤檢查和處理程序源程序目標(biāo)代碼第七頁(yè)，共十九頁(yè)，2022年，8月28日一個(gè)微型PASCAL語(yǔ)言的定義為了便于說(shuō)明，我們引入一個(gè)微型PASCAL語(yǔ)言（PASCAL/M）的定義。它只有如下四種語(yǔ)句：1）PROGRAM語(yǔ)句；2）說(shuō)明語(yǔ)句；3）BEGIN-END語(yǔ)句；4）賦值語(yǔ)句；每個(gè)PASCAL/M語(yǔ)句都以PROGRAM語(yǔ)句開(kāi)頭，后跟說(shuō)明語(yǔ)句，再跟以一個(gè)BEGIN-END語(yǔ)句，在其內(nèi)部可以有若干賦值語(yǔ)句。右邊是一個(gè)該語(yǔ)言程序的例子。程序1-1一個(gè)PASCAL源程序sourcePROGRAMsource;{Thislittlesourceprogramisusedtoillustratecompilingprocedure}VARx,y,z:integer; a:integer;BEGIN{Thisprogramhasonly4statement}x:=23+5;z:=xDIV-3;y:=z+18*3;a:=x+(y-2)DIV4;END.第八頁(yè)，共十九頁(yè)，2022年，8月28日1.2.1詞法分析程序（掃描器）詞法分析程序的任務(wù)是：1）識(shí)別出源程序的各個(gè)基本語(yǔ)法單位（單詞或語(yǔ)法符號(hào)）2）刪除無(wú)用的空白字符及其它與輸入介質(zhì)相關(guān)的非實(shí)質(zhì)性字符（空格、回車(chē)等）3）刪除注釋4）進(jìn)行詞法檢查，報(bào)告所發(fā)現(xiàn)的錯(cuò)誤掃描器依次查看緩沖區(qū)中源程序的各字符，根據(jù)當(dāng)前正查看的字符之種類，并參考掃描過(guò)程中已得到的信息，就能判斷出該字符在源程序中所處地位。一般它是下述幾種情況之一：1）正處理的注釋中的一個(gè)字符；2）無(wú)用字符；3）下一個(gè)單詞的首字符；4）正識(shí)別的單詞中的一個(gè)字符；5）不合法的字符。掃描器輸出以單詞為單位的單詞流例如，以特殊符號(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#.#第九頁(yè)，共十九頁(yè)，2022年，8月28日單詞流的內(nèi)部表示注意，前面的單詞流形式只是我們?yōu)檎f(shuō)明原理便于閱讀而假定的形式。為了讓計(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,‘.’)第十頁(yè)，共十九頁(yè)，2022年，8月28日1.2.2語(yǔ)法分析程序（分析器）語(yǔ)法分析程序以詞法分析程序輸出的單詞流為輸入，分析源程序的結(jié)構(gòu)，判斷它是否為相應(yīng)程序設(shè)計(jì)語(yǔ)言的合法程序。方法：試圖為源程序構(gòu)造一個(gè)語(yǔ)法樹(shù)。分析工作是在相應(yīng)程序設(shè)計(jì)語(yǔ)言的語(yǔ)法規(guī)則指導(dǎo)下進(jìn)行的。語(yǔ)法規(guī)則描述了該語(yǔ)言的各種語(yǔ)成份的組成結(jié)構(gòu)。所謂語(yǔ)法樹(shù)只是邏輯概念上的，并不是在機(jī)器內(nèi)真要存儲(chǔ)一個(gè)樹(shù)形結(jié)構(gòu)。第十一頁(yè)，共十九頁(yè)，2022年，8月28日1.2.3語(yǔ)義分析程序一程序設(shè)計(jì)語(yǔ)言具有語(yǔ)法和語(yǔ)義兩個(gè)特征。語(yǔ)法特征描述各成份的形式或結(jié)構(gòu)；語(yǔ)義特征描述各語(yǔ)法成份的含義與功能，即規(guī)定它們的屬性或在執(zhí)行應(yīng)進(jìn)行的運(yùn)算或操作。因此，只有進(jìn)行了語(yǔ)義分析，才能讓計(jì)算機(jī)知道，應(yīng)進(jìn)行何操作或運(yùn)算。在進(jìn)行語(yǔ)義分析時(shí)還應(yīng)進(jìn)行相應(yīng)的語(yǔ)義檢查（類型匹配、矛盾說(shuō)明、參數(shù)匹配等）。語(yǔ)義處理尚無(wú)公認(rèn)的方法來(lái)系統(tǒng)地描述。當(dāng)前較通用的方法是半機(jī)械化的“語(yǔ)法制導(dǎo)翻譯”方法。第十二頁(yè)，共十九頁(yè)，2022年，8月28日

中間代碼生成為了處理方便和便于代碼優(yōu)化，在語(yǔ)義分析后通常并不直接產(chǎn)生目標(biāo)代碼，而是生成介于二者之間的中間代碼。常見(jiàn)的~有：逆波蘭式、三元式、四元式及樹(shù)形結(jié)構(gòu)等。例如，source程序中的第四條賦值語(yǔ)句相應(yīng)的逆波蘭式可寫(xiě)成：axy2-div+:=source程序相應(yīng)的四元式表示為：(prologue,’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)第十三頁(yè)，共十九頁(yè)，2022年，8月28日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)和無(wú)關(guān)兩類優(yōu)化指標(biāo)有時(shí)是相互矛盾的，應(yīng)根據(jù)具體情況進(jìn)行取舍和側(cè)重source程序優(yōu)化后結(jié)果：(prologue,’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)第十四頁(yè)，共十九頁(yè)，2022年，8月28日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)程序；（3）模塊結(jié)構(gòu)的機(jī)器指令（浮動(dòng)地址）。Source程序?qū)?yīng)的80386匯編程序見(jiàn)書(shū)中P9第十五頁(yè)，共十九頁(yè)，2022年，8月28日1.2.7錯(cuò)誤檢查和處理程序程序中出現(xiàn)錯(cuò)誤是難免的。一完善的編譯程序應(yīng)具有很強(qiáng)的查錯(cuò)能力，并能準(zhǔn)確地報(bào)告源程序中錯(cuò)誤的種類及位置。除報(bào)錯(cuò)外，編譯程序還可生成一些另外的注釋信息，它有助于程序設(shè)計(jì)人員調(diào)試程序。常見(jiàn)的輔助手段根據(jù)請(qǐng)求輸出“對(duì)照?qǐng)D”和各變量的值。Source程序的對(duì)照?qǐng)D，見(jiàn)P10表1-2第十六頁(yè)，共十九頁(yè)，2022年，8月28日1.2.8信息表管理程序編譯過(guò)程中，需經(jīng)常收集、記錄或查詢程序中所出現(xiàn)的各種量的有關(guān)屬性（信息）。為此，編譯程序需要建立一批不同用途的表格（常數(shù)表、變量表、關(guān)鍵字表等）除此