1第1章編譯程序概論§1.1什么是編譯程序語(yǔ)言低級(jí)高級(jí)：FORTRAN,PASCAL，C，C++等機(jī)器語(yǔ)言匯編語(yǔ)言翻譯機(jī)器語(yǔ)言程序匯編程序Assembler編譯程序Compiler源程序SourceProgram目標(biāo)程序ObjectProgram匯編語(yǔ)言程序高級(jí)語(yǔ)言程序Translator2§1.1什么是編譯程序編譯程序:把源程序翻譯(轉(zhuǎn)換)成等價(jià)的目標(biāo)程序的程序

其轉(zhuǎn)換過(guò)程可圖示如下：編譯程序高級(jí)語(yǔ)言程序（源程序）低級(jí)語(yǔ)言程序（目標(biāo)程序）黑盒子說(shuō)明：除編譯程序自身外，多數(shù)編譯系統(tǒng)還需要一些其他的輔助程序來(lái)幫助完成其最終的翻譯(轉(zhuǎn)換)工作。

3§1.1什么是編譯程序（典型）高級(jí)語(yǔ)言程序的處理過(guò)程：需預(yù)處理的源程序預(yù)處理程序

編譯程序

源程序目標(biāo)匯編語(yǔ)言程序

匯編程序可再裝配的機(jī)器代碼

編輯(裝配/連接)程序絕對(duì)機(jī)器代碼可再裝配目標(biāo)文件objexe函數(shù)子程序4§1.1什么是編譯程序例：C語(yǔ)言需預(yù)處理的源程序

/*文件名：example.c*/#include"stdio.h"#defineCHARACTERcharmain(){CHARACTERch;ch=getchar();putchar(ch);}5§1.1什么是編譯程序經(jīng)預(yù)處理程序“CPP.EXE”處理后得如下源程序DOS命令為：cppexample.c

結(jié)果文件名：example.Iexample.c1:main()example.c2:{example.c3:charch;example.c4:ch=((--(((&_streams[0]))->level)>=0)?(unsignedchar)(++((&_streams[0]))->curp)[-1]:_fgetc((&_streams[0])));example.c5:((++(((&_streams[1]))->level)<0)?(unsignedchar)((++((&_streams[1]))->curp)[-1]=((ch))): _fputc(((ch)),(&_streams[1])));example.c6:}6§1.1什么是編譯程序可再裝配的obj文件:----------------------……

調(diào)用sin子程序

……

調(diào)用printf子程序

……

-----------Sin()Cos()…Scanf()Printf()…函數(shù)子程序庫(kù)裝配/連接程序Sin字程序裝配Printf子程序裝配連接連接7§1.2編譯過(guò)程和編譯程序的結(jié)構(gòu)概述一、編譯過(guò)程概述

典型編譯程序工作過(guò)程：源程序詞法分析語(yǔ)法分析語(yǔ)義分析代碼優(yōu)化目標(biāo)程序中間代碼生成目標(biāo)代碼生成8§1.2編譯過(guò)程和編譯程序的結(jié)構(gòu)概述--編譯過(guò)程概述詞法分析主要任務(wù)：掃描源程序的ASCII碼序列，識(shí)別出一個(gè)個(gè)單詞(也稱單詞符號(hào)或（語(yǔ)法）符號(hào))。具體任務(wù)：1.拼單詞:組合分解源程序中的字符,得到符合語(yǔ)言詞法規(guī)則的單詞。例如某源程序片斷如下：

beginvarsum，first，count：real；sum:=first+count*10end．詞法分析將其視為字符（ASCII碼）序列：begin,varsumt*10?end組合分解成單詞符號(hào)序列：*10end?beginvarsum,firstcount92.翻譯單詞：將單詞加工成含有特征/屬性的機(jī)內(nèi)表示（機(jī)內(nèi)符）例如：上述源程序片斷的詞法分析的結(jié)果為如下二元組序列：

1．保留字begin2．保留字var3．標(biāo)識(shí)符sum4．逗號(hào)，

5．標(biāo)識(shí)符first6．逗號(hào)，

7．標(biāo)識(shí)符count8．冒號(hào)：

9．保留字real10．分號(hào)；

11．標(biāo)識(shí)符sum12．賦值號(hào):=13．標(biāo)識(shí)符first14．加號(hào)+15．標(biāo)識(shí)符count16．乘號(hào)*

17．整數(shù)1018．保留字end19．界符·§1.2編譯過(guò)程和編譯程序的結(jié)構(gòu)概述--編譯過(guò)程概述103．詞法檢查：檢查詞法錯(cuò)誤（主要是檢查單詞中使用了非法字符錯(cuò)誤）例如：beg#n@nd~^10$等等

