編譯第七章語法制導(dǎo)翻譯.ppt

《編譯第七章語法制導(dǎo)翻譯.ppt》由會員分享，可在線閱讀，更多相關(guān)《編譯第七章語法制導(dǎo)翻譯.ppt（108頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第七章語法制導(dǎo)翻譯和中間代碼生成,第一節(jié) 概述,語法分析之后，編譯的任務(wù)是由已識別為正確的源程序生成一組規(guī)格一致，便于計算機加工的指令形式。 一、中間代碼生成方法 語法制導(dǎo)翻譯，屬性文法制導(dǎo)翻譯 二、中間代碼 中間代碼：不是機器語言，便于生成機器語言，便于代碼優(yōu)化。 中間代碼的形式： -------逆波蘭式 -------樹形表示法 -------三元式 -------四元式：最常用的形式,第七章中間代碼的生成 1,第一節(jié) 概述,二、翻譯方法 1、語法制導(dǎo)翻譯 ----在語法分析的基礎(chǔ)上進行邊分析邊翻譯。 注：1）語法制導(dǎo)翻譯時會根據(jù)文法產(chǎn)生式右部符號串的含義進行翻譯，翻譯的結(jié)果是生成相應(yīng)中間

2、代碼。 2）語法制導(dǎo)翻譯的依據(jù)是語義子程序。 3）具體做法：為每個產(chǎn)生式配置一個語義子程序，當語法分析進行歸約或推導(dǎo)時，調(diào)用語義子程序，完成一部分翻譯任務(wù)。 4）語法分析完成，翻譯工作也告結(jié)束。,第七章中間代碼的生成 2,第一節(jié) 概述,二、翻譯方法 1、語法制導(dǎo)翻譯 ---語法制導(dǎo)翻譯適用于多種語法分析 ---語法制導(dǎo)翻譯種類 1、自上而下語法制導(dǎo)翻譯：對每個文法符號配以語義動作。 2、自下而上語法制導(dǎo)翻譯：我們主要討論LR語法制導(dǎo)翻譯,第七章中間代碼的生成 3,第一節(jié) 概述,三、語義子程序 1、作用 用來描述一個產(chǎn)生式所對應(yīng)的翻譯工作。 ---如：改進某些變量的值；查填各種符號表；發(fā)現(xiàn)并報告

3、源程序錯誤；產(chǎn)生中間代碼等。 注；這些翻譯工作很大程度上決定了要產(chǎn)生什么形式的中間代碼,三、語義子程序 2、寫法 語義子程序?qū)懺谠摦a(chǎn)生式后面的花括號內(nèi)。 X a語義子程序 注：在一個產(chǎn)生式中同一個文法符號可能出現(xiàn)多次，但它們代表的是不同的語義值，要區(qū)分可以加上角標。 如： E E(1)+E(2) 3、語義值 為了描述語義動作，需要為每個文法符號賦予不同的語義值：類型，地址，代碼值等。,第一節(jié) 概述,,,第一節(jié) 概述,三、語義子程序 4、語義棧 各個符號的語義值放在語義棧中 ---當產(chǎn)生式進行歸約時，需對產(chǎn)生式右部符號的語義值進行綜合， 其結(jié)果作為左部符號的語義值保存到語義棧中。 下推棧包

4、含3部分： ---狀態(tài)棧、符號棧和語義棧 ---注：語義棧與狀態(tài)棧和符號棧是同步變化的。,第一節(jié) 概述,三、語義子程序 注：1）若把語義子程序改成產(chǎn)生某種中間代碼的動作，就能在語法分析制導(dǎo)下，隨著分析的進展逐步生成中間代碼。 2）若把語義子程序改成產(chǎn)生某種機器的匯編語言指令，就能隨著分析的進展逐步生成某機器的匯編語言代碼。,第一節(jié) 概述,例如： 產(chǎn)生式 語義子程序 (0)S E PRINT E VAL (1)E E(1) +E(2) EVAL=E(1)VAL+E(2)VAL (2)E E(1) * E(2) EVAL=E(1)VAL*E(2)VAL (3)E (E(1))

5、 EVAL=E(1)VAL (4)E i EVAL=LEXVAL 注：LEXVAL指的是詞法分析送來的機內(nèi)二進制整數(shù)。,,,,,,下推棧,第一節(jié) 概述,注：由于語義值是放在語義棧中的，它也可以用棧頂指針TOP指出，語義子程序改寫為： 產(chǎn)生式 語義子程序 (0)S E PRINT VALTOP (1)E E(1) +E(2) VALTOP=VALTOP+VALTOP+2 (2)E E(1) * E(2) VALTOP=VALTOP*VALTOP+2 (3)E (E(1)) VALTOP=TOP+1 (4)E i VALTOP=LEXVAL 注：LEXVAL指的是詞法分析

6、送來的機內(nèi)二進制整數(shù)。,,,,,,第一節(jié) 概述,例如：分析輸入串(7+9)*5#,并給出它的計算過程。分析表如下：,第一節(jié) 概述,四、常見的中間代碼形式 1.四元式形式 （Operator,Operand1, Operand2, Result) 注：1）Operand1, Operand2, Result可能是用戶自定義的變量，也可能是編譯時引進的變量，這里Operator是雙目運算符，若只有一個運算量，則是單目運算符。 2）四元式中變量采用符號表入口的地址，而不用變良的地址，因為語義分析不僅需要變量的地址，還需要從符號表查到的變量的屬性，類型和地址等。,第一節(jié) 概述,四、常見的中間代碼形式

