中間代碼生成

中間代碼生成第1頁，課件共93頁，創(chuàng)作于2023年2月例如:表達(dá)式A+B*C對運(yùn)算對象進(jìn)行類型檢查,對變量進(jìn)行先定義后使用檢查如果靜態(tài)語義正確,語義處理則要執(zhí)行真正的翻譯,即生成程序的某種中間代碼的形式或直接生成目標(biāo)代碼。執(zhí)行真正的翻譯第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第2頁，課件共93頁，創(chuàng)作于2023年2月目前多數(shù)編譯程序進(jìn)行語義分析的方法是采用語法制導(dǎo)翻譯法。它不是一種形式系統(tǒng),但它比較接近形式化。

語法制導(dǎo)翻譯法使用屬性文法為工具來描述程序設(shè)計(jì)語言的語義。第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第3頁，課件共93頁，創(chuàng)作于2023年2月(1)屬性對文法的每一個(gè)符號,引進(jìn)一些屬性,這些屬性代表與文法符號相關(guān)的信息,如類型、值、存儲位置等。與屬性相關(guān)的信息,即屬性值,可以在語法分析過程中計(jì)算和傳遞。1.屬性文法第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第4頁，課件共93頁，創(chuàng)作于2023年2月屬性分為兩類: 綜合屬性其計(jì)算規(guī)則按“自下而上”方式進(jìn)行,即規(guī)則左部符號的某些屬性根據(jù)其右部符號的屬性和(或)自己的其他屬性計(jì)算得到。屬性加工的過程即是語義的處理過程。綜合屬性和繼承屬性。第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第5頁，課件共93頁，創(chuàng)作于2023年2月 繼承屬性其計(jì)算規(guī)則按“自上而下”方式進(jìn)行,即規(guī)則右部符號的某些屬性根據(jù)其左部符號的屬性和(或)右部其他符號的某些屬性計(jì)算得到。第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第6頁，課件共93頁，創(chuàng)作于2023年2月(2)屬性文法為文法的每一個(gè)規(guī)則配備的計(jì)算屬性的計(jì)算規(guī)則,稱為語義規(guī)則(描述語義處理的加工動(dòng)作)。屬性文法包含一個(gè)上下文無關(guān)文法和一系列語義規(guī)則。語義規(guī)則:第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第7頁，課件共93頁，創(chuàng)作于2023年2月這些語義規(guī)則附在文法的每個(gè)產(chǎn)生式上,在語法分析過程中,執(zhí)行語義規(guī)則描述的動(dòng)作,從而實(shí)現(xiàn)語義處理。也就是說,附在文法的每個(gè)產(chǎn)生式上語義規(guī)則描述了語義處理的加工動(dòng)作。目前流行的語義描述和語義處理的方法主要是屬性文法和語法制導(dǎo)翻譯方法。第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第8頁，課件共93頁，創(chuàng)作于2023年2月2.語法制導(dǎo)翻譯法

為文法的每個(gè)產(chǎn)生式都配備一個(gè)語義動(dòng)作或語義子程序。在語法分析的過程中，每當(dāng)使用一條產(chǎn)生式進(jìn)行推導(dǎo)或歸約時(shí)，就執(zhí)行相應(yīng)產(chǎn)生式的語義動(dòng)作,從而實(shí)現(xiàn)語義處理。第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成(1)語法制導(dǎo)翻譯法的基本思想第9頁，課件共93頁，創(chuàng)作于2023年2月S→……{……}………A→xy{……}………

a1a2a3…aiai+1…an語義處理的加工動(dòng)作語法制導(dǎo)翻譯法使用屬性文法為工具來說明程序設(shè)計(jì)語言的語義。第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第10頁，課件共93頁，創(chuàng)作于2023年2月(2)語法制導(dǎo)翻譯法在語法分析過程中，依隨分析的過程，根據(jù)每個(gè)產(chǎn)生式所對應(yīng)的語義子程序(或語義規(guī)則描述的語義處理的加工動(dòng)作)進(jìn)行翻譯的方法。第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第11頁，課件共93頁，創(chuàng)作于2023年2月 為文法每一產(chǎn)生式設(shè)計(jì)相應(yīng)的求值的語義描述(語義動(dòng)作)：例如，設(shè)有簡單算術(shù)表達(dá)式的文法：E→E＋E|E*E|(E)|digit1.E→E(1)＋E(2)

