編譯原理第八章

1、u源程序的結(jié)構(gòu)分析源程序的結(jié)構(gòu)分析詞法分析詞法分析 ch4ch4語法分析語法分析 ch5ch5、ch6ch6、ch7ch7u語義分析語義分析由語法分析程序直接調(diào)用相應(yīng)的語義子程由語法分析程序直接調(diào)用相應(yīng)的語義子程序序首先生成語法樹（或該結(jié)構(gòu)的某種表示）首先生成語法樹（或該結(jié)構(gòu)的某種表示），再進(jìn)行語義處理，再進(jìn)行語義處理u生成中間代碼生成中間代碼編譯中的邏輯階段編譯中的邏輯階段源語言程序源語言程序 代碼優(yōu)化代碼優(yōu)化 目標(biāo)代碼（匯編或機(jī)器碼）目標(biāo)代碼（匯編或機(jī)器碼） 詞法分析詞法分析語義分析語義分析語法分析語法分析中間代碼生成中間代碼生成目標(biāo)代碼生成目標(biāo)代碼生成前端處理前端處理后端處理后端處理語義

2、處理語義處理語義處理的任務(wù)：語義處理的任務(wù)：靜態(tài)語義檢查靜態(tài)語義檢查 靜態(tài)語義：語法結(jié)構(gòu)靜態(tài)語義：語法結(jié)構(gòu) 靜態(tài)語義檢查：審查靜態(tài)語義檢查：審查靜態(tài)語義靜態(tài)語義動(dòng)態(tài)語義處理動(dòng)態(tài)語義處理 動(dòng)態(tài)語義：程序單元執(zhí)行的操作動(dòng)態(tài)語義：程序單元執(zhí)行的操作 動(dòng)態(tài)語義處理：生成動(dòng)態(tài)語義處理：生成( (中間中間/ /目標(biāo)目標(biāo)) )代碼代碼語義處理的實(shí)現(xiàn)：語義處理的實(shí)現(xiàn)：l屬性文法：描述語義規(guī)則。屬性文法：描述語義規(guī)則。-工具工具l語法制導(dǎo)翻譯：語法制導(dǎo)翻譯：在語法分析的同時(shí)在語法分析的同時(shí)，執(zhí)行，執(zhí)行語義規(guī)則描述的動(dòng)作：語義規(guī)則描述的動(dòng)作：檢查靜態(tài)語義檢查靜態(tài)語義生成中間代碼生成中間代碼/ /目標(biāo)代碼目標(biāo)代碼語

3、義處理的環(huán)境語義處理的環(huán)境：符號(hào)表符號(hào)表l為語義分析提供類型、作用域等信息。為語義分析提供類型、作用域等信息。l為代碼生成提供類型、作用域、存儲(chǔ)為代碼生成提供類型、作用域、存儲(chǔ)類別、存儲(chǔ)（相對(duì)）位置等信息類別、存儲(chǔ)（相對(duì)）位置等信息。 本章引入屬性文法和語法制導(dǎo)翻譯本章引入屬性文法和語法制導(dǎo)翻譯方法的基本思想，介紹幾種典型的中間方法的基本思想，介紹幾種典型的中間代碼形式，最后討論一些語法成分的翻代碼形式，最后討論一些語法成分的翻譯工作。譯工作。 第第8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 8 81 1 屬性文法屬性文法8 82 2 語法制導(dǎo)翻譯概論語法制導(dǎo)翻譯概論 8 8

4、3 3 中間代碼的形式中間代碼的形式 8 84 4 簡(jiǎn)單賦值語句的翻譯簡(jiǎn)單賦值語句的翻譯 8 85 5 布爾表達(dá)式的翻譯布爾表達(dá)式的翻譯 8 86 6 控制結(jié)構(gòu)的翻譯控制結(jié)構(gòu)的翻譯 8 87 7 說明語句的翻譯說明語句的翻譯 8 88 8 數(shù)組和結(jié)構(gòu)的翻譯數(shù)組和結(jié)構(gòu)的翻譯 8 81 1 屬性文法屬性文法 u屬性文法：屬性文法：語法制導(dǎo)翻譯工具，說明程序設(shè)計(jì)語言語法制導(dǎo)翻譯工具，說明程序設(shè)計(jì)語言的意義。的意義。u屬性文法構(gòu)成：屬性文法構(gòu)成：上下文無關(guān)文法上下文無關(guān)文法 + + 語義規(guī)則語義規(guī)則u語義規(guī)則附在文法的產(chǎn)生式上，在語法分析過程中，語義規(guī)則附在文法的產(chǎn)生式上，在語法分析過程中，完成附加在

