編譯原理第5章

1、第第5 5章章 語法制導(dǎo)翻譯技術(shù)和中間代語法制導(dǎo)翻譯技術(shù)和中間代 碼生成碼生成 編譯程序?qū)⒏呒壵Z言所寫的源程序翻譯 成等價的機(jī)器語言或匯編語言的目標(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)語義, 即驗(yàn)證語法結(jié)構(gòu)合法的程序即驗(yàn)證語

2、法結(jié)構(gòu)合法的程序,是否是否 真正有意義真正有意義。 5.1 概述 例如: 表達(dá)式 a+b*c 對運(yùn)算對象進(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)的信 息, 如類

3、型、值、存儲位置等。與屬性 相關(guān)的信息, 即屬性值,可以在語法分析 過程中計算和傳遞。 1. 屬性文法 5.2 屬性文法 屬性分為兩類: 綜合屬性其計算規(guī)則按“自下而上”方 式進(jìn)行, 即規(guī)則左部符號的某些屬性根 據(jù)其右部符號的屬性和(或)自己的其他 屬性計算而得。 屬性加工的過程即是語義的處理過程。屬性加工的過程即是語義的處理過程。 綜合屬性和繼承屬性。 5.2 屬性文法 繼承屬性其計算規(guī)則按“自上而下”方 式進(jìn)行, 即規(guī)則右部符號的某些屬性根 據(jù)其左部符號的屬性和(或)右部其他符 號的某些屬性計算而得。 5.2 屬性文法 (2) 屬性文法 為文法的每一個規(guī)則配備的計算屬性 的計算規(guī)則, 稱為

4、語義規(guī)則(描述語義處 理的加工動作) 。 屬性文法包含一個上下文無關(guān)文法和 一系列語義規(guī)則。 語義規(guī)則: 5.2 屬性文法 這些語義規(guī)則附在文法的每個產(chǎn)生 式上,在語法分析過程中, 執(zhí)行語義規(guī)則 描述的動作, 從而實(shí)現(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)生式的語義動作, 從而

5、實(shí)現(xiàn)語義處理。 5.3 語法制導(dǎo)翻譯概述 s axy a1 a2 a3 ai ai+1 an 語義處理的 加工動作 語法制導(dǎo)翻譯法使用屬性文法為工具 來說明程序設(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)的加工動作（如查填各類表格、改變 編譯程序的某些變量的值、打印各種錯誤 信息及生成中間代碼等），從

6、而完成預(yù)定 的翻譯工作。 5.3 語法制導(dǎo)翻譯概述 語法制導(dǎo)翻譯法語法制導(dǎo)翻譯法 在語法分析過程中，依隨分析的過程， 根據(jù)每個產(chǎn)生式所對應(yīng)的語義子程序(或 語義規(guī)則描述的語義處理的加工動作)進(jìn) 行翻譯的方法。 為文法每一產(chǎn)生式設(shè)計相應(yīng)的求值的語義 描述(語義動作)： 5.3 語法制導(dǎo)翻譯概述 例如，設(shè)有簡單算術(shù)表達(dá)式的文法： eee | e*e | (e) | digit 1.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.

7、val lex.digit 7+8*5,3+8,6*5, 5.3 語法制導(dǎo)翻譯概述 e.val = 47 e.val = 8 e.val = 40 e.val = 7 e.val = 5 + 5 * 8 7 1.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 e e e e e 5.3 語法制導(dǎo)翻譯概述 語法制導(dǎo)翻譯技術(shù)分為： 自底向上語法制導(dǎo)翻譯 自頂向下語法制導(dǎo)翻譯 我們重點(diǎn)

8、介紹自底向上語法制導(dǎo)翻譯。 5.3 語法制導(dǎo)翻譯概述 lr分析制導(dǎo)的具體實(shí)現(xiàn)方法: 為文法的每一個產(chǎn)生式設(shè)計相應(yīng)的 語義動作 為文法構(gòu)造lr分析表 5.3 語法制導(dǎo)翻譯概述 擴(kuò)充lr分析棧，以便存放文法符號 對應(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) | digit 1.e e(1)e(2) e.val e(1).v

9、al 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è)計相應(yīng)的語義動作 (求值的語義描述) ： 5.3 語法制導(dǎo)翻譯概述 2. 為上述文法構(gòu)造lr分析表如下圖： 9 0 狀 態(tài) actiongoto + digit * ()$e s3 s9s5s4 s2s3 s2s3 s5s4 s2 s5 s2s3 r4r4r4r4 r1r1r1 r2 r3 r2 r3r3 r2r2 r3 1 2 3 4 5 6 7 8 1 6 7 8 a

