編譯原理(4)語義_3(控制語句的翻譯)

1、第第 11 11 講講西北農(nóng)林科技大學(xué)本科教程西北農(nóng)林科技大學(xué)本科教程 主講教師：趙建邦主講教師：趙建邦 第四章第四章 語義分析和中間代碼生成語義分析和中間代碼生成l4.1 4.1 語義分析概述語義分析概述l4.2 4.2 屬性文法屬性文法l4.3 4.3 幾種常見的中間語言幾種常見的中間語言l4.4 4.4 表達式及賦值語句的翻譯表達式及賦值語句的翻譯l4.5 4.5 控制語句的翻譯控制語句的翻譯l4.6 4.6 數(shù)組元素的翻譯數(shù)組元素的翻譯l4.7 4.7 過程或函數(shù)調(diào)用語句的翻譯過程或函數(shù)調(diào)用語句的翻譯l4.8 4.8 說明語句的翻譯說明語句的翻譯l4.9 4.9 遞歸下降語法制導(dǎo)翻譯方

2、法簡介遞歸下降語法制導(dǎo)翻譯方法簡介u第四章第四章語義分析和中間代碼生成語義分析和中間代碼生成l4.5 4.5 控制語句的翻譯控制語句的翻譯l條件語句條件語句ififl條件循環(huán)語句條件循環(huán)語句whilewhilel多分支控制語句多分支控制語句case(case(自學(xué)自學(xué)) )l轉(zhuǎn)移語句轉(zhuǎn)移語句gotogotou重點掌握重點掌握l通過代碼結(jié)構(gòu)圖翻譯通過代碼結(jié)構(gòu)圖翻譯ifif、whilewhile語句語句( (重點重點) )本講目標(biāo)本講目標(biāo) 4.5 4.5 控制語句的翻譯控制語句的翻譯u4.5 程序流程控制的三種基本結(jié)構(gòu)程序流程控制的三種基本結(jié)構(gòu)l順序結(jié)構(gòu)：一般用復(fù)合語句實現(xiàn)；順序結(jié)構(gòu)：一般用復(fù)合語

3、句實現(xiàn)；l選擇結(jié)構(gòu)：選擇結(jié)構(gòu)：if-else , switch-case;if-else , switch-case;l循環(huán)結(jié)構(gòu)：循環(huán)結(jié)構(gòu)：forfor，while, do-whilewhile, do-while4.5 4.5 控制語句的翻譯控制語句的翻譯圖圖4-11 if(E)S的代碼結(jié)構(gòu)的代碼結(jié)構(gòu)圖圖4-10 條件語句條件語句if(E)S1;else S2的的代碼結(jié)構(gòu)代碼結(jié)構(gòu)4.5 4.5 控制語句的翻譯控制語句的翻譯l為了在掃描條件語句過程中不失時機地處理和回填有關(guān)信息，為了在掃描條件語句過程中不失時機地處理和回填有關(guān)信息，可將可將GS改寫為如下的改寫為如下的GS ： GS: (1)

4、SCS(1) (2) Cif(E) (3) STPS(2) (4) TPCS(1);else4.5 4.5 控制語句的翻譯控制語句的翻譯(1)無論是哪種無論是哪種if語句，首先用產(chǎn)生式語句，首先用產(chǎn)生式(2) Cif(E)進行歸約，這進行歸約，這時時E的真出口即為的真出口即為S(1)的第一個四元式；的第一個四元式；E的假出口地址則作為的假出口地址則作為待填信息放在待填信息放在C的語義變量的語義變量C.chain中等待回填；中等待回填； 所以：所以：4.5 4.5 控制語句的翻譯控制語句的翻譯 Cif(E) Backpatch(E.tc, nxq); C.chain=E.fc; (1) SCS(

5、1) (2) Cif(E)掃描到掃描到“)”，立即回填，立即回填E的真出口的真出口C.chain中只保存中只保存E的待填假出口的待填假出口if ( E ) S(1) else S(2) TF(2)不含不含else時，用時，用(1) SCS(1)進行規(guī)約，進行規(guī)約，E的假出口是的假出口是S(1)的出的出口，將口，將C.chain和和S(1).chain一起作為一起作為S的待填信息鏈用函數(shù)的待填信息鏈用函數(shù)merge鏈在一起保留在鏈在一起保留在S的語義值的語義值S.chain中：中：4.5 4.5 控制語句的翻譯控制語句的翻譯 (1) SCS(1) (2) Cif(E)SCS(1) S.chain