5、完成附加在所使用產(chǎn)生式上所使用產(chǎn)生式上的語義規(guī)則描述的動(dòng)作，的語義規(guī)則描述的動(dòng)作，從而實(shí)現(xiàn)語義處理。從而實(shí)現(xiàn)語義處理。 定義：定義： 一個(gè)屬性文法是一個(gè)三元組：一個(gè)屬性文法是一個(gè)三元組： A=（G，V，F(xiàn)）其中其中:G：上下文無關(guān)文法：上下文無關(guān)文法V：屬性的有窮集：屬性的有窮集。 每個(gè)屬性與文法的某個(gè)非終結(jié)符或終結(jié)符相聯(lián)每個(gè)屬性與文法的某個(gè)非終結(jié)符或終結(jié)符相聯(lián)F：關(guān)于屬性的斷言或謂詞：關(guān)于屬性的斷言或謂詞的有窮集。的有窮集。 -屬性的計(jì)算規(guī)則屬性的計(jì)算規(guī)則 每個(gè)斷言與文法的某產(chǎn)生式相聯(lián)。每個(gè)斷言與文法的某產(chǎn)生式相聯(lián)。 例如例如 G：E T1 + T2 | T1 or T2 T num | t

6、rue | false 屬性文法記號(hào)中常使用屬性文法記號(hào)中常使用Nt的形式表示與非終的形式表示與非終結(jié)符結(jié)符N相聯(lián)的屬性。相聯(lián)的屬性。E T1 + T2 T1t = int AND T2t = int E T1 or T2 T1t = bool AND T2t = bool T num Tt = int T true Tt = bool T false Tt = bool 可進(jìn)行可進(jìn)行類型檢查類型檢查的屬性文法（表達(dá)式）的屬性文法（表達(dá)式） 對(duì)輸入串對(duì)輸入串3+4的語法樹：的語法樹： E T1t =T2t T1= int TT T2= int 3 4 + 如果對(duì)如果對(duì)G G中的某一輸入串而言，

7、中的某一輸入串而言，A A中的所有斷言中的所有斷言對(duì)該輸入串的對(duì)該輸入串的語法樹的結(jié)點(diǎn)的屬性全為真，則該串語法樹的結(jié)點(diǎn)的屬性全為真，則該串也是也是A A語言中的句子。語言中的句子。編譯程序的靜態(tài)語義審查工作就是編譯程序的靜態(tài)語義審查工作就是驗(yàn)證關(guān)于所編譯驗(yàn)證關(guān)于所編譯的程序的斷言是否全部為真的程序的斷言是否全部為真。 A為屬性文法為屬性文法例例8.28.2 描述描述說明語句說明語句中各種變量的類型信息中各種變量的類型信息的語義規(guī)則的語義規(guī)則產(chǎn)生式產(chǎn)生式 語義規(guī)則語義規(guī)則(1) DTL L.in := T.type(2) T int T.type := integer(3) T real T.t

8、ype := real(4) L L1,id L1.in := L.in; addtype(id.entry, L.in)(5) L id addtype(id.entry, L.in)entry id entry id 的屬性：可以是它在符號(hào)表中的地址的屬性：可以是它在符號(hào)表中的地址addtype addtype 在符號(hào)表中為變量填加類型信息在符號(hào)表中為變量填加類型信息8 82 2 語法制導(dǎo)翻譯概論語法制導(dǎo)翻譯概論 語法制導(dǎo)翻譯：語法制導(dǎo)翻譯：n首先，使用首先，使用屬性文法屬性文法為工具，描述程序?yàn)楣ぞ撸枋龀绦蛟O(shè)計(jì)語言的語義規(guī)則。設(shè)計(jì)語言的語義規(guī)則。 n在語法分析時(shí)，每應(yīng)用一個(gè)產(chǎn)生式（推在

