《編譯原理》第五章.ppt

《《編譯原理》第五章.ppt》由會員分享，可在線閱讀，更多相關(guān)《《編譯原理》第五章.ppt（193頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、編 譯 原 理Compiler Principles,蔣 凌云 南京郵電大學(xué).計(jì)算機(jī)學(xué)院,第五章 語法制導(dǎo)翻譯及中間代碼生成,教材：編譯技術(shù)原理及其實(shí)現(xiàn)方法王汝傳 編著,第五章 語法制導(dǎo)翻譯及中間代碼生成,,,本章內(nèi)容,5.1 語法制導(dǎo)翻譯概述 一、語法制導(dǎo)翻譯定義 二、語法制導(dǎo)翻譯原理 三、語法制導(dǎo)翻譯實(shí)現(xiàn) 5.2 中間語言 一、引言 二、逆波蘭表示 三、三元式 四、樹形表示 五、四元式,第五章 語法制導(dǎo)翻譯及中間代碼生成,,,本章內(nèi)容,5.3 自底向上語法制導(dǎo)翻譯 一、簡單算術(shù)表達(dá)式和賦值語句的翻譯 二、布爾表達(dá)式的翻譯 三、控制語句翻譯 *************************

2、************ 四、數(shù)組元素的翻譯 五、過程語句的翻譯 六、說明語句的翻譯 5.4 自頂向下語法制導(dǎo)翻譯 一、遞歸下降的語法制導(dǎo)翻譯 二、LL(1)語法制導(dǎo)翻譯 5.5 屬性文法與屬性翻譯 一、屬性文法與L屬性文法 二、屬性翻譯,第五章 語法制導(dǎo)翻譯及中間代碼生成,,,本節(jié)內(nèi)容,5.1 語法制導(dǎo)翻譯概述 一、語法制導(dǎo)翻譯定義 二、語法制導(dǎo)翻譯原理 三、語法制導(dǎo)翻譯實(shí)現(xiàn) 5.2 中間語言 一、引言 二、逆波蘭表示 三、三元式 四、樹形表示 五、四元式,5.1 語法制導(dǎo)翻譯概述,,,本節(jié)內(nèi)容,一、語法制導(dǎo)翻譯定義 二、語法制導(dǎo)翻譯原理 三、語法制導(dǎo)翻譯實(shí)現(xiàn),第五章 語法制導(dǎo)翻譯及中間代碼

3、生成,5.1 語法制導(dǎo)翻譯概述 在前面我們已經(jīng)討論了詞法分析和語法分析，一個程序成功地通過詞法分析和語法分析，只能說明它是一個合法程序，但是對程序內(nèi)部的邏輯含義并未加以考慮，從整個編譯程序來看，詞法分析和語法分析僅僅是編譯程序的一部分，編譯程序最終的目的是將源程序翻譯成可供計(jì)算機(jī)直接執(zhí)行的目標(biāo)程序。 在某些編譯程序中，是直接生成機(jī)器語言或匯編語言形式的目標(biāo)代碼；有些編譯程序是把源程序翻譯為某種形式中間語言代碼，然后 再把中間語言代碼翻譯為目標(biāo)代碼。 下面就來介紹一種語法制導(dǎo)翻譯方法，這種方法先將源程序單詞序列翻譯成中間語言，然后再將中間語言翻譯成目標(biāo)程序。那么，什么叫語法制導(dǎo)翻譯呢

4、？,第五章 語法制導(dǎo)翻譯及中間代碼 5.1 語法制導(dǎo)翻譯概述 一、語法制導(dǎo)翻譯定義 二、語法制導(dǎo)翻譯原理 三、語法制導(dǎo)翻譯實(shí)現(xiàn),第五章 語法制導(dǎo)翻譯及中間代碼 5.1 語法制導(dǎo)翻譯概述 一、語法制導(dǎo)翻譯定義 二、語法制導(dǎo)翻譯原理 三、語法制導(dǎo)翻譯實(shí)現(xiàn),5.1 語法制導(dǎo)翻譯概述 一、語法制導(dǎo)翻譯定義 語法制導(dǎo)翻譯就是以語法分析為主導(dǎo)的語義處理。在自頂向下語法分析 過程中嵌入語義動作，即調(diào)用對應(yīng)的語義子程序。 例如在前面語法分析時分析a+b*c表達(dá)式，其分析語法樹如下：,E,+,,,,E,E,*,,,,E,E,a,,b,,c,,語法分析是將a歸約E，再將b歸約E，將c歸約為E，然后再將E*E歸約成

5、E，再將E+E歸約成E，所以a+b*c是一個合法的句子。如果考慮語義，在歸約過程中加上語義動作，先將a歸約為E，將a值賦給E后，b歸約成E，同時將b值賦給E，在將c值賦給E，然后再將b*c（E*E）給E，最后再將左右兩個E值相加就是最終結(jié)果，這就是語法制導(dǎo)翻譯的基本思想，在語法分析同時進(jìn)行語義分析。,第五章 語法制導(dǎo)翻譯及中間代碼 5.1 語法制導(dǎo)翻譯概述 一、語法制導(dǎo)翻譯定義 二、語法制導(dǎo)翻譯原理 三、語法制導(dǎo)翻譯實(shí)現(xiàn),第五章 語法制導(dǎo)翻譯及中間代碼 5.1 語法制導(dǎo)翻譯概述 一、語法制導(dǎo)翻譯定義 二、語法制導(dǎo)翻譯原理 三、語法制導(dǎo)翻譯實(shí)現(xiàn),5.1 語法制導(dǎo)翻譯概述 二、語法制導(dǎo)翻譯原理

6、 語法制導(dǎo)翻譯的原理就是先為每個文法規(guī)定相應(yīng)的語義，即編寫出相應(yīng)語義處理子程序，整個分析是以語法分析為主導(dǎo)。在自頂向下語法分析時，若某一個規(guī)則右部與輸入串相匹配時，或者，在自底向上語法分析時，當(dāng)一個規(guī)則被用于歸約時，此時該規(guī)則對應(yīng)的語義子程序就進(jìn)入工作，完成既定翻譯任務(wù)，產(chǎn)生與語義相應(yīng)的中間代碼或目標(biāo)代碼。 語義動作：給每個文法符號X賦以各種不同的語義值 這里的語義值不一定指具體數(shù)值，可以是“類型”、“種屬”、“地址”或“代碼”等，我們用記號XTYPE、XCAT或XVAL來表示這些值。如果某規(guī)則的右部有若干個同一符號出現(xiàn)，那么我們就用上角標(biāo)來區(qū)別這些符號。例如，假定有如下規(guī)則和語義動作

7、：,例如，假定有如下規(guī)則和語義動作 ： E=E(1)+E(2) EVAL:=E(1)VAL+E(2)VAL 語義動作寫在規(guī)則之后的花括號里，這里語義動作是表明與規(guī)則左部 文法符號E相關(guān)的語義值EVAL，它是通過把規(guī)則右部文法符號的語義 值E(1)VAL和E(2)VAL加在一起來決定的，規(guī)則中終結(jié)符號“+”按語義 規(guī)則被解釋成通?！凹印钡囊馑?。各規(guī)則的語義動作可以對表達(dá)式計(jì)算，也可以生成中間代碼，甚至還可以來產(chǎn)生目標(biāo)指令。 例5.1 設(shè)有文法 E=E+E E=digit 這里digit代表0和9之間任一數(shù)字，如果我們的目的僅是為了求值，則 語義動作如下 (1) E=E(1)+E()EVAL

