【編譯原理課件】cha8-語法制導(dǎo)翻譯和中間代碼生成

2024/4/271第8章語法制導(dǎo)翻譯和中間代碼生成引言8.1屬性文法8.2語法制導(dǎo)翻譯概論8.3中間代碼形式(重點)8.4簡單賦值語句的翻譯(重點)8.5布爾表達式的翻譯(重點)8.6控制結(jié)構(gòu)的翻譯(重點難點)8.7說明語句的翻譯〔略〕8.8數(shù)組和結(jié)構(gòu)的翻譯〔略〕作業(yè)課程目錄2024/4/272語義分析的任務(wù)p169靜態(tài)語義檢查動態(tài)語義處理——翻譯總目標驗證語法結(jié)構(gòu)合法的程序是否真正有意義。例：類型檢查、控制流檢查、一致性檢查、相關(guān)名字檢查。對程序意義的解釋，執(zhí)行真正的翻譯。例：變量的存儲分配表達式的求值例：語句的翻譯〔中間代碼的生成〕生成等價的中間代碼。2024/4/273編譯中的語義分析描述方法——屬性文法利用屬性文法描述如何將各種語句和表達式翻譯成中間代碼為每個文法符號賦予相應(yīng)屬性，對應(yīng)每一個產(chǎn)生式編制一個語義子程序工作方式——語法制導(dǎo)翻譯當(dāng)一個產(chǎn)生式獲得匹配時，調(diào)用相應(yīng)的語義子程序?qū)崿F(xiàn)語義檢查與翻譯每識別出一個語法結(jié)構(gòu)時，完成相應(yīng)的語義檢查與中間代碼生成章節(jié)目錄2024/4/2748.1屬性文法p169

屬性文法舉例

屬性文法定義

屬性的分類綜合屬性繼承屬性章節(jié)目錄2024/4/275簡單計算器的設(shè)計例3*5+4n表達式的文法L→EnE→E1+TE→TT→T1*FT→FF→(E)F→i

EnE1+TTT1*FFi3i5Fi4要解決的問題表達式求值.val3.val3.val5.val15.val15.val4.val4.val19L顯示19.lexval3.lexval5.lexval4綜合屬性自下而上傳遞信息2024/4/276屬性文法舉例——簡單計算器

p171用語義規(guī)那么描述表達式求值。該屬性文法描述如下：產(chǎn)生式語義規(guī)那么(屬性計算規(guī)那么)L→Enprint(E.val)(虛屬性)E→E1+TE.val:=E1.val+T.valE→TE.val:=T.valT→T1*FT.val:=T1.val*F.valT→FT.val:=F.valF→(E)F.val:=E.valF→iF.val:=i.lexval非終結(jié)符設(shè)有綜合屬性，代表表達式的值終結(jié)符i設(shè)有綜合屬性，其值由詞法分析器提供2024/4/277說明語句的設(shè)計p171例realid1,id2,id3說明語句的文法D→TLT→intT→realL→L1,idL→idDTLrealL1,id3L2,id2id1要解決的問題記錄標識符的類型類型信息傳遞realrealreal.typereal.inreal.inreal.inreal繼承屬性自上而下傳遞信息類型描述變量表2024/4/278D→TLL.in:=T.typeT→intT.type:=integerT→realT.type:=realL→L1,idL1.in:=L.inaddtype(id.entry,L.in)L→idaddtype(id.entry,L.in)entry單詞