7、 2.三元式 （Operator,Operand1, Operand2） 注：1）這里三元式本身作為存放結(jié)果的單元。 2）為了在其它三元式中利用當前三元式的結(jié)果，需要對三元式進行遍號。三元式的編號就作為相應(yīng)三元式的結(jié)果值。,第一節(jié) 概述,四、常見的中間代碼形式 3、后綴表示式（逆波蘭表示式） Operand1 Operand2 Operator 4、樹型表示法,Operator,Operand2,Operand1,,,注：常用中間代碼表示法是四元式,第二節(jié) 簡單算術(shù)表達式和賦值語句的翻譯,一、賦值語句的翻譯 ----僅含簡單變量的表達式和賦值語句的翻譯 1、賦值語句的文法 A i=E E

8、 E+E|E*E|-E|(E)|i 2、需要的語義過程 NEWTEMO函數(shù)：每次使用送回一個代表新臨時變量的序號，可認為是送回T1,T2這樣的一些臨時變量； ENTRY(i)函數(shù)：用于查變量i的符號表入口地址； GEN(OP,ARG1,ARG2,RESULT)過程：產(chǎn)生一個四元式，并填入四元式序列表,,,第二節(jié) 簡單算術(shù)表達式和賦值語句的翻譯,一、賦值語句的翻譯 3、需要的語義變量 EPLACE:與非終結(jié)符E相聯(lián)系的語義變量 ---值為某變量的符號表入口地址或臨時變量序號。 ---它與文法的非終結(jié)符相聯(lián)，分析過程就建立，不需要就消亡。,產(chǎn)生式 語義子程序 (1)A i=E GEN

9、(=,EPLACE,_,ENTRY(i) (2)E -E(1) T=NEWTEMP; ---- GEN(,E(1)PLACE,_,T); ---- EPLACE=T (3)E E(1)*E(2) T=NEWTEMP; GEN(*,E(1)PLACE,E(2)PLACE,T); EPLACE=T (4)E E(1)+E(2) T=NEWTEMP; GEN(+,E(1)PLACE,E(2)PLACE,T); EPLACE=T (5)E (E(1)) EPLACE=E(1)PLACE (6)E i EPLACE=ENTRY(i),,,,,,,注：1、符號

10、棧是為了介紹才列出的，實際上不存在。 2、由于語義分析是在語法分析的過程中進行的，所以狀態(tài)棧實際上是需要的，這里沒有寫出來。 3、這個分析過程是針對整型變量做的。實際上在一個表達式中，可能出現(xiàn)各種不同類型的變量或常量，所以，編譯程序要么拒絕接受某種混合運算，要么能產(chǎn)生有關(guān)類型轉(zhuǎn)換的指令。,第二節(jié) 簡單算術(shù)表達式和賦值語句的翻譯,類型轉(zhuǎn)換 對于表達式文法中的i是實型又可以是整型。 對這種混合運算，我們要先把整型量轉(zhuǎn)化為實型量，就需要為每個非終結(jié)符的語義值添加類型信息，用EMODE表示非終結(jié)符E的類型信息。 1、定義各非終結(jié)符的類型信息 產(chǎn)生式E E(1)op E(2)的語義動作中要加入關(guān)于EMO

11、DE的語義規(guī)則的定義； --IF E(1)MODE=int AND E(2)MODE=int --IF EMODE=int ELSE EMODE=r,,第二節(jié) 簡單算術(shù)表達式和賦值語句的翻譯,2、對運算量進行類型轉(zhuǎn)換 例如：X=Y+I*J,其中X,Y是實型，I,J是整型。 其四元式為： --(*I,I,J,T1) --(itr,T1,_,T2) --(+r,Y,T2,T3) --(=,T3,_,X),第二節(jié) 簡單算術(shù)表達式和賦值語句的翻譯,注：1)對運算符也要指出相應(yīng)的類型（運算符上加角標），說明是定點還是浮點遠算。 2)由于非終結(jié)符E的語義值有EPLACE和EMODE兩個，這兩者都要保存在語

12、義棧中。 3)在運算量的類型較多的情況下，需要仔細推敲語義規(guī)則，否則語義子程序會變置累贅不填。,第三節(jié) 布爾表達式的翻譯,一、布爾表達式在程序設(shè)計語言中的作用 --用作控制語句中的條件表達式 --用于邏輯賦值語句中布爾表達式演算 二、布爾表達式的組成 --由布爾算符作用于布爾變量（或常量）或關(guān)系表達式而形成的。 --布爾算符：,, --關(guān)系表達式的形式： E(1)rop E(2),其中rop是關(guān)系運算符（如,=,), E(1)和E(2)是算術(shù)表達式。,,,第三節(jié) 布爾表達式的翻譯,三、布爾表達式的文法： --G(B):E EE|EE| E|(E)|i|Ea rop Ea --i為布爾變量或常

13、量；Ea為算術(shù)表達式。 注：1)此文法為二義文法，一般布爾算符的優(yōu)先順序為： ,,服從左結(jié)合律；關(guān)系運算優(yōu)先級別高于布爾運算。 2)由于布爾表達式有兩種用途，所以有兩種不同的翻譯方法。,,,,,,第三節(jié) 布爾表達式的翻譯,四、布爾表達式在邏輯演算中的翻譯 1、語義子程序 由于布爾表達式演算與算術(shù)表達式計算非常類似，可以仿照算術(shù)表達式的翻譯方法，為每個產(chǎn)生式寫出語義子程序。,產(chǎn)生式 語義子程序 (1)E Ea(1)ropEa(2) T=NEWTEMP; GEN(rop,Ea(1)PLACE,Ea(2)PLACE,T); EPLACE=T (2)E Ea(1)bopEa