8、:=E(1)VAL+E(2)VAL (2) E=digit EVAL:=digit 假定語義動作中的“+”代表是整型加算術(shù)運(yùn)算。 規(guī)則(1)的語義動作為: E的語義值EVAL等于E(1) 和E(2)的語義值E(1) VAL和E(2)VAL之和. 規(guī)則(2)的語義動作為: E的語義值為09之間任一個數(shù). 這樣，按照它們的語義動作，我們在分析每個句子的同時一步一步地算出 每個句子的值 。,例如，假定有輸入串1+2+3，我們通過語法樹的分析來看如何進(jìn)行語法 制導(dǎo)翻譯，來求出該句子最后值。 輸入串1+2+3的語法樹如下圖所示：,下面我們采用自底向上歸約過程。首先考慮底層最左E的結(jié)點(diǎn)，這個 結(jié)點(diǎn)對應(yīng)于

9、規(guī)則E=1和語義動作EVAL：=1。這樣，底層最左的E的 值1與語義值EVAL相關(guān)。類似地，值2與該結(jié)點(diǎn)的右兄弟的語義值EVAL 相關(guān)。如下圖所示：,E,+,,,,E,E,+,,,,E,E,1,,2,,3,,在圖所示子樹中，子樹根處EVAL的語義值是3，這可用語義動作 EVAL:=E(1)VAL+E(2)VAL算出。使用這個語義動作時，以底部最左的E的 EVAL的值來代替E(1)VAL ，而以右邊E的EVAL的值代替E(2)VAL 。 以這種方法繼續(xù)下去，我們就推出如下圖所示整個語法樹每個結(jié)點(diǎn)的語義值。,E,+,,,,E,E VAL=1,E,1,,2,,E VAL=2,E,+,,,,E VAL

10、=6,E,E VAL=3,E,E VAL=3,+,,,,E,E VAL=1,E,E VAL=2,1,,2,,3,,第五章 語法制導(dǎo)翻譯及中間代碼 5.1 語法制導(dǎo)翻譯概述 一、語法制導(dǎo)翻譯定義 二、語法制導(dǎo)翻譯原理 三、語法制導(dǎo)翻譯實(shí)現(xiàn),第五章 語法制導(dǎo)翻譯及中間代碼 5.1 語法制導(dǎo)翻譯概述 一、語法制導(dǎo)翻譯定義 二、語法制導(dǎo)翻譯原理 三、語法制導(dǎo)翻譯實(shí)現(xiàn),5.1 語法制導(dǎo)翻譯概述 三、語法制導(dǎo)翻譯實(shí)現(xiàn) 上面我們從原則上討論了語法制導(dǎo)翻譯的原理，下面我們通 過一個自底向上LR分析看如何實(shí)現(xiàn)語法制導(dǎo)翻譯。例如： 有規(guī)則： (1)X= 動作1 (2)Y= 動作2 (3)A=XY 動作3

11、 當(dāng)使用規(guī)則(1)、(2)歸約時，動作1和動作2 工作結(jié)果的有關(guān)信息(作為X和Y的語義值)應(yīng)暫時保存下來，以便以后用規(guī)則(3)在歸約時(動作3)可引用這些值。 現(xiàn)在對LR分析器的分析棧加以擴(kuò)充，為了在語法分析過程中平行地進(jìn)行語義處理，使得每個文法符號之后都跟著它的語義值，因此，設(shè)置一個語義信息棧，為了清晰起見，我們把這個分析棧每一項(xiàng)分三部分組成：狀態(tài)STATE、文法符號SYM和語義值VAL。這樣，分析棧如下圖所示。,,,,,,TOP,STATE,VAL,SYM,,TOP(100),歸約前,,TOP(99),歸約后,YVAL,,TOP(99),求值后,AVAL:=YVAL和XVAL的處理結(jié)果

12、,我們假定先歸約后執(zhí)行語義子程序，所以當(dāng)X，Y歸約為A時，此時棧頂 指針下退。 例如：開始TOP指100 VALTOP：=Y.VAL（100） VALTOP-1：=X.VAL（99） 若歸約后，此時TOP指99，所以 VALTOP：=X.VAL（99） VALTOP+1：=Y.VAL（100） 若求值后，此時TOP指99，所以 VALTOP：=A.VAL（99）,例5.2 考慮下面文法及其語義描述： 規(guī) 則 語義動作 (0)S=E print EVAL (1)E=E(1)+E(2) EVAL:=E(1)VAL+E(2)VAL (2)E=E(1)*E(2) EVAL

13、:=E(1)VAL*E(2)VAL (3)E=(E(1)) EVAL=E(1)VAL (4)E=i EVAL:=LEXVAL 其中： 語義動作中的+、*代表整型加、乘算術(shù)運(yùn)算，而且詞法分析 程序?qū)⑺蛠砻總€i的整型內(nèi)部值LEXVAL。 假定語義動作是緊接在歸約之后執(zhí)行的。上面所列的語義動作 就相當(dāng)于下面所列的程序段：,規(guī) 則 程序段 (0)S=E print VALTOP (1)E=E(1)+E(2) VALTOP：=VALTOP+VALTOP+2 (2)E=E(1)*E(2) VALTOP：=VALTOP*VALTOP+2 (3)E=(E(1))

