小型編譯程序介紹

小型編譯程序介紹第一頁，共五十八頁，2022年，8月28日9.1小型編譯程序結(jié)構(gòu) 編譯程序的工作貫穿于從輸入源程序開始到輸出目標(biāo)程序?yàn)橹沟恼麄€(gè)過程，是非常復(fù)雜的。一般來說，整個(gè)過程可以劃分成五個(gè)階段：詞法分析、語法分析、中間代碼生成、優(yōu)化和目標(biāo)代碼生成。 第一階段為詞法分析。詞法分析的任務(wù)是輸入源程序，對構(gòu)成源程序的字符串進(jìn)行掃描和分解，識別出一個(gè)個(gè)單詞符號，如保留字、標(biāo)識符、常數(shù)、算符和界符等。第二頁，共五十八頁，2022年，8月28日 第二階段為語法分析。語法分析的任務(wù)是在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則(文法規(guī)則)把單詞符號串分解成各類語法單位(語法范疇)，如“短語”、“子句”、“句子”、“程序段”和“程序”。通過語法分析確定整個(gè)輸入串是否構(gòu)成一個(gè)語法上正確的“程序”。 第三階段為中間代碼產(chǎn)生。按語言的語義將語法分析出來的語法單位翻譯成中間代碼。一般而言，中間代碼是一種獨(dú)立于具體硬件的記號系統(tǒng)，但它與計(jì)算機(jī)的指令形式有某種程度的接近，或者能夠比較容易地把它變換成計(jì)算機(jī)的機(jī)器指令。常用的中間代碼有四元式、三元式、間接三元式和逆波蘭記號等。第三頁，共五十八頁，2022年，8月28日圖9-1編譯程序結(jié)構(gòu)示意第四頁，共五十八頁，2022年，8月28日 第四階段為優(yōu)化。優(yōu)化的任務(wù)在于對前階段產(chǎn)生的中間代碼進(jìn)行加工變換，以期在最后階段能產(chǎn)生出更為高效(節(jié)省時(shí)間和空間)的目標(biāo)代碼。 第五階段為目標(biāo)代碼生成。這一階段的任務(wù)是把中間代碼(或經(jīng)優(yōu)化處理之后)變換成特定機(jī)器上的絕對指令代碼或可重新定位的指令代碼或匯編指令代碼。這一階段實(shí)現(xiàn)了最后的翻譯，它的工作有賴于硬件系統(tǒng)結(jié)構(gòu)和機(jī)器指令含義。第五頁，共五十八頁，2022年，8月28日 上述編譯過程的五個(gè)階段是編譯程序工作時(shí)的動(dòng)態(tài)特征，編譯程序的結(jié)構(gòu)可以按照這五個(gè)階段的任務(wù)分模塊進(jìn)行設(shè)計(jì)。編譯程序的結(jié)構(gòu)示意如圖9-1所示。 我們設(shè)計(jì)的小型編譯程序包含除優(yōu)化以外的其余各階段。第六頁，共五十八頁，2022年，8月28日9.2小型編譯程序關(guān)于高級語言的規(guī)定 高級語言程序具有四種基本結(jié)構(gòu)：順序結(jié)構(gòu)﹑選擇結(jié)構(gòu)﹑循環(huán)結(jié)構(gòu)和過程。為了便于掌握編譯的核心內(nèi)容，突出重點(diǎn)，簡化編譯程序的結(jié)構(gòu)，同時(shí)又涵蓋高級語言程序的基本結(jié)構(gòu)，我們選取賦值語句﹑if語句和while語句作為前三種結(jié)構(gòu)的代表，略去了過程結(jié)構(gòu)。實(shí)際上，上述三種語句已經(jīng)基本滿足了高級語言的程序設(shè)計(jì)。因此，我們僅考慮由下面產(chǎn)生式所定義的程序語句：

第七頁，共五十八頁，2022年，8月28日

S→ifBthenSelseS︱whileBdoS︱beginLend︱A L→S;L︱S A→i:=E B→B∧B︱B∨B︱?

