【文章內(nèi)容簡介】 . 下面將上述語義動作具體化成語義子程序 : ? 自底向上分析要?dú)w約時先調(diào)用相應(yīng)子程序生成后綴式 ? 假定后綴式存放在數(shù)組 POST中 假設(shè)要?dú)w約的句柄為 E(1)+T(在語法分析棧中 )， 則首先要求調(diào)用相應(yīng)于 E(1)+T的語義子程序 ， 此時 E(1)和 T已調(diào)用過相應(yīng)的語義子程序 ， 因此 ， 它們的后綴式已被生成 ， 對應(yīng)于 E(1)+T的語義子程序所要完成的工作是把已生成的兩后綴式捻接起來 ， 然后再 添上符號 “ +”。 如果我們設(shè)置一個數(shù)組存放后綴式 ， 那么語義動作就可以不涉及 捻接運(yùn)算 。 令這個數(shù)組為 POST， p為下標(biāo) ， 初值為 1。 如下圖： … E(1).CODE + POST(P) 對于上述文法 G［ E］ 的語義動作 ， 可以改寫為如下相應(yīng)的 語義子程序： (1) E∷ =E(1)+T {POST[p]:=?+?。p:=p+1} (2) E∷ =T { } (3) T∷ =T(1)*F {POST[p]:=?*?。p:=p+1} (4) T∷ =F { } (5) F∷ =(E) { } (6) F∷ =i {POST[p]:=i。p:=p+1} 最后，我們以表達(dá)式 a+b*c為例按照 G［ E］ LR分析表 給出語法制導(dǎo)翻譯產(chǎn)生后綴式過程， 其中 SUBK表示第 K個規(guī)則相對應(yīng)的語義子程序。分析過程如下表： 步驟 狀態(tài)棧 符號棧 輸入串 歸約規(guī)則 調(diào)用子程序 后綴式 1 0 ＃ a+b*c 2 05 ＃ a +b*c F::=i SUB6 a 3 03 ＃ F +b*c T::=F SUB4 a 4 02 ＃ T +b*c E(1)::=T SUB2 a 5 01 ＃ E(1) +b*c a 6 016 ＃ E(1)+ b*c a 7 0165 ＃ E(1)+b *c F::=i SUB6 ab 8 0163 ＃ E(1)+F *c T(1)::=F SUB4 ab 9 0169 ＃ E(1)+T(1) *c ab 10 01697 ＃ E(1)+T(1) * c ab 11 016975 ＃ E(1)+T* c F::=i SUB6 abc 12 016970 ＃ E(1)+T(1) * F T::=T(1) *F SUB3 abc* 13 0169 ＃ E(1)+T E::=E(1) +T SUB1 abc*+ 14 01 ＃ E abc*+ 第五章 語法制導(dǎo)翻譯及中間代碼生成 167。 中間語言 一、引言 二、逆波蘭表示 三、三元式 四、樹形表示 1. 表示方法 2. 樹表示生成 五、四元式 第五章 語法制導(dǎo)翻譯及中間代碼生成 167。 中間語言 一、引言 二、逆波蘭表示 三、三元式 四、樹形表示 1. 表示方法 2. 樹表示生成 五、四元式 167。 中間語言 三、三元式表示 (1) 定義 三元式的一般形式為 (i) (OP, ARG1, ARG2) 其中 ： (i)為三元式的編號 ， 不同三元式不能有相同的編號 OP是運(yùn)算符部分 ARG1和 ARG2是運(yùn)算對象部分 ， 它們或者指向符號表登記項指示 器 (對于運(yùn)算對象是常數(shù)或標(biāo)識符的情況 )， 或者是一個指向三元式 序列 (或三元式表 )中某一個三元式位置的指示器 (對于運(yùn)算對象是中 間結(jié)果的情況 )。 如： A+B*C對應(yīng)的三元式表示為： (1) (*， B， C) (2) (+， A， (1)) 注：運(yùn)算符 OP通常用一個整數(shù)碼表示，它除了標(biāo)識運(yùn)算符的種屬 之外，還附帶地表示其它一些語義特性。例如若 OP表示一個加法 運(yùn)算符，則相應(yīng)的整數(shù)碼除了標(biāo)識加法運(yùn)算本身外，還兼有表示 數(shù)據(jù)類型 (如整型、實型等 )、運(yùn)算方式 (定點(diǎn)、浮點(diǎn) )和運(yùn)算精度等 信息，且不同語義屬性使用不同的運(yùn)算符代碼。 對于一目運(yùn)算符 OP， ARG1和 ARG2只需其一。我們可以隨意規(guī)定選用一個，例如，規(guī)定用 ARG1。至于多目運(yùn)算符可以用若干個相繼三元式表示。 如： 賦值語句 x:=b*(c+d) 用三元式來表示，則可寫成 (1) ( ,b, ) (2) (+, c, d) (3)(*,(1),(2)) (4)(:=,x,(3)) 其中，三元式 (3)就引用三元式 (1)和 (2)的結(jié)果作為它的兩個運(yùn)算對象 三元式出現(xiàn)先后順序和表達(dá)式各部分計算順序相一致！ (2) 三元式的生成 同樣可以用語法制導(dǎo)翻譯來產(chǎn)生三元式： 下面給出文法 G［ E］ 的語義動作來描述這種翻譯的算法： (1)E∷ =E(1)+T {EVAL:=TRIP(+,E(1)VAL,TVAL)} (2)E∷ =T {EVAL:=TVAL} (3)T∷ =T(1)*F {TVAL:=TRIP(*,T(1)VAL,FVAL)} (4)T∷ =F {TVAL:=FVAL} (5)F∷ =(E) {FVAL:=EVAL} (6)F∷ =i {FVAL:=ENTRY(i)} 其中語義值 EVAL、 TVAL和 FVAL， 是一個指示器 ， 或指向有關(guān)符號 表某一項 ， 或指向三元式表自身某一項 ， TRIP(OP， ARG1， ARG2)是 一個語義子程序 ， 回送新產(chǎn)生的三元式存放在三元式表位置 。 ENTRY(i)是一個語義子程序 ， 通過 ENTRY查 i在符號表中位置 ， 即 對應(yīng)地址 ， 若查不到 ， 認(rèn)為有錯誤 。 第五章 語法制導(dǎo)翻譯及中間代碼生成 167。 中間語言 一、引言 二、逆波蘭表示 三、三元式 四、樹形表示 1. 表示方法 2. 樹表示生成 五、四元式 167。 中間語言 三、三元式表示 2. 間接三元式 為了便于代碼優(yōu)化，常常采用間接三元式。這由兩張表組成： （ 1） 三元式表 ， 用來存放各三元式本身； （ 2） 執(zhí)行表 (間接碼表 )， 它按執(zhí)行三元式順序 ， 依次列出相應(yīng)各 三元式在三元式表中位置 。 x:=a*b+c+a*b (1) (*,a,b) (2) (+,(1),c) (3) (*,a,b) (4) (+,(2),(3)) (5) (:=,x,(4)) 其中，三元式 (1)和 (3)完全一樣， 但是不能將 (3)省去。 執(zhí)行表 (1) (1) (*,a,b) (2) (2) (+,(1),c) (1) (3) (+,(2),(1)) (3) (4) (:=,x,(3)) (4) 間接三元式的優(yōu)點(diǎn)： （ 1）便于代碼優(yōu)化 在進(jìn)行代碼優(yōu)化時 ， 常常要從中間代碼刪去一些運(yùn)算 ， 或者 把某些運(yùn)算移到另外位置上 ， 若采用一般三元式 ， 則由于三元式 之間引用太多 ， 很難做到這一點(diǎn) 。 （ 2） 節(jié)省空間 由于在間接三元式執(zhí)行表中已經(jīng)依次列出每次要執(zhí)行的那個 三元式 ， 所以 ， 若有若干個相同三元式 ， 則僅須在三元式表中 保存其中之一 。 如上面賦值語句右部表達(dá)式中有兩個 a*b子表達(dá)式 ， 而三元式表中只出現(xiàn)一次 (*, a, b) 。 對于間接三元式表示，語義子程序應(yīng)增添產(chǎn)生執(zhí)行表的動作。 在填寫三元式表時，應(yīng)首先看 一下此三元式是否在其中， 如已在其中，則無需填入。 第五章 語法制導(dǎo)翻譯及中間代碼生成 167。 中間語言 一、引言 二、逆波蘭表示 三、三元式 四、樹形表示 1. 表示方法 2. 樹表示生成 五、四元式 第五章 語法制導(dǎo)翻譯及中間代碼生成 167。 中間語言 一、引言 二、逆波蘭表示 三、三元式 四、樹形表示 1. 表示方法 2. 樹表示生成 五、四元式 167。 中間語言 四、樹形表示 1. 表示方法 我們可以用樹形數(shù)據(jù)結(jié)構(gòu)來表示一個表達(dá)式或語句 。 在樹表示中 ， 葉子結(jié)點(diǎn)表示運(yùn)算對象 ， 即常量或變量 ， 其它結(jié)點(diǎn) 表示運(yùn)算符 ， a+b, ab, a 的樹表示分別定義為： + a b － a b － a 雙目運(yùn)算對應(yīng)二叉樹，多目運(yùn)算對應(yīng)多叉樹，單目運(yùn)算對應(yīng)單叉樹 。 如表達(dá)式 a*b(c+d)/(ef) 的二叉樹如下圖： 后序遍歷上述二叉樹便得到該表達(dá)式的逆波蘭表示為 ab*cd+ef/ － * / a b + － c d e f 表達(dá)式的三元式可以看作是樹的直接表示 ， 圖 (1) (*,a,b) (2) (+,c,d) (3) (,e,f) (4) (/,(2),(3)) (5) (,(1),(4)) 顯然 ， 每一個三元式對應(yīng)一棵子樹 ， 子樹的根便是三元式的運(yùn)算符 ， 三元式的運(yùn)算對象是子樹兩個分枝 。 第五章 語法制導(dǎo)翻譯及中間代碼生成 167。 中間語言 一、引言 二、逆波蘭表示 三、三元式 四、樹形表示 1. 表示方法 2. 樹表示生成 五、四元式 167。 中間語言 四、樹形表示 2. 樹表示生成 對文 G[E]翻譯成樹形表示語義動作描述如下： (1)E∷ =E(1)+T {EVAL:=NODE(+,E(1)VAL,TVAL)} (2)E∷ =T {EVAL:=TVAL} (3)T∷ =T(1)*F {TVAL:=NODE(*,T(1)VAL,FVAL)} (4)T∷ =F {TVAL:=FVAL} (5)F∷ =(E) {FVAL:=EVAL} (6)F∷ =i {FVAL:=LEAF(i)} 其中：語義值 EVAL、 TVAL和 FVAL是一個指示器，指向樹一個結(jié)點(diǎn)。 NODE (OP， LEFT， RIGHT)是一個函數(shù)子程序 ， OP是一個二元運(yùn)算符 ， LEFT， RIGHT為指示器 ， 每調(diào)用 此函數(shù)一次 ,就建立一個新結(jié)點(diǎn) ， 其標(biāo)記為 OP， LEFT和 RIGHT分別指向左右子樹根結(jié)點(diǎn)指針 ， 從 NODE回送 的值是一個指示器 ， 指向這棵新樹的根 。 LEAF(i)是建立一個末端結(jié)點(diǎn) (葉結(jié)點(diǎn) ) 第五章 語法制導(dǎo)翻譯及中間代碼生成 167。 中間語言 一、引言 二、逆波蘭表示 三、三元式 四、樹形表示 1. 表示方法 2. 樹表示生成 五、四元式 第五章 語法制導(dǎo)翻譯及中間代碼生成 167。 中間語言 一、引言 二、逆波蘭表示 三、三元式 四、樹形表示 1. 表示方法 2. 樹表示生成 五、四元式 167。 中間語言 五、四元式表示 四元式是一種用得比較多的一種中間語言代碼形式 ， 四元式 (OP， ARG1， ARG2， RESULT) 其中： OP是運(yùn)算符 ， 其含義與三元式中 OP類似； ARG1和 A