14、 VALTOP:=VALTOP+1 (4)E=i VALTOP:=LEXVAL,由于有一個“+“號，所以為TOP+2,由于有一個“(“號，所以為TOP+1,由于有一個”*”號，所以為TOP+2,根據(jù)上述程序段，若輸入2*3+2，就有如下圖所示的語法制導(dǎo)翻譯的分析樹。,S,E,E,E,E,E,+,,,,*,,,,2,,,2,,3,,E VAL=8,E VAL=6,E VAL=2,E VAL=2,E VAL=3,LEXVAL=2,LEXVAL=3,LEXVAL=2,對2*3+2利用P136.表4.23進(jìn)行分析和翻譯(實(shí)為計(jì)算值)該輸入串過程如下表所示。當(dāng)狀態(tài)1面臨#時對應(yīng)的分析動作為acc

15、(接受)，此時， 相應(yīng)的語義動作為print VALTOP，即輸出語義程序的計(jì)值結(jié)果：8。,第五章 語法制導(dǎo)翻譯及中間代碼生成,,,本節(jié)內(nèi)容,5.1 語法制導(dǎo)翻譯概述 一、語法制導(dǎo)翻譯定義 二、語法制導(dǎo)翻譯原理 三、語法制導(dǎo)翻譯實(shí)現(xiàn) 5.2 中間語言 一、引言 二、逆波蘭表示 三、三元式 四、樹形表示 五、四元式,第五章 語法制導(dǎo)翻譯及中間代碼生成,5.2 中間語言 一、引言 1.什么是中間語言 2.為什么要引入中間語言 二、逆波蘭表示 1.表達(dá)式逆波蘭表示 2.逆波蘭表示的擴(kuò)充 3.語法制導(dǎo)翻譯生成后綴式 三、三元式 1.三元式 2.間接三元式 四、樹形表示 1. 表示方法 2. 樹表示生成

16、 五、四元式,第五章 語法制導(dǎo)翻譯及中間代碼生成,5.2 中間語言 一、引言 1.什么是中間語言 2.為什么要引入中間語言 二、逆波蘭表示 1.表達(dá)式逆波蘭表示 2.逆波蘭表示的擴(kuò)充 3.語法制導(dǎo)翻譯生成后綴式 三、三元式 1.三元式 2.間接三元式 四、樹形表示 1. 表示方法 2. 樹表示生成 五、四元式,第五章 語法制導(dǎo)翻譯及中間代碼生成,5.2 中間語言 一、引言 1.什么是中間語言 2.為什么要引入中間語言 二、逆波蘭表示 1.表達(dá)式逆波蘭表示 2.逆波蘭表示的擴(kuò)充 3.語法制導(dǎo)翻譯生成后綴式 三、三元式 1.三元式 2.間接三元式 四、樹形表示 1. 表示方法 2. 樹表示生成 五

17、、四元式,5.2 中間語言 一、引言 1. 什么是中間語言 就是和源程序等價的一種編碼形式，其復(fù)雜性介于源程序 和機(jī)器語言中間。,源程序,前端,,,中間代碼,代碼 優(yōu)化器,,中間代碼,代碼 生成器,,目標(biāo)程序,,符號表,,,第五章 語法制導(dǎo)翻譯及中間代碼生成,5.2 中間語言 一、引言 1.什么是中間語言 2.為什么要引入中間語言 二、逆波蘭表示 1.表達(dá)式逆波蘭表示 2.逆波蘭表示的擴(kuò)充 3.語法制導(dǎo)翻譯生成后綴式 三、三元式 1.三元式 2.間接三元式 四、樹形表示 1. 表示方法 2. 樹表示生成 五、四元式,5.2 中間語言 一、引言 2. 為什么要引入中間語言 (1) 為了使編

18、譯程序結(jié)構(gòu)上邏輯簡單明確 (2) 為了便于目標(biāo)代碼優(yōu)化工作 (3) 便于目標(biāo)代碼生成,第五章 語法制導(dǎo)翻譯及中間代碼生成,5.2 中間語言 一、引言 1.什么是中間語言 2.為什么要引入中間語言 二、逆波蘭表示 1.表達(dá)式逆波蘭表示 2.逆波蘭表示的擴(kuò)充 3.語法制導(dǎo)翻譯生成后綴式 三、三元式 1.三元式 2.間接三元式 四、樹形表示 1. 表示方法 2. 樹表示生成 五、四元式,第五章 語法制導(dǎo)翻譯及中間代碼生成,5.2 中間語言 一、引言 1.什么是中間語言 2.為什么要引入中間語言 二、逆波蘭表示 1.表達(dá)式逆波蘭表示 2.逆波蘭表示的擴(kuò)充 3.語法制導(dǎo)翻譯生成后綴式 三、三元式 1.三

19、元式 2.間接三元式 四、樹形表示 1. 表示方法 2. 樹表示生成 五、四元式,第五章 語法制導(dǎo)翻譯及中間代碼生成,5.2 中間語言 一、引言 1.什么是中間語言 2.為什么要引入中間語言 二、逆波蘭表示 1.表達(dá)式逆波蘭表示 2.逆波蘭表示的擴(kuò)充 3.語法制導(dǎo)翻譯生成后綴式 三、三元式 1.三元式 2.間接三元式 四、樹形表示 1. 表示方法 2. 樹表示生成 五、四元式,5.2 中間語言 二、逆波蘭表示 1. 表達(dá)式逆波蘭表示 （1）波蘭表示的概念 對于一個算術(shù)表達(dá)式A+B或邏輯表達(dá)式AB，根據(jù)運(yùn)算符和運(yùn)算 對象的位置關(guān)系，可分為三種等價表示形式： 1) 中綴表示法 運(yùn)算符在運(yùn)算對象

20、中間，如：A+B，A B，a+b*(c+d*(e-f))等. 2) 后綴表示法 將運(yùn)算符放在運(yùn)算對象后面，通常將后綴表示稱為逆波蘭表示. 如：A+B表示為AB+，A B表示為AB，a+b*c表示為abc*+ 對于逆波蘭表示非常適合機(jī)械處理，只要從左到右按運(yùn)算順序 一個個計(jì)算下去 3) 前綴表示法 即將運(yùn)算符放在運(yùn)算對象前面。如: +AB， AB，,例如表達(dá)式中綴表示和后綴表示如下表所示(p155表5.2）,說明： 以后我們主要討論逆波蘭表示，即后綴表示，因前綴表示并不常用，所以有時也將后綴表示籠統(tǒng)地統(tǒng)稱為波蘭表示。 從上表中可以看出： (1)在中綴表示和后綴表示中，運(yùn)算對象按相同次

21、序出現(xiàn)。 (2)在后綴表示中，運(yùn)算符是按實(shí)際計(jì)算順序從左到右排列，且每一運(yùn)算符總是跟在它的運(yùn)算對象之后。,(2)逆波蘭(后綴)表示的優(yōu)點(diǎn) 1）后綴表示是一種無括號表示法，不但簡明，而且又確切規(guī) 定了計(jì)算順序。 2）運(yùn)算處理極其簡單方便，只要從左到右掃描后綴表達(dá)式 各個符號，就能進(jìn)行對表達(dá)式的處理 一般步驟是從左到右掃描后綴表達(dá)式各個符號，每碰到運(yùn)算對象時就把它推進(jìn)棧，每碰到一個K元運(yùn)算符時，就取出棧頂?shù)腒個運(yùn)算對象進(jìn)行相應(yīng)的運(yùn)算，并且用運(yùn)算結(jié)果去替換棧頂?shù)腒個運(yùn)算對象，然后再繼續(xù)掃描表達(dá)式中余留符號，如此等等，直到整個表達(dá)式計(jì)算完畢為止。 當(dāng)上述過程結(jié)束后，整個表達(dá)式之值將留于棧頂。 3

22、) 便于生成目標(biāo)指令,(3) 逆波蘭(后綴)表示的形成 為了說明逆波蘭(后綴)表示的形成，荷蘭學(xué)者 W.DEJKSTRA給出下面形象的解釋。,比棧頂高進(jìn)棧，比棧頂?shù)突蛳嗤耐藯?下面用圖解形式來說明A+B*C形成的過程。,,A,,,,運(yùn)算對象A移進(jìn)對象棧,,#,,+B*C#,,下面用圖解形式來說明A+B*C形成的過程。,,A,,,,#，向下進(jìn)運(yùn)算符棧,,#,,B*C#,,下面用圖解形式來說明A+B*C形成的過程。,,AB,,,,運(yùn)算對象B移進(jìn)對象棧,,#,,*C#,,下面用圖解形式來說明A+B*C形成的過程。,,AB,,,,*+，*向下進(jìn)運(yùn)算符棧,,*#,,C#,,下面用圖解形式來說明A+B*