14、(2) T=NEWTEMP; GEN(bop,Ea(1)PLACE,Ea(2)PLACE,T); EPLACE=T (3)E E(1) T=NEWTEMP; GEN( ,E(1)PLACE,_,T); EPLACE=T (4)E (E(1)) EPLACE=E(1)PLACE (5)E i EPLACE=ENTRY(i),,,,,,,,,,第三節(jié) 布爾表達式的翻譯,四、布爾表達式在邏輯演算中的翻譯 2、實例：對布爾式X+YZA( BC) 進行翻譯： 解：語法制導(dǎo)翻譯是在語法分析下的過程中進行的，若利用G(B)文法的LR分析表對上句進行LR分析，在其過程

15、中進行語義分析；則得到對上句進行LR分析，在其過程中進行語義分析；則得到的四元式序列是： --(+,X,Y,T1);E+E進行歸約，識別了算術(shù)運算 --(,T1,Z,T2);EE進行歸約，識別了關(guān)系運算 --( ,B,_,T3); E歸約 --(,T3,C,T4);EE進行歸約 --(,A,T4,T5); EE進行歸約 --(,T2,T5,T6); EE進行歸約,,,,,,,第三節(jié) 布爾表達式的翻譯,注：上面的翻譯質(zhì)量并不高，可以采取某種優(yōu)化措施： 例如： 對AB.若已知A的值是1.那么 B的值就不需要知道就能得出AB=1； ---可以表示為：IF A THEN TRUE ELSE B 對AB

