編譯原理語義控制語句的翻譯

編譯原理語義控制語句的翻譯第1頁，共27頁，2023年，2月20日，星期四第四章語義分析和中間代碼生成4.1語義分析概述4.2屬性文法4.3幾種常見的中間語言4.4表達(dá)式及賦值語句的翻譯4.5控制語句的翻譯4.6數(shù)組元素的翻譯4.7過程或函數(shù)調(diào)用語句的翻譯4.8說明語句的翻譯4.9遞歸下降語法制導(dǎo)翻譯方法簡介第2頁，共27頁，2023年，2月20日，星期四第四章《語義分析和中間代碼生成》4.5控制語句的翻譯條件語句if條件循環(huán)語句while多分支控制語句case(自學(xué))轉(zhuǎn)移語句goto重點掌握通過代碼結(jié)構(gòu)圖翻譯if、while語句(重點)本講目標(biāo)

第3頁，共27頁，2023年，2月20日，星期四4.5控制語句的翻譯4.5程序流程控制的三種基本結(jié)構(gòu)順序結(jié)構(gòu)：一般用復(fù)合語句實現(xiàn)；選擇結(jié)構(gòu)：if-elseif-else,switch-case;循環(huán)結(jié)構(gòu)：for，while,do-while第4頁，共27頁，2023年，2月20日，星期四4.5控制語句的翻譯圖4-11if(E)S的代碼結(jié)構(gòu)圖4-10條件語句if(E)S1;elseS2的代碼結(jié)構(gòu)第5頁，共27頁，2023年，2月20日，星期四4.5控制語句的翻譯第6頁，共27頁，2023年，2月20日，星期四為了在掃描條件語句過程中不失時機地處理和回填有關(guān)信息，可將G[S]改寫為如下的G'[S]：

G'[S]:

(1)

S→CS(1)

(2)

C→if(E)

(3)

S→TPS(2)

(4)

TP→CS(1);else4.5控制語句的翻譯第7頁，共27頁，2023年，2月20日，星期四(1)無論是哪種if語句，首先用產(chǎn)生式(2)C→if(E)進(jìn)行歸約，這時E的真出口即為S(1)的第一個四元式；E的假出口地址則作為待填信息放在C的語義變量C.chain中等待回填；

所以：4.5控制語句的翻譯

C→if(E){Backpatch(E.tc,nxq);

C.chain?=?E.fc;}(1)S→CS(1)

(2)

C→if(E)掃描到“)”，立即回填E的真出口C.chain中只保存E的待填假出口if(E)S(1)else

S(2)

TF第8頁，共27頁，2023年，2月20日，星期四(2)不含else時，用(1)S→CS(1)進(jìn)行規(guī)約，E的假出口是S(1)的出口，將C.chain和S(1).chain一起作為S的待填信息鏈用函數(shù)merge鏈在一起保留在S的語義值S.chain中：4.5控制語句的翻譯(1)S→CS(1)

(2)

C→if(E)S→CS(1){S.chain

=

merge(C.chain,S(1).chain)}if(E)S(1)TFCS(1)S(1).chain=104C.chain=101S.chain=104規(guī)約后：S(1).chainC.chain第9頁，共27頁，2023年，2月20日，星期四(3)用產(chǎn)生式(2)C→if(E)進(jìn)行歸約之后，如果：條件語句后有else，用(4)繼續(xù)規(guī)約。4.5控制語句的翻譯(2)C→if(E)(3)

S→TPS(2)

(4)

TP→CS(1);elseTP→CS(1);else{q=nxq;

emit(j,_,_,0);

Backpatch(C.chain,nxq);

TP.chain?=?merge(S(1).chain,q);}注意1：只要遇到有else的規(guī)約，必須先產(chǎn)生一條無條件轉(zhuǎn)移。if(E)S(1);else

S(2)

CS(1);else

S(2)

TPS(2)

2：S(2)

就是C.chain3：q就是S(1).chainif(E)S(1);else

S(2)

TFq:(j,_,_,0)nxq:第10頁，共27頁，2023年，2月20日，星期四(4)最后用產(chǎn)生式(3)?S→TPS(2)進(jìn)行歸約，S(2)語句序列處理完后繼續(xù)翻譯if語句之后的后繼語句。后繼語句的四元式地址與S(2)語句序列的出口一致，故將TP.chain與S(2).chain鏈接后掛入鏈頭為S.chain的鏈中，即：4.5控制語句的翻譯(2)C→if(E)(3)

S→TPS(2)

(4)

TP→CS(1);elseS→TPS(2){S.chain

=

merge(TP.chain,S(2).chain);}第11頁，共27頁，2023年，2月20日，星期四課堂練習(xí)：將下列語句翻譯成四元式（重點）4.5控制語句的翻譯（課本P120例4.5）if(x>y)if(a∧b)m=m+1;elsem=m-1;elsex=y;[解答]：解題技巧：不需要根據(jù)語義子程序，只需要畫出

代碼結(jié)構(gòu)圖，根據(jù)轉(zhuǎn)換關(guān)系來翻譯四元式：if(x>y)if(a∧b)m=m+1;elsem=m-1;elsex=y;

一個布爾分量對應(yīng)個四元式；else對應(yīng)個無條件跳轉(zhuǎn)四元式；