23、C形成的過程。,,ABC,,,,運(yùn)算對象C移進(jìn)對象棧,,*#,,#,,下面用圖解形式來說明A+B*C形成的過程。,,ABC*,,,,#<*，*退棧往左,,#,,#,,下面用圖解形式來說明A+B*C形成的過程。,,ABC*,,,,#<，退棧往左,,#,,#,,最后生成A+B*C的后綴式ABC*,(4)用后綴表式對表達(dá)式處理的過程 下面通過求后綴表達(dá)式ab+c*的值，來說明用后綴表式對表達(dá)式處理的 過程 設(shè)a，b和c分別為1，3和5，為了求1 3+5*的值，其計(jì)算過程如下： 1)把1推進(jìn)棧。 2)把3推進(jìn)棧。 3)將棧頂兩個元素1和3相加，使它們退出棧，然后把 結(jié)果4存入棧。 4)把5推進(jìn)棧。 5

24、)將棧頂兩個元素4和5相乘，使它們退出棧，然后將 結(jié)果20存入棧。 結(jié)束時棧頂?shù)闹?這里是20)是整個表達(dá)式值。,第五章 語法制導(dǎo)翻譯及中間代碼生成,5.2 中間語言 一、引言 1.什么是中間語言 2.為什么要引入中間語言 二、逆波蘭表示 1.表達(dá)式逆波蘭表示 2.逆波蘭表示的擴(kuò)充 3.語法制導(dǎo)翻譯生成后綴式 三、三元式 1.三元式 2.間接三元式 四、樹形表示 1. 表示方法 2. 樹表示生成 五、四元式,5.2 中間語言 二、逆波蘭表示 2.逆波蘭表示的擴(kuò)充 只要遵守在運(yùn)算對象后直接緊跟運(yùn)算符這條規(guī)則，我們就可以 簡單地把這種后綴式擴(kuò)充到比通常表達(dá)式更大范圍，即擴(kuò)充到程序 語言的其它語

25、法成分。 （1）賦值語句 左部:=表達(dá)式 把賦值號“:=”看成是一個賦值運(yùn)算符，它的后綴式為 左部表達(dá)式的后綴式：= 例如：x:=5 x:=a*b-c/d 的后綴式分別為 x5:= xab*cd/-:=,賦值語句的后綴式的處理方法和后綴式表達(dá)式處理方法類似。所不同的 是棧中保存的是左部變量的地址，而不是其值，在賦值運(yùn)算處理結(jié)束后， 不產(chǎn)生任何中間計(jì)算結(jié)果，因而也不存在保存中間計(jì)算結(jié)果的問題，而是 把存放在運(yùn)算棧中棧頂兩項(xiàng)左部和表達(dá)式的值這兩個量退掉。,（2）條件語句 if E then S1 else S 對于用后綴式來表示條件語句，我們假定后綴式中各符號存放在一個 一維數(shù)組POS

26、T1n之中，每一個數(shù)組元素存放一個運(yùn)算對象或運(yùn)算符。 同時我們約定如下幾個符號： JUMP表示無條件轉(zhuǎn)； JLT表示小于轉(zhuǎn)； JEZ表示零轉(zhuǎn)。 后綴式P JUMP表示無條件轉(zhuǎn)移到下標(biāo)P所指那個元素POSTp (即從該符號開始繼續(xù)執(zhí)行)。 后綴式e P JEZ表示當(dāng)后綴表達(dá)式e的值為零時，則轉(zhuǎn)移至POSTP。 后綴式e1e2 P JLT表示當(dāng)后綴表達(dá)式e1小于后綴表達(dá)式e2時，則轉(zhuǎn)移至POSTP,于是，對于形如 if e then S1 else S2 的條件語句可按后綴式寫成ep1JEZ S1p2JUMP S2 我們約定e0時,該條件語句的值是S1,否則等于S2 。 對于后綴式條件語句中:e

27、、 S1和S2 分別是e、 S1和S2的后綴式。 此外, p1表示S2 在數(shù)組POST的起始位置, p2表示S2 之后那個符號 位置。 上述后綴式條件語句的意思是,若e=0時,則轉(zhuǎn)至POSTp1對S2 進(jìn)行計(jì)算,否則計(jì)算S1,然后轉(zhuǎn)到POSTp2的位置。 e p1 JEZ S1 p2 JUMP S2 （ p1和p2 等處理S2后再反填）,第五章 語法制導(dǎo)翻譯及中間代碼生成,5.2 中間語言 一、引言 1.什么是中間語言 2.為什么要引入中間語言 二、逆波蘭表示 1.表達(dá)式逆波蘭表示 2.逆波蘭表示的擴(kuò)充 3.語法制導(dǎo)翻譯生成后綴式 三、三元式 1.三元式 2.間接三元式 四、樹形表示 1.

28、 表示方法 2. 樹表示生成 五、四元式,5.2 中間語言 二、逆波蘭表示 3. 語法制導(dǎo)翻譯生成后綴式 下面我們討論語法制導(dǎo)翻譯生成后綴式的過程。我們以例4.15 文法GE為例，說明如何按語法制導(dǎo)翻譯方法把一個中綴形式的 簡單算術(shù)表達(dá)式翻譯成為后綴式。,后綴式的語義動作 規(guī)則 語義動作 (1) E=E(1)+T ECODE:=E(1).CODET.CODE+ (2) E=T ECODE:=TCODE (3) T=T(1)*F TCODE:=T(1)CODEFCODE* (4) T=F TCODE:=FCODE (5) F=(E) FCODE:=ECODE (6) F

29、=i FCODE:=i 幾點(diǎn)說明: E.CODE,T.CODE,F.CODE表示構(gòu)成后綴式的符號串 符號“”表示兩個串的“捻接”運(yùn)算，即并置運(yùn)算 。顯然, E(1).CODET.CODE+ 是E.CODE,因?yàn)榉栐诤?其它類似.,下面將上述語義動作具體化成語義子程序:,自底向上分析要?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的語義子程序所要完成的工作是把已生成的兩后綴式捻接起

30、來，然后再 添上符號“+”。 如果我們設(shè)置一個數(shù)組存放后綴式，那么語義動作就可以不涉及 捻接運(yùn)算。令這個數(shù)組為POST，p為下標(biāo)，初值為1。 如下圖：,,,POST(P),對于上述文法GE的語義動作，可以改寫為如下相應(yīng)的 語義子程序： (1) E=E(1)+T POSTp:=+;p:=p+1 (2) E=T (3) T=T(1)*F POSTp:=*;p:=p+1 (4) T=F (5) F=(E) (6) F=i POSTp:=i;p:=p+1,最后，我們以表達(dá)式a+b*c為例按照P118.表4.15文法GELR分析表 給出語法制導(dǎo)翻譯產(chǎn)生后綴式過程， 其

31、中SUBK表示第K個規(guī)則相對應(yīng)的語義子程序。分析過程如下表：,,第五章 語法制導(dǎo)翻譯及中間代碼生成,5.2 中間語言 一、引言 1.什么是中間語言 2.為什么要引入中間語言 二、逆波蘭表示 1.表達(dá)式逆波蘭表示 2.逆波蘭表示的擴(kuò)充 3.語法制導(dǎo)翻譯生成后綴式 三、三元式 1.三元式 2.間接三元式 四、樹形表示 1. 表示方法 2. 樹表示生成 五、四元式,第五章 語法制導(dǎo)翻譯及中間代碼生成,5.2 中間語言 一、引言 1.什么是中間語言 2.為什么要引入中間語言 二、逆波蘭表示 1.表達(dá)式逆波蘭表示 2.逆波蘭表示的擴(kuò)充 3.語法制導(dǎo)翻譯生成后綴式 三、三元式 1.三元式 2.間接三元式