{E.val＝E(1).val＋E(2).val}2.E→E(1)*E(2)

{E.val＝E(1).val*E(2).val}3.E→(E(1)){E.val＝E(1).val}4.E→digit{E.val＝Lex.digit}第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第12頁，課件共93頁，創(chuàng)作于2023年2月E.val=47E.val=8E.val=40E.val=7E.val=5+5*871.E→E(1)＋E(2)

{E.val＝E(1).val＋E(2).val}2.E→E(1)*E(2)

{E.val＝E(1).val*E(2).val}3.E→(E(1)){E.val＝E(1).val}4.E→digit{E.val＝Lex.digit}句子7+8*5EEEEE第13頁，課件共93頁，創(chuàng)作于2023年2月

3.

編譯中常用的中間代碼:逆波蘭式四元式三元式樹形表示第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第14頁，課件共93頁，創(chuàng)作于2023年2月逆波蘭式

逆波蘭式除去了原表達(dá)式中的括號，并將運(yùn)算對象寫在前面，運(yùn)算符寫在后面，因而又稱為后綴式。例如：逆波蘭式a*bab*(a+b)*(c+d)ab+cd+*中綴表達(dá)式第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第15頁，課件共93頁，創(chuàng)作于2023年2月逆波蘭式表示法同中綴表示法相比其優(yōu)點(diǎn)是:不再有括號,且運(yùn)算符出現(xiàn)的順序體現(xiàn)了中綴表達(dá)式的運(yùn)算順序2.易于計(jì)算機(jī)處理第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第16頁，課件共93頁，創(chuàng)作于2023年2月一般表達(dá)式計(jì)值時(shí)，要處理兩類符號，一類是運(yùn)算對象，另一類是運(yùn)算符，通常用兩個(gè)工作棧分別處理。但處理用逆波蘭式表示的表達(dá)式卻只用一個(gè)工作棧。第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第17頁，課件共93頁，創(chuàng)作于2023年2月當(dāng)計(jì)算機(jī)自左到右順序掃描逆蘭波式時(shí)，若當(dāng)前符號是運(yùn)算對象則進(jìn)棧，若當(dāng)前符號是運(yùn)算符，設(shè)為K元運(yùn)算符，則將棧頂?shù)腒個(gè)元素依次取出，同時(shí)進(jìn)行K元運(yùn)算，并將運(yùn)算結(jié)果置于棧頂，表達(dá)式處理完畢時(shí)，其計(jì)算結(jié)果自然呈現(xiàn)在棧頂。第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第18頁，課件共93頁，創(chuàng)作于2023年2月逆波蘭式ab+c*的處理過程如下圖：baT1第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成cT1T2第19頁，課件共93頁，創(chuàng)作于2023年2月逆波蘭形式可以推廣到其他語法結(jié)構(gòu)：賦值語句V=E逆波蘭式VE=條件語句逆波蘭式ifES1;elseS2ES1S2￥第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第20頁，課件共93頁，創(chuàng)作于2023年2月三元式和樹形表示三元式主要由三部分組成：（OP，arg1,arg2）其中OP是運(yùn)算符，arg1,arg2分別是第一和第二個(gè)運(yùn)算對象。當(dāng)OP是一目運(yùn)算時(shí)，常常將運(yùn)算對象定義為arg1。第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第21頁，課件共93頁，創(chuàng)作于2023年2月例如a+b*c

的三元式序列：

(1)(*,b,c)

(2)(+,a,(1)) 運(yùn)算對象是指向符號表的某一項(xiàng)或指向三元式表的某一項(xiàng)。第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第22頁，課件共93頁，創(chuàng)作于2023年2月1.三元式出現(xiàn)的順序和語法成分的計(jì)值順序相一致。三元式的特點(diǎn)：2.三元式之間的聯(lián)系是通過指示器實(shí)現(xiàn)的。第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第23頁，課件共93頁，創(chuàng)作于2023年2月間接三元式(1)間接三元式表:用來存放各三元式本身。(2)間接碼表:按執(zhí)行各三元式的順序,依次列出各三元式在三元式表中的位置。注意:間接三元式表中不存放重復(fù)的三元式。第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第24頁，課件共93頁，創(chuàng)作于2023年2月例如語句X=(A+B)*C

