語法制導(dǎo)翻譯技術(shù)和中間代碼生成

1、第第5 5章章 語法制導(dǎo)翻譯技術(shù)和中間代語法制導(dǎo)翻譯技術(shù)和中間代碼生成碼生成 編譯程序?qū)⒏呒壵Z言所寫的源程序翻譯成等價的機器語言或匯編語言的目標(biāo)程序,首先進(jìn)行詞法分析，得到單詞符號序列，再進(jìn)行語法分析，得到各類語法成份（或語法單位），接著，將進(jìn)行語義分析。 第第5 5章章 語法制導(dǎo)翻譯技術(shù)和中間代語法制導(dǎo)翻譯技術(shù)和中間代碼生成碼生成本章主要介紹：語法制導(dǎo)翻譯法的基本思想 常見的幾種中間代碼的形式 各種不同語法結(jié)構(gòu)的語法制 導(dǎo)翻譯技術(shù) 5.1 概述語義分析的任務(wù)：靜態(tài)語義審查靜態(tài)語義審查 審查每個語法結(jié)構(gòu)的靜態(tài)語義審查每個語法結(jié)構(gòu)的靜態(tài)語義,即驗證語法結(jié)構(gòu)合法的程序即驗證語法結(jié)構(gòu)合法的程序,是否

2、是否真正有意義真正有意義。5.1 概述例如: 表達(dá)式 A+B*C對運算對象進(jìn)行類型檢查, 對變量進(jìn)行先定義后使用檢查 如果靜態(tài)語義正確, 語義處理則要執(zhí)行真正的翻譯, 即生成程序的某種中間代碼的形式或直接生成目標(biāo)代碼。執(zhí)行真正的翻譯執(zhí)行真正的翻譯5.1 概述 目前多數(shù)編譯程序進(jìn)行語義分析的方法是采用語法制導(dǎo)翻譯法采用語法制導(dǎo)翻譯法 。它不是一種形式系統(tǒng), 但它比較接近形式化。 語法制導(dǎo)翻譯法使用屬性文法為工具來描述程序設(shè)計語言的語義。5.2 屬性文法(1) 屬性 對文法的每一個符號, 引進(jìn)一些屬性, 這些屬性代表與文法符號相關(guān)的信息, 如類型、值、存儲位置等。與屬性相關(guān)的信息, 即屬性值,可以

3、在語法分析過程中計算和傳遞。1. 屬性文法5.2 屬性文法屬性分為兩類:綜合屬性其計算規(guī)則按“自下而上”方式進(jìn)行, 即規(guī)則左部符號的某些屬性根據(jù)其右部符號的屬性和(或)自己的其他屬性計算而得。屬性加工的過程即是語義的處理過程。屬性加工的過程即是語義的處理過程。綜合屬性和繼承屬性。5.2 屬性文法繼承屬性其計算規(guī)則按“自上而下”方式進(jìn)行, 即規(guī)則右部符號的某些屬性根據(jù)其左部符號的屬性和(或)右部其他符號的某些屬性計算而得。5.2 屬性文法(2) 屬性文法 為文法的每一個規(guī)則配備的計算屬性的計算規(guī)則, 稱為語義規(guī)則(描述語義處理的加工動作) 。 屬性文法包含一個上下文無關(guān)文法和一系列語義規(guī)則。語義

4、規(guī)則:5.2 屬性文法 這些語義規(guī)則附在文法的每個產(chǎn)生式上,在語法分析過程中, 執(zhí)行語義規(guī)則描述的動作, 從而實現(xiàn)語義處理。也就是說, 附在文法的每個產(chǎn)生式上語義規(guī)則描述了語義處理的加工動作。 目前流行的語義描述和語義處理的方法主要是屬性文法和語法制導(dǎo)翻譯方法。5.3 語法制導(dǎo)翻譯概述語法制導(dǎo)翻譯法的基本思想語法制導(dǎo)翻譯法的基本思想 為文法的每個產(chǎn)生式都配備一個語義動作或語義子程序。 在語法分析的過程中，每當(dāng)使用一條產(chǎn)生式進(jìn)行推導(dǎo)或歸約時，就執(zhí)行相應(yīng)產(chǎn)生式的語義動作, 從而實現(xiàn)語義處理。5.3 語法制導(dǎo)翻譯概述S Axy a1 a2 a3 ai ai+1 an語義處理的加工動作 語法制導(dǎo)翻譯法