6、 = merge(C.chain,S(1).chain)if ( E ) S(1)TFC S(1)S(1).chain=104C.chain=101S.chain=104規(guī)約后：S(1).chainC.chain練習(xí)：練習(xí)：if (a) if (b) c = 1;(3)用產(chǎn)生式用產(chǎn)生式(2) Cif(E)進行歸約之后，如果：條件語句后有進行歸約之后，如果：條件語句后有else，用，用(4)繼續(xù)規(guī)約。繼續(xù)規(guī)約。4.5 4.5 控制語句的翻譯控制語句的翻譯(2) Cif(E) (3) STPS(2) (4) TPCS(1);elseTP CS(1); else q=nxq; emit(j,_,_,

7、0); Backpatch(C.chain,nxq); TP.chain=merge(S(1) .chain, q); 注意注意1：只要遇到有：只要遇到有else的規(guī)約，必須先產(chǎn)生一條無條件轉(zhuǎn)移。的規(guī)約，必須先產(chǎn)生一條無條件轉(zhuǎn)移。if ( E ) S(1) ;else S(2) C S(1) ;else S(2) TP S(2) 2： S(2) 就是就是C.chain3：q就是就是S(1) .chainif ( E ) S(1) ;else S(2) TFq: (j,_,_,0)nxq:(4)最后用產(chǎn)生式最后用產(chǎn)生式(3) STPS(2)進行歸約，進行歸約， S(2)語句序列處理完語句序列處理

8、完后繼續(xù)翻譯后繼續(xù)翻譯if語句之后的后繼語句。后繼語句的四元式地址與語句之后的后繼語句。后繼語句的四元式地址與S(2)語句序列的出口一致，故將語句序列的出口一致，故將TP.chain與與S(2).chain鏈接后掛入鏈接后掛入鏈頭為鏈頭為S.chain的鏈中，即：的鏈中，即：4.5 4.5 控制語句的翻譯控制語句的翻譯(2) Cif(E) (3) STPS(2) (4) TPCS(1);elseSTPS(2) S.chain = merge(TP.chain, S(2).chain);練習(xí)：練習(xí)：if (a) b =1; else b = 2;課堂練習(xí)：將下列語句翻譯成四元式課堂練習(xí)：將下列語

9、句翻譯成四元式（重點）（重點）4.5 4.5 控制語句的翻譯控制語句的翻譯（課本（課本P120 例例4.5）if (xy) if(a b) m=m+1;else m=m-1;else x=y;解答解答：解題技巧：不需要根據(jù)語義子程序，只需要畫出：解題技巧：不需要根據(jù)語義子程序，只需要畫出 代碼結(jié)構(gòu)圖代碼結(jié)構(gòu)圖，根據(jù)轉(zhuǎn)換關(guān)系來翻譯四元式：，根據(jù)轉(zhuǎn)換關(guān)系來翻譯四元式：if (xy) if(a b) m=m+1;else m=m-1;else x=y; 一個布爾分量對應(yīng)一個布爾分量對應(yīng) 個四元式；個四元式； else對應(yīng)對應(yīng) 個無條件跳轉(zhuǎn)四元式；個無條件跳轉(zhuǎn)四元式； 注意真假出口的預(yù)留與回填。注意真

10、假出口的預(yù)留與回填。21TFTFTF4.5 4.5 控制語句的翻譯控制語句的翻譯u4.5.2 循環(huán)語句循環(huán)語句while的翻譯的翻譯l1.1.循環(huán)語句的代碼結(jié)構(gòu)圖：循環(huán)語句的代碼結(jié)構(gòu)圖：while (E) S(1) 圖圖4-12 4-12 條件循環(huán)語句條件循環(huán)語句whilewhile的代碼結(jié)構(gòu)的代碼結(jié)構(gòu)1：E的真出口是的真出口是S(1)2：E的假出口是循環(huán)的假出口是循環(huán)體外體外3：S(1)的后面無條件的后面無條件轉(zhuǎn)移，重新判斷轉(zhuǎn)移，重新判斷E4.5 4.5 控制語句的翻譯控制語句的翻譯l2.2.翻譯思想：翻譯思想：S while (E) S(1) (1)(1)翻譯翻譯E代碼段，并留兩個待填的代

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

12、1) SWdS(1) (2) WdW(E) (3) Wwhilel語義子程序語義子程序 例：例：while(ab) S(1) (1) 使用使用(3) Wwhile進行規(guī)約。保存條件的開始位置，進行規(guī)約。保存條件的開始位置，也就是無條件語句轉(zhuǎn)移的位置。也就是無條件語句轉(zhuǎn)移的位置。 Wwhile W.quad=nxq; 4.5 4.5 控制語句的翻譯控制語句的翻譯l例：例：while(ab) S(1) (2)使用使用(2) WdW(E)進行規(guī)約。進行規(guī)約。 由于由于E的真出口已經(jīng)確定為的真出口已經(jīng)確定為nxq，回填，回填E.tc; E.fc無法確定，無法確定，Wd.chain用于保存待填信息，以備