10、cc 5.3 語法制導(dǎo)翻譯概述 根據(jù)前表，用lr語法制導(dǎo)翻譯法得到 表達(dá)式7+8*5的計值過程，如下圖 ： 步驟狀態(tài)棧 語義棧 符號棧輸入符號棧 主要動作 1 _ 203 0$ _ $7 301 _7$e 4014 _7_$e+ 50143 _7_ $e+8 7+8*5$s3 +8*5$ +8*5$ 8*5$ *5$ r4 s4 s3 r4 4. e digit e.val lex.digit 5.3 語法制導(dǎo)翻譯概述 步驟狀態(tài)棧語義棧符號棧輸入符號棧 主要動作 6 _7_8 701475 0147$e+e _7_8 $e+e* 8014753 _7_8_$e+e*5 9014758 _7_8

11、_5$e+e*e 10 0147 _7_40$e+e *5$s5 5$ $ $ $ s3 r4 r2 r1 1101 _47$e$acc 2. 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)翻譯法的特點(diǎn): 語義分析棧與語法分析棧同步操作 當(dāng)棧頂形成句柄執(zhí)行規(guī)約時，調(diào)用相 應(yīng)的語義動作 若將其翻譯成某種中間代碼, 如何給出 相應(yīng)的語義描述 ? 5.4 中間語言 編譯中常見的中間語言 : 逆波蘭式（后綴式） 三元式 樹形表示 四元式 5.4.1 逆波蘭式 逆波蘭式逆波蘭式 逆波

12、蘭式除去了原表達(dá)式中的括號， 并將運(yùn)算對象寫在前面，運(yùn)算符寫在后 面，因而又稱為后綴式后綴式。 例如：逆波蘭式 a*bab* (a+b)*(c+d)ab+cd+* 中綴表達(dá)式 5.4.1 逆波蘭式 逆波蘭式表示法同中綴表示法相比其 優(yōu)點(diǎn)是: 1. 不再有括號,且運(yùn)算符出現(xiàn)的順序體 現(xiàn)了中綴表達(dá)式 的運(yùn)算順序 2. 易于計算機(jī)處理 5.4.1 逆波蘭式 一般表達(dá)式計值時，要處理兩類符 號，一類是運(yùn)算對象，另一類是運(yùn)算符， 通常用兩個工作棧分別處理。但處理用 逆波蘭式表示的表達(dá)式卻只用一個工作 棧。 5.4.1 逆波蘭式 當(dāng)計算機(jī)自左到右順序掃描逆蘭波 式時，若當(dāng)前符號是運(yùn)算對象則進(jìn)棧， 若當(dāng)前符

13、號是運(yùn)算符，設(shè)為k元運(yùn)算符， 則將棧頂?shù)膋個元素依次取出，同時進(jìn) 行k元運(yùn)算，并將運(yùn)算結(jié)果置于棧頂， 表達(dá)式處理完畢時，其計算結(jié)果自然呈 現(xiàn)在棧頂。 5.4.1 逆波蘭式 逆波蘭式ab+c*的處理過程如下圖： b at1 c t1t2 5.4.1 逆波蘭式： 逆波蘭形式可以推廣到其他語法結(jié)構(gòu)： 賦值語句 v=e 逆波蘭式 ve= 條件語句逆波蘭式 if e s1 ; else s2es1s2￥ 5.4.1 逆波蘭式 lr分析制導(dǎo)生成逆波蘭式：分析制導(dǎo)生成逆波蘭式： 1. 給出算術(shù)表達(dá)式翻譯到逆波蘭式的語義 描述 (1)首先搞清楚生成什么樣的中間代碼 或計值 (2)根據(jù)各種語法成份的語義, 搞清