5、使用屬性文法為工具來說明程序設(shè)計語言的語義。5.3 語法制導(dǎo)翻譯概述(語義子程序語義子程序) 描述了一個產(chǎn)生式所對應(yīng)的翻譯工作描述了一個產(chǎn)生式所對應(yīng)的翻譯工作。 產(chǎn)生式只能產(chǎn)生符號串,并沒有指明所產(chǎn)生符號串的意義,僅僅是一些符號串的集合。語義動作語義動作5.3 語法制導(dǎo)翻譯概述 語義動作不僅指明了該產(chǎn)生式所產(chǎn)生符號串的意義，而且還根據(jù)這種意義規(guī)定了對應(yīng)的加工動作（如查填各類表格、改變編譯程序的某些變量的值、打印各種錯誤信息及生成中間代碼等），從而完成預(yù)定的翻譯工作。 5.3 語法制導(dǎo)翻譯概述語法制導(dǎo)翻譯法語法制導(dǎo)翻譯法 在語法分析過程中，依隨分析的過程，根據(jù)每個產(chǎn)生式所對應(yīng)的語義子程序(或語義

6、規(guī)則描述的語義處理的加工動作)進(jìn)行翻譯的方法。 為文法每一產(chǎn)生式設(shè)計相應(yīng)的求值的語義描述(語義動作)： 5.3 語法制導(dǎo)翻譯概述例如，設(shè)有簡單算術(shù)表達(dá)式的文法： EEE | 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+8*5,3+8,6*5,5.3 語法制導(dǎo)翻譯概述E.val = 47E.val = 8E.val = 40E.val = 7E.val

7、= 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*5 EEEEE5.3 語法制導(dǎo)翻譯概述語法制導(dǎo)翻譯技術(shù)分為： 自底向上語法制導(dǎo)翻譯 自頂向下語法制導(dǎo)翻譯 我們重點介紹自底向上語法制導(dǎo)翻譯。 5.3 語法制導(dǎo)翻譯概述LR分析制導(dǎo)的具體實現(xiàn)方法: 為文法的每一個產(chǎn)生式設(shè)計相應(yīng)的 語義動作為文法構(gòu)造LR分析表 5.3 語法制導(dǎo)翻譯概述擴充LR分析棧，以便存放文法符號 對

8、應(yīng)的語義值 語義值棧狀態(tài)棧文法符號棧 S0 $ S1 X1 X1.val Sk Xk Xk.val . . . . . . .5.3 語法制導(dǎo)翻譯概述修改總控程序 :查分析表, 當(dāng)用某產(chǎn) 生式歸約時,調(diào)用相應(yīng)的語義動作5.3 語法制導(dǎo)翻譯概述例如，設(shè)有簡單算術(shù)表達(dá)式的文法： EEE | 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 1. 為文法每一產(chǎn)生式設(shè)計

9、相應(yīng)的語義動作 (求值的語義描述) ： 5.3 語法制導(dǎo)翻譯概述2. 為上述文法構(gòu)造LR分析表如下圖： 90狀態(tài)ACTIONGOTO+digit*()$ES3S9S5S4S2S3S2S3S5S4S2S5S2S3r4r4r4r4r1r1r1r2r3r2r3r3r2r2r3123456781678acc5.3 語法制導(dǎo)翻譯概述 根據(jù)前表，用LR語法制導(dǎo)翻譯法得到表達(dá)式7+8*5的計值過程，如下圖 ：步驟狀態(tài)棧 語義棧 符號棧輸入符號棧 主要動作1_2030$_$7301_7$E4014_7_$E+50143_7_$E+87+8*5$S3+8*5$+8*5$8*5$*5$r4S4S3r44. E d