id的屬性，id在符號表的入口addtype在符號表中為變量添加類型信息用語義規(guī)那么描述變量說明。該屬性文法描述如下：產(chǎn)生式語義規(guī)那么(屬性計算規(guī)那么)說明語句的屬性文法p171綜合屬性繼承屬性節(jié)目錄2024/4/279屬性文法定義p169屬性文法是Knuth在1968年提出的。屬性文法的特點：是一種接近形式化的語義描述方法。每個文法符號有相應(yīng)的屬性V——屬性集合代表與文法符號相關(guān)的信息；例如類型、值、代碼序列等。每個產(chǎn)生式配有相應(yīng)的語義規(guī)那么F——規(guī)那么集合作用：計算屬性的規(guī)那么,可以產(chǎn)生代碼、在符號表中存放信息、給出錯誤信息或執(zhí)行任何其它動作，實現(xiàn)翻譯；形式：b:=f(c1,c2,…,ck)。屬性文法：三元組A=(G,V,F)在上下文無關(guān)文法的根底上，把每個文法符號和一組屬性相關(guān)聯(lián)，并給產(chǎn)生式附加以語義規(guī)那么。節(jié)目錄2024/4/2710屬性分類p170產(chǎn)生式A→α語義規(guī)那么b:=f(c1,c2,…,ck)綜合屬性用于“自下而上”傳遞信息b是A的綜合屬性,c1,c2,…,ck是右邊文法符號的屬性從其子結(jié)點的屬性值計算出來的終結(jié)符只有綜合屬性，由詞法分析器提供例如E.valT.valF.val繼承屬性用于“自上而下”傳遞信息b是右邊某個文法符號的繼承屬性,c1,c2,…,ck是A或右邊任何文法符號的屬性從其兄弟結(jié)點和父結(jié)點的屬性值計算出來開始符號的繼承屬性作為屬性計算前初值例如L.in非終結(jié)符既可有綜合屬性也可有繼承屬性,一般對于出現(xiàn)在產(chǎn)生式右邊的繼承屬性和出現(xiàn)在產(chǎn)生式左邊的綜合屬性都必須提供一個計算規(guī)那么節(jié)目錄2024/4/27118.2語法制導(dǎo)翻譯概論p171語法制導(dǎo)翻譯計算語義規(guī)那么依賴圖S-屬性文法和自下而上翻譯L-屬性文法在自上而下分析中的實現(xiàn)L-屬性文法在自下而上分析中的實現(xiàn)章節(jié)目錄2024/4/2712基于屬性文法的處理方法p171對單詞符號串進行語法分析，構(gòu)造語法分析樹，然后根據(jù)需要遍歷語法樹，并在語法樹的各結(jié)點處按語義規(guī)那么進行計算。輸入串語法樹依賴圖語義規(guī)那么計算次序2024/4/2713語法制導(dǎo)翻譯法由源程序的語法結(jié)構(gòu)所驅(qū)動的處理方法為文法中每個產(chǎn)生式配上一組語義規(guī)那么，并且在語法分析的同時執(zhí)行這些語義規(guī)那么，完成相應(yīng)的語義處理問題：何時執(zhí)行語義規(guī)那么？每當(dāng)用一個產(chǎn)生式推導(dǎo)或歸約時，就執(zhí)行對應(yīng)的語義規(guī)那么節(jié)目錄2024/4/2714屬性的計算——依賴圖p172一張有向圖描述語法樹各結(jié)點屬性之間的相互依賴關(guān)系如果屬性b的計算依賴于屬性c，那么附屬性c到屬性b有一條有向邊c→b根據(jù)依賴關(guān)系決定計算順序依賴圖的任意一個拓撲排序TopologicalSort如果結(jié)點c→b，在序列中c必須在b之前2024/4/2715①例3*5+4n的語法樹與屬性計算L.val=3EnE1+TTT1*FFiiFi.val=3.val=5.val=15.val=15.val=4.val=4.val=19顯示19.lexval=3.lexval=5.lexval=4依賴關(guān)系拓撲排序自下而上依賴圖②③④⑤⑥⑦⑧⑨2024/4/2716例realid1,id2,id3的語法樹和屬性計算p172DTLrealL1,id3L2,id2id1addtype.type=real.in=real.in=real.in=real依賴關(guān)系拓撲排序自下而上無法直接實現(xiàn).entry.entry.entry自上而下存在左遞歸,可改造realaddtyperealaddtypereal④⑤⑥⑦⑧⑨①②③⑩節(jié)目錄2024/4/2717S-屬性文法p173S-attributedDefinitionS-attributedGrammar僅包含綜合屬性的語法制導(dǎo)定義對于所有Ａ→Ｘ1Ｘ2…Ｘn，Ａ的屬性計算僅用Ｘ1,Ｘ2,…,Ｘn的屬性自下而上計算屬性如算術(shù)表達式求值的屬性文法節(jié)目錄2024/4/2718L-屬性文法p175L-attributedDefinitionL-attributedGrammar包含綜合屬性和繼承屬性的語法制導(dǎo)定義對于所有Ａ→Ｘ1Ｘ2…Ｘi-1Ｘi

…ＸnＸi屬性計算僅使用Ｘ1,Ｘ2…Ｘi-1的屬性和A的繼承屬性自上而下計算屬性如說明語句的屬性文法節(jié)目錄2024/4/2719翻譯模式p176語法制導(dǎo)翻譯的兩種描述形式屬性文法(語法制導(dǎo)定義)(GrammarDirectedDefinition)語義的抽象說明，隱去實現(xiàn)細節(jié)翻譯模式(TranslationScheme)規(guī)定實現(xiàn)方法，說明計算次序翻譯模式的特征規(guī)定在語法分析中使用語義規(guī)那么進行計算的次序保證當(dāng)動作使用某屬性時，該屬性必須是可用的翻譯模式的構(gòu)造方法將{語義動作}插入到產(chǎn)生式中的某個位置2024/4/2720表達式文法的翻譯模式E→E1+T{E.val:=E1.val+T.val}E→T{E.val:=T.val}T→T1*F{T.val:=T1.val*F.val}T→F{T.val:=F.val}F→(E){F.val:=E.val}F→i{F.val:=i.lexval}2024/4/2721說明語句的翻譯模式

將語義動作中的計算向前移，使繼承屬性的計算出現(xiàn)在其文法符號之前D→T{L.in:=T.type}LT→int{T.type:=integer}T→real{T.type:=real}L→{L1.in:=L.in}L1,id{addtype(id.entry,L.in)}L→id{addtype(id.entry,L.in)}問題：如何自下而上計算繼承屬性？2024/4/2722解決方法從翻譯模式中去掉嵌入在產(chǎn)生式中間的動作自下而上計算繼承屬性p176D→T{L.in:=T.type}LT→int{T.type:=integer}T→real{T.type:=real}L→{L1.in:=L.in}L1,id

{addtype(id.entry,L.in)}L→id{addtype(id.entry,L.in)}引入6.

M→ε{L.in:=T.type}

引入7.

N→ε{L1.in:=L.in}

MN2024/4/2723realid1,id2的翻譯過程D→TMLT→int{T.type:=integer}T→real{T.type:=real}L→NL1,id{addtype(id.entry,L.in)}L→id{addtype(id.entry,L.in)}M→ε{L.in:=T.type}N→ε{L1.in:=L.in}DTMLrealεNL1

,id2εid1T.type=realL.in=realL1.in=realrealreal節(jié)目錄2024/4/27248.3中間代碼形式

