計(jì)算機(jī)課件第06章 編譯技術(shù)

第6章編譯技術(shù)

6」編譯程序的工作過(guò)程

6.2狀態(tài)矩陣法的編譯過(guò)程

6.3詞法分

6.4中間語(yǔ)言表示

6.5語(yǔ)法的分析與加工

左

編譯程序是一種將高級(jí)語(yǔ)言編

寫(xiě)的源程序編譯成機(jī)器語(yǔ)言程序

（稱(chēng)為目標(biāo)程序）的實(shí)用程序。

g.i編譯程序的工作過(guò)程

為了將源程序翻譯成目標(biāo)程序，一般

都要包括以下幾個(gè)步驟。

①輸入源程序。

②對(duì)以機(jī)內(nèi)碼表示的源程序進(jìn)行詞法

分析，辨認(rèn)出一個(gè)個(gè)單詞符號(hào)。

③根據(jù)源語(yǔ)言的語(yǔ)法規(guī)則進(jìn)行語(yǔ)法

分析。

④在實(shí)際運(yùn)行之前，通常還要對(duì)目

標(biāo)程序的各部分進(jìn)行連接裝配。

對(duì)于塊結(jié)構(gòu)的語(yǔ)言（如C語(yǔ)言和

FORTRAN語(yǔ)言等），通常是進(jìn)行分塊

編譯，分別得到半目標(biāo)程序，最后可用

裝配程序組裝成一個(gè)完整的程序。

圖6.1三遍掃描的編譯過(guò)程

半目標(biāo)程序1

裝

半目標(biāo)程序2配錯(cuò)誤處理

程

.一-庫(kù)程序

序

半目標(biāo)程序72

▼

目標(biāo)程序

璐圖丘2半目標(biāo)程序的裝配示意圖

編譯程序一般要包含以下幾個(gè)程序模塊。

(1)詞法分析程序

(2)語(yǔ)法分析程序

(3)加工程序

(4)優(yōu)化修飾部分

(5)裝配程序或連接編輯程序

6.2狀態(tài)矩陣法的編譯過(guò)程

6.2.1狀態(tài)矩陣法的基本原理

所謂“狀態(tài)”，粗略地說(shuō)，是表示過(guò)

去已經(jīng)掃描了什么語(yǔ)法成分，以便當(dāng)遇到

新的語(yǔ)法符號(hào)時(shí)，在不同的狀態(tài)下對(duì)該語(yǔ)

法符號(hào)作出不同的處理。

狀態(tài)矩陣法的核心是狀態(tài)矩陣（也稱(chēng)

‘犬態(tài)表），如表6」所示。

\單擊鼠標(biāo)左鍵換頁(yè)R|G|>P

<61狀態(tài)矩陣

??~?A4?

SY?

】

STSUB1]SUBn

ST1SUB?1SUBJ2

ST,SUBfSUBpSUB"

單擊鼠標(biāo)左鍵換頁(yè)

6.2.2狀態(tài)矩陣的壓縮

在具體實(shí)現(xiàn)狀態(tài)矩陣法時(shí)，為了節(jié)省

存儲(chǔ)空間，通常要對(duì)狀態(tài)矩陣進(jìn)行壓縮。

V冏〉同

表6.2m=〃=3的狀態(tài)矩陣

SY,SY3

SUB12EPJI.OR

STJERRORSUBnERROR

ST】ERRORSUBnSUB33

*朦麻蟋V窗〉a

??

表6.3狀態(tài)矩陳壓縮后的形式

狀態(tài)符號(hào)加工子程序伏態(tài)改變轉(zhuǎn)向

1

SY1SUBnfST,>ST,N

SY：SUBn+STjN

????

OtherERRORP

f

SYjSUBn

ST3

1OtherERROR

SYj+STj,STN

?SUB33r

鵬SHSUB”-STiN

15'■.■1,?

FOtherERRORp

各列的意義如下:

①狀態(tài)指狀態(tài)棧棧頂項(xiàng)中所包含的

可能狀態(tài)。

②符號(hào)指當(dāng)前掃描到的可能符號(hào)。

③加工子程序指當(dāng)前遇到的相應(yīng)狀

態(tài)符號(hào)配對(duì)時(shí)編譯程序應(yīng)做的工作。

V冏〉同

INITIATION

圖6.3狀態(tài)矩陣法的總控程序框圖

6.3詞法分析

6.3.1詞法分析的任務(wù)

詞法分析是編譯過(guò)程各階段的基礎(chǔ)和

必要的準(zhǔn)備。

詞法分析的主要任務(wù)是從源程序語(yǔ)句