16、若已知A的值是0，那么B的值就不需要知道就錯得出AB=0； ---可以表示為： IF A THEN FALSE ELSE TRUE,第三節(jié) 布爾表達式的翻譯,五、控制語句中布爾式的翻譯 1、控制語句中布爾式并不需要計算表達式的值，只用if-then-else來解釋, , ,以來控制程序流向。 If E then S1 else S2,,,E的代碼序列,S1的代碼序列,S2的代碼序列,,,,,,,,假,真,第三節(jié) 布爾表達式的翻譯,五、控制語句中的布爾式的翻譯 2、控制語句中的布爾式的翻譯的四元式為以下三種： (juz,A1,_,P - if A1 then goto P (jQ,A1,A2,

17、 - if A1QA2 then goto P (j,_,_,P) -Goto P 注：這些四元式都是轉(zhuǎn)移四元式，其中P為出口的四元式序號，與E的真假值相對應(yīng)的分別為真出口和假出口兩類四元式。,例如：把語句if AB

18、2代碼段 (p+1)S2語句的第一個四元式 . (q)此語句的后繼語句,第三節(jié) 布爾表達式的翻譯,五、控制語句中布爾式的翻譯 4、增加語義值 ETC、EFC的值也可以放在語義棧中，即下推棧又增加了兩欄.,S,SYM,PLACE,TC,FC,分析棧,語義棧,,,第三節(jié) 布爾表達式的翻譯,五、控制語句中布爾式的翻譯 5、文法G(B)各產(chǎn)生式的語義子程序 ----文法：E EAE|E0E| E|(E)|i|EaropEa EA E E0 E 語義子程序： --(1)E i ETC=NXQ; EFC=NXQ+1; -- GEN(jnz,ENTRY(i),_,O); -- GEN(

19、j,_,_,O) --注：將布爾型操作數(shù)進行歸約，產(chǎn)生兩個四元式； 無論真假都不知該轉(zhuǎn)到哪個四元式上去，故轉(zhuǎn)向0,,,,,,例如：將控制語句中的AB

20、轉(zhuǎn)移到歸約后的下一個四元式，即判斷右邊式子的值的第一個四元式。,,第三節(jié) 布爾表達式的翻譯,五、控制語句中布爾式的翻譯 5、文法G(B)各產(chǎn)生式的語義子程序 PROCEDURE BACKPATCH(p,t) Q=P; WHILE (Q0) q=四元式Q第四段的內(nèi)容； 把t填入四元式Q的第四段； Q=q; 注：其算法思想是：從鏈頭算起，邊找邊讀，直到鏈尾為止。,例如：將控制語句中的AB

21、G(B)各產(chǎn)生式的語義子程序 (2)E EaropEa -- ETC=NXQ; EFC=NXQ+1; -- GEN(jrop,Ea(1)PLACE,Ea(2)PLACE,0); -- GEN(j,_,_,0),,例如：將控制語句中的AB

22、8) E E0E(2) -- EFC=E(2)FC; -- ETC=MERG(E0TC, E(2)TC 注：由于E的真假決定于E(2)為假時它們的轉(zhuǎn)移相同；由于E(1)或E(2)為真時都導(dǎo)致問真，所以它們?yōu)檎娴那闆r要合并起來。,,例如：將控制語句中的AB

23、HILE 四元式P的第4段內(nèi)容不為0 P=四元式P的第4段內(nèi)容； 把P1填進四元式P的第四段； MERG=P2; 注：算法思想：找到P2的鏈尾，然后將P1連接到P2的鏈尾。,第三節(jié) 布爾表達式的翻譯,(3)E (E(1)) ETC=E(1)TC; EFC=E(1)FC (4)E E(1) ETC=E(1)FC; EFC=E(1)FC (5)EA E(1) -- BACKPATCH(ETC,NXQ); -- EAFC=E(1)FC; (6)E EAE(2) -- ETC=E(1)TC; -- EFC=MERG(EAFC,E(2)FC,,,,,第三節(jié) 布爾表達式的翻譯,五、控制語句中布

24、爾式的翻譯 例如：將布爾式AB C在語法制導(dǎo)下翻譯成四元式。,,,,,,,,,,,,,,,,,,,,,,,,,,,,,第四節(jié) 控制語句的翻譯,一、控制語句的種類： 無條件轉(zhuǎn)換語句 條件語句 迭代語句 循環(huán)語句 分支語句,第四節(jié) 控制語句的翻譯,二、標號和轉(zhuǎn)移語句(GOTO) 1、標號和轉(zhuǎn)移語句(GOTO) (1)標號語句 ---GOTO語句實現(xiàn)無條件轉(zhuǎn)移，要確定轉(zhuǎn)移的目的語句，需要給語句加標號。 ---帶標號的語句形式：L:S L是標號 (2)標號的定義和使用： ---先定義后使用 L:S ..GOTO L ---先使用后定義 GOTO LL:S,第四節(jié) 控制語句的翻譯,2、先定義后使用 (1

25、)形式：L:S --- . --- GOTO L --- . (2)定義和使用表號的文法 --- S goto L --- Label i: (3)翻譯過程： ---當遇到定義性的標號語句時，將L歸約為Label，再將L填入符號表，如下：,,,S.QUAD:即S對應(yīng)的入口四元式序號。 當后面遇到GOTO L語句時，便產(chǎn)生四元式： (j,_,_,P), 其中P=S.QUAD,2、先使用后定義 (1)形式：GOTO L ------ ------ GOTO L ------ . ------ GOTO L ------ . ------ L:S (2)翻

26、譯過程： ----由于這里是先使用，所以當遇到標號L時，它還未定義，故而填入符號表時情況與上不同，表如下：,(2)翻譯過程： (a)填符號表：將定義否欄填“未”，地址檔暫填即將生成的四元式序號P,CAT欄填“標號”； (b)生成四元式 (P) (j,_,_,0),等待回填；,(c)當遇到第2個使用性標號L時，修改符號表，僅將L這一行的地址欄內(nèi)容修改為即將生成的四元式序號q; (b)生成四元式 (q) (j,_,_,P),其中第四段的P取自符號表的地址欄在修改前的內(nèi)容，即形成一個需要回填的鏈，不斷重復(fù)(c)(d).,,(p) (j,_,_,0) (q) (j,_,_,p) (r) (j,_,_,

27、q),第四節(jié) 控制語句的翻譯,二、標號和轉(zhuǎn)移語句(GOTO) 2、先使用后定義 (2)翻譯過程： ---e)當定義性語句L:S出現(xiàn)時，用S語句所對應(yīng)的第一個四元式序號回填這個鏈，即使用 BACKPATCH過程。 ---注：此鏈表的鏈首在符號表的相應(yīng)行的地址欄內(nèi)。 (3)形式化的語義子程序： ---產(chǎn)生式 語義子程序 --- S goto L 程序1 ---label i: 程序2,,,----查符號表： ----若L不在表中，在表中建L這行，CAT欄置標號，定義否填“未”，地址為NXQ;GEN(j,_,_,0); ----若L在表中，但未定義，則;P=L

28、地址； L.地址為NXQ;GEN(j,_,_,p); ----若L在表中，已定義，則:P=L.地址； GEN(j,_,_,p); ----,----查符號表： ----若L不在表中，在表中建L這行，CAT欄置標號，定義否填“已”，地址為NXQ; ----若L已在表中，但定義否填“已”或CAT標號，則出錯； ----否則，將定義否改為“已”； ----q=L.地址； ----BACKPATCH(q.NXQ); ----L.地址=NXQ; ----,第四節(jié) 控制語句的翻譯,三、IF語句的翻譯 1、描述IF語句的文法 ----S if E then S(1) ----S if E then

29、S(1) else S(2) 2、IF語句的翻譯 ---(1)完成對布爾式E的翻譯，獲得一元四元式，并留下兩個待續(xù)的語義值EEC，EFC; ---(2)掃描完then之后，就得到了E的真出口，用BACKPATCH(EEC,NXQ)過程或填； ---(3)翻譯S(1)，它可能會是任何一種語句，總可以遞歸地調(diào)用語句翻譯過程來完成，得到一組四元式序列；,,,第四節(jié) 控制語句的翻譯,三、IF語句的翻譯 2、IF語句的翻譯 ---(4)若遇到else，表示S(1)已翻譯完，應(yīng)無條件生成一條GOTO四元式(j,_,_,0)轉(zhuǎn)到S(2)語句后面，以示這個IF語句已執(zhí)行結(jié)束。但這個無條件轉(zhuǎn)移語句究竟轉(zhuǎn)到什么地

30、方去,是不確定的.甚至在翻譯完S(2)語句之后也不一定確定下來。遇到else還表示已獲得E的假出口。 例如：語句 ---if E1 then if E2 then S1 else S2 else S3 注：由于轉(zhuǎn)移指令的轉(zhuǎn)移目標只能等到出口明朗了才能回填。此時應(yīng)把該待填的四元式序號并鏈后存在與代表整個語句的非終結(jié)符S相聯(lián)系的語義棧 SCHAIN中。,第四節(jié) 控制語句的翻譯,三、IF語句的翻譯 2、IF語句的翻譯 (4)若不遇到else，那么布爾式的假出口與S(1)的結(jié)束出口都表示IF語句的結(jié)束。 (5)翻譯S(2)語句成四元式序列。它執(zhí)行過后也表示IF語句應(yīng)該結(jié)束了，它的結(jié)束出口和S(1)是一

31、樣的，可將它們出口并鏈，鏈首置于SCHAIN. 姑，條件語句翻譯之后，除了生成相應(yīng)E,S(1),S(2)的四元式之外，還剩下一個待填語句鏈，鏈首在 SCHAIN中，出口明確后接此回填。,第四節(jié) 控制語句的翻譯,三、IF語句的翻譯 3、改寫產(chǎn)生式 S if E then S(1)else S(2)改寫為： --- C if E then --- T C S(1)else --- S T S(2) S if E then S(1)改寫為： -- C if E then --- S CS(1),,,,,,,,第四節(jié) 控制語句的翻譯,三、IF語句的翻譯 4、語義子程序 C if E then BA

32、CKPATCH(EEC,NXQ); CCHAIN=EFC; T CS(1) else q=NXQ;GEN(j,_,_,0); BACKPATCH(CCHAIN,NXQ); TCHAIN=MERG(S(1)CHAIN,q) S TS(2) SCHAIN=MERG(TCHAIN, S(2)CHAIN) S CS(1) SCHAIN=MERG(TCHAIN, S(2)CHAIN),,,,,第四節(jié) 控制語句的翻譯,例如：翻譯無條件嵌套語句： if a then if b then A:=2 else A:=3 ELSE if c then A:=4 Else A

33、:=5 翻譯成四元式為：,(1)(jnz,a,_,0) (2)(j,_,_,0) (3)(jnz,b,_,0) (4)(j,_,_,0) (5)(:=,2,_,A) (6)(j,_,_,0) (7)(:=,3,_,A) (8)(j,_,_,0),第四節(jié) 控制語句的翻譯,(1)(jnz,a,_,0) (2)(j,_,_,0) (3)(jnz,b,_,0) (4)(j,_,_,0) (5)(:=,2,_,A) (6)(j,_,_,0) (7)(:=,3,_,A) (8)(j,_,_,0),(8)(j,_,_,6) (9)(jnz,c,_,11) (10)(j,_,_,13) (11)(:=,4,_

34、,A) (12)(j,_,_,8) (13)(:=,5,_.A),a,S4(A:=5),b,S1(A:=2),S2(A:=3),c,S3(A:=4),1,2,3,4,9,10,11,13,7,5,,,,,,,,,,,,,,,,,,,,,,,12,8,6,TRUE,FALSE,if a then if b then A:=2 else A:=3 ELSE if c then A:=4 Else A:=5,第四節(jié) 控制語句的翻譯,四、WHILE語句的翻譯 1、WHILE語句的文法 S while E do S(1) 2、WHILE 語句的翻譯思想 (1)翻譯E代碼段，并留兩個待填的ETC

35、,ETC鏈 (2)掃描過do之后，就可以回填ETC (3)翻譯S(1)成代碼段,S(1)翻譯之后，應(yīng)無條件轉(zhuǎn)到E代碼段的第一條四元式。 ：1)因此,開始翻譯while語句時，應(yīng)留下第一條四元式序號，以備S(1)翻譯之后用。 2)E為假時需回填，此時ETC作為SCHAIN一部分，以便回填。,,第四節(jié) 控制語句的翻譯,四、WHILE語句的翻譯 3、改寫產(chǎn)生式 S while E do S(1)改寫為： --- W while --- Wd WE do --- S Wd S(1),,,,,第四節(jié) 控制語句的翻譯,4、語義子程序 W while WQUAD=NXQ Wd WE do BACKP