9、語法分析時(shí)，每應(yīng)用一個(gè)產(chǎn)生式（推導(dǎo)或歸約），同時(shí)完成該產(chǎn)生式上所附導(dǎo)或歸約），同時(shí)完成該產(chǎn)生式上所附的語義規(guī)則描述的動(dòng)作，從而完成語義的語義規(guī)則描述的動(dòng)作，從而完成語義處理。處理。在進(jìn)行語法分析的同時(shí)，完成相應(yīng)的語義處理在進(jìn)行語法分析的同時(shí)，完成相應(yīng)的語義處理 語法制導(dǎo)翻譯的具體實(shí)現(xiàn)途徑不難。如語法制導(dǎo)翻譯的具體實(shí)現(xiàn)途徑不難。如有一個(gè)有一個(gè)LRLR分析器，擴(kuò)充它的分析棧，使得每分析器，擴(kuò)充它的分析棧，使得每個(gè)文法符號(hào)都跟有語義值。同時(shí)擴(kuò)充個(gè)文法符號(hào)都跟有語義值。同時(shí)擴(kuò)充LRLR分析分析器功能，使它不僅執(zhí)行語法分析任務(wù)，且能器功能，使它不僅執(zhí)行語法分析任務(wù)，且能在用某個(gè)產(chǎn)生式進(jìn)行歸約的在用某個(gè)產(chǎn)

10、生式進(jìn)行歸約的同時(shí)同時(shí)調(diào)用相應(yīng)語調(diào)用相應(yīng)語義子程序。義子程序。 例例 算術(shù)表達(dá)式算術(shù)表達(dá)式求值求值的語義描述的語義描述 （0）LE print（E.val) （1）E E1 + T E.val:=E1.val+T.val（2）E T E.val:=T.val （3）T T1 * F T.val:=T1.val*F.val（4）T F T.val:=F.val （5）F（E） F.val:=E.val（6）Fdigit F.val:=digit.lexval 輸入串輸入串2+32+3* *5,5,語義處理是計(jì)算表達(dá)式的值，采用語義處理是計(jì)算表達(dá)式的值，采用LRLR分析法，分析法，LRLR分析表如

11、下：分析表如下： 狀狀態(tài)態(tài) ACITON ACITON（動(dòng)作）（動(dòng)作）GOTOGOTO（轉(zhuǎn)換）（轉(zhuǎn)換）d d+ +* *（）# #E ET TF F0 0S S5 S S4 1 12 23 31 1 S S6 accacc 2 2 r r2S S7 r r2r r2 3 3 r r4r r4 r r4r r4 4 4S S5 S S4 8 82 23 35 5 r r6r r6 r r6r r6 6 6S S5 S S4 9 93 37 7S S5 S S4 10108 8 S S6 S S11 9 9 r r1S S7 r r1r r1 1010 r r3r r3 r r3r r3 1111

12、 r r5r r5 r r5r r5 步驟步驟 狀態(tài)棧狀態(tài)棧 語義棧（值棧）語義棧（值棧） 符號(hào)棧符號(hào)棧 剩余輸入串剩余輸入串 歸約動(dòng)作歸約動(dòng)作1 0 - # 2+31 0 - # 2+3* *5# 5# 2 05 - - #2 +32 05 - - #2 +3* *5#5#3 03 -3 03 -2 2 #F +3 #F +3* *5# 5# r6r64 02 -4 02 -2 2 #T +3 #T +3* *5# 5# r4r45 01 -5 01 -2 2 #E +3 #E +3* *5# 5# r2r26 016 -2- #E+ 36 016 -2- #E+ 3* *5#5#7 016

13、5 -2- - #E+3 7 0165 -2- - #E+3 * *5#5# 步驟步驟 狀態(tài)棧狀態(tài)棧 語義棧（值棧）語義棧（值棧） 符號(hào)棧符號(hào)棧 剩余輸入串剩余輸入串 歸約動(dòng)作歸約動(dòng)作8 0163 -2-8 0163 -2-3 3 #E+F #E+F * *5# 5# r6r69 0169 -2-9 0169 -2-3 3 #E+T #E+T * *5# 5# r4r410 01697 -2-3- #E+T10 01697 -2-3- #E+T* * 5# 5#11 016975 -2-3- #E+T11 016975 -2-3- #E+T* *5 #5 #12 0169712 01697（1

14、010）-2-3-2-3-5 5 #E+T #E+T* *F # F # r6r613 0169 -2-13 0169 -2-（1515） #E+T # r3#E+T # r314 01 -14 01 -（1717） #E #E # r1r115 15 接受接受 8 83 3 中間代碼的形式中間代碼的形式 中間代碼有多種形式，常見的有中間代碼有多種形式，常見的有v 逆波蘭式逆波蘭式v 三元式三元式v 四元式四元式v 樹形表示樹形表示 一、一、 逆波蘭記號(hào)逆波蘭記號(hào) 最簡(jiǎn)單的一種中間代碼形式。最簡(jiǎn)單的一種中間代碼形式。將運(yùn)算對(duì)象寫在前面，運(yùn)算符號(hào)寫在后面將運(yùn)算對(duì)象寫在前面，運(yùn)算符號(hào)寫在后面如如a