4．刪除空白符、注釋等

語(yǔ)法分析任務(wù)：1.對(duì)單詞（機(jī)內(nèi)符）序列進(jìn)行分析，組合分解出各類語(yǔ)法單位（語(yǔ)法短語(yǔ)）例如：用id代表標(biāo)識(shí)符，則有：

11．標(biāo)識(shí)符sum12．賦值號(hào):=表達(dá)式

13．標(biāo)識(shí)符first14．加號(hào)+id1:=id2+id3*1015．標(biāo)識(shí)符count16．乘號(hào)*賦值語(yǔ)句

17．整數(shù)10§1.2編譯過(guò)程和編譯程序的結(jié)構(gòu)概述--編譯過(guò)程概述112．檢查形式語(yǔ)法錯(cuò)誤

例如：Y=A+B；//PASCAL賦值語(yǔ)句其賦值號(hào)應(yīng)為:=Y:=IF*Y；//PASCAL中用保留字作為標(biāo)識(shí)符來(lái)使用

a=b++c；//C中兩個(gè)子表達(dá)式之間沒(méi)有運(yùn)算符

if=x+y；//C中條件語(yǔ)句出錯(cuò)

(x+y))*z；//C中括號(hào)不配對(duì)等等說(shuō)明：關(guān)于書(shū)中在這里引進(jìn)的有關(guān)語(yǔ)言的“遞歸規(guī)則定義”和“語(yǔ)法樹(shù)”相關(guān)知識(shí)，我們暫不討論?！?.2編譯過(guò)程和編譯程序的結(jié)構(gòu)概述--編譯過(guò)程概述12

語(yǔ)義分析任務(wù)：檢查(靜態(tài))語(yǔ)義錯(cuò)誤，提取語(yǔ)義信息。其中：語(yǔ)義錯(cuò)誤分為靜態(tài)和動(dòng)態(tài)兩種.

靜態(tài)語(yǔ)義錯(cuò)誤：在編譯期間可以檢查的語(yǔ)義錯(cuò)誤例如：int*px,*py,i;

…px+py…;//兩個(gè)運(yùn)算對(duì)象類型不相容

…a[i]…;//a沒(méi)有聲明

gotoloop;//loop沒(méi)有定義等等(即獨(dú)立的觀察一條語(yǔ)句看不出的錯(cuò)誤)

動(dòng)態(tài)語(yǔ)義錯(cuò)誤：在目標(biāo)程序運(yùn)行時(shí)才可以檢查的語(yǔ)義錯(cuò)誤。例如：sqrt(x)//當(dāng)x為負(fù)數(shù)時(shí)

1/x//當(dāng)x為0時(shí)

fopen(pf,”r”)//文件如果不存在語(yǔ)義信息包括：標(biāo)識(shí)符的“種類”、“類型”等信息§1.2編譯過(guò)程和編譯程序的結(jié)構(gòu)概述--編譯過(guò)程概述13

中間代碼生成中間代碼：介于源程序和目標(biāo)程序之間的一種結(jié)構(gòu)簡(jiǎn)單、含義明確的記號(hào)系統(tǒng)。如：逆波蘭式、三元式、四元式、樹(shù)形結(jié)構(gòu)表示等例如：源程序（賦值語(yǔ)句）sum:=first+count*10所對(duì)應(yīng)的四元式序列如下：

(inttoreal,10,_,t1)(*,id3,t1,t2)(+,id2,t2,t3)(:=,t3,_,id1)源程序中間代碼目標(biāo)程序目的：方便加工，便于優(yōu)化。設(shè)計(jì)原則：容易生成，容易將其翻譯成目標(biāo)代碼§1.2編譯過(guò)程和編譯程序的結(jié)構(gòu)概述14§1.2編譯過(guò)程和編譯程序的結(jié)構(gòu)概述--編譯過(guò)程概述

中間代碼優(yōu)化：為得到高質(zhì)量的目標(biāo)代碼而進(jìn)行的變換工作任務(wù)：把原中間代碼轉(zhuǎn)換成可產(chǎn)生高質(zhì)量（省時(shí)間和省空間）目標(biāo)代碼的中間代碼。例如：

(inttoreal,10,_,t1)(*,id3,t1,t2)(*,id3,10.0,t1)(+,id2,t2,t3)(+,id2,t1,id1)(:=,t3,_,id1)優(yōu)化優(yōu)化方式局部?jī)?yōu)化全局優(yōu)化優(yōu)化種類常表達(dá)式的優(yōu)化公共子表達(dá)式的優(yōu)化循環(huán)優(yōu)化消減運(yùn)算強(qiáng)度15