中識(shí)別出具有獨(dú)立意義的語(yǔ)法單位（即語(yǔ)

法符號(hào)），并且建立一個(gè)符號(hào)表，用以保

存各語(yǔ)法符號(hào)的屬性。

表6.4符號(hào)表

序號(hào)符號(hào)屬性其他信息

001RN實(shí)符號(hào)名

002賦值號(hào)

003(左括號(hào)

0042.4實(shí)常數(shù)

005*乘號(hào)

006+加號(hào)

007X實(shí)符號(hào)名

008)右括號(hào)

009除號(hào)

010N整符號(hào)名

表6.4中的符號(hào)最后都變成二進(jìn)制

形式的代碼串。

可以將這些通用符號(hào)建立一個(gè)通

用符號(hào)表，這些符號(hào)的代碼可用較大

的編號(hào)來(lái)表示，如表6.5所示。

在這種情況下，上述賦值語(yǔ)句經(jīng)

詞法分析后可以得到一張符號(hào)表如表

6.6所示。

醒噌蝴㈱

表65通用符號(hào)表

符號(hào)編碼

+900

901

*902

903

904

)905

906

表6.6符號(hào)表

序號(hào)符號(hào)屬性其他信息

001RN實(shí)符號(hào)名

0022.4實(shí)常數(shù)

003實(shí)符號(hào)名

004N整符號(hào)名

6.3.2讀字符程序

讀字符程序的任務(wù)是從源程序字符串中順

序讀出基本符號(hào)，并作一些簡(jiǎn)單的處理后提供

給詞法分析程序。

6.3.3狀態(tài)矩陣法的詞法分析過(guò)程

詞法分析程序可以用狀態(tài)矩陣法來(lái)實(shí)現(xiàn)。

醒

由圖6.4可以看出，每執(zhí)行一次這

個(gè)程序，就順序從源程序中讀出一個(gè)

語(yǔ)法符號(hào)，并且將有關(guān)的信息存放在

一些工作單元中。

讀下一個(gè)語(yǔ)法單位的第一個(gè)字符CH

判斷CH

圖6.4直接分析方法的框圖

左

下面以FORTRAN語(yǔ)言為例來(lái)說(shuō)明用

狀態(tài)矩陣法實(shí)現(xiàn)詞法分析的過(guò)程。為簡(jiǎn)單

起見(jiàn)，作如下一些假設(shè)：

①不考慮格式語(yǔ)句。

②不考慮數(shù)的翻譯。

③不考慮以E開(kāi)頭的運(yùn)算符，且運(yùn)算

符只有兩個(gè)字母。

V冏〉同

?表6.7FORTRAN說(shuō)詞程序的狀態(tài)矩陣

狀態(tài)符號(hào)加工子程序狀態(tài)改變轉(zhuǎn)向

字母fNAMEN

數(shù)字—NUMBERN

fRN

PR

*-STARN

4結(jié)束N

其他給出隊(duì)列中的符號(hào)N

字母當(dāng)隊(duì)列中是專(zhuān)用定義符時(shí)，給出該符號(hào)，并且N

-PR.否則不做任何工作

NAME

數(shù)字N

其他給出隊(duì)列中“名”，保留其他fPRP

左

狀態(tài)符號(hào)加工子程序狀態(tài)改變轉(zhuǎn)向

數(shù)字

*保留讀字符指示器N

NUMBERE—PNN

-PN

其他給出隊(duì)列中的“整型數(shù)”，保留其他-*PRP

RN字母給出隊(duì)列中的“整型數(shù)”恢復(fù)讀字符指示器-*PRP

數(shù)字N

RN1E給出隊(duì)列中的“實(shí)型數(shù)”，保留其他fPN

其他-PRP

數(shù)字fPlN

PN

其他錯(cuò)誤P

數(shù)字-*P1N

+fPNN

P

—fPNN

其他錯(cuò)誤P

左

數(shù)字N

Pl

其他給出隊(duì)列中的“實(shí)型數(shù)”，保留其他fPRP

字母-R1N

R數(shù)字-*PN1N

其他給出隊(duì)列中的“”，保留其他-PR，P

字母N

RI

其他錯(cuò)誤->POINTP

■若隊(duì)列中為拼寫(xiě)運(yùn)算符，則給出運(yùn)算符，并N

POINT-PR,否則錯(cuò)誤

其他錯(cuò)誤P

?給出隊(duì)列中的“**”—PR:"N

STAR->PR1

其他給出隊(duì)列中的，保留其他P

f

w#ssi