36、ATCH(EFC,NXQ); --- WdCHAIN=EFC; --- WdQUAD=WQUAD; S WdS(1) BACKPATCH(S(1)CHAIN,WdQUAD); --- GEN(j,_,_,WdQUAD); --- SCHAIN= WdCHAIN,,,,第四節(jié) 控制語句的翻譯,例如：翻譯 While(A

37、105)(:=,T1,_,X) (106)(j,_,_,(100)),第四節(jié) 控制語句的翻譯,七、復(fù)合語句的翻譯 1、文法 S begin L end L S L LSS LS L,,,,,第四節(jié) 控制語句的翻譯,七、復(fù)合語句的翻譯 2、語義子程序 (1)L S LCHAIN=SCHAIN; (2)LS L BACKPATCH(LCHAIN,NXQ); (3)L LSS LCHAIN=SCHAIN; (4)S begin L end --- BACKPATCH(LCHAIN,NXQ); --- SCHAIN=0;,,,,,第五節(jié) 數(shù)組元素及其在賦值語句中的翻譯,一

38、、數(shù)組及其下標變量地址的計算 1、數(shù)組分類： ---一維數(shù)組，二維數(shù)組，多維數(shù)組 ---確定數(shù)組，可變數(shù)組： 根據(jù)數(shù)組所需存儲空間是否在編譯時就已知道 2、多維數(shù)組的存放 ---按行存放 ---按列存放（FORTRAN) ---只要知道數(shù)組的首地址，及每個數(shù)組元素占多少內(nèi)存單元，就可計算出任一數(shù)組元素的地址。,例如：2維數(shù)組定義為： ---ArrayL1:u1,L2:u2 ---令di=ui-Li+1,i=1,2, 稱為每一維尺寸 ---D=a+((i1-L1)d2+(i2-L2))*/*m為每個元素所占尺寸*/ 改寫為D=CONSPART+VARPART ---CONSPART=a-C