目標(biāo)代碼生成任務(wù)：把中間代碼或語(yǔ)義分析的結(jié)果轉(zhuǎn)換成目標(biāo)代碼程序目標(biāo)代碼的三種形式：1.絕對(duì)指令代碼：具有絕對(duì)地址的機(jī)器指令代碼，無(wú)需連接即可運(yùn)行。2.可重定位的指令代碼：具有浮動(dòng)地址的機(jī)器指令代碼，需連接裝配后方能運(yùn)行。3.匯編指令代碼：匯編語(yǔ)言形式的目標(biāo)程序，需經(jīng)匯編程序匯編產(chǎn)生相應(yīng)的機(jī)器代碼。MOVFid3R2MULF#10.0R2MOVFid2R1ADDFR1R2MOVR1id1(*,id3,10.0,t1)(+,id2,t1,id1)生成例如：使用兩個(gè)寄存器R1、R2，則可有：§1.2編譯過(guò)程和編譯程序的結(jié)構(gòu)概述--編譯過(guò)程概述16二、編譯程序的結(jié)構(gòu)表格管理程序出錯(cuò)處理程序

源程序詞法分析程序語(yǔ)法分析程序語(yǔ)義分析程序代碼優(yōu)化程序

目標(biāo)程序中間代碼生成程序目標(biāo)代碼生成程序§1.2編譯過(guò)程和編譯程序的結(jié)構(gòu)概述17三、編譯階段的組合其組合具體實(shí)現(xiàn)上可從以下兩個(gè)角度來(lái)考慮1．前端(frontend)和后端(backend)與目標(biāo)機(jī)無(wú)關(guān)的工作前端詞法分析語(yǔ)法分析語(yǔ)義分析中間代碼生成中間代碼優(yōu)化后端：只與目標(biāo)機(jī)有關(guān)的工作，即目標(biāo)代碼中間代碼優(yōu)點(diǎn)：便于移植(在不同機(jī)器或不同語(yǔ)言之間使用)其中：前端可用于在不同機(jī)器開(kāi)發(fā)相同語(yǔ)言的編譯程序后端可用于在同一臺(tái)機(jī)器上開(kāi)發(fā)不同語(yǔ)言的編譯程序§1.2編譯過(guò)程和編譯程序的結(jié)構(gòu)概述--編譯程序的結(jié)構(gòu)18一遍掃描的優(yōu)點(diǎn)：編譯的速度快多遍掃描的優(yōu)點(diǎn)：算法清晰，便于分工，便于優(yōu)化設(shè)：COMP編譯程序則有：2.分遍(或趟)：是指對(duì)源程序或?qū)ζ涞葍r(jià)的中間語(yǔ)言程序從頭至尾掃視并完成規(guī)定任務(wù)的過(guò)程（此過(guò)程稱為掃描）。編譯程序按掃描遍數(shù)分為：一遍掃描多遍掃描§1.2編譯過(guò)程和編譯程序的結(jié)構(gòu)概述--編譯程序的結(jié)構(gòu)19

語(yǔ)法分析程序COMP

詞法分析程序

語(yǔ)義分析及代碼生成程序取單詞送單詞語(yǔ)法結(jié)構(gòu)返回源程序目標(biāo)程序一遍掃描的編譯程序的工作流程：/*語(yǔ)法分析為合心*/§1.2編譯過(guò)程和編譯程序的結(jié)構(gòu)概述--編譯程序的結(jié)構(gòu)20COMPCOMPnCOMP3COMP2COMP1L0L1L2L3Ln-1Ln源程序中間語(yǔ)言程序目標(biāo)程序多遍掃描的編譯程序的工作流程：§1.2編譯過(guò)程和編譯程序的結(jié)構(gòu)概述--編譯程序的結(jié)構(gòu)21§1.3解釋程序和一些軟件工具源程序初始數(shù)據(jù)解釋程序計(jì)算結(jié)果一、解釋程序

?解釋程序(Interpreter):其工作方式是邊翻譯邊執(zhí)行，其加工的結(jié)果是源程序的運(yùn)行結(jié)果。解釋程序工作方式：22編譯程序和解釋程序的不同工作模式對(duì)比：§1.3解釋程序和一些軟件工具—解釋程序解釋程序編譯程序……b:=2;a:=b+2;writea;……MOV#2.0R1MOVR1bMOVbR2ADDR1R2MOVR1a直接將4的值輸出（顯示）23編譯程序和解釋程序的不同存儲(chǔ)區(qū)及內(nèi)容對(duì)比編譯階段和運(yùn)行階段存儲(chǔ)區(qū)內(nèi)容：§1.3解釋程序和一些軟件工具—解釋程序源程序緩沖區(qū)名字表目標(biāo)代碼緩沖區(qū)編譯程序用中間表示及各種表格目標(biāo)代碼區(qū)數(shù)據(jù)區(qū)解釋系統(tǒng)源程序工作單元及名字表標(biāo)號(hào)表緩沖區(qū)（輸入輸出）棧區(qū)

