【正文】 GEN (itr, E(1)PLACE,,U)。 GEN (opr,U,E(2)PLACE,T)。 EMODE:=r END ELSE / * E(1) MODE=r and E(2)MODE=int * / BEGIN U:=NEWTEMP。 GEN (itr, E(2) PLACE,,U)。 GEN (opr,E(1) PLACE,U,T)。 EMODE:=r END。 EPLACE:=T。 這樣 , X*2+A*(I+1) 其中 I為整型量 ， X、 A為實(shí)型量 , (itr,2,,T1) (*r,X,T１ ,T２ ) (+i,I,1,T3) (itr,T3,,T４ ) (*r,A,T4,T5) (+r,T2,T5,T6) 第五章 語(yǔ)法制導(dǎo)翻譯及中間代碼生成 167。 自底向上語(yǔ)法制導(dǎo)翻譯 一、簡(jiǎn)單算術(shù)表達(dá)式和賦 值語(yǔ)句的翻譯 1. 翻譯成四元式 2. 類型檢查與類型轉(zhuǎn)換 二、布爾表達(dá)式的翻譯 1. 概述 三、控制語(yǔ)句翻譯 goto語(yǔ)句的翻譯 翻譯 四、數(shù)組元素的翻譯 1. 下標(biāo)變量地址的計(jì)算 五、過(guò)程語(yǔ)句的翻譯 六、說(shuō)明語(yǔ)句的翻譯 第五章 語(yǔ)法制導(dǎo)翻譯及中間代碼生成 167。 自底向上語(yǔ)法制導(dǎo)翻譯 一、簡(jiǎn)單算術(shù)表達(dá)式和賦 值語(yǔ)句的翻譯 1. 翻譯成四元式 2. 類型檢查與類型轉(zhuǎn)換 二、布爾表達(dá)式的翻譯 1. 概述 三、控制語(yǔ)句翻譯 goto語(yǔ)句的翻譯 翻譯 四、數(shù)組元素的翻譯 1. 下標(biāo)變量地址的計(jì)算 五、過(guò)程語(yǔ)句的翻譯 六、說(shuō)明語(yǔ)句的翻譯 167。 自底向上語(yǔ)法制導(dǎo)翻譯 二、布爾表達(dá)式的翻譯 1. 概述 布爾表達(dá)式由布爾運(yùn)算符 ∧ (與 )、 ∨ (或 )和 ?(非 )等作用于布爾量或 關(guān)系表達(dá)式構(gòu)成 ,關(guān)系表達(dá)式的形式是 E1 rop E2,其中 rop是關(guān)系運(yùn)算符 (如 、 =、 =、 、 =及 )。 而 E1和 E2是算術(shù)表達(dá)式 。 (1)布爾表達(dá)式的 用途 在程序設(shè)計(jì)語(yǔ)言中 ， 布爾表達(dá)式有兩個(gè)基本 用途 : 1） 一個(gè)是求邏輯值 ， 邏輯值的結(jié)果是真或假 。 2） 另一個(gè)用得最多的是在控制語(yǔ)句中用作條件表達(dá)式 ， 例如 ， 在 ifthen、 ifthenelse和 whiledo語(yǔ)句里表示控制條件 。 (2)布爾表達(dá)式的文法 布爾表達(dá)式文法 G［ E］如下 : E∷ =E∧ E|E∨ E| ? E|(E)|i|i rop i 說(shuō)明： 1） 布爾表達(dá)式的文法是一個(gè)二義文法 例如：該文法的一個(gè)句子 a ∧ b ∨ c有兩棵不同的語(yǔ)法樹(shù)與之對(duì)應(yīng)，所以該文法是一個(gè)二義文法。 E E E ∨ E E ∧ a b c E E E ∧ a E E ∨ b c 2） 規(guī)定布爾運(yùn)算符的優(yōu)先順序是 : ? 、 ∧ 、 ∨ 。并假定 ∧ 和 ∨ 為左結(jié)合。 所有關(guān)系運(yùn)算符優(yōu)先級(jí)相同 ,且高于任何布爾運(yùn)算符 ,低于算術(shù)運(yùn)算符。 3） i可認(rèn)為是布爾表達(dá)式也可視為數(shù)值（ 1為真 true,0為假 false)。 4） i rop i 中 rop是 關(guān)系運(yùn)算符， i是布爾變量或算術(shù)值 (3)布爾表達(dá)式求值 方法 1） 把真和假數(shù)值化，使布爾表達(dá)式計(jì)算類似于算術(shù)表達(dá)式的計(jì)算， 常用 1表示真， 0表示假，或者用非零整數(shù)表示真 。 如： 1∨ （ ? 0∧ 0） ∨ 0= 1∨ （ 1∧ 0） ∨ 0= 1∨ 0∨ 0=1 2） 采取某種優(yōu)化措施，有時(shí)并不需要將一個(gè)布爾表達(dá)式從頭算到尾， 而只須計(jì)算它的一個(gè)子表達(dá)式， 便能確定整個(gè)布爾表達(dá)式真和假。 例如，對(duì)于 A∨ B，只要計(jì)算出 A為真，則不管 B值如何， A∨ B之值 一定為真。又如對(duì) A∧ B，只要計(jì)算出 A為假，則 A∧ B必然為假，等等。 對(duì)于三種邏輯運(yùn)算 ， A∨ B: if A then true else B A∧ B: if A then B else false ? A: if A then false else true 用這種方式實(shí)現(xiàn)控制語(yǔ)句的布爾表達(dá)式尤其方便 。 對(duì)應(yīng)上述兩種 計(jì)算方法 ， 其布爾表達(dá)式有兩種不同的翻譯方法 。 第五章 語(yǔ)法制導(dǎo)翻譯及中間代碼生成 167。 自底向上語(yǔ)法制導(dǎo)翻譯 一、簡(jiǎn)單算術(shù)表達(dá)式和賦 值語(yǔ)句的翻譯 1. 翻譯成四元式 2. 類型檢查與類型轉(zhuǎn)換 二、布爾表達(dá)式的翻譯 1. 概述 三、控制語(yǔ)句翻譯 goto語(yǔ)句的翻譯 翻譯 四、數(shù)組元素的翻譯 1. 下標(biāo)變量地址的計(jì)算 五、過(guò)程語(yǔ)句的翻譯 六、說(shuō)明語(yǔ)句的翻譯 167。 自底向上語(yǔ)法制導(dǎo)翻譯 二、布爾表達(dá)式的翻譯 （ 1） 如同翻譯算術(shù)表達(dá)式一樣，用于求值 例如， 布爾表達(dá)式 ? a∧ (b∨ c=d)將被翻譯成如下四元式： 1) (? ,a,,T1) 2) (=,c,d,T2) 3) (∨ ,b,T2,T3) 4) (∧ ,T1,T3,T4) 仿照翻譯算術(shù)表達(dá)式的方法，很容易寫出布爾表達(dá)式文法 G［ E］的 每個(gè)規(guī)則 用于求值的 語(yǔ)義動(dòng)作 。 (1) E∷ = E(1) ∧ E(2) {EPLACE:=NEWTEMP。 GEN(∧ ,E(1) PLACE, E(2)。 PLACE ,EPLACE)} (2) E∷ = E(1) ∨ E(2) {EPLACE:=NEWTEMP。 GEN(∨ ,E(1) PLACE, E(2).PLACE ,EPLACE)} (3) E∷ = ? E(1) {EPLACE:=NEWTEMP； GEN（ ? ， E(1)PLACE, ,EPLACE)} (4) E∷ =（ E(1) ） {EPLACE:= E(1) PLACE } (5) E∷ =i {EPLACE:=ENTRY（ i） } (6) E∷ =i rop i {EPLACE:=NEWTEMP。 GEN(rop,ENTRY(i(1)),ENTRY(i(2)),)}} (2)作為條件控制的布爾表達(dá)式的翻譯 1)布爾表達(dá)式 E作為條件控制的代碼結(jié)構(gòu) 對(duì)于條件語(yǔ)句 if E then S1 else S2 中布爾表達(dá)式 E，它的作用就是控制 S1和 S2的選擇， 我們賦于 E代碼 兩種出口，其一為“真出口”，另一個(gè)是“假出口”，它們分別指出 當(dāng) E值為 true和 false時(shí)，控制轉(zhuǎn)向的目標(biāo) (即某一四元式所在位置或 序號(hào) )。條件語(yǔ)句可翻譯成如 下圖： E的代碼 S1的代碼 true false S2的代碼 2)三種形式的四元式 作為條件控制的布爾表達(dá)式 E的翻譯歸納起來(lái)只有三種形式的四元式 (jnz, a1, ,p) 若 a1為真時(shí) ,則轉(zhuǎn)向第 p個(gè)四元式。 (jrop,a1,a2, p) 若關(guān)系 a1 rop a2成立時(shí) ,轉(zhuǎn)向第 p個(gè)四元式。 (j, , ,p) 無(wú)條件轉(zhuǎn)向第 p個(gè)四元式 。 除上述兩種真轉(zhuǎn)外 ， 可用無(wú)條件表示假轉(zhuǎn) 例如 , if a∨ b c then S1 else S2 經(jīng)翻譯后 ， 可得如下四元式序列： (1) (jnz,a, ,5) (2) (j, , ,3) (3) (j,b,c,5) (4) (j, , ,p+1) (5) (關(guān)于 S1的四元式序列 ) (P) (j, , ,q) (p+1) (關(guān)于 S2的四元式序列 ) (q) （ 1） a為真， a∨ bc就為真，轉(zhuǎn) 5執(zhí)行 （ 2） a為假， a∨ bc的值取決于 bc的值，所以轉(zhuǎn) 3執(zhí)行 （ 3） a為假，且 bc，則 a∨ bc為真，轉(zhuǎn) 5執(zhí)行 （ 4） a為假，且 bc也是假，則 a∨ bc為假，執(zhí)行 S2語(yǔ)句，即應(yīng)轉(zhuǎn) p+1執(zhí)行 （ p）執(zhí)行完 S1（對(duì)應(yīng)四元式為（ 5））則應(yīng)轉(zhuǎn)到條件語(yǔ)句的下一條語(yǔ)句執(zhí)行，所以無(wú)條件跳轉(zhuǎn)到（ q）執(zhí)行。 四元式 (1)～ (4)中顯然含有多余的四元式，如 (2)顯然是不需要 。 第五章 語(yǔ)法制導(dǎo)翻譯及中間代碼生成 167。 自底向上語(yǔ)法制導(dǎo)翻譯 一、簡(jiǎn)單算術(shù)表達(dá)式和賦 值語(yǔ)句的翻譯 1. 翻譯成四元式 2. 類型檢查與類型轉(zhuǎn)換 二、布爾表達(dá)式的翻譯 1. 概述 三、控制語(yǔ)句翻譯 goto語(yǔ)句的翻譯 翻譯 四、數(shù)組元素的翻譯 1. 下標(biāo)變量地址的計(jì)算 五、過(guò)程語(yǔ)句的翻譯 六、說(shuō)明語(yǔ)句的翻譯 167。 自底向上語(yǔ)法制導(dǎo)翻譯 二、布爾表達(dá)式的翻譯 （ 1） 回填 在自底向上的語(yǔ)法制導(dǎo)翻譯過(guò)程中 ， 在產(chǎn)生一個(gè)條件或無(wú)條件轉(zhuǎn)移 四元式時(shí) ， 它所要轉(zhuǎn)移到的那個(gè)四元式尚未產(chǎn)生 ， 故無(wú)法立即產(chǎn)生一 個(gè)完全控制轉(zhuǎn)移四元式 。 例如 ， 對(duì)于上例 ， 在產(chǎn)生第一個(gè)四元式時(shí) ， 因?yàn)檎Z(yǔ)句 S1的中間代碼尚未產(chǎn)生 ， 故此時(shí)只得產(chǎn)生一個(gè)空缺轉(zhuǎn)移目標(biāo) 的四元式 (jnz,a, ,0)， 且將此四元式的序號(hào)作為語(yǔ)義信息存起來(lái) ， 待開(kāi)始翻譯語(yǔ)句 S1時(shí) ， 再將 S1的第一個(gè)四元式序號(hào) (即 5)填入這個(gè)不 完全條件轉(zhuǎn)移四 元式中 。 我們把這種事后再填轉(zhuǎn)移目標(biāo)叫做回填 。 （ 2） 真鏈 T和假鏈 F 在翻譯過(guò)程中 ， 有時(shí)會(huì)存在著若干個(gè)轉(zhuǎn)移四元式 ,如例中的 1和 3兩個(gè)四元式 ， 它們有同一個(gè)轉(zhuǎn)移目標(biāo) 5，但此目標(biāo)的具體位置在形成四元式時(shí)還不知道 ， 此時(shí) ， 我們將這些四元式鏈接起來(lái) ， 并且用一個(gè)指示器指示這條鏈的鏈頭 ， 以后 ， 便可以從鏈頭開(kāi)始 ，沿著這條鏈逐個(gè)為其中各四元式填入轉(zhuǎn)移目標(biāo) 。 (1) (jnz,a, ,5) (2) (j, , ,3) (3) (j,b,c,5) (4) (j, , ,p+1) (5) (關(guān)于 S1的四元 式序列 ) (P) (j, , ,q) (p+1) (關(guān)于 S2的四 元式序列 ) (q) 167。 自底向上語(yǔ)法制導(dǎo)翻譯 二、布爾表達(dá)式的翻譯 在實(shí)際操作時(shí)， 1） 將要填真出口的各四元式鏈接起來(lái)，組成一個(gè)鏈稱 真鏈 T ，記為 TC 2） 將要填假出口的各四元式鏈接起來(lái)，組成一個(gè)鏈稱 假鏈 F ，記為 FC 首先定義兩個(gè)語(yǔ)義變量 T鏈和 F鏈的鏈頭。 如下圖： 鏈中各個(gè)四元式 RESULT字段為相應(yīng)結(jié)點(diǎn)指針字段，當(dāng)其不為零時(shí)，它是 鏈中后繼四元式的序號(hào)如（ 2）中的 3，否則，相應(yīng)四元式是鏈尾結(jié)點(diǎn)，如（ 1）中的 0 (1) (jnz, a, , 0) (2) (j , , ,3) ETC → (3) (j, b, c, 1) EFC → (4) (j , , ,0) (5) (3)改寫布爾表達(dá)式文法 G[E] 為了使用語(yǔ)法制導(dǎo)翻譯做回填工作，便于編制相應(yīng)的語(yǔ)義子程序， 我們對(duì)上面布爾表達(dá)式文法 G［ E］改寫為 E∷ =E∧ E|E∨ Ｅ | ? E|(E)|i|i rop i E∧ ∷ =E∧ E∨ ∷ =E∨ 這樣，當(dāng)掃描到 E∧ 和 E∨ 并歸約到 E∧ 和 E∨ 時(shí) 就可以及時(shí)回填 ,知道真假出口，如果不是這樣改寫，當(dāng)掃描到 E∧ 和 E∨ 時(shí)，還不能歸約，因此就不能及時(shí)回填。 （ 4） 文法 G[E]各規(guī)則語(yǔ)義子程序 1