《編譯原理》第一章 cha1 引論

1第一章引論1.1編譯程序和解釋程序1.2編譯過程和編譯程序的結(jié)構(gòu)（重點(diǎn)）1.2.1編譯過程概述1.2.2編譯程序結(jié)構(gòu)1.2.3編譯階段的組合1.3編譯程序在其他軟件中的應(yīng)用1.4程序設(shè)計(jì)語言范型1.5編譯程序?qū)崿F(xiàn)途徑（可略）本章練習(xí)作業(yè)課程目錄21.1什么是編譯程序p1編譯程序的必要性計(jì)算機(jī)是當(dāng)代科學(xué)發(fā)展的重要工具，已滲入到各個(gè)行業(yè)乃至家庭生活中要讓計(jì)算機(jī)為人類工作服務(wù)，就必須建立人與計(jì)算機(jī)之間的信息交流但計(jì)算機(jī)只認(rèn)識(shí)由“0”和“1”構(gòu)成的機(jī)器語言，每臺(tái)機(jī)器都有自己獨(dú)特的指令系統(tǒng)，即機(jī)器語言最早的程序就是用8進(jìn)制和16進(jìn)制碼的機(jī)器語言書寫的3編譯程序的必要性（續(xù)）用機(jī)器語言書寫程序，不僅不易學(xué)，而且可調(diào)試性、可讀性、可維護(hù)性和結(jié)構(gòu)性都很差，開發(fā)時(shí)間也很長(zhǎng)因此，先后出現(xiàn)了用于源程序設(shè)計(jì)的語言：基于助記符的匯編語言接近人類自然語言的高級(jí)程序設(shè)計(jì)語言編譯程序最初的定義是把一種高級(jí)語言設(shè)計(jì)的源程序(面向人的)翻譯成另一種等價(jià)的低級(jí)程序設(shè)計(jì)語言(面向硬件的)即機(jī)器語言或匯編語言4程序設(shè)計(jì)語言源程序的執(zhí)行方式程序設(shè)計(jì)語言源程序的執(zhí)行基本有兩種方式翻譯使用翻譯程序，將源程序翻譯成為低級(jí)語言目標(biāo)程序，然后執(zhí)行目標(biāo)程序解釋