15、+ba+b寫成寫成ab+ab+，也稱，也稱后綴式后綴式。后綴表示法表。后綴表示法表示表達(dá)式的最大優(yōu)點(diǎn)是計(jì)算機(jī)處理表達(dá)式方示表達(dá)式的最大優(yōu)點(diǎn)是計(jì)算機(jī)處理表達(dá)式方便。如便。如BCDBCD* *+ + （ 表示一元減，中綴表示為表示一元減，中綴表示為-B+C-B+C* *D D） 如如 GOTO L GOTO L 寫為寫為 L jumpL jumpif E then Sif E then S1 else elseS S2 表示為表示為 ESES1S S2 ，把，把if-then-elseif-then-else看成三目運(yùn)算符，用看成三目運(yùn)算符，用 表示。表示。但要注意，要對(duì)新添加的運(yùn)算符的含義正確處

16、但要注意，要對(duì)新添加的運(yùn)算符的含義正確處理。理。 組成組成：（OPOP，ARGARG1，ARGARG2）OPOP為算符，為算符，ARGARG1和和ARGARG2分別為第一、第二分別為第一、第二運(yùn)算對(duì)象。運(yùn)算對(duì)象。 （1 1） （* *，b b， c c） （2 2） （/ /，c c，d d）（3 3） （+ +，（1 1），（2 2）（4 4） （：（：= =，（3 3），a a） 三元式中的（三元式中的（1 1）、（）、（2 2）表示第一和第二個(gè)）表示第一和第二個(gè)三元式的結(jié)果。三元式的結(jié)果。 對(duì)一元運(yùn)算符，規(guī)定只用對(duì)一元運(yùn)算符，規(guī)定只用ARGARG1。 樹形表示是三元式的樹形表示是三元式的

17、翻版翻版。表達(dá)式的樹形。表達(dá)式的樹形表示很容易實(shí)現(xiàn)：簡(jiǎn)單變量或常數(shù)的樹是自表示很容易實(shí)現(xiàn)：簡(jiǎn)單變量或常數(shù)的樹是自身，如果表達(dá)式身，如果表達(dá)式e e1和和e e2的樹分別為的樹分別為T T1和和T T2，那，那么么e e1+e+e2、e e1* *e e2，-e-e1的樹為：的樹為： e1 + e2+T1T2*T1T2-T1e1 * e2 -e1二目運(yùn)算對(duì)應(yīng)二叉子樹，多目運(yùn)算對(duì)應(yīng)多叉子樹。二目運(yùn)算對(duì)應(yīng)二叉子樹，多目運(yùn)算對(duì)應(yīng)多叉子樹。 普遍采用的一種中間代碼形式。普遍采用的一種中間代碼形式。組成：組成：（OPOP，ARGARG1，ARGARG2，RESULTRESULT）其中其中: OP: OP，

18、ARGARG1，ARGARG2的含義同三元式的含義同三元式 RESULTRESULT是運(yùn)算結(jié)果。是運(yùn)算結(jié)果。 有時(shí)為了直觀，也把四元式的形式寫成簡(jiǎn)單有時(shí)為了直觀，也把四元式的形式寫成簡(jiǎn)單賦值形式賦值形式，例如把上述四元式寫成：，例如把上述四元式寫成： （1 1） t t1：=b=b* *c c（2 2） t t2：=c/d=c/d（3 3） t t3：=t=t1+t+t2（4 4） a a：=t=t3 如，如， a a：=b=b* *c+c/dc+c/d的四元式表示如下：的四元式表示如下： （1 1）（）（* *，b b，c c，t t1）（2 2）（）（/ /，c c，d d，t t2）（3

