編譯原理第五章

編譯原理

CompilerPrinciples徐佳xujia@教學(xué)網(wǎng)站：南京郵電大學(xué).計(jì)算機(jī)學(xué)院

第五章語法制導(dǎo)翻譯及中間代碼生成compilingrunningprogramming教材：《編譯技術(shù)原理及其實(shí)現(xiàn)方法》王汝傳編著1第五章語法制導(dǎo)翻譯及中間代碼生成本章內(nèi)容§5.1語法制導(dǎo)翻譯概述一、語法制導(dǎo)翻譯定義二、語法制導(dǎo)翻譯原理三、語法制導(dǎo)翻譯實(shí)現(xiàn)§5.2中間語言一、引言二、逆波蘭表示三、三元式四、樹形表示五、四元式2第五章語法制導(dǎo)翻譯及中間代碼生成本章內(nèi)容§5.3自底向上語法制導(dǎo)翻譯一、簡單算術(shù)表達(dá)式和賦值語句的翻譯二、布爾表達(dá)式的翻譯三、控制語句翻譯*************************************四、數(shù)組元素的翻譯五、過程語句的翻譯六、說明語句的翻譯§5.4自頂向下語法制導(dǎo)翻譯

一、遞歸下降的語法制導(dǎo)翻譯二、LL(1)語法制導(dǎo)翻譯§5.5屬性文法與屬性翻譯一、屬性文法與L屬性文法二、屬性翻譯3第五章語法制導(dǎo)翻譯及中間代碼生成本節(jié)內(nèi)容§5.1語法制導(dǎo)翻譯概述一、語法制導(dǎo)翻譯定義二、語法制導(dǎo)翻譯原理三、語法制導(dǎo)翻譯實(shí)現(xiàn)§5.2中間語言一、引言二、逆波蘭表示三、三元式四、樹形表示五、四元式4§5.1語法制導(dǎo)翻譯概述

本節(jié)內(nèi)容一、語法制導(dǎo)翻譯定義

二、語法制導(dǎo)翻譯原理

三、語法制導(dǎo)翻譯實(shí)現(xiàn)5第五章語法制導(dǎo)翻譯及中間代碼生成§5.1語法制導(dǎo)翻譯概述

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

一、語法制導(dǎo)翻譯定義

二、語法制導(dǎo)翻譯原理

三、語法制導(dǎo)翻譯實(shí)現(xiàn)7第五章語法制導(dǎo)翻譯及中間代碼§5.1語法制導(dǎo)翻譯概述

一、語法制導(dǎo)翻譯定義

二、語法制導(dǎo)翻譯原理

三、語法制導(dǎo)翻譯實(shí)現(xiàn)8§5.1語法制導(dǎo)翻譯概述

一、語法制導(dǎo)翻譯定義

語法制導(dǎo)翻譯就是以語法分析為主導(dǎo)的語義處理。語法分析過程中嵌入語義動作，即調(diào)用對應(yīng)的語義子程序。例如在前面語法分析時分析a+b*c表達(dá)式，其分析語法樹如下：E+EE*EEabc語法分析是將a歸約E，再將b歸約E，將c歸約為E，然后再將E*E歸約成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)行語義分析。9第五章語法制導(dǎo)翻譯及中間代碼§5.1語法制導(dǎo)翻譯概述

一、語法制導(dǎo)翻譯定義

二、語法制導(dǎo)翻譯原理

三、語法制導(dǎo)翻譯實(shí)現(xiàn)10第五章語法制導(dǎo)翻譯及中間代碼§5.1語法制導(dǎo)翻譯概述

一、語法制導(dǎo)翻譯定義

二、語法制導(dǎo)翻譯原理

三、語法制導(dǎo)翻譯實(shí)現(xiàn)11§5.1語法制導(dǎo)翻譯概述

二、語法制導(dǎo)翻譯原理

語法制導(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ù)值，可以是“類型”、“種屬”、“地址”或“代碼”等，我們用記號X·TYPE、X·CAT或X·VAL來表示這些值。如果某規(guī)則的右部有若干個同一符號出現(xiàn)，那么我們就用上角標(biāo)來區(qū)別這些符號。例如，假定有如下規(guī)則和語義動作：12例如，假定有如下規(guī)則和語義動作：E∷=E(1)+E(2){E·VAL:=E(1)·VAL+E(2)·VAL}語義動作寫在規(guī)則之后的花括號里，這里語義動作是表明與規(guī)則左部文法符號E相關(guān)的語義值E·VAL，它是通過把規(guī)則右部文法符號的語義值E(1)·VAL和E(2)·VAL加在一起來決定的，規(guī)則中終結(jié)符號“+”按語義規(guī)則被解釋成通?！凹印钡囊馑?。各規(guī)則的語義動作可以對表達(dá)式計(jì)算，也可以生成中間代碼，甚至還可以來產(chǎn)生目標(biāo)指令。例5.1設(shè)有文法E∷=E+EE∷=digit這里digit代表0和9之間任一數(shù)字，如果我們的目的僅是為了求值，則語義動作如下(1)E∷=E(1)+E(２){E·VAL:=E(1)·VAL+E(2)·VAL}(2)E∷=digit{E·VAL:=digit}假定語義動作中的“+”代表是整型加算術(shù)運(yùn)算。規(guī)則(1)的語義動作為:E的語義值E·VAL等于E(1)和E(2)的語義值E(1)·VAL和E(2)·VAL之和.規(guī)則(2)的語義動作為:E的語義值為0～9之間任一個數(shù).這樣，按照它們的語義動作，我們在分析每個句子的同時一步一步地算出每個句子的值。13例如，假定有輸入串1+2+3，我們通過語法樹的分析來看如何進(jìn)行語法制導(dǎo)翻譯，來求出該句子最后值。輸入串1+2+3的語法樹如下圖所示：下面我們采用自底向上歸約過程。首先考慮底層最左E的結(jié)點(diǎn)，這個結(jié)點(diǎn)對應(yīng)于規(guī)則E∷=1和語義動作E·VAL：=1。這樣，底層最左的E的值1與語義值E·VAL相關(guān)。類似地，值2與該結(jié)點(diǎn)的右兄弟的語義值E·VAL相關(guān)。如下圖所示：E+EE+EE12314