(Intermediatelanguage/code/representation)許多編譯程序采用的獨立于機器的、復(fù)雜性界于源語言和機器語言之間語言源程序的一種內(nèi)部表示——中間代碼序列〔中間語言的語句〕用中間語言過渡的好處便于進行與機器無關(guān)的優(yōu)化工作使編譯程序改變目標機容易，便于移植使編譯程序的結(jié)構(gòu)在邏輯上更為簡單明確2024/4/2725中間語言p177章節(jié)目錄常見形式后綴式〔逆波蘭式〕圖表示法抽象語法樹、DAG圖三地址代碼〔抽象描述〕四元式、三元式、間接三元式〔具體實現(xiàn)〕特點形式簡單、語義明確、便于翻譯獨立于目標語言2024/4/2726舉例中綴式后綴式

(1)(a+b)*c(2)-a*(b+c)(3)(a+b)*(c+d)(4)not(AorB)后綴式〔逆波蘭式〕p177是表達式的一種表示形式把運算符寫在運算量(操作數(shù))后面定義設(shè)E是表達式，那么假設(shè)E是變量或常量，E的后綴式為E自身E1OPE2==>E1’E2’OP，其中E1’和E2’分別為E1和E2的后綴式(E)==>E’ab+c*a@bc+*ab+cd+*ABornot2024/4/2727中綴式改寫成后綴式課堂練習(xí)中綴式

1.-a+b*c2.a+b*(c-d)+e/(c-d)↑n乘冪運算

3.x:=a-b/(c+d)對應(yīng)后綴式后綴式特點

1.運算量的順序與中綴式相同

2.運算符的先后順序即為運算的先后順序

3.有利于表達式運算的實現(xiàn)BEGIN1.a@bc*+2.abcd-*+ecd-n↑/+3.xabcd+/-:=2024/4/2728中綴式改寫成后綴式的屬性文法 產(chǎn)生式 語義規(guī)那么E→E1opE2 E.code:=E1.code||E2.code||opE→(E1) E.code:=E1.codeE→id E.code:=id功能：完成中綴表達式到后綴表達式的翻譯例如：id1+id2+id3后綴式：E.codeEE+EE+Eid2id1id3數(shù)組postid1id2+id3E1E2+節(jié)目錄2024/4/2729

三地址代碼一般形式x:=yopz(1)三個地址xyz為變量、常數(shù)或編譯產(chǎn)生的臨時變量(2)每條語句的右邊只能有一個運算符op表達式x+y*z的三地址代碼

(1)T1:=y*z(2)T2:=x+T1賦值語句a:=b*-c+b*-c的三地址代碼

(1)T1:=-c(2)T2:=b*T1(3)T3:=-c(4)T4:=b*T3(5)T5:=T2+T4(6)a:=T5結(jié)果操作數(shù)操作數(shù)運算符2024/4/2730三地址代碼種類x:=yopzx:=opyx:=ygotoLifxrelopygotoLparxcallpreturnxx:=y[i]x[i]:=yx:=&yx:=*y*x:=y雙目運算單目運算賦值無條件轉(zhuǎn)移條件轉(zhuǎn)移實在參數(shù)過程調(diào)用過程返回數(shù)組運算(取數(shù))(存數(shù))地址和指針運算2024/4/2731三元式和樹形表示p178表示方法：三個域

(i)(op，arg1，arg2)例：a+b*c三元式(i)(op,arg1,arg2)

(1)(*,b,c)

(2)(+,a,(1))arg1，arg2：或者是指向符號表的指針，或者是指向三元式表的指針。三元式編號存放結(jié)果操作數(shù)操作數(shù)運算符樹形表示+a*bc2024/4/2732三元式課堂練習(xí)賦值語句A:=-B*(C+D)對應(yīng)的三元式序列

(1)(@,B,_)(2)(+,C,D)(3)(*,(1),(2))

(4)(:=,A，(3))可以看出：三元式是按相應(yīng)表達式的實際運算順序出現(xiàn)的三元式間的相互引用非常頻繁，而這些引用又是通過編號來實現(xiàn)的在優(yōu)化時，要刪除或挪動三元式會造成大量修改的局面BEGIN操作數(shù)為空用下劃線表示節(jié)目錄2024/4/2733間接三元式建立兩個與三元式相關(guān)的表格三元式表執(zhí)行表(間接代碼表)

三元式表(1)(+,A,B)(2)(*,(1),C)(3)(:=,X,(2))(4)(↑,D,(1))(5)(:=,Y,(4))

間接代碼

(1)(2)(3)

(1)(4)(5)

——用來存放各三元式本身——按各三元式執(zhí)行順序列出相應(yīng)三元式在三元式表中位置例：X:=(A+B)*C;Y:=D↑(A+B);2024/4/2734間接三元式優(yōu)點相同的三元式無需重復(fù)填進三元式表中，節(jié)省三元式空間需要調(diào)整運算順序時，只需重新安排間接代碼表，無需改變?nèi)奖?024/4/2735間接三元式課堂練習(xí)賦值語句X:=(A+B)*CB:=A+BY:=C*(A+B)對應(yīng)的間接三元式為：間接碼表〔1〕〔2〕〔3〕〔1〕〔4〕〔1〕〔2〕〔5〕

三元式表(1)(+,A,B)(2)(*,1,C)(3)(:=,X,2)(4)(:=,B,1)(5)(:=,Y,2)三元式代碼(1)(+,A,B)(2)(*,1,C)(3)(:=,X,2)(4)(+,A,B)(5)(:=,B,4)(6)(+,A,B)(7)(*,C,6)(8)(:=,Y,7)BEGIN節(jié)目錄2024/4/2736四元式p172表示方法：四個域