10、igitE.val Lex.digit 5.3 語法制導(dǎo)翻譯概述步驟狀態(tài)棧語義棧符號棧輸入符號棧 主要動作6_7_87014750147$E+E_7_8$E+E*8014753_7_8_$E+E*59014758_7_8_5$E+E*E100147_7_40$E+E*5$S55$S3r4r2r11101_47$E$acc2. E E*E E.val E(1).val*E(2).val 1. E E+E E.val E(1).val+E(2).val 5.3 語法制導(dǎo)翻譯概述自下而上語法制導(dǎo)翻譯法的特點: 語義分析棧與語法分析棧同步操作 當(dāng)棧頂形成句柄執(zhí)行歸約時，調(diào)用相應(yīng)的語義動作若將其翻譯成某

11、種中間代碼, 如何給出相應(yīng)的語義描述 ?5.4 中間語言編譯中常見的中間語言 :逆波蘭式（后綴式） 三元式 樹形表示 四元式5.4.1 逆波蘭式逆波蘭式逆波蘭式 逆波蘭式除去了原表達(dá)式中的括號，并將運算對象寫在前面，運算符寫在后面，因而又稱為后綴式后綴式。 例如：逆波蘭式a*bab*(a+b)*(c+d)ab+cd+*中綴表達(dá)式5.4.1 逆波蘭式 逆波蘭式表示法同中綴表示法相比其優(yōu)點是:1. 不再有括號,且運算符出現(xiàn)的順序體 現(xiàn)了中綴表達(dá)式 的運算順序2. 易于計算機處理5.4.1 逆波蘭式 一般表達(dá)式計值時，要處理兩類符號，一類是運算對象，另一類是運算符，通常用兩個工作棧分別處理。但處理用

12、逆波蘭式表示的表達(dá)式卻只用一個工作棧。 5.4.1 逆波蘭式 當(dāng)計算機自左到右順序掃描逆蘭波式時，若當(dāng)前符號是運算對象則進(jìn)棧，若當(dāng)前符號是運算符，設(shè)為K元運算符，則將棧頂?shù)腒個元素依次取出，同時進(jìn)行K元運算，并將運算結(jié)果置于棧頂，表達(dá)式處理完畢時，其計算結(jié)果自然呈現(xiàn)在棧頂。 5.4.1 逆波蘭式逆波蘭式ab+c*的處理過程如下圖： baT1cT1T25.4.1 逆波蘭式：逆波蘭形式可以推廣到其他語法結(jié)構(gòu)： 賦值語句V=E逆波蘭式VE=條件語句逆波蘭式if E S1 ; else S2ES1S2￥5.4.1 逆波蘭式LR分析制導(dǎo)生成逆波蘭式：分析制導(dǎo)生成逆波蘭式： 1. 給出算術(shù)表達(dá)式翻譯到逆波

13、蘭式的語義 描述(1)首先搞清楚生成什么樣的中間代碼 或計值(2)根據(jù)各種語法成份的語義, 搞清楚它們應(yīng)翻譯成什么形式的代 碼結(jié)構(gòu)LR分析制導(dǎo)生成逆波蘭式：例如: 賦值語句 V=E 計算E值的代碼 將E值存放到V中的代碼 其代碼結(jié)構(gòu):LR分析制導(dǎo)生成逆波蘭式：例如: 條件語句 if E S1 ; else S2 其代碼結(jié)構(gòu):計算E值的代碼S2的代碼S1的代碼FTLR分析制導(dǎo)生成逆波蘭式：(3) 給出從源結(jié)構(gòu)到目標(biāo)結(jié)構(gòu)的變換方法例如，簡單算術(shù)表達(dá)的文法： 給出算術(shù)表達(dá)式翻譯到逆波蘭式的語義描述EEE | E*E | (E) | i 源結(jié)構(gòu) a+b*c目標(biāo)結(jié)構(gòu) abc*+LR分析制導(dǎo)生成逆波蘭式：