在圖所示子樹中，子樹根處E·VAL的語義值是3，這可用語義動作E·VAL:=E(1)·VAL+E(2)·VAL算出。使用這個語義動作時，以底部最左的E的E·VAL的值來代替E(1)·VAL，而以右邊E的E·VAL的值代替E(2)·VAL。以這種方法繼續(xù)下去，我們就推出如下圖所示整個語法樹每個結(jié)點(diǎn)的語義值。

E+EE?VAL=1E12E?VAL=215E+E?VAL=6EE?VAL=3EE?VAL=3+EE?VAL=1EE?VAL=212316第五章語法制導(dǎo)翻譯及中間代碼§5.1語法制導(dǎo)翻譯概述

一、語法制導(dǎo)翻譯定義

二、語法制導(dǎo)翻譯原理

三、語法制導(dǎo)翻譯實(shí)現(xiàn)17第五章語法制導(dǎo)翻譯及中間代碼§5.1語法制導(dǎo)翻譯概述

一、語法制導(dǎo)翻譯定義

二、語法制導(dǎo)翻譯原理

三、語法制導(dǎo)翻譯實(shí)現(xiàn)18§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}當(dāng)使用規(guī)則(1)、(2)歸約時，{動作1}和{動作2}工作結(jié)果的有關(guān)信息(作為X和Y的語義值)應(yīng)暫時保存下來，以便以后用規(guī)則(3)在歸約時(動作3)可引用這些值?，F(xiàn)在對LR分析器的分析棧加以擴(kuò)充，為了在語法分析過程中平行地進(jìn)行語義處理，使得每個文法符號之后都跟著它的語義值，因此，設(shè)置一個語義信息棧，為了清晰起見，我們把這個分析棧每一項(xiàng)分三部分組成：狀態(tài)STATE、文法符號SYM和語義值VAL。這樣，分析棧如下圖所示。

19SmY?VALYSm-1X?VALXS0－#………TOPSTATEVALSYM20SmSm-1Y?VALX?VALYXTOP(100)歸約前SiX?VALATOP(99)歸約后Y?VALSiA?VALATOP(99)求值后A?VAL:=Y?VAL和X?VAL的處理結(jié)果我們假定先歸約后執(zhí)行語義子程序，所以當(dāng)X，Y歸約為A時，此時棧頂指針下退。例如：開始TOP指100VAL[TOP]：=Y.VAL（100）VAL[TOP-1]：=X.VAL（99）若歸約后，此時TOP指99，所以VAL[TOP]：=X.VAL（99）VAL[TOP+1]：=Y.VAL（100）若求值后，此時TOP指99，所以VAL[TOP]：=A.VAL（99）21例5.2考慮下面文法及其語義描述：

規(guī)則語義動作(0)S′∷=E{printE·VAL}(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∷=i{E·VAL:=LEXVAL}其中：語義動作中的+、*代表整型加、乘算術(shù)運(yùn)算，而且詞法分析程序?qū)⑺蛠砻總€i的整型內(nèi)部值LEXVAL。

假定語義動作是緊接在歸約之后執(zhí)行的。上面所列的語義動作就相當(dāng)于下面所列的程序段：

22規(guī)則程序段(0)S′∷=E{printVAL［TOP］}(1)E∷=E(1)+E(2){VAL[TOP]：=VAL[TOP]+VAL[TOP+2]}(2)E∷=E(1)*E(2){VAL[TOP]：=VAL[TOP]*VAL[TOP+2]}(3)E∷=(E(1)){VAL［TOP］:=VAL［TOP+1］}(4)E∷=i{VAL［TOP］:=LEXVAL}23根據(jù)上述程序段，若輸入2*3+2，就有如下圖所示的語法制導(dǎo)翻譯的分析樹。S’EEEEE+*223E?VAL=8E?VAL=6E?VAL=2E?VAL=2E?VAL=3LEXVAL=2LEXVAL=3LEXVAL=224對2*3+2利用P136.表4.23進(jìn)行分析和翻譯(實(shí)為計(jì)算值)該輸入串過程如下表所示。當(dāng)狀態(tài)1面臨#時對應(yīng)的分析動作為acc(接受)，此時，相應(yīng)的語義動作為printVAL[TOP]，即輸出語義程序的計(jì)值結(jié)果：8。步驟狀態(tài)棧語義值棧符號棧輸入串歸約規(guī)則及動作10－＃2*3+2＃S3203－－＃2*3+2＃r4301－2＃E*3+2＃GOTO[0,E]=1,S54015－2－＃E*3+2＃S350153－2－－＃E*3+2＃r460158－2－3＃E*E+2＃GOTO[5,E]=8,r2701－6＃E+2＃GOTO[0,E]=1,S48014－6－＃E+2＃S390143－6－－＃E+2＃r4100147－6－2＃E+E＃GOTO[4,E]=7,r11101－8＃E＃acc25第五章語法制導(dǎo)翻譯及中間代碼生成本節(jié)內(nèi)容§5.1語法制導(dǎo)翻譯概述一、語法制導(dǎo)翻譯定義二、語法制導(dǎo)翻譯原理三、語法制導(dǎo)翻譯實(shí)現(xiàn)§5.2中間語言一、引言二、逆波蘭表示三、三元式四、樹形表示五、四元式26第五章語法制導(dǎo)翻譯及中間代碼生成§5.2中間語言