19、 3）（）（+ +，t t1，t t2，t t3）（4 4）（：）（：= =，t t3，- -，a a） 四元式和三元式的主要不同在于：四元式和三元式的主要不同在于：四元四元式對(duì)中間結(jié)果的引用必須通過給定的名字，式對(duì)中間結(jié)果的引用必須通過給定的名字，三元式是通過產(chǎn)生中間結(jié)果的三元式編號(hào)。三元式是通過產(chǎn)生中間結(jié)果的三元式編號(hào)。 四元式表示類似于三地址指令，有時(shí)也四元式表示類似于三地址指令，有時(shí)也把這種表示稱為三地址代碼，它對(duì)代碼優(yōu)化和把這種表示稱為三地址代碼，它對(duì)代碼優(yōu)化和目標(biāo)代碼生成都較有利。目標(biāo)代碼生成都較有利。 說明：說明： 在實(shí)際實(shí)現(xiàn)中，四元式的在實(shí)際實(shí)現(xiàn)中，四元式的ARGARG1和和A

20、RGARG2、RESULTRESULT，或者是一個(gè)指針，指向符號(hào)表，或者是一個(gè)指針，指向符號(hào)表的某一登錄項(xiàng)；或者是一個(gè)臨時(shí)變量的的某一登錄項(xiàng)；或者是一個(gè)臨時(shí)變量的整數(shù)碼。整數(shù)碼。 語義變量語義變量ididnamename：idid表示的單詞的一屬性表示的單詞的一屬性語義變量語義變量E Eplaceplace：表示存放：表示存放E E值的變量名在符值的變量名在符 號(hào)表的登錄項(xiàng)或一整數(shù)碼號(hào)表的登錄項(xiàng)或一整數(shù)碼語義過程語義過程emitemit：表示輸出四元式到輸出文件上：表示輸出四元式到輸出文件上語義過程語義過程newtempnewtemp：表示生成一臨時(shí)變量。：表示生成一臨時(shí)變量。函數(shù)函數(shù)Look

21、upLookup（ididnamename）：查：查ididnamename是否在符是否在符號(hào)表中，如在，則返回指向號(hào)表中，如在，則返回指向該登錄項(xiàng)指針，否則返回該登錄項(xiàng)指針，否則返回nilnil。 下面列出了下面列出了翻譯賦值語句到四元式翻譯賦值語句到四元式的語義的語義描述，這里的語義工作包括對(duì)變量進(jìn)行描述，這里的語義工作包括對(duì)變量進(jìn)行“先定先定義后使用義后使用”的檢查。的檢查。 （1 1） Sid ：= E p：= Lookup（idname）；）； if nilthenemit（p：Eplace） else error 四元式采用賦值形式，即四元式采用賦值形式，即result：=arg1

22、 op arg2（2） EE1 + E2 E.place := newtemp； emit（E.place := E1.place+E2.place） （3） EE1 * E2 E.place := newtemp； emit（E.place := E1.place*E2.place） （4） E - E1 E.place := newtemp； emit（E.place := uminus E1.place） （5） E（E1） E.place := E1.place （6） Eid p := Lookup（）；）； if p nilthenE.place := p else

23、error 編譯程序還可對(duì)表達(dá)式中的運(yùn)算對(duì)象進(jìn)編譯程序還可對(duì)表達(dá)式中的運(yùn)算對(duì)象進(jìn)行行類型檢查、類型轉(zhuǎn)換類型檢查、類型轉(zhuǎn)換。約定：約定：當(dāng)兩個(gè)不同類型的量進(jìn)行運(yùn)算時(shí)，先當(dāng)兩個(gè)不同類型的量進(jìn)行運(yùn)算時(shí)，先將整型量轉(zhuǎn)換為實(shí)型量，并增加將整型量轉(zhuǎn)換為實(shí)型量，并增加E.typeE.type表示表示E E的類型信息，值為的類型信息，值為intint或或realreal，用，用+ + i（* * i）、）、+ + r（* * r）區(qū)別整型加和實(shí)型加。）區(qū)別整型加和實(shí)型加。 帶類型轉(zhuǎn)換類型轉(zhuǎn)換的語義處理如下：（ EEEE1 * * E E2） EE1 * E2 E.place:=newtemp； if E1.t

24、ype=int AND E2.type=int then begin emit(E.place,:=,E1.place,*i,E2.place); E.type:=int end else if E1.type=real AND E2.type=real then begin emit(E.place,:=,E1.place,*r, E2.place); E.type:=real end else if E1type=int /* E2type=real*/ thenbegin t:=newtemp； emit（t,:=，itr，E1.place）；）； emit（E.place,:=，t,*