Y=D↑(A+B)三元式序列(1)(+,A,B)(2)(*,(1),C)(3)(=,X,(2))(5)(↑,D,(4))(4)(+,A,B)(6)(=,Y,(5))間接三元式間接碼表三元式表(1)(2)(3)(1)(4)(5)(1)(+,A,B)(2)(*,(1),C)(3)(=,X,(2))(4)(↑,D,(1))(5)(=,Y,(4))第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第25頁，課件共93頁，創(chuàng)作于2023年2月樹形表示

A*B+C*D+C*A*BD末端結(jié)點(diǎn)表示一個(gè)運(yùn)算對象,每一個(gè)內(nèi)結(jié)點(diǎn)表示一個(gè)一元或二元運(yùn)算符。樹形表示是三元式的翻版(3)+(1)*(2)*CABD第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第26頁，課件共93頁，創(chuàng)作于2023年2月四元式主要由四部分組成：（OP，arg1,arg2,result）其中OP是運(yùn)算符，arg1,arg2分別是第一和第二兩個(gè)運(yùn)算對象。當(dāng)OP是一目運(yùn)算時(shí)，常常將運(yùn)算對象定義為arg1。第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第27頁，課件共93頁，創(chuàng)作于2023年2月四元式的第四個(gè)分量result是編譯程序?yàn)榇娣胖虚g運(yùn)算結(jié)果而臨時(shí)引進(jìn)的變量，常稱為臨時(shí)變量，如Ti，也可以是用戶自定義變量，如X。例如X＝a*b＋c/d

的四元式序列：(1)(*,a,b,T1)(2)(/,c,d,T2)(3)(+,T1,T2,T3)(4)(=,T3,-,X

)第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第28頁，課件共93頁，創(chuàng)作于2023年2月2.四元式之間的聯(lián)系是通過臨時(shí)變量實(shí)現(xiàn)的，這樣易于調(diào)整和變動(dòng)四元式。1.四元式出現(xiàn)的順序和語法成份的計(jì)值順序相一致。四元式的特點(diǎn)：3.便于優(yōu)化處理。第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第29頁，課件共93頁，創(chuàng)作于2023年2月編譯系統(tǒng)中，有時(shí)將四元式表示成另一種更直觀，更易理解的形式——三地址代碼或三地址語句。result:＝arg1OParg2

三地址語句:語句中是三個(gè)量的賦值語句,每個(gè)量占一個(gè)地址。三地址代碼形式定義為：第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第30頁，課件共93頁，創(chuàng)作于2023年2月例如X＝a*b＋c/d的四元式序列：(1)(*,a,b,T1)(2)(/,c,d,T2)(3)(+,T1,T2,T3)(4)(=,T3,-,X

)相應(yīng)的三地址語句序列為：（1）T1＝a*b（2）T2＝c/d（3）T3＝T1＋T2

（4）X＝T3

第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第31頁，課件共93頁，創(chuàng)作于2023年2月例1.–a+b*(–c+d)的逆波蘭式a@bc@d+*+第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第32頁，課件共93頁，創(chuàng)作于2023年2月t1=@a

t2=@c

t3=t2+dt5=t1+t4

–a+b*(–c+d)的四元式表示

t4=b*t3第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第33頁，課件共93頁，創(chuàng)作于2023年2月i↑(i/(i–i))的逆波蘭式

i↑(i/(i–i))的四元式

t1=i–i

t2=i/t1t3=i↑t2iiii–/↑例2.第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第34頁，課件共93頁，創(chuàng)作于2023年2月4.采用自下而上的語法制導(dǎo)翻譯法語義動(dòng)作的設(shè)計(jì)（1）搞清楚源結(jié)構(gòu)和目標(biāo)結(jié)構(gòu)（2）自下而上的語法制導(dǎo)翻譯特點(diǎn)：棧頂形成句柄，歸約時(shí)執(zhí)行相應(yīng)語義動(dòng)作（3）給出從源結(jié)構(gòu)到目標(biāo)結(jié)構(gòu)的變換方法第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第35頁，課件共93頁，創(chuàng)作于2023年2月例1.設(shè)文法及其相應(yīng)的語義動(dòng)作如下:

S→bTc{print“1”}

S→a{print“2”}

T→R{print“3”}

R→R/S{print“4”}

R→S{print“5”}采用自下而上語法制導(dǎo)翻譯,給出輸入串bR/bTc/bSc/ac的翻譯結(jié)果第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第36頁，課件共93頁，創(chuàng)作于2023年2月分析:首先對輸入串