14、楚它 們應(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的代碼 ft lr分析制導(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)生成逆波蘭式： eee | e*e | (e) | i 1.e e(1)e(2

15、) 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 * ()$e s3 s9s5s4 s2s3 s2s3 s5s4 s2 s5 s2s3 r4r4r4r4 r1r1r1 r2 r3 r2 r3r3 r2r2 r3 1 2 3 4 5 6 7 8 9 1 6 7 8 acc 2.為上述文法構(gòu)造lr分析表如下圖： lr分析制導(dǎo)生成逆波蘭式： 3. 算術(shù)

16、表達(dá)式a+b*c翻譯到逆波蘭式的過程： 狀態(tài)棧符號棧輸入串輸出區(qū) 03 0 $ $a 01$e 014$e+ 0143$e+b a+b*c$ +b*c$ +b*c$ b*c$ *c$ a a a 4.ei print i lr分析制導(dǎo)生成逆波蘭式： 01475 0147$e+e $e+e* 014753$e+e*c 014758$e+e*e 0147$e+e *c$ ab c$ $ $ $ ab ab abc abc* 01$e$ abc*+ 狀態(tài)棧符號棧輸入串輸出區(qū) acc 2. ee(1)*e(2) print * 1. ee(1)+e(2) print + 5.4.2 三元式和樹形表示

17、三元式三元式主要由三部分組成： （op，arg1, arg2） 其中op是運(yùn)算符， arg1,arg2分別是第一和第二兩個運(yùn)算對象。 當(dāng)op是一目運(yùn)算時，常常將運(yùn)算對象定 義為arg1。 5.4.2 三元式和樹形表示 例如 a+b*c 的 三元式序列： (1) ( * b c ) (2) ( + a (1) ) 運(yùn)算對象是指向符號表的某一項(xiàng)或指向 三元式表的某一項(xiàng)。 5.4.2 三元式和樹形表示 1. 三元式出現(xiàn)的順序和語法成份的 計值順序相一致。 三元式的特點(diǎn)： 2. 三元式之間的聯(lián)系是通過指示器 實(shí)現(xiàn)的。 5.4.2 三元式和樹形表示 間接三元式 (1) 間接三元式表: 用來存放各三元式本

18、身。 (2) 間接碼表: 按執(zhí)行各三元式的順序,依次 列出各三元式在三元式表中的位置。 注意注意 : 間接三元式表中不存放重復(fù)的間接三元式表中不存放重復(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 ,

19、 b ) (2) ( * , (1) , c ) (3) ( = , x , (2) ) (4) ( , d , (1) ) (5) ( = , y, (4) ) 5.4.2 三元式和樹形表示 樹形表示 a * b + c*d + c * a * bd 末端結(jié)點(diǎn)表示一個運(yùn)算對象, 每一個內(nèi) 結(jié)點(diǎn)表示一個一元或二元運(yùn)算符。 樹形表示是三元式的翻版 (3)+ (1)*(2)* cabd 5.4.3 四元式 四元式四元式主要由四部分組成： （op，arg1, arg2, result） 其中op是運(yùn)算符， arg1,arg2分別是第一和第二兩個運(yùn)算對象。 當(dāng)op是一目運(yùn)算時，常常將運(yùn)算對象定義 為a

20、rg1。 四元式的第四個分量result是編譯程序 為存放中間運(yùn)算結(jié)果而臨時引進(jìn)的變量， 常稱為臨時變量，如ti，也可以是用戶 自定義變量，如x。 5.4.3 四元式 例如 x a*bc/d 的 四元式序列： (1) ( *, a, b, t1 ) (2) ( /, c, d, t2 ) (3) ( +, t1, t2, t3 ) (4) ( =, t3, - -, x ) 5.4.4 四元式 2. 四元式之間的聯(lián)系是通過臨時變量實(shí) 現(xiàn)的，這樣易于調(diào)整和變動四元式。 1. 四元式出現(xiàn)的順序和語法成份的計值 順序相一致。 四元式的特點(diǎn)： 3. 便于優(yōu)化處理。 5.4.4 四元式 編譯系統(tǒng)中，有時

21、將四元式表示成另一 種更直觀，更易理解的形式三地址代 碼或三地址語句。 result : arg1 op arg2 三地址語句三地址語句:語句中是三個量的賦值語句, 每個量占一個地址。 三地址代碼形式定義為： 5.4.4 四元式的翻譯： 例如 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)

22、生成四元式分析制導(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 （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ù)