25、r , E2.place）；）； Etype:=realendelse /* E1.type=real AND E2.type=int */begin t:=newtemp； emit（t,:=，itr，E2.place） emit（E.place,:=，E1.place,*r ，t）；）； E.type:=real end； 語義值的設(shè)計(jì)是與語義處理的描述相關(guān)的語義值的設(shè)計(jì)是與語義處理的描述相關(guān)的，如非終結(jié)符如非終結(jié)符E，有語義值，有語義值Eplace、Etype或或Ekind（見（見PL/0編譯程序）編譯程序） 在程序設(shè)計(jì)語言中，在程序設(shè)計(jì)語言中，布爾表達(dá)式的作用有布爾表達(dá)式的作用有兩個(gè)：

26、兩個(gè)：一是用作邏輯賦值語句的邏輯運(yùn)算，二一是用作邏輯賦值語句的邏輯運(yùn)算，二是用作控制語句中的條件表達(dá)式是用作控制語句中的條件表達(dá)式。 布爾表達(dá)式的形式為：布爾表達(dá)式的形式為：E1 rop E2，E1和和E2是算是算術(shù)表達(dá)式，術(shù)表達(dá)式，rop是關(guān)系符是關(guān)系符=、=、=、。為簡(jiǎn)單起見，只考慮如下文法生成的布爾表。為簡(jiǎn)單起見，只考慮如下文法生成的布爾表達(dá)式：達(dá)式： EE and E |E or E | not E |id rop id |true |false布爾運(yùn)算符的優(yōu)先順序?yàn)椋翰紶栠\(yùn)算符的優(yōu)先順序?yàn)椋簄ot、and、or，并且，并且and和和or服從左結(jié)合。服從左結(jié)合。 一、一、 布爾表達(dá)式的

27、翻譯方法布爾表達(dá)式的翻譯方法 計(jì)算布爾表達(dá)式的值有兩種辦法：計(jì)算布爾表達(dá)式的值有兩種辦法： 第一種第一種：同算術(shù)表達(dá)式的計(jì)算一樣，按步計(jì)算：同算術(shù)表達(dá)式的計(jì)算一樣，按步計(jì)算各部分的真假值，最后計(jì)算整個(gè)表達(dá)式各部分的真假值，最后計(jì)算整個(gè)表達(dá)式的值。的值。例如：例如： 1 or（not 0 and 0）or 0 = 1 or（1 and 0） or 0 = 1 or 0 or 0 = 1 or 0 = 1 采取哪種方法取決于程序設(shè)計(jì)語言的語義。采取哪種方法取決于程序設(shè)計(jì)語言的語義。 第二種第二種：采取某種采取某種措施，只計(jì)算部分表達(dá)措施，只計(jì)算部分表達(dá)式，如式，如 A or BA or B，若，若

28、A A的值為的值為1 1，則無需計(jì)算，則無需計(jì)算B B，整個(gè)布爾表達(dá)式的值為整個(gè)布爾表達(dá)式的值為1 1。同理，對(duì)于。同理，對(duì)于A and BA and B，若若A A為為0 0，則整個(gè)布爾表達(dá)式值為，則整個(gè)布爾表達(dá)式值為0 0，無需計(jì)算，無需計(jì)算B B。 若按第一種方法計(jì)算布爾表達(dá)式，若按第一種方法計(jì)算布爾表達(dá)式， a or b and not c a or b and not c 翻譯成四元式為：翻譯成四元式為： （1） t1：= not c（2） t2：= b and t1（3） t3：= a or t2 對(duì)于對(duì)于a a b b這樣的關(guān)系表達(dá)式，可看成等價(jià)的條這樣的關(guān)系表達(dá)式，可看成等價(jià)的

29、條件語句件語句: : if aif a b then 1 else 0 b then 1 else 0，翻譯成的，翻譯成的四元式序列為：四元式序列為： （1） if a b goto （4）（2） t：= 0（3） goto （5）（4） t：= 1（5） 用t t存放a a b b的值，（5）為后繼的四元式序號(hào)。 p182 p182 圖圖8.14 8.14 給出了按給出了按第一種第一種辦法計(jì)算布爾表達(dá)辦法計(jì)算布爾表達(dá)式的值。其中：式的值。其中： nextstatnextstat：給出輸出序列中下一四元式序號(hào)；給出輸出序列中下一四元式序號(hào)； emitemit：輸出四元式，每調(diào)用一次，輸出四元式