13、回填；用于保存待填信息，以備回填； 的首入口的首入口(W.quad)用用Wd.quad保存，以備強制轉(zhuǎn)移。保存，以備強制轉(zhuǎn)移。 WdW(E) Backpatch(E.tc,nxq); Wd.chain=E.fc; Wd.quad= W.quad; 4.5 4.5 控制語句的翻譯控制語句的翻譯l例：例：while(ab) S(1) (3)使用使用(1) SWdS(1)進行規(guī)約。進行規(guī)約。 如果如果S(1)也是也是if-else語句，語句，S(1).chain表示表示S(1)后續(xù)的四元式序后續(xù)的四元式序列，但不是列，但不是while循環(huán)體外的四元式。這時的跳轉(zhuǎn)一定是再回循環(huán)體外的四元式。這時的跳轉(zhuǎn)

14、一定是再回到到E條件，因此需要回填條件，因此需要回填S(1).chain對應(yīng)的四元式串；對應(yīng)的四元式串； 產(chǎn)生無條件跳轉(zhuǎn)四元式，回到產(chǎn)生無條件跳轉(zhuǎn)四元式，回到E條件，進行循環(huán)；條件，進行循環(huán)； 整個整個while語句的出口，是語句的出口，是Wd 的出口，也就是的出口，也就是E.fc。 SWd S(1) Backpatch (S(1).chain,Wd.quad); emit(j,_,_,Wd.quad); S.chain= Wd .chain; 課堂練習(xí)：將下列語句翻譯成四元式課堂練習(xí)：將下列語句翻譯成四元式（重點）（重點）4.5 4.5 控制語句的翻譯控制語句的翻譯（課本（課本 例例4.6）

15、while(AB) if (CD) X = Y+Z;解答解答：只需要畫出：只需要畫出代碼結(jié)構(gòu)圖代碼結(jié)構(gòu)圖，根據(jù)轉(zhuǎn)換關(guān)系來翻譯四元式：，根據(jù)轉(zhuǎn)換關(guān)系來翻譯四元式： 一個布爾分量對應(yīng)一個布爾分量對應(yīng) 個四元式；個四元式； else對應(yīng)對應(yīng) 個無條件跳轉(zhuǎn)四元式；個無條件跳轉(zhuǎn)四元式； while的循環(huán)體的循環(huán)體S最后必須有最后必須有 個強制跳轉(zhuǎn)四元式。個強制跳轉(zhuǎn)四元式。211 while(AB) if (CD) X = Y+Z; jump q:while后面的語句后面的語句TTFF課堂練習(xí)：將下列語句翻譯成四元式課堂練習(xí)：將下列語句翻譯成四元式（重點）（重點）（ 例例4.7 ）if (a b) whi

16、le (xn) x = x + y; /(+,x,y,x)qTFTFTFFTTF1. 將下面的語句翻譯成四元式序列，規(guī)定四元式的標(biāo)將下面的語句翻譯成四元式序列，規(guī)定四元式的標(biāo)號從號從100開始。開始。if(ab)while(AD) X = X-1； else X=X+1；else X=Y；void WhileStatement(): /while 語句語句 condition() StatementBlock() 程序程序 void main ( ) 語句塊語句塊* 語句塊語句塊 語句語句 | 語句塊語句塊* 語句語句 順序語句順序語句 | 條件語句條件語句 |循環(huán)語句循環(huán)語句實習(xí)內(nèi)容：實習(xí)內(nèi)