注意真假出口的預(yù)留與回填。21TFTFTF第12頁，共27頁，2023年，2月20日，星期四4.5控制語句的翻譯4.5.2條件循環(huán)語句while的翻譯1.循環(huán)語句的代碼結(jié)構(gòu)圖：while(E)S(1)圖4-12條件循環(huán)語句while的代碼結(jié)構(gòu)1：E的真出口是S(1)2：E的假出口是循環(huán)體外3：S(1)的后面無條件轉(zhuǎn)移，重新判斷E第13頁，共27頁，2023年，2月20日，星期四4.5控制語句的翻譯2.翻譯思想：S→while(E)S(1)

(1)翻譯E代碼段，并留兩個待填的E.tc和E.fc;(2)掃描過“)”之后，就可回填E.tc;(3)翻譯S(1)，然后無條件轉(zhuǎn)移到E的第一條四元式；因此：1.為了保證(3)的無條件轉(zhuǎn)移，必須保存E的第一條四元式序號；2.E為假時，需要回填，需要用S.chain保存E.fc;第14頁，共27頁，2023年，2月20日，星期四4.5控制語句的翻譯3.給出易于及時處理和回填的條件循環(huán)語句while的文法G[S]如下：

G[S]:

(1)

S→WdS(1)

(2)

Wd→W(E)

(3)

W→while語義子程序

例：while(a<b)S(1)

(1)使用(3)

W→while進(jìn)行規(guī)約。保存條件Ｅ的開始位置，也就是無條件語句轉(zhuǎn)移的位置。

W→while{W.quad=nxq;}第15頁，共27頁，2023年，2月20日，星期四4.5控制語句的翻譯例：while(a<b)S(1)

(2)使用(2)

Wd→W(E)進(jìn)行規(guī)約。

由于E的真出口已經(jīng)確定為nxq，回填E.tc;E.fc無法確定，Wd.chain用于保存待填信息，以備回填；

Ｅ的首入口(W.quad)用Wd.quad保存，以備強制轉(zhuǎn)移。

Wd→W(E)

{Backpatch(E.tc,nxq);

Wd.chain=E.fc;

Wd.quad=W.quad;}第16頁，共27頁，2023年，2月20日，星期四4.5控制語句的翻譯例：while(a<b)S(1)

(3)使用(1)

S→WdS(1)進(jìn)行規(guī)約。

如果S(1)也是if-else語句，S(1).chain表示S(1)后續(xù)的四元式序列，但不是while循環(huán)體外的四元式。這時的跳轉(zhuǎn)一定是再回到E條件，因此需要回填S(1).chain對應(yīng)的四元式串；

產(chǎn)生無條件跳轉(zhuǎn)四元式，回到E條件，進(jìn)行循環(huán)；

整個while語句的出口，是Wd

的出口，也就是E.fc。

S→WdS(1){Backpatch(S(1).chain,Wd.quad);

emit(j,_,_,Wd.quad);

S.chain=Wd.chain;}第17頁，共27頁，2023年，2月20日，星期四課堂練習(xí)：將下列語句翻譯成四元式（重點）4.5控制語句的翻譯（課本P121例4.6）while(A<B)if(C<D)X=Y+Z;[解答]：只需要畫出代碼結(jié)構(gòu)圖，根據(jù)轉(zhuǎn)換關(guān)系來翻譯四元式：

一個布爾分量對應(yīng)個四元式；else對應(yīng)個無條件跳轉(zhuǎn)四元式；while的循環(huán)體S最后必須有個強制跳轉(zhuǎn)四元式。211while(A<B)if(C<D)X=Y+Z;jumpq:{while后面的語句}TTFF第18頁，共27頁，2023年，2月20日，星期四課堂練習(xí)：將下列語句翻譯成四元式（重點）4.5控制語句的翻譯（課本P121例4.7）if(a∧b)while(x<y)if(m≠n)m=n;

elsem=m+1;//(+,m,1,m)

elsewhile(m>n)x=x+y;//(+,x,y,x)TTTTjumpFFFFqTF第19頁，共27頁，2023年，2月20日，星期四4.5控制語句的翻譯4.5.4多分支控制語句case的翻譯(自學(xué))4.5.5語句標(biāo)號和轉(zhuǎn)移語句的翻譯程序語言中直接改變控制流程的語句是gotoL語句，其中L是源程序中的語句標(biāo)號。標(biāo)號L在源程序中可以以兩種方式出現(xiàn)(1)定義性出現(xiàn)。定義性出現(xiàn)的語句形式為

L:S

此時，帶標(biāo)號的語句S所生成的第一個四元式地址即為標(biāo)號L的值。(2)引用性出現(xiàn)。引用性出現(xiàn)的語句形式為

gotoL

它引用L的值作為四元式(j,_,_,L)中轉(zhuǎn)向的目標(biāo)地址。第20頁，共27頁，2023年，2月20日，星期四4.5控制語句的翻譯翻譯gotoL語句需要查詢符號表，根據(jù)L是否已經(jīng)定值，將該語句的使用分為以下幾種情況：1.先定義，后使用：(1)形式：L:S—……—GOTOL—……(2)文法：S→gotoL(使用標(biāo)號)Label→i:(定義標(biāo)號)第21頁，共27頁，2023年，2月20日，星期四4.5控制語句的翻譯(3)翻譯過程：遇到標(biāo)號語句時，先將標(biāo)號規(guī)約為Lable,再將L填入符號表中：

其中，S.QUAD為S對應(yīng)的入口四元式序號；

當(dāng)后面的程序中遇到GOTOL時，便產(chǎn)生(j,_,_,S.QUAD)。

第22頁，共27頁，2023年，2月20日，星期四4.5控制語句的翻譯翻譯gotoL語句需要查詢符號表，根據(jù)L是否已經(jīng)定值，將該語句的使用分