30、，每調(diào)用一次，nextstat nextstat 增加增加1 1。 E E1 or E2 E.place:= newtemp； emit（E.place:=E1.place or E2.place）E E1 and E2 E.place:= newtemp； emit（E.place := E1.placeandE2.place）E not E1 E.place:= newtemp； emit（E.place:=notE1.place）E（E1 ） E.place:= E1.place Eid1 relop id2 E.place := newtemp； emit（if id1.place r

31、elop id2.place goto nextstat+3）；）； emit（E.place := 0）；）； emit（goto nextstat+2）；）； emit（E.place := 1）；）；E true E.place:= newtemp； emit（E.place := 1）E false E.place:= newtemp； emit（E.place := 0）二、二、 控制語句中布爾表達(dá)式的翻譯控制語句中布爾表達(dá)式的翻譯 討論出現(xiàn)在討論出現(xiàn)在if - then；if then - else和和while - do等語句中的布爾表達(dá)式等語句中的布爾表達(dá)式E的翻譯語法：的翻譯

32、語法： S if E then S1 | if E then S1 else S2 | while E do S1 begin：out：假假假假假假真真真真真真E的代碼的代碼E的代碼的代碼E的代碼的代碼S1 的代碼的代碼S1 的代碼的代碼S1 的代碼的代碼S2 的代碼的代碼jump outjump beginif E then S1if E then S1 else S2while E do S1 作為條件轉(zhuǎn)移的作為條件轉(zhuǎn)移的E，僅把僅把E翻譯成條件轉(zhuǎn)移和翻譯成條件轉(zhuǎn)移和無條件轉(zhuǎn)移的四元式。無條件轉(zhuǎn)移的四元式。翻譯的翻譯的基本思路基本思路是：是： 對(duì)于對(duì)于E為為a rop b的形式，生成代碼為

33、：的形式，生成代碼為： if a rop b goto E.true 和和 goto E.false 對(duì)于對(duì)于E E為為E E1 or E or E2 的形式，的形式，u若若E E1 1為真，則為真，則E E為真，即為真，即E E1 1的真出口和的真出口和E E的的真出口一樣。真出口一樣。u若若E E1 1為假則需計(jì)算為假則需計(jì)算E E2 2，E E1 1的假出口應(yīng)是的假出口應(yīng)是E E2 2代碼的第一個(gè)四元式標(biāo)號(hào)，代碼的第一個(gè)四元式標(biāo)號(hào)，E E2 2的真出口和的真出口和假出口分別與假出口分別與E E的真出口和假出口一樣。的真出口和假出口一樣。 E E為為E E1 1 and E and E2

34、2 的形式，與的形式，與2) 2)類似，只需調(diào)換類似，只需調(diào)換E E1 1的真假出口即可的真假出口即可 對(duì)于對(duì)于not Enot E1 1的翻譯，的翻譯，E E的真假出口是的真假出口是E E1 1的假的假真出口。真出口。 例例8.3 布爾表達(dá)式布爾表達(dá)式a b or c d and e f 翻譯成如下四元式序列：翻譯成如下四元式序列： （1） if ab goto E.ture（2） goto 3（3） if cd goto 5（4） goto E.false（5） if e f goto E.true（6） goto E.false 上述四元式（上述四元式（2 2）是不需要的，這種問題可在代