17、容：while語句的翻譯語句的翻譯cValue = qtTable.addQTInfo(new QTInfo(J, _, _, quad); / 回填回填cValue假鏈假鏈 quad = 條件語句四元式起始序號條件語句四元式起始序號; / 回填回填cValue真鏈真鏈 int quad; /記錄條件語句四元式起始序號記錄條件語句四元式起始序號ConditionValue cValue; / 條件表達式返回值：真、假鏈條件表達式返回值：真、假鏈 4.5 4.5 控制語句的翻譯控制語句的翻譯u4.5.3 for語句的翻譯語句的翻譯lforfor語句的代碼結(jié)構(gòu)圖：語句的代碼結(jié)構(gòu)圖：for ( E1

18、; E2; E3) S(1) 四元式的出現(xiàn)次序四元式的出現(xiàn)次序for語句代碼結(jié)構(gòu)語句代碼結(jié)構(gòu)4.5 4.5 控制語句的翻譯控制語句的翻譯u4.5.4 多分支控制語句多分支控制語句case的翻譯的翻譯(自學(xué)自學(xué))u4.5.5 語句標(biāo)號和轉(zhuǎn)移語句的翻譯語句標(biāo)號和轉(zhuǎn)移語句的翻譯l程序語言中直接改變控制流程的語句是程序語言中直接改變控制流程的語句是goto Lgoto L語句，其中語句，其中L L是是源程序中的語句標(biāo)號源程序中的語句標(biāo)號。標(biāo)號。標(biāo)號L L在源程序中可以以兩種方式出現(xiàn)在源程序中可以以兩種方式出現(xiàn)(1) 定義性出現(xiàn)定義性出現(xiàn)。定義性出現(xiàn)的語句形式為。定義性出現(xiàn)的語句形式為L: S此時，帶標(biāo)

19、號的語句此時，帶標(biāo)號的語句S所生成的第一個四元式地址即為標(biāo)號所生成的第一個四元式地址即為標(biāo)號L的值。的值。(2) 引用性出現(xiàn)引用性出現(xiàn)。引用性出現(xiàn)的語句形式為。引用性出現(xiàn)的語句形式為 goto L它引用它引用L的值作為四元式的值作為四元式(j,_,_,L)中轉(zhuǎn)向的目標(biāo)地址。中轉(zhuǎn)向的目標(biāo)地址。4.5 4.5 控制語句的翻譯控制語句的翻譯l翻譯翻譯goto L 語句需要查詢符號表，根據(jù)語句需要查詢符號表，根據(jù)L是否已經(jīng)定值，將該是否已經(jīng)定值，將該語句的使用分為以下幾種情況：語句的使用分為以下幾種情況：l1. 先定義，后使用：先定義，后使用： (1)形式：形式： L:S GOTO L (2)文法：文

20、法： S goto L (使用標(biāo)號使用標(biāo)號) Label i: (定義標(biāo)號定義標(biāo)號)4.5 4.5 控制語句的翻譯控制語句的翻譯 (3) (3)翻譯過程：遇到標(biāo)號語句時，先將標(biāo)號規(guī)約為翻譯過程：遇到標(biāo)號語句時，先將標(biāo)號規(guī)約為Lable,Lable,再再將將L L填入符號表中：填入符號表中： 其中，其中，S.QUAD為為S對應(yīng)的入口四元式序號；對應(yīng)的入口四元式序號； 當(dāng)后面的程序中遇到當(dāng)后面的程序中遇到GOTO L時，便產(chǎn)生時，便產(chǎn)生(j,_,_,S.QUAD)。 4.5 4.5 控制語句的翻譯控制語句的翻譯l翻譯翻譯goto L 語句需要查詢符號表，根據(jù)語句需要查詢符號表，根據(jù)L是否已經(jīng)定值，

21、將該是否已經(jīng)定值，將該語句的使用分為以下幾種情況：語句的使用分為以下幾種情況：l2. 先使用，后定義：先使用，后定義： (1)形式：形式： GOTO L GOTO L L:S (2)翻譯過程：當(dāng)遇到符號翻譯過程：當(dāng)遇到符號L時，符號表中還未定義，填入符時，符號表中還未定義，填入符號表中的信息與之前有些不同，如下：號表中的信息與之前有些不同，如下：4.5 4.5 控制語句的翻譯控制語句的翻譯 第一次遇到第一次遇到L L的翻譯過程：的翻譯過程： (a)(a)填符號表，將填符號表，將“定義否定義否”一欄填寫一欄填寫“未未”，地址欄暫時，地址欄暫時填寫即將生成的四元式序號，填寫即將生成的四元式序號，CATCAT欄填寫欄填寫“標(biāo)號標(biāo)號”； (b)(b)生成四元式生成四元式(p)(j,_,_,0)(p)(j,_,_,0)等待回填；等待回填；4.5 4.5 控制語句的翻譯控制語句的翻譯 第二次遇到第二次遇到L L的翻譯過程：的翻譯過程： (c)(c)修改符號表，僅將地址欄內(nèi)容修改為即將生成的四元式修改符號表，僅將地址欄內(nèi)容修改為即將生成的四元式序號序號q q； (d)(d)生成四元式生成四元式(q)(j,_,_,p),(q)(j,_,_,p),其中第四字段的其中第四字段的p p取自取自L L的地的地址欄修改前的內(nèi)容，即形