32、四、樹形表示 1. 表示方法 2. 樹表示生成 五、四元式,5.2 中間語言 三、三元式表示 1.三元式 (1) 定義 三元式的一般形式為 (i) (OP, ARG1, ARG2) 其中：(i)為三元式的編號，不同三元式不能有相同的編號 OP是運(yùn)算符部分 ARG1和ARG2是運(yùn)算對象部分，它們或者指向符號表登記項(xiàng)指示 器(對于運(yùn)算對象是常數(shù)或標(biāo)識符的情況)，或者是一個指向三元式 序列(或三元式表)中某一個三元式位置的指示器(對于運(yùn)算對象是中 間結(jié)果的情況)。 如：A+B*C對應(yīng)的三元式表示為： (1) (*，B，C) (2) (+，A，(1)),注：運(yùn)算符OP通常用一個整數(shù)碼表示，

33、它除了標(biāo)識運(yùn)算符的種屬 之外，還附帶地表示其它一些語義特性。例如若OP表示一個加法 運(yùn)算符，則相應(yīng)的整數(shù)碼除了標(biāo)識加法運(yùn)算本身外，還兼有表示 數(shù)據(jù)類型(如整型、實(shí)型等)、運(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)就引用三元式(

34、1)和(2)的結(jié)果作為它的兩個運(yùn)算對象,三元式出現(xiàn)先后順序和表達(dá)式各部分計(jì)算順序相一致！,(2) 三元式的生成 同樣可以用語法制導(dǎo)翻譯來產(chǎn)生三元式： 下面給出文法GE的語義動作來描述這種翻譯的算法： (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，是一個指示器，或指向有

35、關(guān)符號 表某一項(xiàng)，或指向三元式表自身某一項(xiàng)，TRIP(OP，ARG1，ARG2)是 一個語義子程序，回送新產(chǎn)生的三元式存放在三元式表位置。 ENTRY(i)是一個語義子程序，通過ENTRY查i在符號表中位置，即 對應(yīng)地址，若查不到，認(rèn)為有錯誤。,第五章 語法制導(dǎo)翻譯及中間代碼生成,5.2 中間語言 一、引言 1.什么是中間語言 2.為什么要引入中間語言 二、逆波蘭表示 1.表達(dá)式逆波蘭表示 2.逆波蘭表示的擴(kuò)充 3.語法制導(dǎo)翻譯生成后綴式 三、三元式 1.三元式 2.間接三元式 四、樹形表示 1. 表示方法 2. 樹表示生成 五、四元式,5.2 中間語言 三、三元式表示 2. 間接三元式

36、為了便于代碼優(yōu)化，常常采用間接三元式。這由兩張表組成： （1）三元式表，用來存放各三元式本身； （2）執(zhí)行表(間接碼表)，它按執(zhí)行三元式順序，依次列出相應(yīng)各 三元式在三元式表中位置 。,例如，對于如下賦值語句 x:=a*b+c+a*b 若按三元式表示，可寫成,按間接三元式表示，則可寫成 執(zhí)行表 三元式表 (1) (1) (*,a,b) (2) (2) (+,(1),c) (1) (3) (+,(2),(1)) (3) (4) (:=,x,(3)) (4),(1) (*,a,b) (2) (+,(1),c) (3) (*,a,b) (4) (+,(2),(3)) (5) (:=

37、,x,(4)) 其中，三元式(1)和(3)完全一樣， 但是不能將(3)省去。,間接三元式的優(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)首先看一下此三元式是

38、否在其中， 如已在其中，則無需填入。,第五章 語法制導(dǎo)翻譯及中間代碼生成,5.2 中間語言 一、引言 1.什么是中間語言 2.為什么要引入中間語言 二、逆波蘭表示 1.表達(dá)式逆波蘭表示 2.逆波蘭表示的擴(kuò)充 3.語法制導(dǎo)翻譯生成后綴式 三、三元式 1.三元式 2.間接三元式 四、樹形表示 1. 表示方法 2. 樹表示生成 五、四元式,第五章 語法制導(dǎo)翻譯及中間代碼生成,5.2 中間語言 一、引言 1.什么是中間語言 2.為什么要引入中間語言 二、逆波蘭表示 1.表達(dá)式逆波蘭表示 2.逆波蘭表示的擴(kuò)充 3.語法制導(dǎo)翻譯生成后綴式 三、三元式 1.三元式 2.間接三元式 四、樹形表示 1. 表示方

39、法 2. 樹表示生成 五、四元式,5.2 中間語言 四、樹形表示 1. 表示方法 我們可以用樹形數(shù)據(jù)結(jié)構(gòu)來表示一個表達(dá)式或語句 。 在樹表示中，葉子結(jié)點(diǎn)表示運(yùn)算對象，即常量或變量，其它結(jié)點(diǎn) 表示運(yùn)算符，如表達(dá)式 a+b, a-b, -a 的樹表示分別定義為：,+,,,a,b,,,,a,b,,,a,雙目運(yùn)算對應(yīng)二叉樹，多目運(yùn)算對應(yīng)多叉樹，單目運(yùn)算對應(yīng)單叉樹 。 如表達(dá)式a*b-(c+d)/(e-f)的二叉樹如下圖：,后序遍歷上述二叉樹便得到該表達(dá)式的逆波蘭表示為 ab*cd+ef-/-,,,,*,/,,,a,b,,,+,,,,c,d,,,e,f,表達(dá)式的三元式可以看作是樹的直接表示，圖5.7所

40、對應(yīng)的三元式為 (1) (*,a,b) (2) (+,c,d) (3) (-,e,f) (4) (/,(2),(3)) (5) (-,(1),(4)) 顯然，每一個三元式對應(yīng)一棵子樹，子樹的根便是三元式的運(yùn)算符， 三元式的運(yùn)算對象是子樹兩個分枝 。,第五章 語法制導(dǎo)翻譯及中間代碼生成,5.2 中間語言 一、引言 1.什么是中間語言 2.為什么要引入中間語言 二、逆波蘭表示 1.表達(dá)式逆波蘭表示 2.逆波蘭表示的擴(kuò)充 3.語法制導(dǎo)翻譯生成后綴式 三、三元式 1.三元式 2.間接三元式 四、樹形表示 1. 表示方法 2. 樹表示生成 五、四元式,5.2 中間語言 四、樹形表示 2. 樹表示生成

41、對文GE翻譯成樹形表示語義動作描述如下： (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ù)一次

42、,就建立一個新結(jié)點(diǎn)，其標(biāo)記為OP， LEFT和RIGHT分別指向左右子樹根結(jié)點(diǎn)指針，從NODE回送 的值是一個指示器，指向這棵新樹的根。 LEAF(i)是建立一個末端結(jié)點(diǎn)(葉結(jié)點(diǎn)),第五章 語法制導(dǎo)翻譯及中間代碼生成,5.2 中間語言 一、引言 1.什么是中間語言 2.為什么要引入中間語言 二、逆波蘭表示 1.表達(dá)式逆波蘭表示 2.逆波蘭表示的擴(kuò)充 3.語法制導(dǎo)翻譯生成后綴式 三、三元式 1.三元式 2.間接三元式 四、樹形表示 1. 表示方法 2. 樹表示生成 五、四元式,第五章 語法制導(dǎo)翻譯及中間代碼生成,5.2 中間語言 一、引言 1.什么是中間語言 2.為什么要引入中間語言

43、 二、逆波蘭表示 1.表達(dá)式逆波蘭表示 2.逆波蘭表示的擴(kuò)充 3.語法制導(dǎo)翻譯生成后綴式 三、三元式 1.三元式 2.間接三元式 四、樹形表示 1. 表示方法 2. 樹表示生成 五、四元式,5.2 中間語言 五、四元式表示 四元式是一種用得比較多的一種中間語言代碼形式，四元式 一般形式是 (OP，ARG1，ARG2，RESULT) 其中：OP是運(yùn)算符，其含義與三元式中OP類似； ARG1和ARG2是運(yùn)算對象， RESULT是運(yùn)算結(jié)果,例如：賦值語句 a:=-b*(c+d) 用四元式表示，則可寫成 (1) ( - , b,,T1) (2) (+,c,d,T2) (3) (*,T1,T2,T3

44、) (4) (:=,T3, ,a),,四元式之間聯(lián)系是通過臨時變量實(shí)現(xiàn) 的，調(diào)整四元式之間相對位置并不 意味著一定要改變一系列指示器值。 因此，對中間代碼進(jìn)行優(yōu)化處理時， 四元式比三元式方便得多。 下面主要討論如何用四元式表示 各種語句，并產(chǎn)生四元式語義子程序。,第五章 語法制導(dǎo)翻譯及中間代碼生成,,,本節(jié)內(nèi)容,5.3 自底向上語法制導(dǎo)翻譯 一、簡單算術(shù)表達(dá)式和賦值語句的翻譯 二、布爾表達(dá)式的翻譯 三、控制語句翻譯 四、數(shù)組元素的翻譯 五、過程語句的翻譯 六、說明語句的翻譯 5.4 自頂向下語法制導(dǎo)翻譯 一、遞歸下降的語法制導(dǎo)翻譯 二、LL(1)語法制導(dǎo)翻譯 5.5 屬性文法與屬性翻譯 一、屬

45、性文法與L屬性文法 二、屬性翻譯,第五章 語法制導(dǎo)翻譯及中間代碼生成 5.3 自底向上語法制導(dǎo)翻譯,一、簡單算術(shù)表達(dá)式和賦 值語句的翻譯 1. 翻譯成四元式 2. 類型檢查與類型轉(zhuǎn)換 二、布爾表達(dá)式的翻譯 1. 概述 2.布爾表達(dá)式的翻譯方法 3.翻譯成四元式的實(shí)現(xiàn) 三、控制語句翻譯 1.語句標(biāo)號和goto語句的翻譯 2.條件語句的翻譯 3.布爾表達(dá)式的翻譯方法 4.while循環(huán)語句翻譯 5.for循環(huán)語句的翻譯,四、數(shù)組元素的翻譯 1. 下標(biāo)變量地址的計(jì)算 2.數(shù)組元素的翻譯 五、過程語句的翻譯 1.參數(shù)傳遞方式 2.過程語句的翻譯 六、說明語句的翻譯 1.變量說明的翻譯 2.數(shù)組說明

46、的翻譯 3.過程說明的翻譯,,第五章 語法制導(dǎo)翻譯及中間代碼生成 5.3 自底向上語法制導(dǎo)翻譯,一、簡單算術(shù)表達(dá)式和賦 值語句的翻譯 1. 翻譯成四元式 2. 類型檢查與類型轉(zhuǎn)換 二、布爾表達(dá)式的翻譯 1. 概述 2.布爾表達(dá)式的翻譯方法 3.翻譯成四元式的實(shí)現(xiàn) 三、控制語句翻譯 1.語句標(biāo)號和goto語句的翻譯 2.條件語句的翻譯 3.布爾表達(dá)式的翻譯方法 4.while循環(huán)語句翻譯 5.for循環(huán)語句的翻譯,四、數(shù)組元素的翻譯 1. 下標(biāo)變量地址的計(jì)算 2.數(shù)組元素的翻譯 五、過程語句的翻譯 1.參數(shù)傳遞方式 2.過程語句的翻譯 六、說明語句的翻譯 1.變量說明的翻譯 2.數(shù)組說明的翻

47、譯 3.過程說明的翻譯,,第五章 語法制導(dǎo)翻譯及中間代碼生成 5.3 自底向上語法制導(dǎo)翻譯,一、簡單算術(shù)表達(dá)式和賦 值語句的翻譯 1. 翻譯成四元式 2. 類型檢查與類型轉(zhuǎn)換 二、布爾表達(dá)式的翻譯 1. 概述 2.布爾表達(dá)式的翻譯方法 3.翻譯成四元式的實(shí)現(xiàn) 三、控制語句翻譯 1.語句標(biāo)號和goto語句的翻譯 2.條件語句的翻譯 3.布爾表達(dá)式的翻譯方法 4.while循環(huán)語句翻譯 5.for循環(huán)語句的翻譯,四、數(shù)組元素的翻譯 1. 下標(biāo)變量地址的計(jì)算 2.數(shù)組元素的翻譯 五、過程語句的翻譯 1.參數(shù)傳遞方式 2.過程語句的翻譯 六、說明語句的翻譯 1.變量說明的翻譯 2.數(shù)組說明的翻譯

48、3.過程說明的翻譯,,5.3 自底向上語法制導(dǎo)翻譯 一、簡單算術(shù)表達(dá)式和賦值語句的翻譯 1. 翻譯成四元式 我們首先討論僅含有簡單變量的表達(dá)式和賦值語句到四元式的翻譯，對于復(fù)雜的表達(dá)式和賦值語句的翻譯將在以后討論 。 為簡便起見，假定賦值語句中所含的全部變量是同一類型整型變量，此外在翻譯過程中也不作語義檢查。 (1) 賦值語句的文法 1) A=V:=E 5)T=F 2) E=E (1)+T 6)F=(E) 3) E=T 7)F=i 4) T=T(1)*F 8)V=i 為了實(shí)現(xiàn)到四元式的翻譯，需要引進(jìn)一系列語義變量和語義子程序。,(2)語義變量和語義子程序 NEWTEMP是一