解釋程序的存儲(chǔ)區(qū)內(nèi)容：運(yùn)行時(shí)編譯時(shí)2410PRINT“X,Y=?”20INPUTX,Y30IFX<YTHEN6040LETZ=Y-X50GOTO7060LETZ=X-Y70PRINT“Z=“,Z80ENDBASIC語(yǔ)言程序直接解釋源程序工作過(guò)程：PrintInputAssig子程序n子程序3子程序2子程序1主程序…§1.3解釋程序和一些軟件工具—解釋程序25編譯+解釋其工作過(guò)程：§1.3解釋程序和一些軟件工具—解釋程序Java源程序（.java）Java編譯程序JavaBYTECODES（.class）JavaBYTECODES（來(lái)自本地的或經(jīng)由網(wǎng)絡(luò)的）編譯環(huán)境類裝載器BYTECODES驗(yàn)證器Java類庫(kù)解釋程序即時(shí)編譯程序硬件Java虛擬機(jī)運(yùn)行環(huán)境（Java平臺(tái)）261.語(yǔ)言的結(jié)構(gòu)化編輯器（或稱智能化編輯器）即編輯器具有檢查簡(jiǎn)單語(yǔ)法錯(cuò)誤的功能如：括弧配對(duì)檢查，關(guān)鍵字組合檢查等2.語(yǔ)言程序的調(diào)試工具調(diào)試（或稱糾錯(cuò)）：是在測(cè)試發(fā)現(xiàn)錯(cuò)誤之后排錯(cuò)的過(guò)程如：debug等3.程序格式化工具格式化：使在編輯窗口中輸入的源程序具有一定的清晰可讀的結(jié)構(gòu)形式加以顯示。如：關(guān)鍵字顯示采用非黑色（如：藍(lán)色）；注釋可以用一種專門(mén)的字體或顏色顯示；語(yǔ)句的嵌套層次結(jié)構(gòu)可用縮排方式表示。等等二、處理源程序的軟件工具§1.3解釋程序和一些軟件工具274.語(yǔ)言程序測(cè)試工具靜態(tài)分析器基于源程序（不運(yùn)行其目標(biāo)程序）進(jìn)行分析，以發(fā)現(xiàn)程序中潛在的錯(cuò)誤或異常等。其目的是，檢查編譯程序的語(yǔ)法分析發(fā)現(xiàn)不了的錯(cuò)誤。如：檢查變量定值與引用的關(guān)系；多余的源代碼等。動(dòng)態(tài)測(cè)試器基于源程序（運(yùn)行其目標(biāo)程序）進(jìn)行分析，以發(fā)現(xiàn)程序中存在的邏輯錯(cuò)誤等。其目的是，檢查編譯程序的語(yǔ)法分析和語(yǔ)義分析均發(fā)現(xiàn)不了的錯(cuò)誤。其中包括：白盒測(cè)試(測(cè)試路徑)；黑盒測(cè)試(測(cè)試結(jié)果)§1.3解釋程序和一些軟件工具—處理源程序的軟件工具285.程序理解工具該工具對(duì)程序進(jìn)行分析，確定模塊間的調(diào)用關(guān)系，記錄程序數(shù)據(jù)的靜態(tài)屬性和結(jié)構(gòu)屬性，并畫(huà)出控制流程圖，幫助用戶理解程序。6.高級(jí)語(yǔ)言之間的轉(zhuǎn)換工具如：Pascal<---->CC、Pascal、FORTRAN---->x語(yǔ)言（如Ada語(yǔ)言）目的：解決舊語(yǔ)言程序在新機(jī)器新語(yǔ)言編譯環(huán)境下重用問(wèn)題。說(shuō)明：上述轉(zhuǎn)換目前僅限于結(jié)構(gòu)間的轉(zhuǎn)化,而語(yǔ)義間的轉(zhuǎn)換還是待研究、解決的問(wèn)題。注意：匯編語(yǔ)言程序到高級(jí)語(yǔ)言程序的轉(zhuǎn)換不屬于該范疇之問(wèn)題，而是反編譯問(wèn)題。它也是待研究和解決的問(wèn)題?！?.3解釋程序和一些軟件工具--處理源程序的軟件工具29§1.4程序設(shè)計(jì)語(yǔ)言范型1.強(qiáng)制（命令）式語(yǔ)言—過(guò)