B︱(B)︱iropi︱i E→E+E︱E*E︱(E)︱i第八頁，共五十八頁，2022年，8月28日 其中，各非終結(jié)符的含義如下：

S——語句；

L——語句串；

A——賦值句；

B——布爾表達(dá)式；

E——算術(shù)表達(dá)式。第九頁，共五十八頁，2022年，8月28日 各終結(jié)符的含義如下：

i?——整型變量或常數(shù)，布爾變量或常數(shù)；

rop?——六種關(guān)系運(yùn)算符的代表；

;?——起語句分隔符作用；

:=?——賦值符號；

?

——邏輯非運(yùn)算符“not”；∧?——邏輯與運(yùn)算符“and”；第十頁，共五十八頁，2022年，8月28日 ∨?——邏輯或運(yùn)算符“or”；

+?——算術(shù)加運(yùn)算符； *?——算術(shù)乘運(yùn)算符；

(?——左括號；

)?——右括號。 注意，六種關(guān)系運(yùn)算符分別為

<：小于<=：小于等于<>：不等于

>：大于>=：大于等于=：等于第十一頁，共五十八頁，2022年，8月28日 關(guān)于表達(dá)式的運(yùn)算，我們規(guī)定由高到低優(yōu)先順序?yàn)樗阈g(shù)運(yùn)算、關(guān)系運(yùn)算、布爾運(yùn)算；并且服叢左結(jié)合規(guī)則。算術(shù)運(yùn)算符優(yōu)先級的順序依次為“()”﹑“*”﹑“+”；布爾運(yùn)算符優(yōu)先級的順序依次為“?

”﹑“∧”﹑“∨”；六個(gè)關(guān)系運(yùn)算符優(yōu)先級相同。 我們規(guī)定的程序是由一條語句或由begin和end嵌套起來的復(fù)合語句組成的，并且規(guī)定在語句末要加上“#~”表示程序結(jié)束。下面給出的是符合規(guī)定的程序示例：

begin A:=A+B*C; C:=A+2;第十二頁，共五十八頁，2022年，8月28日

whileA<CandB<DdowhileA>BdoifM=NthenC:=DelsewhileA<=DdoA:=D end#~第十三頁，共五十八頁，2022年，8月28日9.3小型編譯程序關(guān)于單詞的內(nèi)部定義

由于我們規(guī)定的程序語句中涉及單詞較少，故在詞法分析階段忽略了單詞輸入錯(cuò)誤的檢查，而將編譯程序的重點(diǎn)放在中間代碼生成階段。詞法分析器的功能是輸入源程序，輸出單詞符號。我們規(guī)定輸出的單詞符號格式為如下的二元式：

(單詞種別，單詞自身的值)

我們對常量，變量，臨時(shí)變量，保留關(guān)鍵字(if、while、begin、end、else、then、do等)，關(guān)系運(yùn)算符，邏輯運(yùn)算符，分號，括號等，規(guī)定其內(nèi)部定義如表9-1所示。

第十四頁，共五十八頁，2022年，8月28日表9-1關(guān)于單詞的內(nèi)部定義

第十五頁，共五十八頁，2022年，8月28日9.4小型編譯程序的LR分析表

1.算術(shù)表達(dá)式的LR分析表 算術(shù)表達(dá)式文法G[E]如下：

E->E+E︱E*E︱(E)︱I

將文法G[E]拓廣為文法G′[E]：(0)S′→E(1)E→E+E(2)E→E*E(3)E→(E)(4)E→i

由此得到算術(shù)表達(dá)式的SLR(1)分析表如表9-2所示。第十六頁，共五十八頁，2022年，8月28日表9-2算術(shù)表達(dá)式的SLR(1)分析表

第十七頁，共五十八頁，2022年，8月28日

2．

布爾表達(dá)式的LR分析表 布爾表達(dá)式的文法如下：

B->B∧B︱B∨B︱?

B︱iropi︱I

為了便于語法分析時(shí)的加工處理，我們將上述文法改寫為文法G[S]：

B→BAB︱BOB︱?