49、個函數(shù)，每次調(diào)用時，都定義一個新臨時變量，回送 一個代表新臨時變量名的整數(shù)碼作為函數(shù)值。為直觀起見，我們將 NEWTEMP產(chǎn)生的臨時變量依次記為T，等等。 ENTRY(i)是一個函數(shù)過程 ，查找符號名i在表中的入口地址。 XPLACE是和非終結(jié)符X相聯(lián)系的語義變量，表示存放X值的變量名在 符號表的入口或整數(shù)碼(若此變量是一個臨時變量)。 如： F=i FPLACE:=ENTRY(i) 表示存放F值變量名i在符號表 中的入口地址。即從變量F.PLACE值可知i在符號表中的位置。 GEN (OP，ARG1，ARG2，RESULT)是一個語義過程，該過程把四元式 (OP，ARG1，ARG

50、2，RESULT)填入四元式表中。,因此，上面定義文法GA語義子程序的描述如下：,(3)語義子程序的描述 (1) A=V:=E GEN(:=,EPLACE, ,VPLACE) (2)E=E(1)+T EPLACE:=NEWTEMP; GEN(+,E(1)PLACE,TPLACE,EPLACE) (3) E=T EPLACE:=TPLACE (4) T=T(1)*F TPLACE:=NEWTEMP; GEN(*,T(1)PLACE,FPLACE,TPLACE) (5) T=F TPLACE:=FPLACE (6) F=(E) FPLACE:=EPLACE