一、引言1.什么是中間語言2.為什么要引入中間語言二、逆波蘭表示1.表達(dá)式逆波蘭表示2.逆波蘭表示的擴(kuò)充3.語法制導(dǎo)翻譯生成后綴式三、三元式1.三元式2.間接三元式

四、樹形表示1.表示方法

2.樹表示生成

五、四元式27第五章語法制導(dǎo)翻譯及中間代碼生成§5.2中間語言

一、引言

1.什么是中間語言2.為什么要引入中間語言二、逆波蘭表示1.表達(dá)式逆波蘭表示2.逆波蘭表示的擴(kuò)充3.語法制導(dǎo)翻譯生成后綴式三、三元式1.三元式2.間接三元式

四、樹形表示1.表示方法

2.樹表示生成

五、四元式28第五章語法制導(dǎo)翻譯及中間代碼生成§5.2中間語言

一、引言1.什么是中間語言

2.為什么要引入中間語言二、逆波蘭表示1.表達(dá)式逆波蘭表示2.逆波蘭表示的擴(kuò)充3.語法制導(dǎo)翻譯生成后綴式三、三元式1.三元式2.間接三元式

四、樹形表示1.表示方法

2.樹表示生成

五、四元式29§5.2中間語言

一、引言1.什么是中間語言

就是和源程序等價的一種編碼形式，其復(fù)雜性介于源程序和機(jī)器語言中間。源程序前端中間代碼代碼優(yōu)化器中間代碼代碼生成器目標(biāo)程序符號表30第五章語法制導(dǎo)翻譯及中間代碼生成§5.2中間語言

一、引言

1.什么是中間語言2.為什么要引入中間語言

二、逆波蘭表示1.表達(dá)式逆波蘭表示2.逆波蘭表示的擴(kuò)充3.語法制導(dǎo)翻譯生成后綴式三、三元式1.三元式2.間接三元式

四、樹形表示1.表示方法

2.樹表示生成

五、四元式31§5.2中間語言

一、引言

2.為什么要引入中間語言

(1)為了使編譯程序結(jié)構(gòu)上邏輯簡單明確(2)為了便于目標(biāo)代碼優(yōu)化工作(3)便于目標(biāo)代碼生成32第五章語法制導(dǎo)翻譯及中間代碼生成§5.2中間語言

一、引言1.什么是中間語言2.為什么要引入中間語言二、逆波蘭表示1.表達(dá)式逆波蘭表示2.逆波蘭表示的擴(kuò)充3.語法制導(dǎo)翻譯生成后綴式三、三元式1.三元式2.間接三元式

四、樹形表示1.表示方法

2.樹表示生成

五、四元式33第五章語法制導(dǎo)翻譯及中間代碼生成§5.2中間語言

一、引言1.什么是中間語言2.為什么要引入中間語言二、逆波蘭表示1.表達(dá)式逆波蘭表示2.逆波蘭表示的擴(kuò)充3.語法制導(dǎo)翻譯生成后綴式三、三元式1.三元式2.間接三元式

四、樹形表示1.表示方法

2.樹表示生成

五、四元式34第五章語法制導(dǎo)翻譯及中間代碼生成§5.2中間語言

一、引言1.什么是中間語言2.為什么要引入中間語言二、逆波蘭表示

1.表達(dá)式逆波蘭表示2.逆波蘭表示的擴(kuò)充3.語法制導(dǎo)翻譯生成后綴式三、三元式1.三元式2.間接三元式

四、樹形表示1.表示方法

2.樹表示生成

五、四元式35§5.2中間語言

二、逆波蘭表示

1.表達(dá)式逆波蘭表示

（1）波蘭表示的概念對于一個算術(shù)表達(dá)式A+B或邏輯表達(dá)式A≥B，根據(jù)運(yùn)算符和運(yùn)算對象的位置關(guān)系，可分為三種等價表示形式：1)中綴表示法運(yùn)算符在運(yùn)算對象中間，如：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，36例如表達(dá)式中綴表示和后綴表示如下表所示(p155表5.2）說明：

以后我們主要討論逆波蘭表示，即后綴表示，因前綴表示并不常用，所以有時也將后綴表示籠統(tǒng)地統(tǒng)稱為波蘭表示。從上表中可以看出：(1)在中綴表示和后綴表示中，運(yùn)算對象按相同次序出現(xiàn)。(2)在后綴表示中，運(yùn)算符是按實(shí)際計(jì)算順序從左到右排列，且每一運(yùn)算符總是跟在它的運(yùn)算對象之后。

中綴表示后綴表示a+b*ca*(b+c/d)a*b+(c-d)/ca+b=3∨d∧c(a+b)*(c-d)a<ba∨b<cabc*+abcd/+*ab*cd-c/+ab+3=dc∧∨ab+cd-*ab<abc<∨37(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)便于生成目標(biāo)指令38

(3)

逆波蘭(后綴)表示的形成為了說明逆波蘭(后綴)表示的形成，荷蘭學(xué)者W.DEJKSTRA給出下面形象的解釋。波蘭表示運(yùn)算對象表達(dá)式運(yùn)算符進(jìn)棧運(yùn)算符棧退棧比棧頂高進(jìn)棧，比棧頂?shù)突蛳嗤耐藯?9