bR/bTc/bSc/ac畫出規(guī)范規(guī)約的語法樹:ScTbRS/R/RS/RcTbaScTbRS再考慮歸約時(shí)執(zhí)行相應(yīng)語義動(dòng)作第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第37頁，課件共93頁，創(chuàng)作于2023年2月

S→bTc{print“1”}

S→a{print“2”}

T→R{print“3”}

R→R/S{print“4”}

R→S{print“5”}14翻譯結(jié)果為:53142431第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成cTbRS/R/RS/RcTbaScTbRSS第38頁，課件共93頁，創(chuàng)作于2023年2月

R→R/S

S→bTc

S→a

T→R

R→S輸出為:1453142431輸入是bR/bTc/bSc/ac給出相應(yīng)語義動(dòng)作(翻譯方案){print“1”}{print“2”}{print“3”}{print“4”}{print“5”}第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成cTbRS/R/RS/RcTbaScTbRSS第39頁，課件共93頁，創(chuàng)作于2023年2月例2簡單算術(shù)表達(dá)式求值的語義描述例如，設(shè)有簡單算術(shù)表達(dá)式的文法：E→E＋E|E*E|(E)|digit1.E→E(1)＋E(2)

{E.val＝E(1).val＋E(2).val}2.E→E(1)*E(2)

{E.val＝E(1).val*E(2).val}3.E→(E(1)){E.val＝E(1).val}4.E→digit{E.val＝Lex.digit}第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第40頁，課件共93頁，創(chuàng)作于2023年2月例3簡單算術(shù)表達(dá)式翻譯到四元式的語義描述例如，設(shè)有簡單算術(shù)表達(dá)式的文法：E→E＋E|E*E|(E)|i第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第41頁，課件共93頁，創(chuàng)作于2023年2月E→E＋E∣E*E∣(E)|i源結(jié)構(gòu)目標(biāo)結(jié)構(gòu)（1）T1＝a*b（2）T2＝c*d（3）T3＝T1＋T2

a*b＋c*d第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第42頁，課件共93頁，創(chuàng)作于2023年2月語義函數(shù)emit（T＝arg1OParg2）

功能是生成一個(gè)三地址語句，并送到輸出文件中。語義函數(shù)newtemp()

功能是產(chǎn)生一個(gè)新的臨時(shí)變量名字，并回送新的臨時(shí)變量名的整數(shù)碼。如T1，T2等。第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第43頁，課件共93頁，創(chuàng)作于2023年2月(2)不進(jìn)符號表，臨時(shí)變量單詞值部分用整數(shù)碼表示。(1)送到符號表。對臨時(shí)變量有兩種不同的處理方法:第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第44頁，課件共93頁，創(chuàng)作于2023年2月語義過程Lookup（）

功能是審查是否出現(xiàn)在符號表中，在則返回其指針，否則返回NULL。語義變量E.place

表示存放非終結(jié)符E值的變量名在符號表中的入口地址或臨時(shí)變量名的整數(shù)碼。第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第45頁，課件共93頁，創(chuàng)作于2023年2月1.E→E(1)＋E(2)2.E→E(1)*E(2){E.place＝newtemp();emit(E.place＝E(1).place＋E(2).place)}{E.place＝newtemp();emit(E.place＝E(1).place*E(2).place)}第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第46頁，課件共93頁，創(chuàng)作于2023年2月3.E→（E(1)）{E.place＝E(1).place；}4.E→i{p＝Lookup();if(p!=NULL)E.place＝p;elseerror();}第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第47頁，課件共93頁，創(chuàng)作于2023年2月90狀態(tài)ACTIONGOTO+

i*()#ES3S9S5S4S2S3S2S3S5S4S2S5S2S3r4r4r4r4r1r1r1r2r3r2r3r3r2r2r3123456781678acc2.為文法構(gòu)造LR分析表如下圖：第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第48頁，課件共93頁，創(chuàng)作于2023年2月3.算術(shù)表達(dá)式a+b*c翻譯到三地址語句的過程：030##a01#E014#E+0143#E+b－a－a－－a－－狀態(tài)棧符號棧語義棧輸入串a(chǎn)+b*c#+b*c#+b*c#b*c#*c#－－－變量在符號表的入口用變量本身表示第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成E→E＋E|E*E|(E)|i第49頁，課件共93頁，創(chuàng)作于2023年2月*c#c#####t1=b*ct2=a+t1