(op，arg1，arg2，result)例：a+b*-c (op,arg1,arg2,result)(1)(@,c,_,T1)arg1，arg2和result是指向有關(guān)名字符號表的指針，可以是常量，變量或臨時變量等結(jié)果操作數(shù)操作數(shù)操作數(shù)運算符操作數(shù)為空用下劃線表示(2)(*,b,T1,T2)(3)(+,a ,T2,T3)2024/4/2737四元式課堂練習(xí)賦值語句A:=-B*(C+D)對應(yīng)的四元式序列(1)(@,B,_,T1)BEGIN(2)(+,C,D,T2)(3)(*,T1,T2,T3)(4)(:=,T3,_,A)節(jié)目錄2024/4/27388.4簡單賦值語句的翻譯p179語法id:=E語義計算表達式E的值之后把值賦給變量id文法G[S]:S→id:=EE→E1+E2E→E1*E2E→-E1E→(E1)E→id章節(jié)目錄2024/4/2739語義過程及屬性設(shè)置p178語義過程lookup()檢查在符號表中是否存在

的表項。emit(x‘:=’y‘+’z)將生成的三地址代碼x:=y+z發(fā)送到輸出文件。newtemp每調(diào)用一次，生成一個臨時變量。屬性設(shè)置存儲位置place。例如E.place,T.place等lookup()=id.entry在表中nil否那么2024/4/2740產(chǎn)生賦值語句三地址代碼的翻譯模式p180S→id:=E{p:=lookup();

(sub1)ifp<>nilthenemit(p‘:=’E.place)/*id在表中*/elseerror/*id不在表中*/}E→E1+E2{E.place=newtemp;(sub2)emit(E.place':='E1.place'+'E2.place')}E→E1*E2{E.place=newtemp;

(sub3)emit(E.place':='E1.place'*'E2.place')}E→-E1{E.place:=newtemp;(sub4)emit(E.place′:=′′uminus′E1.place}E→(E1){E.place:=E1.place}(sub5)E→id{p:=lookup();(sub6)ifp<>nilthenE.place:=p/*id在表中*/ elseerror/*id不在表中*/}2024/4/2741a:=-c+b*d自下而上語法制導(dǎo)翻譯過程舉例步驟符號棧輸入串動作語義值三地址代碼

0#a:=-c+b*d#預(yù)備

i

:=EaSE+E-EicE*Eibid1#i:=-c+b*d#移進

a2#i:=-c+b*d#移進

a_3#i:=-c+b*d#移進

a__4#i:=-i+b*d#移進

a__c5#i:=-E+b*d#歸sub6a__c

6#i:=E+b*d#歸sub5a_T1

T1:=-c

7#i:=E+b*d#移進

a_T1_8#i:=E+i*d#移進

a_T1_b9#i:=E+E*d#歸sub6a_T1_b10#i:=E+E*d#移進

a_T1_b_11#i:=E+E*i#移進

a_T1_b_d12#i:=E+E*E#歸sub6a_T1_b_d

13#i:=E+E#歸sub3a_T1_T2

T2:=b*d

14#i:=E#歸sub2

a_T3

T3:=T1+T215#S#歸sub1

a:=T316分析成功結(jié)束

另見：教材p174圖8.7

2024/4/2742x:=b+c*d自下而上的語法制導(dǎo)翻譯課堂練習(xí)步驟符號棧輸入串動作語義值三地址代碼

0#x:=b+c*d#預(yù)備

1#i:=b+c*d#移進x2#i:=b+c*d#…x_3#i:=i+c*d#移進x_b4#i:=E+c*d#歸sub6x_b5#i:=E+c*d#移進x_b_6#i:=E+i*d#…x_b_c7#i:=E+E*d#歸sub6x_b_c8#i:=E+E*d#移進x_b_c_9#i:=E+E*i#…x_b_c_d10#i:=E+E*E#歸sub6x_b_c_d11#i:=E+E#歸sub3x_b_T1

T1:=c*d12#i:=E#歸sub2

x_T2

T2:=b+T113#S#歸sub1

x:=T214分析成功結(jié)束 Six:=EE+EibE*EicidBEGIN節(jié)目錄2024/4/27438.5布爾表達式的翻譯p181章節(jié)目錄布爾表達式作用布爾表達式文法布爾表達式翻譯方法數(shù)值表示法作為控制條件的布爾表達式翻譯2024/4/2744

布爾表達式的作用p181布爾表達式的作用計算邏輯值控制流語句如if-then，if-then-else和while-do等之中的條件表達式例如1or(not0and0)or0a<borc<dande<fifa<borc<dande<fthenx:=1elsex:=-1whilea<bdoa:=a-b節(jié)目錄2024/4/2745

布爾表達式的文法p182布爾表達式——用布爾運算符號(and,or,not)作用到布爾變量或關(guān)系表達式上而組成例如布爾表達式：aorbandc<d考慮如下生成布爾表達式的文法E→EorE|EandE|notE|(E)|id

relop

id|id

其中relop表示六個關(guān)系運算符之一例如E==>EorEabc<d對應(yīng)語法樹==>EorEandE==>EorEandidrelopid==>Eoridandidrelopid

==>idoridandidrelopid

節(jié)目錄2024/4/2746數(shù)值表示法p182假設(shè)用1表示真，0表示假，那么布爾表達式可以象算術(shù)表達式一樣來計算例如關(guān)系表達式a<b可等價地寫成:ifa<bthen1else0翻譯成三地址代碼：

100ifa<bgoto103101T1:=0102goto104103T1:=1104例如邏輯表達式

aorbandnotc

翻譯成三地址代碼：(1)T1:=notc(2)T2:=bandT1

(3)T3:=aorT2100+3102+2a<b為假a<b為真后續(xù)代碼nextstat2024/4/2747布爾式數(shù)值計算翻譯模式中

有關(guān)屬性和函數(shù)p182屬性E.place

綜合屬性，表示存放布爾表達式值的名字relop.op

綜合屬性，表示六個關(guān)系運算符之一三地址代碼的編號nextstat

給出輸出三地址代碼序列中下一條代碼的編號(地址索引)函數(shù)emit將產(chǎn)生的三地址代碼送到輸出文件中,每產(chǎn)生一條三地址代碼后，emit便把nextstat增12024/4/2748計算布爾表達式值三地址代碼的翻譯模式p182E→E1orE2{E.place:=newtemp;sub1emit(E.place‘:=’E1.place‘or’E2.place)}E→E1andE2{E.place:=newtemp;sub2emit(E.place‘:=’E1.place‘a(chǎn)nd’E2.place)}E→notE1{E.place=newtemp;sub3emit(E.place‘:=’‘not’E1.place)}E→(E1){E.place:=E1.place)}sub4E→id1{E.place:=newtemp;relopid2emit(‘if’id1.placerelop.opid2.placesub5‘goto’nextstat+3);emit(E.place‘:=’‘0’);emit(‘goto’nextstat+2);emit(E.place‘:=’‘1’)}E→id{E.place:=id.place}(與教材不同)sub62024/4/2749把a<borc<dande<f

翻譯

成三地址代碼舉例Eidarelop<idbEidcrelop<iddEiderelop<idfEandEor(1)sub5T1100ifa<bgoto103101T1:=0102goto104103T1:=1(2)sub5T2104ifc<dgoto107105T2:=0106goto108107T2:=1(3)sub5T3108ife<fgoto111109T3:=0110goto112111T3:=1(4)sub2112T4:=T2andT3(5)sub1113T5:=T1orT42024/4/2750把a>bandc>d翻譯成三地址代碼課堂練習(xí)Eidarelop>idbEidcrelop>iddEand(1)sub5T1100ifa>bgoto103101T1:=0102goto104103T1:=1(2)sub5T2104ifc>dgoto107105T2:=0106goto108107T2:=1(3)sub2108T3:=T1andT2BEGIN節(jié)目錄2024/4/2751作為條件控制的布爾式的翻譯p183語法S→ifEthenS1elseS2語義如果E的值為true，那么執(zhí)行S1；否那么,執(zhí)行S2代碼模式E.code：E的目標代碼判別E值的代碼轉(zhuǎn)向E.true的代碼轉(zhuǎn)向E.false的代碼E.true:S1的目標代碼轉(zhuǎn)向S.next的代碼E.false:S2的代碼S.next:后繼語句的代碼if-then-else的代碼結(jié)構(gòu)E.codeS1.codeE.true:S2.codeE.false:gotoS.next...S.next:toE.truetoE.false2024/4/2752選擇語句中布爾式的翻譯思想p183設(shè)E形如a<b屬性E.code為生成的三地址代碼：

ifa<bgotoE.truegotoE.falseE.true為E為“真”時控制流轉(zhuǎn)向的標號E.false為E為“假”時控制流轉(zhuǎn)向標號函數(shù)newlabel每次調(diào)用返回一個新的符號標號該符號標號用來標識一條三地址代碼2024/4/2753使用拉鏈-回填技術(shù)實現(xiàn)布爾式翻譯p184采用四元式實現(xiàn)三地址代碼，約定轉(zhuǎn)移四元式的形式為：(jnz,a,_,p)表示ifagotop(jrop,x,y,p)表示ifxropygotop(j,_,_,p)表示gotop面臨主要問題通過一編掃描來產(chǎn)生代碼時，當(dāng)生成某些轉(zhuǎn)移語句時我們可能還不知道該語句要轉(zhuǎn)移到的標號究竟是什么？解決方法——拉鏈-回填技術(shù)2024/4/2754拉鏈-回填技術(shù)p184拉鏈——在生成暫時不知道轉(zhuǎn)移目標的轉(zhuǎn)移四元式時，先建立鏈表，把轉(zhuǎn)移目標相同的轉(zhuǎn)移四元式鏈接在一起

E.truelist真鏈回填E的真出口E.true

E.falselist假鏈回填E的假出口E.false回填——一旦某條鏈的轉(zhuǎn)移目標確定之后，再把轉(zhuǎn)移目標填入到有關(guān)的四元式中例如

E的四元式中需回填真出口k的有p、q和r三個四元式E.truelist…(k)(*,*,*,*)E.trueE.true(p)(*,*,*,0)…(q)(*,*,*,0)pE.truelist…(r)(*,*,*,0)qE.truelistkkk2024/4/2755使用回填翻譯布爾表達式的文法p185布爾表達式文法：〔1〕E→E1orME2〔2〕|E1andME2〔3〕|notE1〔4〕|(E1)〔5〕|id1relopid2〔6〕|id(與教材不同)〔7〕M→ε插入非終結(jié)符號M是為了引入一個語義動作，以便在適當(dāng)?shù)臅r候獲得即將產(chǎn)生的下一個四元式的編號，或說四元式的索引〔E2.codebegin〕2024/4/2756翻譯模式用到如下變量和函數(shù)p184變量nextquad〔教材nextstat〕指向下一條要產(chǎn)生四元式的編號，每執(zhí)行一次emit，nextquad增1。函數(shù)makelist(i)創(chuàng)立一個僅包含編號為i的四元式的新鏈表，函數(shù)返回指向這個鏈的指針。函數(shù)merge(p1，p2)把以p1和p2為鏈首的兩個鏈合并為一，合并后的鏈首p2作為函數(shù)值回送。過程backpatch(p，i)完成“回填”，把p所指向鏈的每個四元式第四個域都填為i。2024/4/2757作為控制條件的布爾表達式翻譯模式p185sub1EE1orME2{backpatch(E1.falselist,M.quad);E.truelist:=merge(E1.truelist,E2.truelist);E.falselist:=E2.falselist}sub2EE1andME2{backpatch(E1.truelist,M.quad);E.truelist:=E2.truelist;E.falselist:=merge(E1.falselist,E2.falselist)}sub3EnotE1{E.truelist:=E1.falselist;E.falselist:=E1.truelist}sub4E(E){E.truelist:=E1.truelist;E.falselist:=E1.falselist}2024/4/2758作為控制條件的布爾表達式翻譯模式p185sub5Eid1relopid2{E.truelist:=makelist(nextquad);

E.falselist:=makelist(nextquad+1);

emit(‘j’relop.op‘,’id1.place‘,’id2.place,’0’);

emit(‘j,_,_,0’);}sub6Eid

{E.truelist:=makelist(nextquad);

E.falselist:=makelist(nextquad+1);

emit(‘jnz’’,’id.place‘,’‘_’‘,’’0’);

emit(‘j,_,_,0’);}sub7M{M.quad:=nextquad}2024/4/2759布爾表達式

a＜borc＜dande＜f翻譯過程p185E.t={100,104}E.f={103,105}E.t={100}E.f={101}E.t={104}M.q=102

E.t={102}E.f={103}E.t={104}E.f={105}M.q=104c<def<

EandEEMa<borEME①100(j<,a,b,0)101(j,_,_,0

)②sub7102(j<,c,d,0

)103(j,_,_,0)③④sub7⑤104(j>,e,f,0)105(j,_,_,0)⑥sub2①sub5③sub5⑤sub5⑦sub1103E.falselist100E.truelist104E.f={103,105}102回填回填合并合并2024/4/2760布爾表達式a＜borc＜dande＜f翻譯100(j<,a,b,0)101(j,_,_,0)102(j<,c,d,0)103(j,_,_,0)104(j<,e,f,0)105(j,_,_,0)103E.falselist100E.truelist104102回填回填合并合并E.truec<da＜bc＜de<fE.falsee＜fE.trueE.false2024/4/2761翻譯布爾表達式a>1orb>1andb<9課堂練習(xí)100(j>,a,1,0)101(j,_,_,0)102(j>,b,1,0)103(j,_,_,0)104(j<,b,9,0)105(j,_,_,0)103E.falselist100E.truelist104102回填回填合并合并E.trueb>1a>1b>1b<9E.falseb<9E.trueE.falseBEGIN翻譯布爾表達式AandB<CorD課堂練習(xí)2024/4/2762作為控制條件布爾表達式翻譯總結(jié)拉鏈當(dāng)四元式的轉(zhuǎn)移目標不可知時應(yīng)進行拉鏈?；靥町?dāng)知道了四元式的轉(zhuǎn)移目標(條件為真時和條件為假時分別應(yīng)做哪些事)時，就可以進行回填。翻譯結(jié)果E.truelistE.flaselist2024/4/2763作為控制條件布爾表達式應(yīng)用舉例例ifa＜borc＜dande＜fthenx:=y+zelsex:=y-z