39、C=(L1d2+L2)*m ---VARPART=(i1d2+i2)*m,:CONSPART稱作不變部分，它和數(shù)組下標無關(guān)，只和各維尺寸和下界有關(guān)；只需計算一次，其中C在編譯時就可算出。 VARPART稱作可變部分，它和數(shù)組下標有關(guān)，必須根據(jù)下標值，轉(zhuǎn)換成相應(yīng)代碼，待運行時計算出。,第五節(jié) 數(shù)組元素及其在賦值語句中的翻譯,一、數(shù)組及其下標變量地址的計算 3、編譯程序?qū)?shù)組說明的處理 當遇到數(shù)組說明時，必須把數(shù)組的有關(guān)信息記錄在一張“內(nèi)情向量”表中，以便以后計算數(shù)組下標變量地址時引用這些信息。 內(nèi)情向量表的結(jié)構(gòu)： 一維數(shù)，各維上下界，首地址，類型,第五節(jié) 數(shù)組元素及其在賦值語句中的翻譯,一、數(shù)組

40、及其下標變量地址的計算 3、編譯程序?qū)?shù)組說明的處理 1)對于確定的數(shù)組來說：內(nèi)情向量可登記在編譯時的符號表中； 2)對于可變數(shù)組來說： (1)內(nèi)情向量在編譯時無法知道，只有在運行時才能算出來； 因此，編譯程序必須為可變數(shù)組設(shè)置一個存儲空間，以便運行對建立相應(yīng)的內(nèi)情向量表。 (2)這樣,就必須在編譯時為運行程序準備好調(diào)用的運行子程序，我們不作討論。,第五節(jié) 數(shù)組元素及其在賦值語句中的翻譯,二、確定數(shù)組的數(shù)組元素引用的中間代碼形式 1、訪問數(shù)組元素可設(shè)想為： 把它的VARPART計算在某一變址單元T中，用CONSPART作為“基礎(chǔ)”。然后以變址方式訪問存儲單元---CONPARTT,靜態(tài)數(shù)組CO

41、NSPART=a-C,C可以從內(nèi)情向量表中查到，而a在運行時一定可確定下來，所以可以生成a-C代碼，待運行時再確定。假定T1是用于存放CONSPART的臨時單元，T1=a-C那么用T1T表示數(shù)組元素的地址,第五節(jié) 數(shù)組元素及其在賦值語句中的翻譯,三、按行存放的賦值語句中的數(shù)組元素的翻譯 2、訪問數(shù)組元素 引用數(shù)組元素： ----（= ，T1,T,_,X) :這是一個變址取數(shù)組四元式。 含義相當于 X=T1T. 對數(shù)組元素賦值： ----（ =,X,_,T1T) :這是一個變址存數(shù)四元式。含義相當于：T1J=X,第五節(jié) 數(shù)組元素及其在賦值語句中的翻譯,三、按行存放的賦值語句中的數(shù)組元素的翻譯 1

42、、文法 ----A V:=E ----V iElist|i ----Elist Elist,E|E ----E E op E|(E)|V/*op表示各種算術(shù)運算*/ ：V可以是簡單變量也可以是下標變量. 這個遞歸定義可形成數(shù)組嵌套數(shù)組結(jié)構(gòu).,,,,,第五節(jié) 數(shù)組元素及其在賦值語句中的翻譯,三、按行存放的賦值語句中的數(shù)組元素的翻譯 2、文法改寫 ---A V:=E ---V Elist|I ---Elist Elist(1),E|iE ---E EopE|(E)|V 注：把數(shù)組名i和最左下標表達式寫在一起就表示為數(shù)組i開始計算第一個下標，同時使我們在整個下標串Elist的翻譯過程中隨

43、時都能知道數(shù)組i的符號表入口地址及表中相應(yīng)信息。,,,,,第五節(jié) 數(shù)組元素及其在賦值語句中的翻譯,三、按行存放的賦值語句中的數(shù)組元素的翻譯 3、相關(guān)語義變量和函數(shù)過程 語義變量： ----ARRAY:數(shù)組名在符號表的入口地址 ----DIM：數(shù)組下標維數(shù)計數(shù)器 ----PLACE:語義變量，在符號表入口地址或臨時變量的序號 ----OFFSET: 簡單變量：OFFSET=null 下標變量：OFFSET保存已計算出的VARPART,第五節(jié) 數(shù)組元素及其在賦值語句中的翻譯,三、按行存放的賦值語句中的數(shù)組元素的翻譯 3、相關(guān)語義變量和函數(shù)過程 函數(shù)過程： ---LIMITARRAY,K:通過符號表