14、EEE | E*E | (E) | i1.E E(1)E(2) print + 2.E E(1)*E(2) print * 3.E (E(1) 空 4.E i print i 0.E E 空 E(1).code | E(2).code| + E(1).code | E(2).code| *LR分析制導(dǎo)生成逆波蘭式：0狀態(tài)ACTIONGOTO+ i*()$ES3S9S5S4S2S3S2S3S5S4S2S5S2S3r4r4r4r4r1r1r1r2r3r2r3r3r2r2r31234567891678acc2.為上述文法構(gòu)造LR分析表如下圖： LR分析制導(dǎo)生成逆波蘭式：3. 算術(shù)表達(dá)式a+b*c翻譯

15、到逆波蘭式的過程： 狀態(tài)棧符號棧輸入串輸出區(qū)030$a01$E014$E+0143$E+ba+b*c$+b*c$+b*c$b*c$*c$aaa4.Eiprint iLR分析制導(dǎo)生成逆波蘭式：014750147$E+E$E+E*014753$E+E*c014758$E+E*E0147$E+E*c$abc$abababcabc*01$E$abc*+狀態(tài)棧符號棧輸入串輸出區(qū)acc2. EE(1)*E(2)print *1. EE(1)+E(2)print +5.4.2 三元式和樹形表示三元式三元式主要由三部分組成： （OP，arg1, arg2） 其中OP是運算符， arg1,arg2分別是第一和第

16、二兩個運算對象。 當(dāng)OP是一目運算時，常常將運算對象定義為arg1。 5.4.2 三元式和樹形表示例如 a+b*c 的 三元式序列： (1) ( * b c ) (2) ( + a (1) )運算對象是指向符號表的某一項或指向三元式表的某一項。 5.4.2 三元式和樹形表示 1. 三元式出現(xiàn)的順序和語法成份的 計值順序相一致。 三元式的特點：2. 三元式之間的聯(lián)系是通過指示器 實現(xiàn)的。 5.4.2 三元式和樹形表示間接三元式(1) 間接三元式表: 用來存放各三元式本身。(2) 間接碼表: 按執(zhí)行各三元式的順序,依次 列出各三元式在三元式表中的位置。注意注意 : 間接三元式表中不存放重復(fù)的間接三

17、元式表中不存放重復(fù)的 三元式。三元式。5.4.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) )5.4.2 三

18、元式和樹形表示 樹形表示 A * B + C*D +C*A*BD 末端結(jié)點表示一個運算對象, 每一個內(nèi)結(jié)點表示一個一元或二元運算符。樹形表示是三元式的翻版(3)+(1)*(2)*CABD5.4.3 四元式四元式四元式主要由四部分組成： （OP，arg1, arg2, result） 其中OP是運算符， arg1,arg2分別是第一和第二兩個運算對象。 當(dāng)OP是一目運算時，常常將運算對象定義為arg1。 四元式的第四個分量result是編譯程序為存放中間運算結(jié)果而臨時引進(jìn)的變量，常稱為臨時變量，如Ti，也可以是用戶自定義變量，如X。 5.4.3 四元式例如 X a*bc/d 的 四元式序列：(1

19、) ( *, a, b, T1 )(2) ( /, c, d, T2 )(3) ( +, T1, T2, T3 )(4) ( =, T3, - -, X )5.4.4 四元式2. 四元式之間的聯(lián)系是通過臨時變量實 現(xiàn)的，這樣易于調(diào)整和變動四元式。 1. 四元式出現(xiàn)的順序和語法成份的計值 順序相一致。 四元式的特點：3. 便于優(yōu)化處理。 5.4.4 四元式 編譯系統(tǒng)中，有時將四元式表示成另一種更直觀，更易理解的形式三地址代碼或三地址語句。result : arg1 OP arg2 三地址語句三地址語句:語句中是三個量的賦值語句, 每個量占一個地址。 三地址代碼形式定義為：5.4.4 四元式的翻譯

20、：例如 X a*bc/d 的 四元式序列：(1) ( *, a, b, T1 )(2) ( /, c, d, T2 )(3) ( +, T1, T2, T3 )(4) ( =, T3, - -, X )相應(yīng)的三地址語句序列為： （1）T1a*b （2）T2c/d （3）T3T1T2 （4）XT3 簡單算術(shù)表達(dá)式和賦值語句到四元式的翻譯：LR分析制導(dǎo)生成四元式分析制導(dǎo)生成四元式例如 A i E E EE E*E (E) | i 1. 給出算術(shù)表達(dá)式和賦值語句翻譯到 四元式的語義描述簡單算術(shù)表達(dá)式和賦值語句到四元式的翻譯：A i E E EE E*E (E) | i 源結(jié)構(gòu)目標(biāo)結(jié)構(gòu)（1）T1a*b