35、）是不需要的，這種問題可在代碼優(yōu)化階段解決。碼優(yōu)化階段解決。 不是最優(yōu)語句語句if ab or cd and ef then S1 else S2的四元式的四元式(1) if ab goto (7) /轉(zhuǎn)移至轉(zhuǎn)移至(E.true ) (2) goto (3) (3) if cd goto (5)(4) goto (p+1)/轉(zhuǎn)移至轉(zhuǎn)移至(E.false)(5) if ef goto (7)(6) goto (p+1)(7) ( S1的四元式的四元式 (p-1) ）(p) goto (q)(p+1) (S2的四元式的四元式(q-1) ）(q)/轉(zhuǎn)移至轉(zhuǎn)移至(E.true ) /轉(zhuǎn)移至轉(zhuǎn)移至(E.

36、false)/(E.false)入口入口/ (E.true ) 入口入口 E.true E.true和和E.falseE.false的值不能在產(chǎn)生四元式的同時(shí)的值不能在產(chǎn)生四元式的同時(shí)就知道，要在整個(gè)布爾表達(dá)式（或語句）的四就知道，要在整個(gè)布爾表達(dá)式（或語句）的四元式產(chǎn)生完畢之后才得知，因此要元式產(chǎn)生完畢之后才得知，因此要回填回填這個(gè)地這個(gè)地址。址。 為了記錄需回填地址的四元式，常采用一種為了記錄需回填地址的四元式，常采用一種拉鏈的辦法拉鏈的辦法：把需回填：把需回填E.trueE.true的四元式拉成一鏈，的四元式拉成一鏈，稱為稱為“真真”鏈鏈，把需回填，把需回填E.falseE.false的

37、四元式拉成的四元式拉成一鏈，稱為一鏈，稱為“假假”鏈鏈。若有四元式序列：若有四元式序列： （10） goto E.true （20） goto E.true（30） goto E.true（10） goto （0） （20） goto （10）（30） goto （20）其中鏈?zhǔn)诪椋ㄆ渲墟準(zhǔn)诪椋?030），鏈尾為（），鏈尾為（1010），），0 0為鏈尾標(biāo)志。為鏈尾標(biāo)志。則鏈成則鏈成: :使用：使用：E.true 和和 E.false：分別表示：分別表示“真真”鏈和鏈和“假假”鏈鏈nextstat：下一四元式地址：下一四元式地址emit：輸出四元式：輸出四元式merge（p1,p2）：合并：合

38、并p1、p2兩條鏈，即將兩條鏈，即將p2的的鏈尾鏈接到鏈尾鏈接到p1鏈?zhǔn)?，合并后鏈?zhǔn)?，合并后p2為鏈?zhǔn)住殒準(zhǔn)?。例：例?merge(p1, p2)(p10) goto ( 0) p1 鏈鏈 (p100) goto (p10)(p1) goto (p100)(p20) goto( 0) (p1) p2 鏈鏈 (p200) goto (p20)(p2) goto (p200)backpatch（p，t）：把：把p所鏈接的所鏈接的每個(gè)每個(gè)四元式的四元式的第四區(qū)段都填為第四區(qū)段都填為tE.codebegin：E的第一個(gè)四元式序號(hào)（語義值）的第一個(gè)四元式序號(hào)（語義值） 自下而上的分析中布爾表達(dá)式的一種

39、翻譯方案，自下而上的分析中布爾表達(dá)式的一種翻譯方案，如如p167p167圖圖8.138.13所示所示 （1）E E1 or E2 backpatch( E1.false, E2.codebegin); E.codebegin := E1.codebegin; E.true := merge（E1.true, E2.true）; E.false := E2.false； （2）E E1 and E2 backpatch( E1.true, E2.codebegin); E.codebegin := E1.codebegin; E.true := E2.true; E.false :=merge（

40、E1.false, E2.false）；）； （3）E not E1 E.true := E1.false; E.codebegin := E1.codebegin; E.false := E1.true; （4）E ( E1) E.true := E1.true; E.codebegin := E1.codebegin; E.false := E1.false; （5）Eid1 relop id2 E.true :=nextstat; E.codebegin := nextstat; E.false :=nextstat+1; emit(if id1.place rop id2.place

41、goto_ ); emit(goto _ ) ； （6）E true E.true :=nextstat; E.codebegin := nextstat; emit(goto _ ) ； （7）E false E.false :=nextstat; E.codebegin := nextstat; emit(goto _ )； 以以a b or c d and e f 為例，將分析產(chǎn)生語為例，將分析產(chǎn)生語法樹時(shí)的語義動(dòng)作結(jié)果法樹時(shí)的語義動(dòng)作結(jié)果“真真”“”“假假”鏈情況注釋鏈情況注釋在相應(yīng)結(jié)點(diǎn)處在相應(yīng)結(jié)點(diǎn)處 anda borE E.true=104，100 E.false=105，103E1

42、 E.true=100 E.false=101E4 E.true=104 E.false=105，103E2 E.true=102 E.false=103E3 E.true=104 E.false=105c d e f 1） 歸約a b到E1時(shí)，產(chǎn)生兩個(gè)四元式： 100：if a b goto 101：goto （假定（假定nextstat初值為初值為100） E1.true和E1.false分別為100、101， E1.codebegin=100； 2 2） 歸約歸約c d到到E2時(shí)，產(chǎn)生兩個(gè)四元式：時(shí)，產(chǎn)生兩個(gè)四元式： 102：if c d goto 103 103：goto goto E E2.true.true和和E E2.false.false分別為分別為102102、103103， E E2.codebegin=102.codebegin=102； 3 3） 歸約歸約e f 到