回填E.truelist回填E.falselist100(j<,a,b,0)101(j,_,_,102)102(j<,c,d,104)103(j,_,_,0)104(j<,e,f,100)105(j,_,_,103)E.falselistE.truelist106(+,y,z,T1)107(:=,T1,_,x)E.true106106S.next108(j,_,_,0)S.next109(-,y,z,T2)110(:=,T2,_,x)111E.false109109S.next111S.nextlist2024/4/2764作為控制條件布爾表達式應(yīng)用舉例例whilea＜borc＜dande＜fdox:=y+z

回填E.truelist回填E.falselist100(j<,a,b,0)101(j,_,_,102)102(j<,c,d,104)103(j,_,_,0)104(j<,e,f,100)105(j,_,_,103)E.falselistE.truelist106(+,y,z,T1)107(:=,T1,_,x)E.true106106S.next108(j,_,_,100)S.begin109E.false109109S.nextS.beginS.begin節(jié)目錄2024/4/27658.6控制結(jié)構(gòu)的翻譯p1868.6.1條件轉(zhuǎn)移if語句while語句8.6.6過程調(diào)用章節(jié)目錄2024/4/2766if_then語句的代碼結(jié)構(gòu)p183語法S→ifEthenS1語義如果E的值為true，那么執(zhí)行S1舉例