使用解釋程序，對(duì)源程序逐個(gè)語句邊解釋邊執(zhí)行可比喻為譯文—目標(biāo)程序翻譯—筆譯(產(chǎn)生譯文，可進(jìn)行優(yōu)化，一次翻譯過后，多次使用)解釋—口譯(不產(chǎn)生譯文，交互方便，節(jié)省空間，對(duì)重復(fù)部分要反復(fù)解釋，效率低）5翻譯程序和解釋程序圖解源程序(源語言)翻譯程序目標(biāo)程序(目標(biāo)語言)源程序(源語言)解釋程序輸入輸出共同點(diǎn)：都需進(jìn)行詞法、語法和語義分析6程序設(shè)計(jì)語言源程序的執(zhí)行方式例假設(shè)有源程序：read(x);write("x=",x);read(x);write("x=",x);目標(biāo)程序目標(biāo)程序3X=3read(x);write("x=",x);翻譯程序解釋程序3X=37翻譯程序的分類翻譯程序按所處理源語言不同分為兩種

編譯程序

匯編程序高級(jí)語言源程序(*.C/*.PAS)編譯程序匯編或機(jī)器語言目標(biāo)程序(*.OBJ/*.EXE)匯編語言源程序(*.ASM)匯編程序機(jī)器語言目標(biāo)程序(*.EXE)8編譯程序和解釋程序p8最主要區(qū)別是否生成目標(biāo)程序運(yùn)行時(shí)的存儲(chǔ)分配源程序緩沖區(qū)名字表目標(biāo)代碼緩沖區(qū)編譯程序用中間表示及各種表格目標(biāo)代碼區(qū)數(shù)據(jù)區(qū)解釋系統(tǒng)源程序工作單元及名字表標(biāo)號(hào)表緩沖區(qū)（輸入輸出）棧區(qū)編譯程序編譯時(shí)和運(yùn)行時(shí)存儲(chǔ)區(qū)內(nèi)容解釋程序存儲(chǔ)區(qū)內(nèi)容9編譯程序和解釋程序Basic、Lisp、Sql解釋程序、Unix命令語言解釋程序及很多腳本語言Javascript等都解釋執(zhí)行的。C、C++、Pascal等語言是編譯執(zhí)行的。Java語言的處理環(huán)境既有編譯程序，也有解釋程序，見圖1.5(p9)Java→編譯程序→Bytecode→解釋程序10高級(jí)語言程序

的處理過程P1需預(yù)處理的源程序預(yù)處理程序源程序編譯程序目標(biāo)匯編程序匯編程序可再裝配的機(jī)器代碼裝配/連接-編譯程序可再裝配目標(biāo)文件絕對(duì)機(jī)器代碼章節(jié)目錄111.2.1編譯過程概述p2編譯過程可分為下面5個(gè)階段詞法分析語法分析語義分析和中間代碼生成優(yōu)化目標(biāo)代碼生成表格管理和錯(cuò)誤處理12第一階段詞法分析p2任務(wù)輸入源程序(字符串)根據(jù)語言的詞法規(guī)則對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解識(shí)別出一個(gè)個(gè)的單詞單詞內(nèi)部表示形式二元式(class,value)

單詞類型單詞值例某C語言源程序main(){floatsum,first,count;

…sum=first+count*10;…}輸出結(jié)果

classvalue

保留字main界符-左括號(hào)(界符-右括號(hào))界符-左花括號(hào){保留字float標(biāo)識(shí)符1-id1sum…

算符-乘號(hào)*整數(shù)10…

13第二階段語法分析p3

任務(wù)輸入單詞符號(hào)串根據(jù)語言的語法規(guī)則對(duì)單詞符號(hào)串進(jìn)行掃描和分解識(shí)別出各類語法單位程序語言的語法單位表達(dá)式、語句和程序等例X1=Y+10*Z;C語言賦值語句構(gòu)成規(guī)則<賦值語句>→<標(biāo)識(shí)符>=<表達(dá)式>;定義為<表達(dá)式>→<表達(dá)式>+<表達(dá)式><表達(dá)式>→<表達(dá)式>*<表達(dá)式><表達(dá)式>→<標(biāo)識(shí)符>X1,Y,Z<表達(dá)式>→<常數(shù)>10可以構(gòu)成語法單位的單詞符號(hào)語法單位表達(dá)式Y(jié),10,Z,10*Z

賦值語句X1=Y+10*Z;語法單位內(nèi)部表示語法樹

14語法單位的內(nèi)部表示：語法樹例某C語言源程序main(){floatsum,first,count;

…sum=first+count*10;…}<賦值語句>→<標(biāo)識(shí)符>=<表達(dá)式>;<表達(dá)式>→<表達(dá)式>+<表達(dá)式><表達(dá)式>→<表達(dá)式>*<表達(dá)式><表達(dá)式>→<標(biāo)識(shí)符><表達(dá)式>→<常數(shù)>賦值語句的語法樹<賦值語句><標(biāo)識(shí)符>=<表達(dá)式>;sum<表達(dá)式>+<表達(dá)式><標(biāo)識(shí)符>first<表達(dá)式>*<表達(dá)式><標(biāo)識(shí)符>count<常數(shù)>1015第三階段語義分析與中間代碼產(chǎn)生p4任務(wù)輸入各類語法范疇根據(jù)語言的語義規(guī)則，分析其含義，并進(jìn)行初步翻譯產(chǎn)生中間代碼結(jié)構(gòu)簡(jiǎn)單、含義明確的記號(hào)系統(tǒng)介于高級(jí)語言與低級(jí)語言之間，與目標(biāo)機(jī)無關(guān)便于優(yōu)化、移植，容易生成目標(biāo)代碼形式有：三元式、四元式、樹結(jié)構(gòu)等。16中間代碼生成舉例中間代碼生成（四元式）

例：語義分析將

sum=first+count*10；翻譯成如下的四元式序列：(1)(inttofloat,10,_，T1)(2)(*,count，T1，T2)(3)(+,first，T2，T3)(4)(=,T3,_,sum)其中，Ti為語義分析程序?yàn)榇娣胖虚g結(jié)果而生成的臨時(shí)變量例某C語言源程序main(){floatsum,first,count;

…sum=first+count*10;

…}17第四階段優(yōu)化p5任務(wù)輸入中間代碼進(jìn)行等價(jià)變換輸出更高效的中間代碼目的用以提高目標(biāo)代碼的時(shí)、空效率也就是希望完成同樣功能的程序，代碼優(yōu)化后比優(yōu)化前運(yùn)行的時(shí)間短，占用的存儲(chǔ)空間少有時(shí)二者不能同時(shí)達(dá)到，需根據(jù)實(shí)際情況取舍18優(yōu)化舉例優(yōu)化前

(1)(inttofloat,10,_，T1)(2)(*,count，T1，T2)(3)(+,first，T2，T3)(4)(=,T3,-,sum)優(yōu)化后

常數(shù)直接代入(*,count,10.0,T1)節(jié)省臨時(shí)變量(+,first,T1,sum)

優(yōu)化后有兩條代碼整數(shù)轉(zhuǎn)換成實(shí)數(shù)在編譯時(shí)完成臨時(shí)變量只用了一個(gè)T119第五階段目標(biāo)代碼生成p5任務(wù)輸入優(yōu)化后的中間代碼變換成特定機(jī)器上的低級(jí)語言代碼，實(shí)現(xiàn)最后的翻譯產(chǎn)生目標(biāo)代碼特點(diǎn)依賴與機(jī)器硬件系統(tǒng)通常使用匯編語言作為目標(biāo)程序的實(shí)現(xiàn)語言20目標(biāo)代碼生成舉例為了生成高效的目標(biāo)代碼，需要了解機(jī)器指令系統(tǒng)和可用計(jì)算機(jī)資源，假設(shè)有兩個(gè)可用寄存器R0和R1優(yōu)化后中間代碼(1)(*,count,10.0,T1)(2)(+,first,T1,sum）生成的目標(biāo)代碼序列(1)LDR0,count

count值送R0(2)MULR0,#10.0

計(jì)算count*10.0存于R0(3)LDR1,first

first值送R1(4)ADDR1，R0

計(jì)算first+T1存于R121表格管理(符號(hào)表管理)任務(wù)在完成以上5個(gè)過程的同時(shí)必須隨時(shí)對(duì)符號(hào)表進(jìn)行管理記錄源程序中使用的名字收集每個(gè)名字的各種屬性信息如類型、作用域、存儲(chǔ)分配信息等例count變量類型float

first變量類型float地址22出錯(cuò)處理任務(wù)發(fā)現(xiàn)源程序中的錯(cuò)誤檢查詞法、語法和語義中的錯(cuò)誤(靜態(tài))編譯程序的處理能力，如存儲(chǔ)空間越界(動(dòng)態(tài))報(bào)告出錯(cuò)信息和位置處理和恢復(fù)章節(jié)目錄231.2.2編譯程序的結(jié)構(gòu)p6詞法分析程序語法分析程序語義分析程序與中間代碼產(chǎn)生器優(yōu)化器目標(biāo)代碼生成器表格管理出錯(cuò)處理7個(gè)或8個(gè)部分組成24編譯程序

結(jié)構(gòu)框圖P6源程序字符串詞法分析器單詞符號(hào)語法分析器語法單位語義分析程序語法樹中間代碼生成器四元式代碼優(yōu)化程序四元式目標(biāo)代碼生成器匯編語言或機(jī)器語言目標(biāo)程序信息表格管理程序錯(cuò)誤檢查和處理程序章節(jié)目錄251.2.3編譯階段的組合p6

前端完成分析工作(與機(jī)器無關(guān))詞法分析語法分析語義分析后端完成綜合工作(與機(jī)器相關(guān))優(yōu)化：改善目標(biāo)代碼質(zhì)量目標(biāo)代碼生成前端源程序中間代碼后端目標(biāo)代碼目的便于移植前端和后端的概念26遍的概念p6遍從頭到尾對(duì)源程序及其內(nèi)部表示掃描一次，并作有關(guān)的加工處理遍輸入文件輸出文件從源程序掃描是第一遍輸入每前一遍的輸出是后一遍的輸入分遍的原則按實(shí)際情況而定多遍（結(jié)構(gòu)清晰、少占內(nèi)存、讀寫次數(shù)多，耗時(shí)）一遍（多占內(nèi)存，速度快）章節(jié)目錄271.3編譯程序在其它軟件中的應(yīng)用p8語言的結(jié)構(gòu)化編輯器（提示輸入關(guān)鍵字、完成括號(hào)匹配等）語言程序的調(diào)試工具程序格式化工具（以清晰可讀方式打印程序）軟件測(cè)試工具：如FORTRAN，C的靜態(tài)和動(dòng)態(tài)測(cè)試工具（可測(cè)試程序語句的覆蓋率、路徑覆蓋率等，都需要編譯技術(shù)）高級(jí)程序設(shè)計(jì)語言的轉(zhuǎn)換工具程序理解工具（OlinkC\C++數(shù)據(jù)流分析

、EclipseTptp性能分析工具）網(wǎng)絡(luò)中的協(xié)議數(shù)據(jù)庫系統(tǒng)中各種命令語言的翻譯28

編譯程序在系統(tǒng)軟件中的所在層裸機(jī)操作系統(tǒng)語言處理系統(tǒng)應(yīng)用軟件層章節(jié)目錄1.4程序設(shè)計(jì)語言范型p1029強(qiáng)制式語言ImperativeFORTRAN、BASIC、Pascal、C函數(shù)式語言

FunctionalLISP、ML邏輯式語言LogicalProlog面向?qū)ο笳Z言

Object-OrientedSmalltalk、C++、Java、Ada章節(jié)目錄301.5編譯程序的實(shí)現(xiàn)途徑p302應(yīng)考慮開發(fā)周期、目標(biāo)程序的效率、可移植性、可調(diào)試性、可維護(hù)性和可擴(kuò)充性等構(gòu)造方式手工構(gòu)造用機(jī)器語言、匯編語言或高級(jí)程序設(shè)計(jì)語言書寫自動(dòng)構(gòu)造工具Lex，Yacc分別是詞法和語法分析器的生成器移植方式目標(biāo)程序用中間語言自展方式(自編譯方式)用T型圖表示31T型圖STI源語言目標(biāo)語言編譯程序?qū)崿F(xiàn)語言含義S語言源程序I語言實(shí)現(xiàn)編譯程序

T語言目標(biāo)程序32編譯程序設(shè)計(jì)舉例已知A機(jī)器上C語言編譯程序CAAC語言編譯程序要求用C語言編寫PASCAL語言A機(jī)器編譯程序PLAAPASCAL語言編譯程序最初用C語言編寫PLACC語言編寫的PASCAL語言編譯程序CAAAPLA所求PASCAL語言編譯程序33編譯程序設(shè)計(jì)L1AA已知A機(jī)器上有L1

語言編譯程序要求用L1語言編寫L2語言的A機(jī)器編譯程序L2AAL2AL1L1AAL2AA所求L2語言編譯程序34PC機(jī)器上C語言編譯程序自展設(shè)計(jì)實(shí)現(xiàn)目標(biāo)CPCPC步驟1(1)先對(duì)C語言核心部分C1構(gòu)造

PC編譯程序，用低級(jí)語言實(shí)現(xiàn)C1PCPC(2)再用C1編寫含C更多語言成分的C2的PC編譯程序C2PCC1(3)最后用C2編寫

C語言的PC編譯程序CPCC2其中C1是C2的子集，C2是C的子集35PC機(jī)器上C語言編譯程序自展設(shè)計(jì)實(shí)現(xiàn)目標(biāo)CPCPC步驟2構(gòu)造C2的PC編譯程序C2PCC1C1PCPCC2PCPC步驟3構(gòu)造C的PC編譯程序CPCC2C2PCPCCPCPC合并步驟2，3C2PCC1C1PCPC①②③④⑤36L語言編譯程序移植設(shè)計(jì)已知A機(jī)器高級(jí)語言L編譯程序要求B機(jī)器高級(jí)語言L的編譯程序已知LAA實(shí)現(xiàn)目標(biāo)LBB①LAA②LBL用L語言編寫的L→B的編譯程序③LBA用A機(jī)器語言實(shí)現(xiàn)的L→B的編譯程序④LBL用L語言編寫的L→B編譯程序翻譯⑤LBB用B機(jī)器語言實(shí)現(xiàn)的L→B的編譯程序章節(jié)目錄37編譯程序的分類p1診斷型編譯程序(DiagnosticCompiler)專門用于幫助程序開發(fā)和調(diào)試著重提高目標(biāo)代碼效率優(yōu)化型編譯程序(OptimizingCompiler)提供調(diào)試、優(yōu)化等功能，用戶進(jìn)行選擇使用交叉型編譯程序(CrossCompiler)產(chǎn)生不同于其宿主機(jī)的目標(biāo)機(jī)機(jī)器代碼運(yùn)行編譯程序的機(jī)器運(yùn)行所產(chǎn)生目標(biāo)代碼的機(jī)器可變目標(biāo)型編譯程序(RetargetableCompiler)不需重寫編譯程序中與機(jī)器無關(guān)的部分就能改變目標(biāo)機(jī)章節(jié)目錄38本章練習(xí)

1、編譯程序的結(jié)構(gòu)可以分成以下7個(gè)模塊