下面用圖解形式來說明A+B*C形成的過程。A運(yùn)算對象A移進(jìn)對象棧#+B*C#①40

下面用圖解形式來說明A+B*C形成的過程。A＋>#，＋向下進(jìn)運(yùn)算符棧＋#B*C#②41

下面用圖解形式來說明A+B*C形成的過程。AB運(yùn)算對象B移進(jìn)對象棧＋#*C#③42

下面用圖解形式來說明A+B*C形成的過程。AB*>+，*向下進(jìn)運(yùn)算符棧*＋#C#④43

下面用圖解形式來說明A+B*C形成的過程。ABC運(yùn)算對象C移進(jìn)對象棧*＋##⑤44

下面用圖解形式來說明A+B*C形成的過程。ABC*#<*，*退棧往左＋##⑥45

下面用圖解形式來說明A+B*C形成的過程。ABC*＋#<＋，＋退棧往左##⑥最后生成A+B*C的后綴式ABC*＋46(4)用后綴表式對表達(dá)式處理的過程下面通過求后綴表達(dá)式ab+c*的值，來說明用后綴表式對表達(dá)式處理的過程設(shè)a，b和c分別為1，3和5，為了求13+5*的值，其計(jì)算過程如下：1)把1推進(jìn)棧。2)把3推進(jìn)棧。3)將棧頂兩個元素1和3相加，使它們退出棧，然后把結(jié)果4存入棧。4)把5推進(jìn)棧。5)將棧頂兩個元素4和5相乘，使它們退出棧，然后將結(jié)果20存入棧。結(jié)束時棧頂?shù)闹?這里是20)是整個表達(dá)式值。47第五章語法制導(dǎo)翻譯及中間代碼生成§5.2中間語言

一、引言1.什么是中間語言2.為什么要引入中間語言二、逆波蘭表示1.表達(dá)式逆波蘭表示2.逆波蘭表示的擴(kuò)充3.語法制導(dǎo)翻譯生成后綴式三、三元式1.三元式2.間接三元式

四、樹形表示1.表示方法

2.樹表示生成

五、四元式48§5.2中間語言

二、逆波蘭表示

2.逆波蘭表示的擴(kuò)充

只要遵守在運(yùn)算對象后直接緊跟運(yùn)算符這條規(guī)則，我們就可以簡單地把這種后綴式擴(kuò)充到比通常表達(dá)式更大范圍，即擴(kuò)充到程序語言的其它語法成分。

（1）賦值語句〈左部〉:=〈表達(dá)式〉把賦值號“:=”看成是一個賦值運(yùn)算符，它的后綴式為〈左部〉〈表達(dá)式的后綴式〉：=例如：x:=5x:=a*b-c/d的后綴式分別為x5:=xab*cd/-:=49

賦值語句的后綴式的處理方法和后綴式表達(dá)式處理方法類似。所不同的是棧中保存的是左部變量的地址，而不是其值，在賦值運(yùn)算處理結(jié)束后，不產(chǎn)生任何中間計(jì)算結(jié)果，因而也不存在保存中間計(jì)算結(jié)果的問題，而是把存放在運(yùn)算棧中棧頂兩項(xiàng)〈左部〉和〈表達(dá)式〉的值這兩個量退掉。（2）條件語句ifEthenS1elseS２對于用后綴式來表示條件語句，我們假定后綴式中各符號存放在一個一維數(shù)組POST［1··n］之中，每一個數(shù)組元素存放一個運(yùn)算對象或運(yùn)算符。同時我們約定如下幾個符號：①JUMP表示無條件轉(zhuǎn)；②JLT表示小于轉(zhuǎn)；③JEZ表示零轉(zhuǎn)。后綴式PJUMP表示無條件轉(zhuǎn)移到下標(biāo)P所指那個元素POST［p］(即從該符號開始繼續(xù)執(zhí)行)。后綴式ePJEZ表示當(dāng)后綴表達(dá)式e的值為零時，則轉(zhuǎn)移至POST[P]。后綴式e1e2PJLT表示當(dāng)后綴表達(dá)式e1小于后綴表達(dá)式e2時，則轉(zhuǎn)移至POST[P]50于是，對于形如ifethenS1elseS2的條件語句可按后綴式寫成e’p1JEZS1’p2JUMPS2’我們約定e≠0時,該條件語句的值是S1,否則等于S2。對于后綴式條件語句中:e’、S1’和S2’分別是e、S1和S2的后綴式。此外,p1表示S2’在數(shù)組POST的起始位置,p2表示S2’之后那個符號位置。上述后綴式條件語句的意思是,若e’=0時,則轉(zhuǎn)至POST[p1］對S2’進(jìn)行計(jì)算,否則計(jì)算S1’,然后轉(zhuǎn)到POST［p2］的位置。

e’p1JEZS1’p2JUMPS2（p1和p2等處理S2后再反填）e’p1JEZS1’p2JUMPS2’51第五章語法制導(dǎo)翻譯及中間代碼生成§5.2中間語言一、引言1.什么是中間語言2.為什么要引入中間語言二、逆波蘭表示

1.表達(dá)式逆波蘭表示2.逆波蘭表示的擴(kuò)充3.語法制導(dǎo)翻譯生成后綴式三、三元式1.三元式2.間接三元式

四、樹形表示1.表示方法

2.樹表示生成

五、四元式52§5.2中間語言

二、逆波蘭表示

3.語法制導(dǎo)翻譯生成后綴式下面我們討論語法制導(dǎo)翻譯生成后綴式的過程。我們以例4.15文法G［E］為例，說明如何按語法制導(dǎo)翻譯方法把一個中綴形式的簡單算術(shù)表達(dá)式翻譯成為后綴式。

53

后綴式的語義動作規(guī)則語義動作(1)E∷=E(1)+T{E·CODE:=E(1).CODE‖T.CODE‖+}(2)E∷=T{E·CODE:=T·CODE}(3)T∷=T(1)*F{T·CODE:=T(1)CODE‖F(xiàn)·CODE‖*}(4)T∷=F{T·CODE:=F·CODE}(5)F∷=(E){F·CODE:=E·CODE}(6)F∷=i{F·CODE:=i}幾點(diǎn)說明:E.CODE,T.CODE,F.CODE表示構(gòu)成后綴式的符號串符號“‖”表示兩個串的“捻接”運(yùn)算，即并置運(yùn)算。顯然,E(1).CODE‖T.CODE‖+是E.CODE,因?yàn)榉栐诤?其它類似.下面將上述語義動作具體化成語義子程序:54自底向上分析要?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).CODET.CODE+POST(P)55對于上述文法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}表示讀入操作數(shù)56最后，我們以表達(dá)式a+b*c為例按照P118.表4.15文法G［E］LR分析表給出語法制導(dǎo)翻譯產(chǎn)生后綴式過程，其中SUBK表示第K個規(guī)則相對應(yīng)的語義子程序。分析過程如下表：步驟狀態(tài)棧符號棧輸入串歸約規(guī)則調(diào)用子程序后綴式10＃a+b*c#205＃a+b*c#F::=iSUB6a303＃F+b*c#T::=FSUB4a402＃T+b*c#E(1)::=TSUB2a501＃E(1)+b*c#a6016＃E(1)+b*c#a70165＃E(1)+b*c#F::=iSUB6ab80163＃E(1)+F*c#T(1)::=FSUB4ab90169＃E(1)+T(1)