21、 （2）T2c*d （3）T3T1T2 （4）X T3 X a*bc*d 簡單算術(shù)表達(dá)式和賦值語句到四元式的翻譯：語義函數(shù) emit（Targ1 OP arg2） 功能是生成一個三地址語句，并送到輸出文件中。 語義函數(shù) newtemp( ) 功能是產(chǎn)生一個新的臨時變量名字，并回送新的臨時變量名的整數(shù)碼。如T1，T2等。 簡單算術(shù)表達(dá)式和賦值語句到四元式的翻譯： (2) 不進(jìn)符號表，臨時變量單詞值部 分用整數(shù)碼表示。 (1) 送到符號表。 對臨時變量有兩種不同的處理方法: 簡單算術(shù)表達(dá)式和賦值語句到四元式的翻譯：語義過程 Lookup（） 功能是審查是否出現(xiàn)在符號表中，在

22、則返回其指針，否則返回NULL。 語義變量 E.place 表示存放非終結(jié)符E值的變量名在符號表中的入口地址或臨時變量名的整數(shù)碼。 簡單算術(shù)表達(dá)式和賦值語句到四元式的翻譯： 利用以上定義的語義變量和函數(shù)等，寫出每一個規(guī)則式的語義動作如下：1. Ai E p = Lookup (); if ( P != NULL ) emit ( pE.place ) ; else error( ) 簡單算術(shù)表達(dá)式和賦值語句到四元式的翻譯： 2. E E(1) E(2) 3. E E(1) * E(2) E.place newtemp( ); emit(E.placeE(1).placeE(2).p

23、lace ) E.place newtemp( ); emit(E.placeE(1).place*E(2).place ) 簡單算術(shù)表達(dá)式和賦值語句到四元式的翻譯：4. E （E(1)） E.place E(1).place； 5. E i p Lookup (); if (p != NULL) E.place p; else error( ); 簡單算術(shù)表達(dá)式和賦值語句到四元式的翻譯：90狀態(tài)ACTIONGOTO+ i*()$ES3S9S5S4S2S3S2S3S5S4S2S5S2S3r4r4r4r4r1r1r1r2r3r2r3r3r2r2r3123456781678acc2.為

24、文法構(gòu)造LR分析表如下圖： 簡單算術(shù)表達(dá)式和賦值語句到四元式的翻譯：3. 算術(shù)表達(dá)式a+b*c翻譯到三地址語句的過程： 030$a01$E014$E+0143$E+baaa狀態(tài)棧符號棧語義棧輸入串a(chǎn)+b*c$+b*c$+b*c$b*c$*c$ 變量在符號表的入口用變量本身表示簡單算術(shù)表達(dá)式和賦值語句到四元式的翻譯：*c$c$t1=b*c t2=a+t1 狀態(tài)棧符號棧語義棧輸入串014750147$E+E$E+E*014753$E+E*c014758$E+E*E0147$E+E01$Eab abcat1ababt2acc簡單算術(shù)表達(dá)式和賦值語句到四元式的翻譯： 2. E E(1) E(2) 3.

25、 E E(1) * * E(2) E.place newtemp( ); emit(E.placeE(1).placeE(2).place ) E.place newtemp( ); emit(E.placeE(1).place*E(2).place )布爾表達(dá)式到四元式的翻譯一.布爾表達(dá)式的文法 計算邏輯值程序設(shè)計語言中布爾表達(dá)式有兩個作用: 用作控制語句中的條件式布爾表達(dá)式是由布爾算符(、和)施于布爾變量或關(guān)系表達(dá)式而成。 布爾表達(dá)式到四元式的翻譯 對某些語言,如 PL / 1,允許更通用的表達(dá)式,其中,布爾算符、算術(shù)算符和關(guān)系算符可施于任何類型的表達(dá)式,并不區(qū)別布爾值和算術(shù)值。 為簡單起