狀態(tài)棧符號棧語義棧輸入串014750147#E+E#E+E*014753#E+E*c014758#E+E*E0147#E+E01#E－a－b－－－a－b－c－a－t1－a－b－－a－b－t2acc第7章語法制導(dǎo)翻譯技術(shù)和中間代碼生成E→E＋E|E*E|(E)|i第50頁，課件共93頁，創(chuàng)作于2023年2月布爾表達(dá)式到四元式的翻譯一.布爾表達(dá)式的文法●計(jì)算邏輯值程序設(shè)計(jì)語言中布爾表達(dá)式有兩個(gè)作用:

●用作控制語句中的條件式布爾表達(dá)式是由布爾算符(∧、∨和)施于布爾變量或關(guān)系表達(dá)式而成。

第51頁，課件共93頁，創(chuàng)作于2023年2月布爾表達(dá)式到四元式的翻譯

E→E(1)∨E(2)

E→E(1)∧E(2)

E→E(1)

E→(E(1))

E→i(1)ropi(2)

E→true

E→false

E→i第52頁，課件共93頁，創(chuàng)作于2023年2月布爾表達(dá)式到四元式的翻譯二.布爾表達(dá)式的計(jì)值方法1.如同計(jì)算算術(shù)表達(dá)式一樣,逐步計(jì)算出各部分真、假值,最后計(jì)算出整個(gè)表達(dá)式的值。2.根據(jù)布爾運(yùn)算的特殊性,采取某種優(yōu)化措施,可避免計(jì)算整個(gè)表達(dá)式的值。第53頁，課件共93頁，創(chuàng)作于2023年2月布爾表達(dá)式到四元式的翻譯

A∨B

解釋成

A∧B

解釋成

A

解釋成ifAthentrueelseBifAthenBelsefalseifAthenfalseelsetrue三.布爾表達(dá)式的翻譯方法1.同翻譯算術(shù)表達(dá)式一樣,翻譯布爾表達(dá)式。第54頁，課件共93頁，創(chuàng)作于2023年2月布爾表達(dá)式到四元式的翻譯1.E→E(1)∨E(2){E.place＝newtemp()；

emit(E.place＝E(1).place∨E(2).place)}2.E→E(1)∧E(2){E.place＝newtemp()；

emit(E.place＝E(1).place∧E(2).place)}第55頁，課件共93頁，創(chuàng)作于2023年2月布爾表達(dá)式到四元式的翻譯3.E→(E(1)){E.place＝E(1).place；}4.E→i(1)ropi(2){E.place＝newtemp()；

emit(ifi(1).placerop.opi(2).place‘goto’next+3);emit(E.place＝‘0’);emit(gotonext+2);emit(E.place＝‘1’);}當(dāng)前四元式的編號第56頁，課件共93頁，創(chuàng)作于2023年2月布爾表達(dá)式到四元式的翻譯5.E→true

{E.place＝newtemp()；

emit(E.place＝‘1’)}{E.place＝newtemp()；

emit(E.place＝‘0’)}6.E→false

或{E.place＝i.place；}6.E→i

第57頁，課件共93頁，創(chuàng)作于2023年2月布爾表達(dá)式到四元式的翻譯 例如布爾表達(dá)式a==b∨c∧d對應(yīng)如下四元式序列:101ifa==bgoto104102t1=0103goto105104t1=1105t2=c∧d106t3=t1∨

t2

第58頁，課件共93頁，創(chuàng)作于2023年2月布爾表達(dá)式到四元式的翻譯2.控制語句中布爾表達(dá)式的翻譯條件語句的語法為:根據(jù)條件語句的語義,條件語句的代碼結(jié)構(gòu)為:ifEthenS(1)elseS(2)E的代碼S(1)的代碼S(2)的代碼Jumpout

out:

真

假第59頁，課件共93頁，創(chuàng)作于2023年2月布爾表達(dá)式到四元式的翻譯