23、表達(dá)式和賦值語句到四元 式的翻譯： (2) 不進(jìn)符號表，臨時變量單詞值部 分用整數(shù)碼表示。 (1) 送到符號表。 對臨時變量有兩種不同的處理方法: 簡單算術(shù)表達(dá)式和賦值語句到四元 式的翻譯： 語義過程 lookup（） 功能是審查是否出現(xiàn)在符號表中， 在則返回其指針，否則返回null。 語義變量 e.place 表示存放非終結(jié)符e值的變量名在符號 表中的入口地址或臨時變量名的整數(shù)碼。 簡單算術(shù)表達(dá)式和賦值語句到四元 式的翻譯： 利用以上定義的語義變量和函數(shù)等，寫出 每一個規(guī)則式的語義動作如下： 1. ai e p = lookup (); if ( p !=

24、 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).place ) 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

25、) e.place p; else error( ); 簡單算術(shù)表達(dá)式和賦值語句到四元 式的翻譯： 9 0 狀 態(tài) actiongoto + i * ()$e s3 s9s5s4 s2s3 s2s3 s5s4 s2 s5 s2s3 r4r4r4r4 r1r1r1 r2 r3 r2 r3r3 r2r2 r3 1 2 3 4 5 6 7 8 1 6 7 8 acc 2.為文法構(gòu)造lr分析表如下圖： 簡單算術(shù)表達(dá)式和賦值語句到四元 式的翻譯： 3. 算術(shù)表達(dá)式a+b*c翻譯到三地址語句的過程： 03 0 $ $a 01$e 014$e+ 0143$e+b a a a 狀態(tài)棧符號棧語義棧輸入串 a+b

26、*c$ +b*c$ +b*c$ b*c$ *c$ 變量在符號表的 入口用變量本身 表示 簡單算術(shù)表達(dá)式和賦值語句到四元 式的翻譯： *c$ c$ $ $ $ $ t1=b*c t2=a+t1 狀態(tài)棧符號棧語義棧輸入串 01475 0147$e+e $e+e* 014753$e+e*c 014758$e+e*e 0147$e+e 01$e ab abc at1 ab ab t2 acc 簡單算術(shù)表達(dá)式和賦值語句到四元 式的翻譯： 2. e e(1) e(2) 3. e e(1) * * e(2) e.place newtemp( ); emit(e.placee(1).placee(2).pla

27、ce ) 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ù)值。 為簡單起見,只考慮如下文法生成的 布爾表達(dá)式: 布爾表達(dá)式到四元式的翻譯 e e (1) e (2) e e (1) e (2

28、) 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ùn)算的特殊性,采取某種 優(yōu)化措施,可避免計算整個表達(dá)式的值。 布爾表達(dá)式到四元式的翻譯 ab 解釋成 ab 解釋成 a 解釋成 if a then true else b if a then b else false if a then false else true 三. 布爾表達(dá)式的翻譯方法 1. 同翻譯算術(shù)表達(dá)式一樣,