B︱(B)︱iropi︱iBA→B∧BO→B∨第十八頁，共五十八頁，2022年，8月28日 將文法G[S]拓廣為文法G[S′]：(0)S′→B ???(1)B→I ??(2)B→iropi?? ?(3)B→(B)??? (4)B→NOTB??? (5)A→BAND? ??(6)B→AB?? ?(7)O→BOR?? ?(8)B→OB

由此得到布爾表達(dá)式的SLR(1)分析表如表9-3所示。

第十九頁，共五十八頁，2022年，8月28日表9-3布爾表達(dá)式的SLR分析表

第二十頁，共五十八頁，2022年，8月28日

3.程序語句的LR分析表 程序語句的文法G[S]如下：

S→ifethenSelseS︱whileedoS︱beginLend︱aL→S;L︱S

由于在編譯程序設(shè)計(jì)與實(shí)現(xiàn)中，我們是將賦值語句與算術(shù)表達(dá)式歸為一類處理的，故在此將賦值語句僅看作為程序語句文法中的一個(gè)終結(jié)符a，將布爾表達(dá)式B也看作為終結(jié)符e。將文法G[S]拓廣為文法G[S′]：(0)S′→S第二十一頁，共五十八頁，2022年，8月28日

(1)S→ifethenSelseS(2)S→whileedoS(3)S→beginLend(4)S→a(5)L→S(6)L→S;L

由此得到程序語句的SLR(1)分析表如表9-4所示。第二十二頁，共五十八頁，2022年，8月28日表9-4程序語句的SLR分析表

第二十三頁，共五十八頁，2022年，8月28日9.5小型編譯程序執(zhí)行過程 小型編譯程序執(zhí)行分兩個(gè)階段：第一個(gè)階段，將高級語言源程序翻譯成四元式程序；第二個(gè)階段，將四元式程序翻譯成匯編語言目標(biāo)程序。執(zhí)行過程示意如圖9-2所示。

第二十四頁，共五十八頁，2022年，8月28日圖9-2執(zhí)行過程示意

第二十五頁，共五十八頁，2022年，8月28日 下例為一個(gè)名為PAS.DAT的高級語言源程序經(jīng)過PAS的編譯，產(chǎn)生名為PAS.MED的四元式(中間代碼)程序；PAS.MED經(jīng)過COMPILER編譯生成8086/8088匯編語言目標(biāo)程序PAS.ASM。

/*******************************************/ /*pas.dat*/ /*高級語言源程序?*/ /******************************************/第二十六頁，共五十八頁，2022年，8月28日

while(a>b)do begin ifm>=nthena:=a+1 else whilek=hdox:=x+2; m:=n+x*(m+y) end # ~第二十七頁，共五十八頁，2022年，8月28日

/*******************************************/ /*pas.med*/ /*高級語言生成的四元式文件?*/ /******************************************/

100 (j> ,a ,b ,102 ) 101 (j , , ,117 ) 102 (j>= ,m ,n ,104 ) 103 (j , , ,107 ) 104 (+ ,a ,1 ,T1 )第二十八頁，共五十八頁，2022年，8月28日

105 (:= ,T1 , ,a )

106 (j , , ,112 )

107 (j= ,k ,h ,109 )

108 (j , , ,112 )

109 (+ ,x ,2 ,T2 )

110 (:= ,T2 , ,x ) 111 (j , , ,107 )第二十九頁，共五十八頁，2022年，8月28日

112 (+ ,m ,y ,T3 ) 113 (* ,x ,T3 ,T4 ) 114 (+ ,n ,T4 ,T5 ) 115 (:= ,T5 , ,m ) 116 (j , , ,100 )

/*******************************************/ /*pas.asm*/第三十頁，共五十八頁，2022年，8月28日

/*由四元式文件生成的匯編文件*/ /******************************************/

datasegment ;定義數(shù)據(jù)段

h DW k DW m DW n DW x DW y DW a DW b DW第三十一頁，共五十八頁，2022年，8月28日

dataends ;數(shù)據(jù)段定義結(jié)束

;************************************** codesegment ;定義代碼段

mainprocfar ;程序的執(zhí)行部分

assumecs:code,ds:data start: ;為返回操作系統(tǒng)入棧

pushds subbx,bx pushbx第三十二頁，共五十八頁，2022年，8月28日