44、查內(nèi)情向量表，返回第k維的尺寸dk ---HEADARRAY:取得數(shù)組首地址a,或查內(nèi)情向量表，或等運行時分配得到 ---CONSARRAY:查內(nèi)情向量表,得C值 ---TYPEARRAY:查內(nèi)情向量表TYPE項，返回一個數(shù)組元素，占有的字單元數(shù)m值。,第五節(jié) 數(shù)組元素及其在賦值語句中的翻譯,三、按行存放的賦值語句中的數(shù)組元素的翻譯 4、語義子程序 ---(1)A V:=E ---IF(VOFFSET=null() GEN(=,EPLACe,_,VPLACE); ---ELSE --- GEN( =,EPLACE,_,V PLACEVOFFSET),第五節(jié) 數(shù)組元素及其在賦值語句中的翻

45、譯,三、按行存放的賦值語句中的數(shù)組元素的翻譯 4、語義子程序 (2)E E(1)op E(2) T=NEWTEMP; GEN(op,E(1)PLACE,E(2)PLACE,T); EPLACE=T (3)E (E(1)) EPLACE=E(1)PLACE (4)E V IF(VOFFSET=null) --- EPLACE=VPLACE; --- ELSE --- T=NEWTEMP; --- GEN(= ,EPLACEVOFFSET,_,T); --- EPLACE=T;,,,,第五節(jié) 數(shù)組元素及其在賦值語句中的翻譯,(5

46、)V Elist IF(TYPEARRAY1) --- T=NEWTEMP; --- GEN(*,EListPLACE,TYPEARRAY,T); --- ElistPLACE=T; --- VOFFSET=ElistPLACE; --- T=NEWTEMP; --- GEN(_,HEADARRAY,CONSARRAY,T); --- VPLACE=T (6)V i VPLACE=ENTRYi; --- VOFFSET=null,,,第五節(jié) 數(shù)組元素及其在賦值語句中的翻譯,4、語義子程序 (7)Elist Elist(1),E T=NEW

47、TEMP; ---- K=Elist(1)DIMT1; ---- dk=LIMIT(Elist(1)ARRAY,k); ---- GEN(*,Elist(1)PLACE,dk,T); ---- T1=NEWTEMP; ---- GEN(+,T,E PLACE,T1); ---- ElistARRAY=Elist(1)ARRAY; ---- ElistPLACE=T1; ---- ElistDIM=K;,,第五節(jié) 數(shù)組元素及其在賦值語句中的翻譯,4、語義子程序 (8)Elist iE ----- ElistPLACE=EPLA

48、CE; ----- ElistDIM=1; ----- ElistARRAY=ENTRY(i),,第五節(jié) 數(shù)組元素及其在賦值語句中的翻譯,例如：數(shù)組說明為：ARRAY1:10,1:20; 且從內(nèi)情向量表查得數(shù)組首地址為a, C=21,d2=20,m=1為X:=AI,J生成四元式序列： 解：四元式序列為： ----(1)(*,I,20,T1) ----(2)(+,T1,J,T2) ----(3)(-,a,21,T3) ----(4)(= ,T3T2,_,T4) ----(5)(:=,T4,_,X),第六節(jié) 過程調(diào)用語句,一、過程調(diào)用 1、過程 ---定義和調(diào)用過程是程序語言的主要特征之一，過

49、程是模塊化程序設(shè)計的主要手段，同時也是節(jié)省程序代碼和擴充語言能力的主要途徑。 2、過程調(diào)用 ---實質(zhì)是把程序控制轉(zhuǎn)到子程序. 3、過程調(diào)用中遇到的問題： ---子程序完成后如何回到主調(diào)程序； ---子程序回到主調(diào)程序時，運行環(huán)境的恢復(fù)； ---如何進行參數(shù)傳遞；,第六節(jié) 過程調(diào)用語句,二、參數(shù)傳遞 1、參數(shù) ---實在參數(shù) ---形式參數(shù) 2、傳遞方式 1)傳地址（call by reference);把實在參數(shù)的地址傳遞給相應(yīng)的形式參數(shù)。 2)傳值(call by value):把實在參數(shù)的值計算出來傳遞給相應(yīng)的形式參數(shù)。 3)傳名（call by name):ALGOL 60所定義的一種

50、特殊的形實參結(jié)合方式。,第六節(jié) 過程調(diào)用語句,二、參數(shù)傳遞 3、傳地址 1)基本方式 A)若實參是一個變量（包括下標變量），則直接傳遞它的地址； B)若實參是一個常數(shù)或其他表達式，就把值計算出來并存放在某臨時單元，然后傳遞這個臨時單元的地址。,第六節(jié) 過程調(diào)用語句,二、參數(shù)傳遞 3、傳地址 2)傳址過程 A)當程序控制轉(zhuǎn)入被調(diào)用過程之后，被調(diào)用段首先把實地址從連接數(shù)據(jù)區(qū)中讀入形參單元中。 ---注：若已直接傳至形參單元，不做此步。 B)在過程體內(nèi)，對形參的任何引用或賦值都被看作對新參單元的間接訪問，這間接賦值將直接修改實參單元的內(nèi)容。,第六節(jié) 過程調(diào)用語句,二、參數(shù)傳遞 4 、傳值 調(diào)用時把實

