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