26、見,只考慮如下文法生成的布爾表達(dá)式:布爾表達(dá)式到四元式的翻譯 E E (1) E (2) E E (1) E (2) E E (1) E ( E (1) ) E i (1) rop i (2) E true E false E i布爾表達(dá)式到四元式的翻譯 二. 布爾表達(dá)式的計值方法 1. 如同計算算術(shù)表達(dá)式一樣,步步計算出各部分真、假值,最后計算出整個表達(dá)式的值。 2. 根據(jù)布爾運算的特殊性,采取某種優(yōu)化措施,可避免計算整個表達(dá)式的值。布爾表達(dá)式到四元式的翻譯 AB 解釋成 AB 解釋成 A 解釋成if A then true else Bif A then B else falseif A

27、then false else true 三. 布爾表達(dá)式的翻譯方法 1. 同翻譯算術(shù)表達(dá)式一樣,翻譯布爾表達(dá)式。布爾表達(dá)式到四元式的翻譯 1. E E (1) E (2) E.place newtemp( )； emit ( E.placeE(1).placeE(2).place ) 2. E E (1) E (2) E.place newtemp( )； emit ( E.placeE(1).placeE(2).place ) 布爾表達(dá)式到四元式的翻譯3. E ( E (1) ) E.place E(1).place； 4. E i (1) rop i (2) E.place newtem

28、p( )； emit (if i (1).place rop.op i (2).place goto next+3); emit ( E.place 0 ); emit ( goto next+2); emit ( E.place 1 ); 布爾表達(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 布爾表達(dá)式到四元式的翻譯例如布爾表達(dá)式 a = bc d 對應(yīng)如下四元式序列:101

29、 if a = b goto 104102 t1= 0103 goto 105104 t1= 1105 t2= c d106 t3 = t1 t2 布爾表達(dá)式到四元式的翻譯2. 控制語句中布爾表達(dá)式的翻譯條件語句的語法為:根據(jù)條件語句的語義,條件語句的代碼結(jié)構(gòu)為:if E then S(1) else S(2)E的代碼S(1)的代碼S(2)的代碼Jump out out: 真 假布爾表達(dá)式到四元式的翻譯 E是布爾表達(dá)式,根據(jù)布爾運算的特殊性,布爾表達(dá)式的目標(biāo)結(jié)構(gòu)為:假E(1)的代碼E(2)的代碼真S(1)S(2)真假真E(1)的代碼E(2)的代碼假S(2)S(1)假真 (1) 真出口和假出口:

30、真出口表示布爾表達(dá)式E為真時控制流向的轉(zhuǎn)移目標(biāo)假出口表示布爾表達(dá)式E為假時控制流向的轉(zhuǎn)移目標(biāo)布爾表達(dá)式到四元式的翻譯(2) 作為條件轉(zhuǎn)移的E,把E翻譯成的代碼 是一串條件轉(zhuǎn)或無條件轉(zhuǎn)的四元式對于E為 a rop b 的形式生成代碼為: if a rop b goto 真出口 goto 假出口布爾表達(dá)式到四元式的翻譯(q)例如語句 if a bc d then S(1) else S(2) 的四元式為:100 if a b goto 104101 goto 102102 if c d goto 104 103 goto ( p+1) 104 ( 關(guān)于 S(1) 的四元式)(p) goto (q)

31、(p+1) ( 關(guān)于 S(2) 的四元式)E(1)的真出口為104, E(1)的假出口為102E(2)的真出口為104, E(2)的假出口為(p+1)E的真出口為104, E的假出口為(p+1)布爾表達(dá)式到四元式的翻譯布爾表達(dá)式到四元式的翻譯布爾表達(dá)式的真、假出口不能在產(chǎn)生其四元式的同時得知例如 E(1)的真出口為104需分析到S(1)時才能得知,因此E.tr: 記錄表達(dá)式 E 所對應(yīng)的四元式需回填真出口的四元式的地址所構(gòu)成的鏈E.fa: 記錄表達(dá)式 E 所對應(yīng)的四元式需回填假出口的四元式的地址所構(gòu)成的鏈(3) 設(shè)置兩個語義變量:(q)例如語句 if a bc d then S(1) else

32、 S(2) 的四元式為:100 if a b goto 104101 goto 102102 if c d goto 104 103 goto ( p+1) 104 ( 關(guān)于 S(1) 的四元式)(p) goto (q)(p+1) ( 關(guān)于 S(2) 的四元式)布爾表達(dá)式到四元式的翻譯E(1).tr=100, E(1).fa=101E(2).tr=102, E(2).fa=103布爾表達(dá)式到四元式的翻譯E.fa=103; E.tr=100和102所構(gòu)成的鏈 E(1) E(2)歸約E時, 布爾表達(dá)式到四元式的翻譯把以 p1, p2為鏈?zhǔn)椎膬蓷l鏈合并為一, 返回合并后的鏈?zhǔn)?4) 鏈結(jié)函數(shù)和回填函

