編譯(第1章：編譯程序概論)

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

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

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

編譯程序

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

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

編輯(裝配/連接)程序絕對機(jī)器代碼可再裝配目標(biāo)文件objexe函數(shù)子程序4§1.1什么是編譯程序例：C語言需預(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ù)子程序庫裝配/連接程序Sin字程序裝配Printf子程序裝配連接連接7§1.2編譯過程和編譯程序的結(jié)構(gòu)概述一、編譯過程概述

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

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

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

5．標(biāo)識符first6．逗號，

7．標(biāo)識符count8．冒號：

9．保留字real10．分號；

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

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

4．刪除空白符、注釋等

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

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

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

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

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

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

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

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

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

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

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

…a[i]…;//a沒有聲明

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

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

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

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

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

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

中間代碼優(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)化方式局部優(yōu)化全局優(yōu)化優(yōu)化種類常表達(dá)式的優(yōu)化公共子表達(dá)式的優(yōu)化循環(huán)優(yōu)化消減運(yùn)算強(qiáng)度15

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

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

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

語法分析程序COMP

詞法分析程序

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

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

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