;設(shè)置DS段為當(dāng)前數(shù)據(jù)段

movbx,data movds,bx 100: movAX,a ;把條件跳轉(zhuǎn)指令的第一操作數(shù)讀入寄存器

cmpAX,b ;把條件跳轉(zhuǎn)指令的第一操作數(shù)和第二操作數(shù)相減

jg102 ;大于則跳轉(zhuǎn)

101: jmp117 ;產(chǎn)生直接跳轉(zhuǎn)指令第三十三頁，共五十八頁，2022年，8月28日

102: movAX,m ;把條件跳轉(zhuǎn)指令的第一操作數(shù)讀入寄存器

cmpAX,n ;把條件跳轉(zhuǎn)指令的第一操作數(shù)和第二操作數(shù)相減

jge104 ;大于或等于則跳轉(zhuǎn)

103: jmp107;產(chǎn)生直接跳轉(zhuǎn)指令

104:

movAX,a ;把在存儲器中的被加數(shù)賦給結(jié)果寄存器

addAX,1D;把被加數(shù)和加數(shù)立即數(shù)相加第三十四頁，共五十八頁，2022年，8月28日

105: movBX,AX ;執(zhí)行賦值語句，寄存器中的值賦給結(jié)果變量

mova,BX ;在跳出基本塊之前保存寄存器中已改變的變量

106: jmp112 ;產(chǎn)生直接跳轉(zhuǎn)指令

107: movAX,k ;把條件跳轉(zhuǎn)指令的第一操作數(shù)讀入寄存器

cmpAX,h ;把條件跳轉(zhuǎn)指令的第一操作數(shù)和第二操作數(shù)相減

je109 ;相等則跳轉(zhuǎn)第三十五頁，共五十八頁，2022年，8月28日

108: jmp112 ;產(chǎn)生直接跳轉(zhuǎn)指令

109: movAX,x ;把在存儲器中的被加數(shù)賦給結(jié)果寄存器

addAX,2D ;把被加數(shù)和加數(shù)立即數(shù)相加

110: movBX,AX ;執(zhí)行賦值語句，寄存器中的值賦給結(jié)果變量

movx,BX ;在跳出基本塊之前保存寄存器中已改變的變量第三十六頁，共五十八頁，2022年，8月28日

111:jmp107 ;產(chǎn)生直接跳轉(zhuǎn)指令

112:movAX,m ;把在存儲器中的被加數(shù)賦給結(jié)果寄存器

addAX,y ;把被加數(shù)和在存儲器中的加數(shù)相加

113:mulx ;把被乘數(shù)和在存儲器中的乘數(shù)相乘第三十七頁，共五十八頁，2022年，8月28日

114: movBX,n ;把在存儲器中的被加數(shù)賦給結(jié)果寄存器

addBX,AX ;把被加數(shù)和在寄存器中的加數(shù)相加

115: movCX,BX ;執(zhí)行賦值語句，寄存器中的值賦給結(jié)果變量

movm,CX ;在跳出基本塊之前保存寄存器中已改變的變量

116:jmp100 ;產(chǎn)生直接跳轉(zhuǎn)指令第三十八頁，共五十八頁，2022年，8月28日

117: ret mainendp codeends ;代碼段定義結(jié)束

endstart第三十九頁，共五十八頁，2022年，8月28日9.6小型編譯程序運(yùn)行實(shí)例分析 我們以高級語言源程序到四元式的翻譯為例對其進(jìn)行分析。待編譯的PAS.DAT源程序如下：

while(a>b)do begin ifm>=nthena:=a+1 else whilek=hdox:=x+2; m:=n+x*(m+y) end#~第四十頁，共五十八頁，2022年，8月28日 經(jīng)編譯程序運(yùn)行后得到的輸出結(jié)果如下： *******詞法分析結(jié)果*******/*注釋：查單詞內(nèi)部定義和下面的變量名表*/ 3 0/*(sy_while,0)*/ 48 0/*(″(″,0)*/ 56 0/*(變量,a)*/ 42 3/*(rop,″>″)*/ 561/*(變量,b)*/ 490/*(″)″,0)*/第四十一頁，共五十八頁，2022年，8月28日