E是布爾表達(dá)式,根據(jù)布爾運(yùn)算的特殊性,布爾表達(dá)式的目標(biāo)結(jié)構(gòu)為:假E(1)的代碼∨E(2)的代碼真S(1)S(2)真假真E(1)的代碼∧E(2)的代碼假S(2)S(1)假真第60頁，課件共93頁，創(chuàng)作于2023年2月(1)真出口和假出口:真出口表示布爾表達(dá)式E為真時(shí)控制流向的轉(zhuǎn)移目標(biāo)假出口表示布爾表達(dá)式E為假時(shí)控制流向的轉(zhuǎn)移目標(biāo)布爾表達(dá)式到四元式的翻譯第61頁，課件共93頁，創(chuàng)作于2023年2月(2)作為條件轉(zhuǎn)移的E,把E翻譯成的代碼是一串條件轉(zhuǎn)或無條件轉(zhuǎn)的四元式對于E為aropb的形式生成代碼為:

ifaropbgoto真出口

goto假出口布爾表達(dá)式到四元式的翻譯第62頁，課件共93頁，創(chuàng)作于2023年2月(q) 例如語句ifa<b∨c<dthenS(1)elseS(2)

的四元式為:100ifa<bgoto真出口

101goto假出口102ifc<dgoto真出口

103goto假出口104(關(guān)于S(1)

的四元式)……(p)goto(q)(p+1)(關(guān)于S(2)

的四元式)……布爾表達(dá)式到四元式的翻譯E(1)的真出口E->

E(1)VE(2)E(2)的真出口第63頁，課件共93頁，創(chuàng)作于2023年2月(q) 例如語句ifa<b∨c<dthenS(1)elseS(2)

的四元式為:100ifa<bgoto104101goto102102ifc<dgoto104103goto(p+1)104(關(guān)于S(1)

的四元式)……(p)goto(q)(p+1)(關(guān)于S(2)

的四元式)E(1)的真出口為104,E(1)的假出口為102E(2)的真出口為104,E(2)的假出口為(p+1)E的真出口為104,E的假出口為(p+1)……布爾表達(dá)式到四元式的翻譯第64頁，課件共93頁，創(chuàng)作于2023年2月布爾表達(dá)式到四元式的翻譯 布爾表達(dá)式的真、假出口不能在產(chǎn)生其四元式的同時(shí)得知。 例如E(1)的真出口為104需分析到S(1)時(shí)才能得知,因此需回填出口地址E.tr:記錄表達(dá)式E所對應(yīng)的四元式需回填真出口的四元式的地址所構(gòu)成的鏈E.fa:記錄表達(dá)式E所對應(yīng)的四元式需回填假出口的四元式的地址所構(gòu)成的鏈(3)設(shè)置兩個(gè)語義變量:第65頁，課件共93頁，創(chuàng)作于2023年2月布爾表達(dá)式到四元式的翻譯E(1).tr=100,

E(1).fa=101E(2).tr=102,

E(2).fa=103(q) 例如語句ifa<b∨c<dthenS(1)elseS(2)

的四元式為:100ifa<bgoto真出口

101goto假出口102ifc<dgoto真出口

103goto假出口104(關(guān)于S(1)

的四元式)……(p)goto(q)(p+1)(關(guān)于S(2)

的四元式)……第66頁，課件共93頁，創(chuàng)作于2023年2月布爾表達(dá)式到四元式的翻譯E.fa=103;E.tr=100和102所構(gòu)成的鏈