29、翻譯布爾表達(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 newtemp( )； emit (if i (1).place rop.op i (2).place g

30、oto 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 if a = b goto 104 102 t1= 0 103 goto 105 1

31、04 t1= 1 105 t2= c d 106 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ù)布爾運(yùn)算的特殊 性,布爾表達(dá)式的目標(biāo)結(jié)構(gòu)為: 假 e(1)的代碼 e(2)的代碼 真 s(1)s(2) 真假 真 e(1)的代碼 e(2)的代碼 假 s(2)s(1) 假真 (1) 真出口和假出口: 真出口表示布爾表達(dá)式e為真時控

32、制 流向的轉(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 104 101 goto 102 102 if c d goto 104 103 goto ( p+1) 104 ( 關(guān)于 s(1) 的四元式) (p) goto (q) (

33、p+1) ( 關(guān)于 s(2) 的四元式) e(1)的真出口 為104, e(1)的 假出口為102 e(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

34、 a bc d then s(1) else s(2) 的四元式為: 100 if a b goto 104 101 goto 102 102 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=101 e(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

35、為鏈?zhǔn)椎膬蓷l鏈合并為一, 返回合并后的鏈?zhǔn)?(4) 鏈結(jié)函數(shù)和回填函數(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 p

36、2) if p2=0 return( p1 ) ; else p= p2 ; while ( 四元式p的第四分量內(nèi)容不為0) p=四元式p的第四分量內(nèi)容; 把p1填進(jìn)四元式p的第四分量; return( p2 ) ; 100 102 102 (q) 例如語句 if a bc d then s(1) else s(2) 的四元式為: 100 if a b goto 0 101 goto 102 102 if c d goto 100 103 goto ( p+1) 104 ( 關(guān)于 s(1) 的四元式) (p) goto (q) (p+1) ( 關(guān)于 s(2) 的四元式) 布爾表達(dá)式到四元式的翻

37、譯 布爾表達(dá)式到四元式的翻譯 bp ( int p, int t ) : 將 p 所鏈結(jié)的每個四元式的第四 區(qū)分量都回填 t ; 布爾表達(dá)式到四元式的翻譯 bp ( int p, int t ) q=p; while (q != 0 ) r = 四元式 q 的第四分量內(nèi)容; 把 t 填進(jìn)四元式 q 的第四分量; q=r ; 10 2 10 4 10 0 0 10 2 10 0 (q) 例如語句 if a bc d then s(1) else s(2) 的四元式為: 100 if a b goto 104 101 goto 102 102 if c d goto 104 103 goto (

38、p+1) 104 ( 關(guān)于 s(1) 的四元式) (p) goto (q) (p+1) ( 關(guān)于 s(2) 的四元式) 布爾表達(dá)式到四元式的翻譯 布爾表達(dá)式到四元式的翻譯 (5) 為及時回填轉(zhuǎn)移地址, 使用語義變量 e.code 記錄表達(dá)式e的第一個四元式語句 序號。 (6) 定義語義變量 next 為四元式表指針。 e (1).code=100 e (2).code=102 e .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

39、( e(1).tr, e(2).tr ) ; e.fa= e(2).fa ; 布爾表達(dá)式到四元式的翻譯 布爾表達(dá)式語義動作的設(shè)計 2. e e (1) e (2) bp( e(1).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

40、) e.tr= next ; e.code= next ; e.fa= next+1; emit ( if i (1).place rop.op i (2).place goto _ ) ; 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á)式到四元式的翻

41、譯 布爾表達(dá)式語義動作的設(shè)計 5. e i e.tr= next ; e.fa= next +1; e.code= next ; emit(if i.place goto -); emit( goto _ ) ; 5. e true 6. e false 布爾表達(dá)式到四元式的翻譯 例如布爾表達(dá)式 a bc d 的翻譯過 程如下: 布爾表達(dá)式到四元式的翻譯 a bc d e (1)c d 100 if a b goto 0 101 goto 0 e(1).tr=100 ; e(1).fa=101 ; e(1).code=100 ; e (1) e (2) 102 if c d goto 0 10

42、3 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.fa=e(2).fa=103 ; e.tr=merg(e(1).tr, e(2).tr) = merg( 100,102)=102 ; e.code= e(1).code=100 100 if a b goto 0 101 goto 0 102 if c d goto 100 103 goto 0 10 2 e (1)e (2) 歸約為e 布爾表達(dá)式到四元式的翻譯 102 if

43、c d goto 100 103 goto 0 100 if a b goto 0 101 goto 102 布爾表達(dá)式 a bc d e.tr=102 e.fa=103 簡單說明語句的翻譯 程序設(shè)計語言中，程序中的每個名 字（變量名）都必須在使用前進(jìn)行說明。 說明語句的功能就是告知編譯程序每一 個變量的類型信息。 翻譯說明語句時,設(shè)計的語義動作應(yīng) 將變量的類型信息填入符號表中。 簡單說明語句的翻譯 簡單說明語句文法 , id | id d integer real 簡單說明語句的翻譯 用上述文法的規(guī)則式進(jìn)行歸約時，按 照自下而上制導(dǎo)翻譯，首先將所有名字 id歸約為一個名字表namelist后

44、，才能將 namelist中所有名字的性質(zhì)登錄在符號表 里。這樣必須用一個隊(duì)列（或棧）來保 存namelist中的所有名字。 簡單說明語句的翻譯 我們希望在掃描過程中，每遇到一個 名字，就把它及其性質(zhì)及時登錄在符號 表中。歸約過程中涉及到這些名字及其 性質(zhì)時，就可以直接到符號表中進(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ī)定的

45、相關(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(隊(duì)列隊(duì)列queue中的每一項(xiàng)中的每一項(xiàng)p) emit(par,_,_,p); emit(call,_,_,i.place); ,e 將將e.place加入加入queue的隊(duì)尾的隊(duì)尾 e 初始化初始化queue隊(duì)列，僅包含隊(duì)列，僅包含e.place 本本 章章 小小 結(jié)結(jié) 1. 簡單算術(shù)表達(dá)式的逆波蘭式和四元 式的表示 例如 a + b * ( c + d )的逆