ifc<dthena:=b+2

翻譯成四元式序列為：E.codeS1.codeE.true:E.false:...toE.truetoE.false100(j<,c,d,0)E.true101(j,_,_,0)E.falseE.fE.t102(+,b,2,T1)103(:=,T1,_,a)104E.trueE.false1021042024/4/2767if_then_else的代碼結(jié)構(gòu)語法S→ifEthenS1elseS2語義如果E的值為true，那么執(zhí)行S1；否那么執(zhí)行S2舉例ifc<dthenx:=y+zelsex:=y-z

翻譯成四元式序列為：E.codeS1.codeE.true:S2.codeE.false:gotoS.next...S.next:toE.truetoE.false100(j<,c,d,0)101(j,_,_,0)E.trueE.falseE.fE.t102(+,y,z,T1)103(:=,T1,_,x)E.true102104(j,_,_,0)S.next105(-,y,z,T2)106(:=,T2,_,x)107E.false105S.next1072024/4/2768嵌套if_then_else的翻譯練習(xí)ifa<bthenifc>dthenx:=y+zelsex:=y-zelsea:=b+2E1.trueE1.falseE1E2S1S2S3100(j<,a,b,0)101(j,_,_,0)E1.tE1.fE1.truec>d入口E1.falsea:=b+2E2.truex:=y+zE2.falsex:=y-zSQ102(j>,c,d,0)103(j,_,_,0)E2.trueE2.falseE1.true102104(+,y,z,T1)105(:=,T1,_,x)E2.true104106(j,_,_,0)Q.nextQ.nlist107(-,y,z,T2)108(:=,T2,_,x)E2.false107109(j,_,_,0)S.nextS.nlist110(+,b,2,T3)111(:=,T3,_,a)112E1.false110S.next106S.next合并S.nextlist回填S.nextlist112112BEGIN節(jié)目錄2024/4/2769while_do的代碼結(jié)構(gòu)p183語法S→whileEdoS1語義如果E的值為true，那么執(zhí)行S1；否那么退出循環(huán)舉例