51、 (7) F=i FPLACE:=ENTRY(i) (8) V=i VPLACE:=ENTRY(i),在進(jìn)行自底向上語法制導(dǎo)翻譯時，還需一張LR分析表，上述文法GA 是一個SLR(1)文法，其分析表如下：,（4）文法GASLR(1)分析表,（5）對x:=a+b*c語法制導(dǎo)翻譯產(chǎn)生四元式過程（以賦值語句x:=a+b*c為例）,,分析表幾點(diǎn)說明： 在分析表中Vx,Ea,Tb,Fc之類記號，表示與非終結(jié)符V,E,T,F相關(guān)聯(lián) 的VPLACE,E.PLACE,T.PLACE,F.PLACE中存放著ENTRY(x), ENTRY(a), ENTRY(b), ENTRY(c) 符號指針，指向符號表

52、。 在四元式中，如（*，b,c,T1)，*實(shí)際上是某種整數(shù)編碼，反映 運(yùn)算符本身及其信息特征，如類型等。 b, c實(shí)際上也是指示器，指示符號表入口；T1是臨時變量，實(shí)際上 也是整數(shù)碼. 下面我們根據(jù)上面分析表敘述對x:=a+b*c語法制導(dǎo)翻譯產(chǎn)生四元式過程,第五章 語法制導(dǎo)翻譯及中間代碼生成 5.3 自底向上語法制導(dǎo)翻譯,一、簡單算術(shù)表達(dá)式和賦 值語句的翻譯 1. 翻譯成四元式 2. 類型檢查與類型轉(zhuǎn)換 二、布爾表達(dá)式的翻譯 1. 概述 2.布爾表達(dá)式的翻譯方法 3.翻譯成四元式的實(shí)現(xiàn) 三、控制語句翻譯 1.語句標(biāo)號和goto語句的翻譯 2.條件語句的翻譯 3.布爾表達(dá)式的翻譯方法 4.w

53、hile循環(huán)語句翻譯 5.for循環(huán)語句的翻譯,四、數(shù)組元素的翻譯 1. 下標(biāo)變量地址的計(jì)算 2.數(shù)組元素的翻譯 五、過程語句的翻譯 1.參數(shù)傳遞方式 2.過程語句的翻譯 六、說明語句的翻譯 1.變量說明的翻譯 2.數(shù)組說明的翻譯 3.過程說明的翻譯,,5.3 自底向上語法制導(dǎo)翻譯 一、簡單算術(shù)表達(dá)式和賦值語句的翻譯 2. 類型檢查與類型轉(zhuǎn)換 (1)目的 1) 類型檢查是編譯程序語義檢查不可缺少的一部分。 類型檢查就是對訪問數(shù)據(jù)的操作和被訪問數(shù)據(jù)的類型進(jìn)行檢查 檢查操作的合法性和數(shù)據(jù)類型的相容性。例如，在PASCAL語言中， 若算術(shù)運(yùn)算符的操作數(shù)為布爾量，或者賦給實(shí)型變量值是個指針， 則編譯

54、程序報告“類型不相容”的診斷信息。 2)允許類型混合，但在處理時要統(tǒng)一，所以必須進(jìn)行類型轉(zhuǎn)換。 例如，加法運(yùn)算“+”允許運(yùn)算對象是整型數(shù)或?qū)嵭蛿?shù),如果一個 運(yùn)算對象是實(shí)型，另一個運(yùn)算對象是整型，其運(yùn)算結(jié)果的類型是實(shí) 型，由于實(shí)型數(shù)和整型數(shù)的內(nèi)部表示不相同，因此為了使整型數(shù)能 參加實(shí)型數(shù)運(yùn)算，必須事先將整型數(shù)轉(zhuǎn)換成實(shí)型數(shù)。,(2)類型檢查 類型檢查可在生成中間代碼時進(jìn)行，也可在生成目標(biāo)代碼時進(jìn)行，但最好是在生成中間代碼時進(jìn)行，因?yàn)檎Z法和語義檢查最好盡早進(jìn)行，這樣能盡早避免徒勞的工作。 在上面對簡單算術(shù)表達(dá)式和賦值語句翻譯到四元式的討論中，我們假定各個變量是同一類型整型變量，并且規(guī)定在四元式的

55、op代碼中，本身就會有類型信息。所以，在上例各語義子程序中，我們并未考慮有關(guān)類型方面語義處理。,（3）類型轉(zhuǎn)換方法 為了簡單起見，我們僅考慮整型和實(shí)型的情況。 這種混合運(yùn)算中，給每個非終結(jié)符的語義值增添類型信息X.MODE XMODE的值或?yàn)閞(實(shí)型)或?yàn)閕nt(整型)。 原來X的信息除X.PLACE， 還有X.MODE。 對表達(dá)式的每一規(guī)則的語義子程序進(jìn)行修改，增加關(guān)于類型 信息的語義規(guī)則 。 必要時應(yīng)產(chǎn)生對運(yùn)算量進(jìn)行類型轉(zhuǎn)換的四元式 ， (itr,A,,T) 把整型變量A轉(zhuǎn)換成實(shí)型變量，結(jié)果存在T中。,此外，在書寫語義子程序時，為閱讀上的直觀性，我們用+i,*i等 表示整型運(yùn)算符，用+r

56、,*r等表示實(shí)型運(yùn)算符。 現(xiàn)以規(guī)則E=E(1)OP E(2)為例，給出語義子程序的具體描述如下：,現(xiàn)以規(guī)則E=E(1)OP E(2)為例，給出語義子程序的具體描述如下： T:=NEWTEMP; IF E(1)MODE=int AND E(2)MODE=int THEN BEGIN GEN(opi,E(1)PLACE,E(2)PLACE,T); EMODE:=int END ELSE IF E(1)MODE=r AND E(2)MODE=r THEN BEGIN GEN (opr,E(1)PLACE,E(2)PLACE,T); EMODE:=r END ELSE IF E(1)MODE=in