5 0/*(sy_do,0)*/4 0/*(sy_begin,0)*/0 0/*(sy_if,0)*/56 2/*(變量,m)*/42 2/*(rop,″>=″)*/56 3/*(變量,n)*/1 0/*(sy_then,0)*/56 0/*(變量,a)*/第四十二頁，共五十八頁，2022年，8月28日

38 0/*(″:=″,0)*/56 0/*(變量,a)*/34 0/*(″+″,0)*/56 1/*(整常量,1)*/2 0/*(sy_else,0)*/3 0/*(sy_while,0)*/56 4/*(變量,k)*/第四十三頁，共五十八頁，2022年，8月28日

pressanykeytocontinue42 5/*(rop,″=″)*/56 5/*(變量,n)*/5 0/*(sy_do,0)*/56 6/*(變量,x)*/38 0/*(″:=″,0)*/56 6/*(變量,x)*/第四十四頁，共五十八頁，2022年，8月28日

34 0/*(″+″,0)*/57 2/*(整常量,2)*/8 0/*(″;″,0)*/56 2/*(變量,m)*/38 0/*(″:=″,0)*/56 3/*(變量,n)*/34 0/*(″+″,0)*/第四十五頁，共五十八頁，2022年，8月28日

56 6/*(變量,x)*/36 0/*(″*″,0)*/48 0/*(″c″,c)*/56 2/*(變量,m)*/34 0/*(″+″,0)*/56 7/*(變量,y)*/49 0/*(″)″,0)*/6 0/*(sy_end,0)*/10 0/*(″#″,0)*/第四十六頁，共五十八頁，2022年，8月28日

程序總共9行，產(chǎn)生了43個(gè)二元式！*****************變量名表*****************

0 a1

b2

m3

n4

k5

h6

x7

y第四十七頁，共五十八頁，2022年，8月28日 *********狀態(tài)棧分析過程及歸約順序***************

stack[0]=0 n=3 lr=3 stack[1]=3 n=9 lr=7 stack[2]=7 n=5 lr=11 stack[3]=11 n=4 lr=4 stack[4]=4 n=0 lr=2 stack[5]=2 n=9 lr=6 stack[6]=6 n=1 lr=10 stack[7]=10 n=7 lr=5第四十八頁，共五十八頁，2022年，8月28日

stack[8]=5 n=2 lr=104 s->a歸約

stack[7]=10 n=11 lr=14 stack[8]=14 n=2 lr=17 stack[9]=17 n=3 lr=3 stack[10]=3 n=9 lr=7 stack[11]=7 n=5 lr=11 stack[12]=11 n=7 lr=5 stack[13]=5 n=8 lr=104第四十九頁，共五十八頁，2022年，8月28日

s->a歸約

stack[12]=11 n=11 lr=15 stack[13]=15 n=8 lr=102 s->whileedos歸約

stack[9]=17 n=11 lr=18 stack[10]=18 n=8 lr=101第五十頁，共五十八頁，2022年，8月28日

s->ifethenselses歸約

stack[4]=4 n=11 lr=9 stack[5]=9 n=8 lr=13 stack[6]=13 n=7 lr=5 stack[7]=5 n=6 lr=104 s->a歸約

stack[6]=13 n=11 lr=9 stack[7]=9 n=6 lr=105第五十一頁，共五十八頁，2022年，8月28日

L->s歸約

stack[6]=13 n=12 lr=16 stack[7]=16 n=6 lr=106 L->S;L歸約

stack[4]=4 n=12 lr=8 stack[5]=8 n=6 lr=12 stack[6]=12 n=10 lr=103 s->beginLend歸約

stack[3]=11 n=11 lr=15 stack[4]=15 n=10 lr=102第五十二頁，共五十八頁，2022年，8月28日

s->whileedos歸約

stack[0]=0 n=11 lr=1 stack[1]=1 n=10 lr=-2

************四元式分析結(jié)果***************** ********************************************

100(j>, a, b, 102 ) 101(j, , , 117 )第五十三頁，共五十八頁，2022