whilea<bdox:=y+z翻譯成四元式序列為：E.codeS1.codeE.true:E.false:gotoS.begin...S.begin:toE.truetoE.falseE.trueE.false100(j<,a,b,0)101(j,_,_,0)S.beginE.tE.f102(+,y,z,T1)103(:=,T1,_,x)E.true102104(j,_,_,100)S.begin105E.false1052024/4/2770嵌套while_if的翻譯練習(xí)p188whilea<bdoifc<dthenx:=y+zE1.trueE1.falseE1E2S1100(j<,a,b,0)101(j,_,_,0)S.begina<b入口E1.truec<d入口E1.falsewhile

出口E2.truex:=y+zQ.nlist回填

S.beginSQ102(j<,c,d,0)103(j,_,_,0)E2.trueE2.falseE1.true102104(+,y,z,T1)105(:=,T1,_,x)E2.true104106(j,_,_,100)107E1.falseQ.nlist107S.beginS.begin100BEGIN2024/4/2771控制流語句的文法p187(1)S→ifEthenSif_then語句(2)|ifEthenSelseSif_then_else語句(3)|whileEdoSwhile語句(4)|beginLend復(fù)合語句(5)|A賦值語句(6)L→L；S語句序列(7)|S一條語句

E為一個布爾表達式2024/4/2772翻譯模式中的屬性和函數(shù)設(shè)置〔略〕S→ifEthenM1S1NelseM2S2E.truelist需回填E.true的鏈E.falselist需回填E.false的鏈M.quad下一條四元式的標號S.nextlist需回填S.next的鏈N.nextlist需回填S.next的鏈S→beginLendL.nextlist需回填S.next的鏈變量和函數(shù)nextquadmakelistmergebackpatch2024/4/2773控制流語句的翻譯模式〔略〕sub1SifEthenM1S1NelseM2S2{backpatch(E.truelist,M1.quad);M1處生成E.true，回填E.truelistbackpatch(E.falselist,M2.quad);M2處生成E.false，回填E.falselistS.nextlist:=merge(S1.nextlist,N.nextlist,S2.nextlist)

合并轉(zhuǎn)移目標同為S.next的鏈}sub2N

{N.nextlist:=makelist(nextquad);emit(‘j,_,_,0’)N處生成轉(zhuǎn)移指令gotoS.next}sub3M

{M.quad:=nextquadM處生成下一條四元式的標號}2024/4/2774控制流語句的翻譯模式sub4SifEthenMS1{backpatch(E.truelist,M.quad);S.nextlist:=merge(E.falselist,S1.nextlist)}sub5SwhileM1EdoM2S1{backpatch(S1.nextlist,M1.quad);M1處生成標號S.begin，回填S1.nextlist(循環(huán))backpatch(E.truelist,M2.quad);M2處生成E.true,回填E.truelistS.nextlist:=E.falselist;emit(‘j,_,_,’M1.quad)形成循環(huán)}2024/4/2775控制流語句的翻譯模式sub6SbeginLend{S.nextlist:=L.nextlist}sub7SA{S.nextlist:=makelist()}sub8LL1;MS{backpatch(L1.nextlist,M.quad);M處生成標號L.next，回填L1.nextlistL.nextlist:=S.nextlist}sub9LS{L.nextlist:=S.nextlist}節(jié)目錄2024/4/27768.6.6過程調(diào)用的處理p195功能把程序控制轉(zhuǎn)移到子程序(過程段)任務(wù)把實在參數(shù)的信息傳遞給被調(diào)用的子程序保存子程序調(diào)用結(jié)束后的返回地址(不考慮)翻譯工作生成一個調(diào)用序列，包括進入和離開每一個過程所采取的動作序列2024/4/2777過程調(diào)用的文法p195考慮如下的一個簡單的過程調(diào)用語句的文法

(1)S→callid(arglist)調(diào)用語句

(2)arglist→arglist，E實參表

(3)arglist→E實參例過程調(diào)用calls(a+b,z)

翻譯生成代碼如下：計算a＋b置于單元T中/*T:=a+b*/

parT/*第一個實參地址*/parz/*第二個實參地址*/calls/*調(diào)用過程s*/