*c#ab1001697＃E(1)+T(1)*

c#ab11016975＃E(1)+T*c#F::=iSUB6abc12016970＃E(1)+T(1)*F#T::=T(1)*FSUB3abc*130169＃E(1)+T#E::=E(1)+TSUB1abc*+1401＃E#abc*+57第五章語法制導(dǎo)翻譯及中間代碼生成§5.2中間語言一、引言1.什么是中間語言2.為什么要引入中間語言二、逆波蘭表示1.表達(dá)式逆波蘭表示2.逆波蘭表示的擴(kuò)充3.語法制導(dǎo)翻譯生成后綴式三、三元式1.三元式2.間接三元式

四、樹形表示1.表示方法

2.樹表示生成

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

1.三元式2.間接三元式

四、樹形表示1.表示方法

2.樹表示生成

五、四元式59§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))60注：運(yùn)算符OP通常用一個整數(shù)碼表示，它除了標(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)算符代碼。

三元式出現(xiàn)先后順序和表達(dá)式各部分計(jì)算順序相一致！對于一目運(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)算對象61(2)三元式的生成同樣可以用語法制導(dǎo)翻譯來產(chǎn)生三元式：下面給出文法G［E］的語義動作來描述這種翻譯的算法：(1)E∷=E(1)+T{E·VAL:=TRIP(+,E(1)·VAL,T·VAL)}(2)E∷=T{E·VAL:=T·VAL}(3)T∷=T(1)*F{T·VAL:=TRIP(*,T(1)·VAL,F·VAL)}(4)T∷=F{T·VAL:=F·VAL}(5)F∷=(E){F·VAL:=E·VAL}(6)F∷=i{F·VAL:=ENTRY(i)}其中語義值E·VAL、T·VAL和F·VAL，是一個指示器，或指向有關(guān)符號表某一項(xiàng)，或指向三元式表自身某一項(xiàng)，TRIP(OP，ARG1，ARG2)是一個語義子程序，回送新產(chǎn)生的三元式存放在三元式表位置。ENTRY(i)是一個語義子程序，通過ENTRY查i在符號表中位置，即對應(yīng)地址，若查不到，認(rèn)為有錯誤。62第五章語法制導(dǎo)翻譯及中間代碼生成§5.2中間語言一、引言1.什么是中間語言2.為什么要引入中間語言二、逆波蘭表示1.表達(dá)式逆波蘭表示2.逆波蘭表示的擴(kuò)充3.語法制導(dǎo)翻譯生成后綴式三、三元式

1.三元式

2.間接三元式

四、樹形表示1.表示方法

2.樹表示生成

五、四元式63§5.2中間語言

三、三元式表示

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)64間接三元式的優(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)首先看一下此三元式是否在其中，如已在其中，則無需填入。

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

四、樹形表示1.表示方法

2.樹表示生成

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

四、樹形表示

1.表示方法

2.樹表示生成

五、四元式67§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的樹表示分別定義為：+ab－ab－a68雙目運(yùn)算對應(yīng)二叉樹，多目運(yùn)算對應(yīng)多叉樹，單目運(yùn)算對應(yīng)單叉樹。如表達(dá)式a*b-(c+d)/(e-f)的二叉樹如下圖：后序遍歷上述二叉樹便得到該表達(dá)式的逆波蘭表示為ab*cd+ef-/-－*/ab+－cdef69表達(dá)式的三元式可以看作是樹的直接表示，圖5.7所對應(yīng)的三元式為(1)(*,a,b)(2)(+,c,d)(3)(-,e,f)(4)(/,(2),(3))(5)(-,(1),(4))顯然，每一個三元式對應(yīng)一棵子樹，子樹的根便是三元式的運(yùn)算符，三元式的運(yùn)算對象是子樹兩個分枝。70第五章語法制導(dǎo)翻譯及中間代碼生成§5.2中間語言一、引言1.什么是中間語言2.為什么要引入中間語言二、逆波蘭表示1.表達(dá)式逆波蘭表示2.逆波蘭表示的擴(kuò)充3.語法制導(dǎo)翻譯生成后綴式三、三元式1.三元式2.間接三元式