33、數(shù): merg (p1, p2) :布爾表達(dá)式到四元式的翻譯 merg (int p1, int p2) if p2=0 return( p1 ) ;else p= p2 ; while ( 四元式p的第四分量內(nèi)容不為0) p=四元式p的第四分量內(nèi)容; 把p1填進(jìn)四元式p的第四分量; return( p2 ) ;布爾表達(dá)式到四元式的翻譯r1 ( 0 )q1 ( r1 )q2 ( r2 )p1 ( q1 )r2 ( 0 )p2 ( q2 )p1布爾表達(dá)式到四元式的翻譯 merg (int p1, int p2) if p2=0 return( p1 ) ;else p= p2 ; while (

34、 四元式p的第四分量內(nèi)容不為0) p=四元式p的第四分量內(nèi)容; 把p1填進(jìn)四元式p的第四分量; return( p2 ) ;100102102(q)例如語句 if a bc d then S(1) else S(2) 的四元式為:100 if a b goto 0101 goto 102102 if c d goto 100 103 goto ( p+1) 104 ( 關(guān)于 S(1) 的四元式)(p) goto (q)(p+1) ( 關(guān)于 S(2) 的四元式)布爾表達(dá)式到四元式的翻譯布爾表達(dá)式到四元式的翻譯 bp ( int p, int t ) : 將 p 所鏈結(jié)的每個四元式的第四區(qū)分量都回

35、填 t ;布爾表達(dá)式到四元式的翻譯 bp ( int p, int t )q=p;while (q != 0 ) r = 四元式 q 的第四分量內(nèi)容; 把 t 填進(jìn)四元式 q 的第四分量; q=r ;1021041000 102100(q)例如語句 if a bc d then S(1) else S(2) 的四元式為:100 if a b goto 104101 goto 102102 if c d goto 104 103 goto ( p+1) 104 ( 關(guān)于 S(1) 的四元式)(p) goto (q)(p+1) ( 關(guān)于 S(2) 的四元式)布爾表達(dá)式到四元式的翻譯布爾表達(dá)式到四元

36、式的翻譯(5) 為及時回填轉(zhuǎn)移地址, 使用語義變量 E.code 記錄表達(dá)式E的第一個四元式語句序號。(6) 定義語義變量 next 為四元式表指針。E (1).code=100E (2).code=102E .code=100布爾表達(dá)式到四元式的翻譯布爾表達(dá)式語義動作的設(shè)計 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 ;布爾表達(dá)式到四元式的翻譯布爾表達(dá)式語義動作的設(shè)計 2. E E (1) E (2) bp( E(1).

37、tr, E(2).code) ； E.code= E(1).code ; E.tr= E(2).tr ; E.fa=merg( E(1).fa, E(2).fa ) ;布爾表達(dá)式語義動作的設(shè)計 3. E ( E (1) ) E.code= E(1).code ; E.tr=E(1).tr ; E.fa= E(1).fa ;布爾表達(dá)式到四元式的翻譯布爾表達(dá)式語義動作的設(shè)計 4. E i (1) rop i (2) E.tr= next ; E.code= next ; E.fa= next+1; emit ( if i (1).place rop.op i (2).place goto _ )