2024/4/2778過程調(diào)用的翻譯模式p196E.place:存放實在參數(shù)的地址queue：存放實在參數(shù)的地址隊列sub1S→callid(arglist〕｛for隊列queue中的每一項doemit〔‘par’p)；為實參生成par語句emit〔'call'id.place〕call語句}sub2arglist→arglist，E{將E.place參加到queue的隊尾}sub3arglist→E｛初始化queue僅包含E.place}節(jié)目錄2024/4/27798.7說明語句的翻譯p196翻譯工作確定變量類型分配存儲空間——相對地址全局數(shù)據(jù)表示為靜態(tài)數(shù)據(jù)區(qū)的偏移值局部數(shù)據(jù)表示為局部數(shù)據(jù)域(活動記錄的局部)的偏移值作用域地址空間的分配方式設(shè)置一個全局量offset，記錄當(dāng)前可用存儲空間的開始地址，初值為0每次分配一個變量的空間，將offset增加相應(yīng)的值2024/4/2780例存儲布局設(shè)整數(shù)類型域?qū)挒?

實數(shù)類型域?qū)挒?說明語句

x:array[8]ofreal;i:integer;j:real;名字類型相對地址0offset63x6467i6875j76xarray(8,real)0iinteger64jreal682024/4/2781翻譯模式中變量和函數(shù)類型描述符T的屬性type類型width占用的字節(jié)數(shù)語義函數(shù)enter(name,type,offset)在符號表中設(shè)置變量name的類型type和地址offsetarray(num,type)描述數(shù)組類型pointer(type)描述指針類型全局量offset跟蹤下一個可用的相對地址的位置2024/4/2782說明語句的翻譯模式p196(1)P→D(2)D→D;D(3)D→id:T(4)T→integer(5)T→real(6)T→array[num]ofT1(7)T→↑T1說明段說明語句序列說明變量id類型為T數(shù)組指針{offset:=0}{}

{enter(,T.type,offset);offset:=offset+T.width}{T.type:=integer;T.width:=4}{T.type:=real;T.width:=8}{T.type:=array(num.val,T1.type);T.width:=num.val*T1.width}{T.type:=pointer(T1.type);T.width:=4}2024/4/2783xi例x:real;i:integer的翻譯enter(x,real,0)offset=0offset=8T.type=realT.width=8offset=12T.type=integerT.width=4enter(i,integer,8)章節(jié)目錄2024/4/27848.8數(shù)組元素的引用p198翻譯工作計算數(shù)組元素的相對地址產(chǎn)生三地址代碼完成相對地址的計算目標

T3:=T2[T1]

可變局部與下標有關(guān)不變局部與首地址和維數(shù)有關(guān)相對地址2024/4/2785一維數(shù)組元素地址的計算p199說明：VARa:ARRAY[low..high]OFreal;數(shù)組元素a[i]的起始地址:base+(i-low)*w=i*w+base-low*w=V+base-C=可變局部+不變局部(可在編譯時計算出來)其中，base是數(shù)組a的首地址，w是元素的域?qū)捓鏥ARa:ARRAY[1..10]OFreal;元素a[i]的起始地址：base+(i-low)*w=A+(i-1)*8=i*8+A-82024/4/2786二維數(shù)組元素地址的計算二維數(shù)組假設(shè)按行存放可如下計算a[i1,i2]的相對地址：base+((i1-low1)*n2+i2-low2)*w)=(i1*n2)+i2)*w+base-((low1*n2)+low2〕*w(7.5)=V+base-C其中，n2=high2-low2+1，稱為第二維的界差(編譯時可知)例二維整型數(shù)組a[1..10,1..20]n2=20-1+1=20w=4數(shù)組元素a[i,j]的相對地址：A+((i-1)*20+j-1))*4=(i*20+j)*4+A-((1*20)+1)*4=(i*20+j)*4+A-84x:=a[i,j]的三地址代碼

(1)T1:=i*20

(2)T1:=T1+j(3)T2:=A-84

(4)T3:=4*T1(5)T4:=T2[T3](6)x:=T42024/4/2787多維數(shù)組元素

地址的計算推廣公式，假設(shè)按行存放，計算k維數(shù)組元素a[i1,i2,…，ik]的相對地址：((...((i1*n2+i2)*n3+i3)...)*nk+ik)*w+base-((...((low1*n2+low2)*n3+low3)...)*nk+lowk)*w(7.6)=V+base-C其中，對任何j，nj=highj-lowj+1第j維的界差例如三維整型數(shù)組a[1..10,1..20，1..30]n2=20n3=30w=4數(shù)組元素a[i,j,k]的相對地址：((i*20+j)*30+k)*4+A-((1*20+1)*30+1)*4=((i*20+j)*30+k)*4+A-2524

a[i,j,k]

:=

x的三地址代碼

(1)T1:=i*20(2)T1:=T1+j(3)T1:=T1*30(4)T1:=T1+k

(5)T2:=A-2524(6)T3:=4*T1(7)T4:=T2[T3](8)T4:=x2024/4/2788產(chǎn)生引用數(shù)組元素的三地址代碼數(shù)組元素的三地址代碼結(jié)構(gòu)T1:=V計算可變局部(有假設(shè)干條三地址語句)T2:=base-C計算不變局部(base,C可從符號表中查找到)T3:=T2[T1]訪問元素的地址T3假設(shè)x:=a[i1,i2,…，ik]那么x:=T3假設(shè)a[i1,i2,…，ik]:=x那么T3:=x詳解2024/4/2789數(shù)組類型在符號表中的信息組織數(shù)組的類型信息：VARa:ARRAY[1..10,1..20]OFreal;名字表信息向量

a嵌套深度偏移量類型C=84low1=1n1=10low2=1n2=20A基類