1單擊鼠標(biāo)左鍵換頁(yè)

表6.8邏輯條件語(yǔ)句的分析過(guò)程

當(dāng)前掃描到的

狀態(tài)棧隊(duì)列切口工情況轉(zhuǎn)向

基本符號(hào)

PRII—NAME；N

NAMEFIF給出專(zhuān)用定義符IF，且-PRN

*R?：G給出左括號(hào)（:N；

PRRRfNAME；N

NAMER.給出名字R，保留其他，fPRP

PRfRN"

RG,.GfRlN

RIT.GT-POINT；N；

POINT.GT.給出運(yùn)篁符.GT-一PR:N

—*，

PR11-NUMBER；N

NUMBER1.保留讀字符指示器，fRNN

RN01.0N

------------------------------------」

1

RN)1.0)給出實(shí)型數(shù)1.0,保留其他，-PRP

|PR：'給出符號(hào)）N

1PR

AAfNAMEN

[NAMEBABN

[NAME1A—B?IN

|NAME

=ABU給出名字AB1,保留其他，fPRP

PR=給出符號(hào)=N

1PR

*-RN

R22—PJN1N

|RNlE,2E->PN

F+.2E+—PN,N

|PN6,2E+6-PlN

*,2E+6*給出實(shí)型數(shù)2E+6,保留*,fPRP

|PR*fSTARN

'STARB給出*，保留B,fPRP

IPRB-?NAMEN

"NAMECBCN

當(dāng)前掃描到的

狀態(tài)棧隊(duì)列力情況轉(zhuǎn)向

基本符號(hào)nX

NAME—BC-給出名字BC,保留-，-PRP

PR一給出-N

PRXX—NAMEN

NAME2X2H

NAMEHJX2H給出X2,保留T,fPRP

PR結(jié)束N

1

1建換頁(yè)V合〉〉[]

1單擊鼠標(biāo)左4

表6.9語(yǔ)法符號(hào)表

序號(hào)123456

符號(hào)IFR.GT.L0：'

78910111213

ABI=2E+6*BC—X2

聿擊鼠標(biāo)左鍵換頁(yè)〈局〉〉

6.3.4算術(shù)常數(shù)的識(shí)別和翻譯

在詞法分析的過(guò)程中，不僅要識(shí)別出

常數(shù)，還需要將常數(shù)翻譯成統(tǒng)一的格式。

經(jīng)過(guò)詞法分析后，所有的實(shí)數(shù)都分解

成兩部分：一部分是有效數(shù)字的所有位組

成的正整數(shù)；另一部分是以10為底的整數(shù)

指數(shù)部分。

醒

圖6.5算術(shù)常數(shù)的識(shí)別與翻譯流程圖

表6.10常數(shù)翻譯的狀態(tài)矩陣表示

狀態(tài)符號(hào)加工子程序狀態(tài)改變轉(zhuǎn)向

數(shù)字夕=0,x=Q,p=CI,g=+=1。*y+數(shù)fBN

字-*CN

AA

V=0,x=0,p=0,g=+P

耳他ERROR

數(shù)字，=io*y+數(shù)字N

->DN

B

EfE;N

其他V=2^10^*,結(jié)束P

數(shù)字*10*^+數(shù)字,w=n+lfDN

C

其他ERRORP

數(shù)字夕=10**+數(shù)字,？2=力+1：N

DE->EN

其他方=獐10個(gè)",結(jié)束P；

+fFN

—E=一->FN

E

數(shù)字P=10*2?+數(shù)字fGN

其他ERRORP；

數(shù)字尸=10*p+數(shù)字-GN

rn

其他ERRORP

數(shù)字尸=10*p+數(shù)字N

G其他1

*=獐1匕1，結(jié)束P：

單擊鼠標(biāo)左鍵換頁(yè)V合〉H

表6.11狀態(tài)矩陣法對(duì)常效的識(shí)別與翻譯過(guò)程

狀態(tài)棧當(dāng)前掃描到的基本符號(hào)加工緒果轉(zhuǎn)向

A0，=0,n=O>p=O>e=+N

B*.N

D0V-0?門(mén)=1N

D3\V-39n-2N

D232,n=3N

DE-M

E—e=一N

F1P=1N

GV=32x10*】=32xIT，緒束

單擊艮曷標(biāo)左鍵換頁(yè)

6.4中間語(yǔ)言表示

中間語(yǔ)言”,為能用來(lái)表述源程序

并與之等效的一種編碼方式。

6.4.1波蘭表示

一個(gè)表達(dá)式的波蘭表示就是后綴表示,

即表達(dá)式中的運(yùn)算對(duì)象寫(xiě)在前面，運(yùn)算符

寫(xiě)在后面。

（2）無(wú)條件轉(zhuǎn)向語(yǔ)句

GOTOn

的波蘭表示為:

n'GOTO

（3）邏輯條件語(yǔ)句

IFCS

的波蘭表示為:

CS'LIF

（4）子程序調(diào)用語(yǔ)句

CALLS(yl,y2,yn)

的波蘭表示為：

yl',y2',yn'SSUB

6)維數(shù)說(shuō)明語(yǔ)句

DIMENSIONA(N,

的波蘭表示為：

NMADIM

（6）函數(shù)子程序段頭語(yǔ)句

FUNCTIONF(X1,X2,…，XN)

的波蘭表示為:

XI,X2,…，XNFDEFF

V冏〉同

6.4.2三元組表示

波蘭表示有一個(gè)缺點(diǎn)，就是不便于

作代碼的優(yōu)化。

三元組表示的一般形式為:

k,(0olo2)

V冏〉同

表6、12三元組表示的優(yōu)化過(guò)衽

序號(hào)三元組出現(xiàn)次數(shù)變化過(guò)程最終出現(xiàn)次數(shù)

1、*AB121211

2/CD121211

3+1212322

4；然A3122

5+3411

6尸4D11

7-5611

左

去6.13翻譯三元組表示的規(guī)則

運(yùn)算符

可交換運(yùn)算符。不可交換運(yùn)苴符。

運(yùn)算對(duì)象—

olc.2當(dāng)AC=O時(shí)：當(dāng)ACWO時(shí)：

取。1存T

9o2'取"o*"l??

0o2

當(dāng)AC=。時(shí)：當(dāng)ACW0時(shí)：

0取。1存T

olL

ol田Tr?、?/p>

eT

Lo29o2

當(dāng)AC=0時(shí)：當(dāng)ACWO時(shí)：

LL0Tr存T

9T

左

表6.14翻譯三元組的過(guò)程

序號(hào)三元組出現(xiàn)次數(shù)目標(biāo)程序指令

1*AB1取A

2/CD1存T1

取C

ID

3計(jì)122+T1

存T2

4*A32*A

存T3

5斗341+T2

6/4D1存T4

取T3

Q

7-561存T5

取T4

-T5；I

表6.16FORTRAN部分語(yǔ)句的三元組表示

語(yǔ)句名稱(chēng)涪司二兀蛆表示:說(shuō)明

賦值語(yǔ)句V=ee的二兀蛆表示設(shè)表達(dá)式e在第n-1

n,(=n-1V)個(gè)三元組時(shí)算出

無(wú)條件轉(zhuǎn)向語(yǔ)句GOTOL(GOTOL)

邏輯條件語(yǔ)句IF(C)SC的二兀蛆表示設(shè)表達(dá)式C在第n-1

n,(UFn-lL)個(gè)三元組時(shí)算出

語(yǔ)句s的三元組表示

(LABL)

算術(shù)條件語(yǔ)句IF(C)L1L2L3C的二兀組表示設(shè)表達(dá)式C在第n-1

n,(BMn-lL)個(gè)三元組時(shí)算出

n+l>(BZn-1L)

n+2,(BPn-lL)

數(shù)組說(shuō)明語(yǔ)句DIMENSIONA(dl,d2)n,(DIMdl)DIM為維運(yùn)算符

n+1,(DIMd2)ADEC為數(shù)組運(yùn)菖符

n+2,(ADECA)

左：頁(yè)

調(diào)用語(yǔ)句CALLSfywg實(shí)元五的三元蛆表示設(shè)憑值地址在第個(gè)

實(shí)元力的三元蛆表示三元組菖出，SUB為子

1程序調(diào)用運(yùn)算符

*

,(ACAm。

1

(ACAmJ

>(SUBS)：

子程序返回語(yǔ)句RETURN(RETURN)々無(wú)運(yùn)算對(duì)象

結(jié)束行終止語(yǔ)句END(END)無(wú)運(yùn)算對(duì)象

噌曲李㈱蟋

1單擊鼠林左鍵換頁(yè)々合〉以

6.5語(yǔ)法的分析與加工

語(yǔ)法分析和加工的主要任務(wù)有

以下幾項(xiàng)。

①識(shí)別出各種類(lèi)型的語(yǔ)句，并

進(jìn)行語(yǔ)法檢查。

②語(yǔ)法的加工處理。

③編譯程序工作的最后結(jié)果是

產(chǎn)生目標(biāo)程序或半目標(biāo)程序。

醒噌蝴蟋

示左鍵換V冏〉同

6.5.1優(yōu)先矩陣法

優(yōu)先矩陣法的基本思想如下。

將程序設(shè)計(jì)語(yǔ)言中的所有算符（廣

義運(yùn)算符，包括算術(shù)運(yùn)算符、分隔符、

拼寫(xiě)定義符及界限符卜和T等）設(shè)置一

個(gè)優(yōu)先關(guān)系，而這種優(yōu)先關(guān)系用一張優(yōu)

先矩陣表來(lái)表示。

表6.17;優(yōu)先矩陣表

1

**

+一?/()

+>><<<<>>

一>><<<<>>

?>>>><<>>

/>>>><<>>

**>>>>><>>

(<<<<<<=X

)>>>>>X>>

卜<<<<<<XQ

?21

L?■■—Q(■、I[----』

表6.18優(yōu)先矩陣法編譯過(guò)程

當(dāng)前掃描到的

當(dāng)前運(yùn)算對(duì)象棧當(dāng)前算符棧處理說(shuō)明目標(biāo)程序指令

語(yǔ)法符號(hào)

H喳算符棧：

A卜A進(jìn)運(yùn)算對(duì)象棧

?h卜因1c叫率進(jìn)算符棧

A*卜因*<3（進(jìn)算符棧

BA(*hB進(jìn)運(yùn)算對(duì)象棧

+BA(*F因（《+，+進(jìn)翼符枝

CBA+(*hC進(jìn)運(yùn)算對(duì)象棧

)CBA；+（葉因+>），產(chǎn)生B+D代碼取B

+C

A（*卜因(=），）進(jìn)菖符棧

1

w#ssi

i單擊1標(biāo)左V?！狄?/p>

AX葉因））-，）與（退出算符棧

A葉因*）-,產(chǎn)生A*AC代碼?A

H因卜<-，-進(jìn)篁符棧

c-F.；C進(jìn)運(yùn)算對(duì)象棧

rC-卜因"磁算符棧

DCD進(jìn)運(yùn)篁?qū)ο髽O

r二.取?密

HDCH因/>T，存累加器，產(chǎn)生CQ存T1

代碼取C

/D

-卜因->T，產(chǎn)生T1-AC代碼存T2

取T1

-T2

卜因卜與T配對(duì)，結(jié)束

左

6.5.2優(yōu)先數(shù)法

基于算符的優(yōu)先數(shù)進(jìn)行編譯的方法稱(chēng)

為優(yōu)先數(shù)法。

表6.19優(yōu)先敬我

*

)**/+一(卜

棧內(nèi)優(yōu)先數(shù)工?)97553310

棧外優(yōu)先數(shù)虱夕)16442280

6.5.3狀態(tài)矩陣法

狀態(tài)矩陣法用表格形式來(lái)描述編

譯過(guò)程，因此條理十分清楚，這是其

他方法所不及的。

V冏〉同

6.5.4遞歸子程序法

遞歸子程序法的基本思想是：從整個(gè)

源程序開(kāi)始，根據(jù)各種語(yǔ)法成分的形成規(guī)

則從大到小逐層往細(xì)分析處理，而對(duì)于每

個(gè)遞歸定義的語(yǔ)法成分，都用一個(gè)相應(yīng)的

遞歸子程序來(lái)進(jìn)行處理。

V冏〉同

SuccesswithMoneyandJoy

附熠人生心語(yǔ)

?成功是一種觀念

?致富是一種義務(wù)

?快樂(lè)是一種權(quán)利

?每個(gè)人都有能力、有義

務(wù)、有權(quán)利辦到成功

致富快樂(lè)

附贈(zèng)人生心語(yǔ)

成成功不是打敗別人

功成功不是超越別人

成功不是名、利、權(quán)的獲得

致?lián)碛薪】档纳眢w

豐足的物質(zhì)生活

富平衡的心理狀態(tài)

又才能擁有成功

快SuccesswithMoneyandJoy

戰(zhàn)勝自己

樂(lè)貢獻(xiàn)自己

扮演好自己的歷史角色

才能超越自己

融入成功里

附贈(zèng)人生心語(yǔ)

知人者智，自知者明，勝人者力，自

勝者強(qiáng)。

——老子

附贈(zèng)人生心語(yǔ)

?成功必須靠百分之九十八的辛勤血

汗，加上百分之二的天才靈感。

?世界上注定只有百分之二十的人會(huì)成

功。

附贈(zèng)人生心語(yǔ)

成猶太諺語(yǔ)中有一句名