四、樹形表示

1.表示方法

2.樹表示生成

五、四元式71§5.2中間語言

四、樹形表示2.樹表示生成對文法G[E]翻譯成樹形表示語義動作描述如下：(1)E∷=E(1)+T{E·VAL:=NODE(+,E(1)·VAL,T·VAL)}(2)E∷=T{E·VAL:=T·VAL}(3)T∷=T(1)*F{T·VAL:=NODE(*,T(1)·VAL,F·VAL)}(4)T∷=F{T·VAL:=F·VAL}(5)F∷=(E){F·VAL:=E·VAL}(6)F∷=i{F·VAL:=LEAF(i)}其中：語義值E·VAL、T·VAL和F·VAL是一個指示器，指向樹一個結(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))72第五章語法制導(dǎo)翻譯及中間代碼生成§5.2中間語言一、引言1.什么是中間語言2.為什么要引入中間語言二、逆波蘭表示1.表達(dá)式逆波蘭表示2.逆波蘭表示的擴(kuò)充3.語法制導(dǎo)翻譯生成后綴式三、三元式1.三元式2.間接三元式

四、樹形表示1.表示方法

2.樹表示生成

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

四、樹形表示1.表示方法

2.樹表示生成

五、四元式74§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)(4)(:=,T3,,a)

四元式之間聯(lián)系是通過臨時變量實(shí)現(xiàn)的，調(diào)整四元式之間相對位置并不意味著一定要改變一系列指示器值。因此，對中間代碼進(jìn)行優(yōu)化處理時，四元式比三元式方便得多。下面主要討論如何用四元式表示各種語句，并產(chǎn)生四元式語義子程序。75第五章語法制導(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屬性文法與屬性翻譯一、屬性文法與L屬性文法二、屬性翻譯76第五章語法制導(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ù)組說明的翻譯3.過程說明的翻譯

77第五章語法制導(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ù)組說明的翻譯3.過程說明的翻譯

78第五章語法制導(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ù)組說明的翻譯3.過程說明的翻譯

79§5.3自底向上語法制導(dǎo)翻譯

一、簡單算術(shù)表達(dá)式和賦值語句的翻譯

1.翻譯成四元式

我們首先討論僅含有簡單變量的表達(dá)式和賦值語句到四元式的翻譯，對于復(fù)雜的表達(dá)式和賦值語句的翻譯將在以后討論。為簡便起見，假定賦值語句中所含的全部變量是同一類型整型變量，此外在翻譯過程中也不作語義檢查。

(1)賦值語句的文法1)A∷=V:=E5)T∷=F2)E∷=E(1)+T6)F∷=(E)3)E∷=T7)F∷=i4)T∷=T(1)*F8)V∷=i為了實(shí)現(xiàn)到四元式的翻譯，需要引進(jìn)一系列語義變量和語義子程序。

80(2)語義變量和語義子程序

①NEWTEMP是一個函數(shù)，每次調(diào)用時，都定義一個新臨時變量，回送一個代表新臨時變量名的整數(shù)碼作為函數(shù)值。為直觀起見，我們將NEWTEMP產(chǎn)生的臨時變量依次記為T１，Ｔ２…等等。

②ENTRY(i)是一個函數(shù)過程，查找符號名i在表中的入口地址。

③X·PLACE是和非終結(jié)符X相聯(lián)系的語義變量，表示存放X值的變量名在符號表的入口或整數(shù)碼(若此變量是一個臨時變量)。如：F∷=i{F·PLACE:=ENTRY(i)}

表示存放F值變量名i在符號表中的入口地址。即從變量F.PLACE值可知i在符號表中的位置。

④