38、; emit( goto _ ) ;布爾表達(dá)式到四元式的翻譯布爾表達(dá)式語義動作的設(shè)計 5. E true E.tr= next ; E.code= next ; emit( goto _ ) ;布爾表達(dá)式到四元式的翻譯布爾表達(dá)式到四元式的翻譯布爾表達(dá)式語義動作的設(shè)計 6. E false E.fa= next ; E.code= next ; emit( goto _ ) ;布爾表達(dá)式到四元式的翻譯布爾表達(dá)式語義動作的設(shè)計 5. E i E.tr= next ; E.fa= next +1; E.code= next ; emit(if i.place goto -); emit( goto

39、_ ) ;5. E true 6. E false布爾表達(dá)式到四元式的翻譯例如布爾表達(dá)式 a bc d 的翻譯過程如下:布爾表達(dá)式到四元式的翻譯a bc d E (1)c d 100 if a b goto 0101 goto 0 E(1).tr=100 ; E(1).fa=101 ; E(1).code=100 ; E (1) E (2) 102 if c d goto 0103 goto 0 E(2).tr=102 ; E(2).fa=103 ; E(2).code=102 ; 布爾表達(dá)式到四元式的翻譯 E bp( E(1).fa, E(2).code) =bp( 101,102); E.

40、fa=E(2).fa=103 ; E.tr=merg(E(1).tr, E(2).tr) = merg( 100,102)=102 ; E.code= E(1).code=100100 if a b goto 0101 goto 0102 if c d goto 100103 goto 0102E (1)E (2) 歸約為E布爾表達(dá)式到四元式的翻譯102 if c d goto 100103 goto 0100 if a b goto 0101 goto 102布爾表達(dá)式 a bc d E.tr=102E.fa=103簡單說明語句的翻譯 程序設(shè)計語言中，程序中的每個名字（變量名）都必須在使用前

41、進(jìn)行說明。說明語句的功能就是告知編譯程序每一個變量的類型信息。 翻譯說明語句時,設(shè)計的語義動作應(yīng)將變量的類型信息填入符號表中。簡單說明語句的翻譯簡單說明語句文法 , id | idD integer real 簡單說明語句的翻譯 用上述文法的規(guī)則式進(jìn)行歸約時，按照自下而上制導(dǎo)翻譯，首先將所有名字id歸約為一個名字表namelist后，才能將namelist中所有名字的性質(zhì)登錄在符號表里。這樣必須用一個隊列（或棧）來保存namelist中的所有名字。簡單說明語句的翻譯 我們希望在掃描過程中，每遇到一個名字，就把它及其性質(zhì)及時登錄在符號表中。歸約過程中涉及到這些名字及其性質(zhì)時，就可以直接到符號表中

42、進(jìn)行查找，而無需占用額外空間保存namelist 中名字的信息簡單說明語句的翻譯文法改寫：DD(1)，idinteger id real id（1） 函數(shù)FILL(id，A)的功能是把名字 id和性質(zhì)A登錄在符號表中。對文法設(shè)計語義動作如下：（2）設(shè)置非終結(jié)符D的語義變量D.ATT, 記錄說明語句所規(guī)定的相關(guān)名字性質(zhì)。簡單說明語句的翻譯（1）Dinteger id（2）Dreal id（3）DD(1), id FILL(id, int) ; D.ATTint FILL(id, real) ; D.ATT=real FILL(id, D(1).ATT) ; D.ATT=D(1).ATT 過程或函數(shù)調(diào)用語句的翻譯過程或函數(shù)調(diào)用語句的翻譯一種描述過程或函數(shù)調(diào)用語句的文法一種描述過程或函數(shù)調(diào)用語句的文法如下：如下：GS: Scall i() ,E E 過程或函數(shù)調(diào)用語句的翻譯過程或函數(shù)調(diào)用語句的翻譯Scall i() for(隊列隊列queue中的每一項中的每一項P) emit(par,_,_,P); emit(call,_,_,i.place);,E 將將E.place加入加入queue的隊尾的隊尾E 初始化初始化queue隊列，僅包含隊列，僅包含E.place本本 章章 小小 結(jié)結(jié)1. 簡單算術(shù)表達(dá)式的逆波蘭式和四元 式的表示例如 a + b * ( c + d )的逆