57、t/*and E(2)MODE=r*/THEN BEGIN U:=NEWTEMP; 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í)型量,則產(chǎn)生四元式序列為,(it

58、r,2,-,T1) (*r,X,T,T) (+i,I,1,T3) (itr,T3,-,T) (*r,A,T4,T5) (+r,T2,T5,T6),第五章 語法制導(dǎo)翻譯及中間代碼生成 5.3 自底向上語法制導(dǎo)翻譯,一、簡單算術(shù)表達(dá)式和賦 值語句的翻譯 1. 翻譯成四元式 2. 類型檢查與類型轉(zhuǎn)換 二、布爾表達(dá)式的翻譯 1. 概述 2.布爾表達(dá)式的翻譯方法 3.翻譯成四元式的實(shí)現(xiàn) 三、控制語句翻譯 1.語句標(biāo)號和goto語句的翻譯 2.條件語句的翻譯 3.布爾表達(dá)式的翻譯方法 4.while循環(huán)語句翻譯 5.for循環(huán)語句的翻譯,四、數(shù)組元素的翻譯 1. 下標(biāo)變量地址的計(jì)算 2.數(shù)組元素的翻譯

59、 五、過程語句的翻譯 1.參數(shù)傳遞方式 2.過程語句的翻譯 六、說明語句的翻譯 1.變量說明的翻譯 2.數(shù)組說明的翻譯 3.過程說明的翻譯,,第五章 語法制導(dǎo)翻譯及中間代碼生成 5.3 自底向上語法制導(dǎo)翻譯,一、簡單算術(shù)表達(dá)式和賦 值語句的翻譯 1. 翻譯成四元式 2. 類型檢查與類型轉(zhuǎn)換 二、布爾表達(dá)式的翻譯 1. 概述 2.布爾表達(dá)式的翻譯方法 3.翻譯成四元式的實(shí)現(xiàn) 三、控制語句翻譯 1.語句標(biāo)號和goto語句的翻譯 2.條件語句的翻譯 3.布爾表達(dá)式的翻譯方法 4.while循環(huán)語句翻譯 5.for循環(huán)語句的翻譯,四、數(shù)組元素的翻譯 1. 下標(biāo)變量地址的計(jì)算 2.數(shù)組元素的翻譯 五

60、、過程語句的翻譯 1.參數(shù)傳遞方式 2.過程語句的翻譯 六、說明語句的翻譯 1.變量說明的翻譯 2.數(shù)組說明的翻譯 3.過程說明的翻譯,,5.3 自底向上語法制導(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ì)語言中，布爾表達(dá)式有兩個基本用途: 1）一個是求邏輯值，邏輯值的結(jié)果是真或假。 2）另一個用得最多的是在控制語句中用作條件表達(dá)式， 例如，在if-then、if-then-else

61、和while-do語句里表示控制條件。,(2)布爾表達(dá)式的文法 布爾表達(dá)式文法GE如下 : E=EE|EE| E|(E)|i|i rop i 說明： 1）布爾表達(dá)式的文法是一個二義文法 例如：該文法的一個句子a b c有兩棵不同的語法樹與之對應(yīng)，所以該文法是一個二義文法。,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)先級相同,且高于任何布爾運(yùn)算符,低于算術(shù)運(yùn)算符。 3）i可認(rèn)為是布爾表達(dá)式也可視為數(shù)值（1為真true,0為假false)。 4） i rop

62、 i 中rop是關(guān)系運(yùn)算符，i是布爾變量或算術(shù)值,(3)布爾表達(dá)式求值方法 1）把真和假數(shù)值化，使布爾表達(dá)式計(jì)算類似于算術(shù)表達(dá)式的計(jì)算， 常用1表示真，0表示假，或者用非零整數(shù)表示真 。 如：1（ 00）0= 1（10）0= 100=1 2）采取某種優(yōu)化措施，有時并不需要將一個布爾表達(dá)式從頭算到尾， 而只須計(jì)算它的一個子表達(dá)式，便能確定整個布爾表達(dá)式真和假。 例如，對于AB，只要計(jì)算出A為真，則不管B值如何，AB之值 一定為真。又如對AB，只要計(jì)算出A為假，則AB必然為假，等等。 對于三種邏輯運(yùn)算，可作如下等價的解釋： AB: if A then true else B AB: if

63、A then B else false A: if A then false else true 用這種方式實(shí)現(xiàn)控制語句的布爾表達(dá)式尤其方便。對應(yīng)上述兩種 計(jì)算方法，其布爾表達(dá)式有兩種不同的翻譯方法。,第五章 語法制導(dǎo)翻譯及中間代碼生成 5.3 自底向上語法制導(dǎo)翻譯,一、簡單算術(shù)表達(dá)式和賦 值語句的翻譯 1. 翻譯成四元式 2. 類型檢查與類型轉(zhuǎn)換 二、布爾表達(dá)式的翻譯 1. 概述 2.布爾表達(dá)式的翻譯方法 3.翻譯成四元式的實(shí)現(xiàn) 三、控制語句翻譯 1.語句標(biāo)號和goto語句的翻譯 2.條件語句的翻譯 3.布爾表達(dá)式的翻譯方法 4.while循環(huán)語句翻譯 5.for循環(huán)語句的翻譯,四、數(shù)組

64、元素的翻譯 1. 下標(biāo)變量地址的計(jì)算 2.數(shù)組元素的翻譯 五、過程語句的翻譯 1.參數(shù)傳遞方式 2.過程語句的翻譯 六、說明語句的翻譯 1.變量說明的翻譯 2.數(shù)組說明的翻譯 3.過程說明的翻譯,,5.3 自底向上語法制導(dǎo)翻譯 二、布爾表達(dá)式的翻譯 2.布爾表達(dá)式的翻譯方法 （1）如同翻譯算術(shù)表達(dá)式一樣，用于求值 例如， 布爾表達(dá)式 a(bc=d)將被翻譯成如下四元式： 1) ( ,a,-,T1) 2) (=,c,d,T2) 3) (,b,T2,T3) 4) (,T1,T3,T4),仿照翻譯算術(shù)表達(dá)式的方法，很容易寫出布爾表達(dá)式文法GE的 每個規(guī)則用于求值的語義動作 。 (1) E

65、= 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:=NEWTEM

66、P; GEN(rop,ENTRY(i(1)),ENTRY(i(2)),E.PLACE),(2)作為條件控制的布爾表達(dá)式的翻譯 1)布爾表達(dá)式E作為條件控制的代碼結(jié)構(gòu) 對于條件語句 if E then S1 else S2 中布爾表達(dá)式E，它的作用就是控制S1和S2的選擇，我們賦于E代碼 兩種出口，其一為“真出口”，另一個是“假出口”，它們分別指出 當(dāng)E值為true和false時，控制轉(zhuǎn)向的目標(biāo)(即某一四元式所在位置或 序號)。條件語句可翻譯成如下圖：,E的代碼,S1的代碼,,,,,true,,,false,S2的代碼,,,,2)三種形式的四元式 作為條件控制的布爾表達(dá)式E的翻譯歸納起來只有三種形式的四元式 (jnz, a1, ,p) 若a1為真時,則轉(zhuǎn)向第p個四元式。 (jrop,a1,a2, p) 若關(guān)系a1 rop a2成立時,轉(zhuǎn)向第p個四元式。 (j, , ,p) 無條件轉(zhuǎn)向第p個四元式。 除上述兩種真轉(zhuǎn)外，可用無條件表示假轉(zhuǎn),例如,對于條件語句 if ab < c then S1 else S2 經(jīng)翻譯后，可得如下四元式序列： (1) (jnz,a, ,5) (2