51、在參數(shù)的值計算出來，把值直接傳遞給形式單元中，在過程體內(nèi)應(yīng)用這些單元不會修改實質(zhì)單元的值。 5、傳名 過程調(diào)用相當于把調(diào)用段的過程代替調(diào)用語句，并且過程體內(nèi)形參名皆用相應(yīng)的實參名代替。,第六節(jié) 過程調(diào)用語句,三、過程調(diào)用語句的翻譯（傳址） 1、文法 ---S call i(Arglist) ---Arglist Arglist,E ---Arglist E 2、相關(guān)四元式 1)(par,_,_,T) ---含義是：將參數(shù)T傳遞到一個公共的區(qū)域或直接傳遞到過程的形參單元 2)(jsr,_,n,S) ---含義是：轉(zhuǎn)移指令，轉(zhuǎn)移到S過程的四元式入口序號。,,,,第六節(jié) 過程調(diào)用語句,三、過程

52、調(diào)用語句的翻譯（傳址） (1)S call i(Arglist) ---- n=0; ---- for(隊列ArglistQUEUE中的每個P) ---- GEN(par,_,_,P); ---- n=n+1; ---- GEN(jsr,_,n,ENTRY(i)) (2)Arglist Arglist(1) E ---- 把EPLACE添加入Arglist(1) QUEUE 末端； ---- ArglistQUEUE=Arglist(1)QUEUE,,,第六節(jié) 過程調(diào)用語句,例如：過程調(diào)用：CALL S(A+B,Z) 譯為： ----- K(+,A,B,T) -----

53、K+1(par,_,_,T) ----- K+2(par,_,_,Z) ----- K+3(jsr,_,2,S),第九節(jié) 自上而下分析的制導(dǎo)的翻譯,一、自上而下分析的制導(dǎo)的翻譯 通過推導(dǎo)自左而右地產(chǎn)生句子的各終結(jié)符號，再按產(chǎn)生式推導(dǎo)的過程添加語義子程序，無需得到侯選式匹配完后，即不必改寫文法。 注：1)在按產(chǎn)生式推導(dǎo)的中間任何一步都可以添加語義子程序，所以不必改寫文法。 2)實際上，程序設(shè)計語言絕大部分均可使用自上而下分析并生成相應(yīng)中間代碼。 二、自上而下分析制導(dǎo)翻譯種類 1、遞歸下降分析制導(dǎo)翻譯 2、LL(1)分析制導(dǎo)翻譯,第十節(jié) 中間代碼的其它形式,一、后綴表示法（逆波蘭表示法） 1、

54、后綴表示法的文法 ---- ::=| | ---- ::= ---- ::=+|-|*|/ ----注：這種表示法不帶括號，根據(jù)運算量和運算符出現(xiàn)的先后位置，以及每個運算符的目數(shù)，就完全決定了一個表達式的計算程序。,第十節(jié) 中間代碼的其它形式,后綴表示法的特點： ---(1)運算量的排列順序與中綴表示法相同； ---(2)遠算量是按運算的順序排列的； ---(3)運算符緊跟在被云酸的對象之后出現(xiàn)。 ---注：它顯然不符合人的習灌，但隊計算機來說，很容易使用一個棧來計算它的值，或轉(zhuǎn)換成另一種代碼。,第十節(jié) 中間代碼的其它形式,二、語法制導(dǎo)產(chǎn)生后綴式 首先，除了堆棧外，為分析過程

55、設(shè)置一個一維數(shù)組POST來存放后綴式；初始時，其下標K為1。 然后，利用算符優(yōu)先分析法,第十節(jié) 中間代碼的其它形式,二、語法制導(dǎo)產(chǎn)生后綴式 1、利用算符優(yōu)先分析法進行語法分析 語義子程序 產(chǎn)生式 語義子程序 (1)E E(1)opE(2) POSTK=op;k=k+1; (2)E (E(1)) (3)E i POSTK=ENTRY(i);k=k+1; 例如：假定算符優(yōu)先分析表已選好，對表達式A*(B+C)# 翻譯成后綴式,,,,第十節(jié) 中間代碼的其它形式,二、語法制導(dǎo)產(chǎn)生后綴式 2、后綴表示法的計值和產(chǎn)生中間代碼 1)計值過程：至左至右掃描后綴式，沒碰到運算量就

56、將其入棧，每遇到K目運算符就將它作用于棧頂?shù)膋項，并將運算結(jié)果來代替這k項。 --例如：ab+c* 2)產(chǎn)生四元式過程：自左至右掃描后綴式，每碰到運算量就將其入棧，每遇到k目運算符就將它作用于棧頂?shù)腒項，并生成相應(yīng)的中間代碼，以結(jié)果的臨時變量序號代替該棧頂?shù)膋項。,第十節(jié) 中間代碼的其它形式,二、語法制導(dǎo)產(chǎn)生后綴式 3、后綴式的推廣 方法：遵守運算符緊跟在被作用的運算量之后。 例如:(1) 賦值語句A:=E,后綴式為：AE:= (2)轉(zhuǎn)向語句GOTO L,后綴式為：Ljmp ---其中L是指示器，用POST中的下標值表示。 (3)條件語句 if xy then m:=x else m:=y;其后綴值為：,,,,,,,Begin k:=100; L:if ki+j;goto L end else k:=i2-j2 i:=0; End.,注：翻譯成后綴式時也存在拉鏈回填的問題,小結(jié),1、算術(shù)表達式及賦值語句翻譯 2、控制語句中布爾表達式翻譯 ---留有真、假出口 ---回填過程與并鏈函數(shù) 3、標號和轉(zhuǎn)移語句翻譯 4、IF語句的翻譯 5、WHILE語句的翻譯 6、語法制導(dǎo)生成后綴式（逆波蘭表達式）,