GEN(OP，ARG1，ARG2，RESULT)是一個語義過程，該過程把四元式(OP，ARG1，ARG2，RESULT)填入四元式表中。因此，上面定義文法G[A]語義子程序的描述如下：81(3)語義子程序的描述(1)A∷=V:=E{GEN(:=,E·PLACE,,V·PLACE)}(2)E∷=E(1)+T{E·PLACE:=NEWTEMP;GEN(+,E(1)·PLACE,T·PLACE,E·PLACE)}(3)E∷=T{E·PLACE:=T·PLACE}(4)T∷=T(1)*F{T·PLACE:=NEWTEMP;GEN(*,T(1)·PLACE,F·PLACE,T·PLACE)}(5)T∷=F{T·PLACE:=F·PLACE}(6)F∷=(E){F·PLACE:=E·PLACE}(7)F∷=i{F·PLACE:=ENTRY(i)}(8)V∷=i{V·PLACE:=ENTRY(i)}在進(jìn)行自底向上語法制導(dǎo)翻譯時，還需一張LR分析表，上述文法G［A］是一個SLR(1)文法，其分析表如下：82（4）文法G[A]SLR(1)分析表狀態(tài)ACTIONGOTOi+*():=#AVETF0S2131acc2r83S44S9S85675S10r16r3S11r3r37r5r5r5r58S9S812679r7r7r7r710S9S813711S9S81412S10S1513r2S11r2r214r4r4r4r415r6r6r6r683（5）對x:=a+b*c語法制導(dǎo)翻譯產(chǎn)生四元式過程（以賦值語句x:=a+b*c為例）步驟狀態(tài)棧符號棧PLACE輸入串歸約規(guī)則調(diào)用子程序四元式10＃－X:=a+b*c#202＃x－Vx:=a+b*c#V::=iSUB8303＃V－Vx:=a+b*c#4034＃V:=－Vx-a+b*c#50349＃V:=a－Vx-Fa+b*c#F::=iSUB760347＃V:=F－Vx-Ta+b*c#T::=FSUB570346＃V:=T－Vx-Ea+b*c#E::=TSUB380345＃V:=E－Vx-Ea+b*c#903450＃V:=E+－Vx-Ea-b*c#10034509＃V:=E+b－Vx-Ea-Fb*c#F::=iSUB711034507＃V:=E+F－Vx-Ea-Tb*c#T::=FSUB512034503＃V:=E+T－Vx-Ea-Tb*c#130345031＃V:=E+T*－Vx-Ea-Tb-c#1403450319＃V:=E+T*c－Vx-Ea-Tb-FC#F::=iSUB71503450314＃V:=E+T*F－Vx-Ea-T1#T::=T(1)*FSUB4(*,b,c,T1)16034503＃V:=E+T－Vx-T2#E::=E(1)+TSUB2(+,a,T1,T2)170345＃V:=E－Vx-T2#A::=V:=ESUB1(:=,T2,,x)1801＃A#84分析表幾點(diǎn)說明：在分析表中Vx,Ea,Tb,Fc之類記號，表示與非終結(jié)符V,E,T,F相關(guān)聯(lián)的V·PLACE,E.PLACE,T.PLACE,F.PLACE中存放著ENTRY(x),ENTRY(a),ENTRY(b),ENTRY(c)符號指針，指向符號表。在四元式中，如（*，b,c,T1)，*實(shí)際上是某種整數(shù)編碼，反映運(yùn)算符本身及其信息特征，如類型等。b,c實(shí)際上也是指示器，指示符號表入口；T1是臨時變量，實(shí)際上也是整數(shù)碼.85第五章語法制導(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ù)組說明的翻譯3.過程說明的翻譯

86§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í)型變量值是個指針，則編譯程序報(bào)告“類型不相容”的診斷信息。

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ù)。87

(2)類型檢查

類型檢查可在生成中間代碼時進(jìn)行，也可在生成目標(biāo)代碼時進(jìn)行，但最好是在生成中間代碼時進(jìn)行，因?yàn)檎Z法和語義檢查最好盡早進(jìn)行，這樣能盡早避免徒勞的工作。在上面對簡單算術(shù)表達(dá)式和賦值語句翻譯到四元式的討論中，我們假定各個變量是同一類型整型變量，并且規(guī)定在四元式的op代碼中，本身就會有類型信息。所以，在上例各語義子程序中，我們并未考慮有關(guān)類型方面語義處理。88（3）類型轉(zhuǎn)換方法為了簡單起見，我們僅考慮整型和實(shí)型的情況。①這種混合運(yùn)算中，給每個非終結(jié)符的語義值增添類型信息X.MODE

X·MODE的值或?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,*r等表示實(shí)型運(yùn)算符?，F(xiàn)以規(guī)則E∷=E(1)OPE(2)為例，給出語義子程序的具體描述如下：89現(xiàn)以規(guī)則E∷=E(1)OPE(2)為例，給出語義子程序的具體描述如下：T:=NEWTEMP;IFE(1)·MODE=intANDE(2)·MODE=intTHENBEGINGEN(opi,E(1)·PLACE,E(2)·PLACE,T);E·MODE:=intENDELSEIFE(1)·MODE=rANDE(2)·MODE=rTHENBEGINGEN(opr,E(1)·PLACE,E(2)·PLACE,T);E·MODE:=rENDELSEIFE(1)·MODE=int/*andE(2)·MODE=r*/THENBEGINU:=NEWTEMP;GEN(itr,E(1)·PLACE,-,U);GEN(opr,U,E(2)·PLACE,T);E·MODE:=rENDELSE/*E(1)·MODE=randE(2)·MODE=int*/BEGINU:=NEWTEMP;GEN(itr,E(2)·PLACE,-,U);GEN(opr,E(1)·PLACE,U,T);E·MODE:=rEND;E·PLACE:=T;90這樣,對于輸入串為X*2+A*(I+1)其中I為整型量，X、A為實(shí)型量,則產(chǎn)生四元式序列為(itr,2,-,T1)(*r,X,T１,T２)(+i,I,1,T3)(itr,T3,-,T４)(*r,A,T4,T5)(+r,T2,T5,T6)91第五章語法制導(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ù)組說明的翻譯3.過程說明的翻譯

92第五章語法制導(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ù)組說明的翻譯3.過程說明的翻譯

93§5.3自底向上語法制導(dǎo)翻譯

二、布爾表達(dá)式的翻譯

1.概述布爾表達(dá)式由布爾運(yùn)算符∧(與)、∨(或)和(非)等作用于布爾量或關(guān)系表達(dá)式構(gòu)成,關(guān)系表達(dá)式的形式是E1ropE2,其中rop是關(guān)系運(yùn)算符(如<、<=、=、>、>=及<>)。而E1和E2是算術(shù)表達(dá)式。(1)布爾表達(dá)式的用途在程序設(shè)計(jì)語言中，布爾表達(dá)式有兩個基本用途:1）一個是求邏輯值，邏輯值的結(jié)果是真或假。2）另一個用得最多的是在控制語句中用作條件表達(dá)式，例如，在if-then、if-then-else和while-do語句里表示控制條件。94(2)布爾表達(dá)式的文法布爾表達(dá)式文法G［E］如下:E∷=E∧E|E∨E|E|(E)|i|iropi