E(1)∨E(2)歸約E時(shí),第67頁，課件共93頁，創(chuàng)作于2023年2月布爾表達(dá)式到四元式的翻譯 把以p1,p2為鏈?zhǔn)椎膬蓷l鏈合并為一,返回合并后的鏈?zhǔn)?4)鏈結(jié)函數(shù)和回填函數(shù):●merg(p1,p2):第68頁，課件共93頁，創(chuàng)作于2023年2月布爾表達(dá)式到四元式的翻譯

}merg(intp1,intp2){ifp2=0return(p1);else{p=p2;

while(四元式p的第四分量內(nèi)容不為0)

p=四元式p的第四分量內(nèi)容;

把p1填進(jìn)四元式p的第四分量;

return(p2);

}返回的鏈?zhǔn)讘?yīng)該是回填相同數(shù)字的四元式最后一個(gè)的編號第69頁，課件共93頁，創(chuàng)作于2023年2月布爾表達(dá)式到四元式的翻譯r1(× × × 0)q1(× × × r1)q2(× × × r2)p1(× × × q1)r2(× × × 0)p2(× × × q2)p1第70頁，課件共93頁，創(chuàng)作于2023年2月布爾表達(dá)式到四元式的翻譯

}merg(intp1,intp2){ifp2=0return(p1);else{p=p2;

while(四元式p的第四分量內(nèi)容不為0)

p=四元式p的第四分量內(nèi)容;

把p1填進(jìn)四元式p的第四分量;

return(p2);

}100102102第71頁，課件共93頁，創(chuàng)作于2023年2月(q)例如語句ifa<b∨c<dthenS(1)elseS(2)

的四元式為:100ifa<bgoto0101goto102102ifc<dgoto100

103goto(p+1)104(關(guān)于S(1)

的四元式)……(p)goto(q)(p+1)(關(guān)于S(2)

的四元式)……布爾表達(dá)式到四元式的翻譯第72頁，課件共93頁，創(chuàng)作于2023年2月布爾表達(dá)式到四元式的翻譯●bp(intp,intt):

將p所鏈結(jié)的每個(gè)四元式的第四分量都回填t;第73頁，課件共93頁，創(chuàng)作于2023年2月布爾表達(dá)式到四元式的翻譯}bp(intp,intt){q=p;while(q!=0){r=四元式q的第四分量內(nèi)容;

把t填進(jìn)四元式q的第四分量;

q=r;

}1021041000102100第74頁，課件共93頁，創(chuàng)作于2023年2月(q) 例如語句ifa<b∨c<dthenS(1)elseS(2)

的四元式為:100ifa<bgoto104101goto102102ifc<dgoto104

103goto(p+1)104(關(guān)于S(1)

的四元式)……(p)goto(q)(p+1)(關(guān)于S(2)

的四元式)……布爾表達(dá)式到四元式的翻譯第75頁，課件共93頁，創(chuàng)作于2023年2月布爾表達(dá)式到四元式的翻譯(5)為及時(shí)回填轉(zhuǎn)移地址,使用語義變量E.code記錄表達(dá)式E的第一個(gè)四元式語句序號。(6)定義語義變量next為四元式表指針。E(1).code=100E(2).code=102E.code=100第76頁，課件共93頁，創(chuàng)作于2023年2月布爾表達(dá)式到四元式的翻譯布爾表達(dá)式語義動(dòng)作的設(shè)計(jì)1.E→E(1)∨E(2){bp(E(1).fa,E(2).code)；

E.code=E(1).code;E.tr=merg(E(1).tr,E(2).tr);E.fa=E(2).fa;}第77頁，課件共93頁，創(chuàng)作于2023年2月布爾表達(dá)式到四元式的翻譯布爾表達(dá)式語義動(dòng)作的設(shè)計(jì)2.E→E(1)∧E(2){bp(E(1).tr,E(2).code)；

E.code=E(1).code;E.tr=E(2).tr;E.fa=merg(E(1).fa,E(2).fa);}第78頁，課件共93頁，創(chuàng)作于2023年2月布爾表達(dá)式語義動(dòng)作的設(shè)計(jì)3.E→(E(1)){E.code=E(1).code;E.tr=E(1).tr;E.fa=E(1).fa;}布爾表達(dá)式到四元式的翻譯第79頁，課件共93頁，創(chuàng)作于2023年2月布爾表達(dá)式語義動(dòng)作的設(shè)計(jì)4.E→i(1)ropi(2){E.tr=next;E.code=next;E.fa=next+1;emit(ifi(1).placerop.opi(2).placegoto_);emit(goto_);}布爾表達(dá)式到四元式的翻譯第80頁，課件共93頁，創(chuàng)作于2023年2月布爾表達(dá)式語義動(dòng)作的設(shè)計(jì)5.E→true{E.tr=next;E.code=next;emit(goto_);}布爾表達(dá)式到四元式的翻譯第81頁，課件共93頁，創(chuàng)作于2023年2月布爾表達(dá)式到四元式的翻譯布爾表達(dá)式語義動(dòng)作的設(shè)計(jì)6.E→false{E.fa=next;E.code=next;emit(goto_);}第82頁，課件共93頁，創(chuàng)作于2023年2月布爾表達(dá)式到四元式的翻譯布爾表達(dá)式語義動(dòng)作的設(shè)計(jì)5.E→i{E.tr=next;E.fa=next+1;E.code=next;emit(ifi.placegoto-);emit(goto_);}5.E→true6.E→false第83