說明：1）布爾表達(dá)式的文法是一個二義文法例如：該文法的一個句子a∧b∨c有兩棵不同的語法樹與之對應(yīng)，所以該文法是一個二義文法。EEE∨EE∧abcEEE∧aEE∨bc952）規(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）

iropi中rop是關(guān)系運(yùn)算符，i是布爾變量或算術(shù)值96(3)布爾表達(dá)式求值方法

1）把真和假數(shù)值化，使布爾表達(dá)式計(jì)算類似于算術(shù)表達(dá)式的計(jì)算，常用1表示真，0表示假，或者用非零整數(shù)表示真。如：1∨（0∧0）∨0=1∨（1∧0）∨0=1∨0∨0=1

2）采取某種優(yōu)化措施，有時并不需要將一個布爾表達(dá)式從頭算到尾，而只須計(jì)算它的一個子表達(dá)式，便能確定整個布爾表達(dá)式真和假。例如，對于A∨B，只要計(jì)算出A為真，則不管B值如何，A∨B之值一定為真。又如對A∧B，只要計(jì)算出A為假，則A∧B必然為假，等等。對于三種邏輯運(yùn)算，可作如下等價的解釋：A∨B:ifAthentrueelseBA∧B:ifAthenBelsefalseA:ifAthenfalseelsetrue用這種方式實(shí)現(xiàn)控制語句的布爾表達(dá)式尤其方便。對應(yīng)上述兩種計(jì)算方法，其布爾表達(dá)式有兩種不同的翻譯方法。97第五章語法制導(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ù)組說明的翻譯3.過程說明的翻譯

98§5.3自底向上語法制導(dǎo)翻譯

二、布爾表達(dá)式的翻譯

2.布爾表達(dá)式的翻譯方法

（1）如同翻譯算術(shù)表達(dá)式一樣，用于求值例如，布爾表達(dá)式a∧(b∨c=d)將被翻譯成如下四元式：1)(,a,-,T1)2)(=,c,d,T2)3)(∨,b,T2,T3)4)(∧,T1,T3,T4)99仿照翻譯算術(shù)表達(dá)式的方法，很容易寫出布爾表達(dá)式文法G［E］的每個規(guī)則用于求值的語義動作。(1)E∷=E(1)∧E(2){E·PLACE:=NEWTEMP;GEN(∧,E(1)·PLACE,E(2)。PLACE,E·PLACE)}(2)E∷=E(1)∨E(2){E·PLACE:=NEWTEMP;GEN(∨,E(1)·PLACE,E(2).PLACE,E·PLACE)}(3)E∷=E(1){E·PLACE:=NEWTEMP；GEN（，E(1)·PLACE,,E·PLACE)}(4)E∷=（E(1)）

{E·PLACE:=E(1)·PLACE}(5)E∷=i{E·PLACE:=ENTRY（i）}(6)E∷=iropi{E·PLACE:=NEWTEMP;GEN(rop,ENTRY(i(1)),ENTRY(i(2)),E.PLACE)}}100(2)作為條件控制的布爾表達(dá)式的翻譯

1)布爾表達(dá)式E作為條件控制的代碼結(jié)構(gòu)對于條件語句ifEthenS1elseS2中布爾表達(dá)式E，它的作用就是控制S1和S2的選擇，我們賦于E代碼兩種出口，其一為“真出口”，另一個是“假出口”，它們分別指出當(dāng)E值為true和false時，控制轉(zhuǎn)向的目標(biāo)(即某一四元式所在位置或序號)。條件語句可翻譯成如下圖：E的代碼S1的代碼truefalseS2的代碼1012)三種形式的四元式作為條件控制的布爾表達(dá)式E的翻譯歸納起來只有三種形式的四元式

(jnz,a1,,p)若a1為真時,則轉(zhuǎn)向第p個四元式。(jrop,a1,a2,p)若關(guān)系a1ropa2成立時,轉(zhuǎn)向第p個四元式。(j,,,p)無條件轉(zhuǎn)向第p個四元式。除上述兩種真轉(zhuǎn)外，可用無條件表示假轉(zhuǎn)102例如,對于條件語句ifa∨b<cthenS1elseS2經(jīng)翻譯后，可得如下四元式序列：(1)(jnz,a,,5)(2)(j,,,3)(3)(j<,b,c,5)(4)(j,,,p+1)(5)(關(guān)于S1的四元式序列)(P)(j,,,q)(p+1)(關(guān)于S2的四元式序列)(q)（1）a為真，a∨b<c就為真，轉(zhuǎn)5執(zhí)行（2）a為假，a∨b<c的值取決于b<c的值，所以轉(zhuǎn)3執(zhí)行（3）a為假，且b<c，則a∨b<c為真，轉(zhuǎn)5執(zhí)行（4）a為假，且b<c也是假，則a∨b<c為假，執(zhí)行S2語句，即應(yīng)轉(zhuǎn)p+1執(zhí)行（p）執(zhí)行完S1（對應(yīng)四元式為（5））則應(yīng)轉(zhuǎn)到條件語句的下一條語句執(zhí)行，所以無條件跳轉(zhuǎn)到（q）執(zhí)行。四元式(1)～(4)中顯然含有多余的四元式，如(2)顯然是不需要。

103第五章語法制導(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ù)組說明的翻譯3.