編譯原理

CompilerPrinciples徐佳xujia@教學網站：南京郵電大學.計算機學院

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

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

本節內容一、語法制導翻譯定義

二、語法制導翻譯原理

三、語法制導翻譯實現5第五章語法制導翻譯及中間代碼生成§5.1語法制導翻譯概述

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

一、語法制導翻譯定義

二、語法制導翻譯原理

三、語法制導翻譯實現7第五章語法制導翻譯及中間代碼§5.1語法制導翻譯概述

一、語法制導翻譯定義

二、語法制導翻譯原理

三、語法制導翻譯實現8§5.1語法制導翻譯概述

一、語法制導翻譯定義

語法制導翻譯就是以語法分析為主導的語義處理。語法分析過程中嵌入語義動作，即調用對應的語義子程序。例如在前面語法分析時分析a+b*c表達式，其分析語法樹如下：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值相加就是最終結果，這就是語法制導翻譯的基本思想，在語法分析同時進行語義分析。9第五章語法制導翻譯及中間代碼§5.1語法制導翻譯概述

一、語法制導翻譯定義

二、語法制導翻譯原理

三、語法制導翻譯實現10第五章語法制導翻譯及中間代碼§5.1語法制導翻譯概述

一、語法制導翻譯定義

二、語法制導翻譯原理

三、語法制導翻譯實現11§5.1語法制導翻譯概述

二、語法制導翻譯原理

語法制導翻譯的原理就是先為每個文法規定相應的語義，即編寫出相應語義處理子程序，整個分析是以語法分析為主導。在自頂向下語法分析時，若某一個規則右部與輸入串相匹配時，或者，在自底向上語法分析時，當一個規則被用于歸約時，此時該規則對應的語義子程序就進入工作，完成既定翻譯任務，產生與語義相應的中間代碼或目標代碼。

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

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

一、語法制導翻譯定義

二、語法制導翻譯原理

三、語法制導翻譯實現17第五章語法制導翻譯及中間代碼§5.1語法制導翻譯概述

一、語法制導翻譯定義

二、語法制導翻譯原理

三、語法制導翻譯實現18§5.1語法制導翻譯概述

三、語法制導翻譯實現上面我們從原則上討論了語法制導翻譯的原理，下面我們通過一個自底向上LR分析看如何實現語法制導翻譯。例如：有規則：(1)X∷=…{動作1}(2)Y∷=…{動作2}(3)A∷=XY{動作3}當使用規則(1)、(2)歸約時，{動作1}和{動作2}工作結果的有關信息(作為X和Y的語義值)應暫時保存下來，以便以后用規則(3)在歸約時(動作3)可引用這些值。現在對LR分析器的分析棧加以擴充，為了在語法分析過程中平行地進行語義處理，使得每個文法符號之后都跟著它的語義值，因此，設置一個語義信息棧，為了清晰起見，我們把這個分析棧每一項分三部分組成：狀態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的處理結果我們假定先歸約后執行語義子程序，所以當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考慮下面文法及其語義描述：

規則語義動作(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}其中：語義動作中的+、*代表整型加、乘算術運算，而且詞法分析程序將送來每個i的整型內部值LEXVAL。

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

22規則程序段(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根據上述程序段，若輸入2*3+2，就有如下圖所示的語法制導翻譯的分析樹。S’EEEEE+*223E?VAL=8E?VAL=6E?VAL=2E?VAL=2E?VAL=3LEXVAL=2LEXVAL=3LEXVAL=224對2*3+2利用P136.表4.23進行分析和翻譯(實為計算值)該輸入串過程如下表所示。當狀態1面臨#時對應的分析動作為acc(接受)，此時，相應的語義動作為printVAL[TOP]，即輸出語義程序的計值結果：8。步驟狀態棧語義值棧符號棧輸入串歸約規則及動作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第五章語法制導翻譯及中間代碼生成本節內容§5.1語法制導翻譯概述一、語法制導翻譯定義二、語法制導翻譯原理三、語法制導翻譯實現§5.2中間語言一、引言二、逆波蘭表示三、三元式四、樹形表示五、四元式26第五章語法制導翻譯及中間代碼生成§5.2中間語言

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

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

2.樹表示生成

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

一、引言

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

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

2.樹表示生成

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

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

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

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

2.樹表示生成

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

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

就是和源程序等價的一種編碼形式，其復雜性介于源程序和機器語言中間。源程序前端中間代碼代碼優化器中間代碼代碼生成器目標程序符號表30第五章語法制導翻譯及中間代碼生成§5.2中間語言

一、引言

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

二、逆波蘭表示1.表達式逆波蘭表示2.逆波蘭表示的擴充3.語法制導翻譯生成后綴式三、三元式1.三元式2.間接三元式

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

2.樹表示生成

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

一、引言

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

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

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

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

2.樹表示生成

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

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

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

2.樹表示生成

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

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

1.表達式逆波蘭表示2.逆波蘭表示的擴充3.語法制導翻譯生成后綴式三、三元式1.三元式2.間接三元式

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

2.樹表示生成

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

二、逆波蘭表示

1.表達式逆波蘭表示

（1）波蘭表示的概念對于一個算術表達式A+B或邏輯表達式A≥B，根據運算符和運算對象的位置關系，可分為三種等價表示形式：1)中綴表示法運算符在運算對象中間，如：A+B，A≥B，a+b*(c+d*(e-f))等.2)后綴表示法將運算符放在運算對象后面，通常將后綴表示稱為逆波蘭表示.如：A+B表示為AB+，A≥B表示為AB≥，a+b*c表示為abc*+對于逆波蘭表示非常適合機械處理，只要從左到右按運算順序一個個計算下去3)前綴表示法即將運算符放在運算對象前面。如:+AB，≥AB，36例如表達式中綴表示和后綴表示如下表所示(p155表5.2）說明：

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

中綴表示后綴表示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)逆波蘭(后綴)表示的優點

1）后綴表示是一種無括號表示法，不但簡明，而且又確切規定了計算順序。

2）運算處理極其簡單方便，只要從左到右掃描后綴表達式各個符號，就能進行對表達式的處理

一般步驟是從左到右掃描后綴表達式各個符號，每碰到運算對象時就把它推進棧，每碰到一個K元運算符時，就取出棧頂的K個運算對象進行相應的運算，并且用運算結果去替換棧頂的K個運算對象，然后再繼續掃描表達式中余留符號，如此等等，直到整個表達式計算完畢為止。當上述過程結束后，整個表達式之值將留于棧頂。

3)便于生成目標指令38

(3)

逆波蘭(后綴)表示的形成為了說明逆波蘭(后綴)表示的形成，荷蘭學者W.DEJKSTRA給出下面形象的解釋。波蘭表示運算對象表達式運算符進棧運算符棧退棧比棧頂高進棧，比棧頂低或相同的退棧39

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

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

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

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

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

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

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

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

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

2.樹表示生成

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

二、逆波蘭表示

2.逆波蘭表示的擴充

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

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

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

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

1.表達式逆波蘭表示2.逆波蘭表示的擴充3.語法制導翻譯生成后綴式三、三元式1.三元式2.間接三元式

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

2.樹表示生成

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

二、逆波蘭表示

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

53

后綴式的語義動作規則語義動作(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·CODE‖*}(4)T∷=F{T·CODE:=F·CODE}(5)F∷=(E){F·CODE:=E·CODE}(6)F∷=i{F·CODE:=i}幾點說明:E.CODE,T.CODE,F.CODE表示構成后綴式的符號串符號“‖”表示兩個串的“捻接”運算，即并置運算。顯然,E(1).CODE‖T.CODE‖+是E.CODE,因為符號在后,其它類似.下面將上述語義動作具體化成語義子程序:54自底向上分析要歸約時先調用相應子程序生成后綴式假定后綴式存放在數組POST中假設要歸約的句柄為E(1)+T(在語法分析棧中)，則首先要求調用相應于E(1)+T的語義子程序，此時E(1)和T已調用過相應的語義子程序，因此，它們的后綴式已被生成，對應于E(1)+T的語義子程序所要完成的工作是把已生成的兩后綴式捻接起來，然后再添上符號“+”。如果我們設置一個數組存放后綴式，那么語義動作就可以不涉及捻接運算。令這個數組為POST，p為下標，初值為1。如下圖：

…E(1).CODET.CODE+POST(P)55對于上述文法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}表示讀入操作數56最后，我們以表達式a+b*c為例按照P118.表4.15文法G［E］LR分析表給出語法制導翻譯產生后綴式過程，其中SUBK表示第K個規則相對應的語義子程序。分析過程如下表：步驟狀態棧符號棧輸入串歸約規則調用子程序后綴式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第五章語法制導翻譯及中間代碼生成§5.2中間語言一、引言1.什么是中間語言2.為什么要引入中間語言二、逆波蘭表示1.表達式逆波蘭表示2.逆波蘭表示的擴充3.語法制導翻譯生成后綴式三、三元式1.三元式2.間接三元式

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

2.樹表示生成

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

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

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

2.樹表示生成

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

三、三元式表示

1.三元式(1)定義三元式的一般形式為(i)(OP,ARG1,ARG2)其中：(i)為三元式的編號，不同三元式不能有相同的編號OP是運算符部分ARG1和ARG2是運算對象部分，它們或者指向符號表登記項指示器(對于運算對象是常數或標識符的情況)，或者是一個指向三元式序列(或三元式表)中某一個三元式位置的指示器(對于運算對象是中間結果的情況)。如：A+B*C對應的三元式表示為：(1)(*，B，C)(2)(+，A，(1))60注：運算符OP通常用一個整數碼表示，它除了標識運算符的種屬之外，還附帶地表示其它一些語義特性。例如若OP表示一個加法運算符，則相應的整數碼除了標識加法運算本身外，還兼有表示數據類型(如整型、實型等)、運算方式(定點、浮點)和運算精度等信息，且不同語義屬性使用不同的運算符代碼。

三元式出現先后順序和表達式各部分計算順序相一致！對于一目運算符OP，ARG1和ARG2只需其一。我們可以隨意規定選用一個，例如，規定用ARG1。至于多目運算符可以用若干個相繼三元式表示。如：賦值語句x:=-b*(c+d)用三元式來表示，則可寫成(1)(-,b,)(2)(+,c,d)(3)(*,(1),(2))(4)(:=,x,(3))其中，三元式(3)就引用三元式(1)和(2)的結果作為它的兩個運算對象61(2)三元式的生成同樣可以用語法制導翻譯來產生三元式：下面給出文法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，是一個指示器，或指向有關符號表某一項，或指向三元式表自身某一項，TRIP(OP，ARG1，ARG2)是一個語義子程序，回送新產生的三元式存放在三元式表位置。ENTRY(i)是一個語義子程序，通過ENTRY查i在符號表中位置，即對應地址，若查不到，認為有錯誤。62第五章語法制導翻譯及中間代碼生成§5.2中間語言一、引言1.什么是中間語言2.為什么要引入中間語言二、逆波蘭表示1.表達式逆波蘭表示2.逆波蘭表示的擴充3.語法制導翻譯生成后綴式三、三元式

1.三元式

2.間接三元式

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

2.樹表示生成

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

三、三元式表示

2.間接三元式為了便于代碼優化，常常采用間接三元式。這由兩張表組成：（1）三元式表，用來存放各三元式本身；（2）執行表(間接碼表)，它按執行三元式順序，依次列出相應各三元式在三元式表中位置。例如，對于如下賦值語句x:=a*b+c+a*b若按三元式表示，可寫成(1)(*,a,b)(2)(+,(1),c)(3)(*,a,b)(4)(+,(2),(3))(5)(:=,x,(4))其中，三元式(1)和(3)完全一樣，但是不能將(3)省去。

按間接三元式表示，則可寫成執行表三元式表(1)(1)(*,a,b)(2)(2)(+,(1),c)(1)(3)(+,(2),(1))(3)(4)(:=,x,(3))(4)64間接三元式的優點：（1）便于代碼優化在進行代碼優化時，常常要從中間代碼刪去一些運算，或者把某些運算移到另外位置上，若采用一般三元式，則由于三元式之間引用太多，很難做到這一點。（2）節省空間由于在間接三元式執行表中已經依次列出每次要執行的那個三元式，所以，若有若干個相同三元式，則僅須在三元式表中保存其中之一。如上面賦值語句右部表達式中有兩個a*b子表達式，而三元式表中只出現一次(*,a,b)。對于間接三元式表示，語義子程序應增添產生執行表的動作。在填寫三元式表時，應首先看一下此三元式是否在其中，如已在其中，則無需填入。

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

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

2.樹表示生成

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

四、樹形表示

1.表示方法

2.樹表示生成

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

四、樹形表示

1.表示方法我們可以用樹形數據結構來表示一個表達式或語句。在樹表示中，葉子結點表示運算對象，即常量或變量，其它結點表示運算符，如表達式a+b,a-b,-a的樹表示分別定義為：+ab－ab－a68雙目運算對應二叉樹，多目運算對應多叉樹，單目運算對應單叉樹。如表達式a*b-(c+d)/(e-f)的二叉樹如下圖：后序遍歷上述二叉樹便得到該表達式的逆波蘭表示為ab*cd+ef-/-－*/ab+－cdef69表達式的三元式可以看作是樹的直接表示，圖5.7所對應的三元式為(1)(*,a,b)(2)(+,c,d)(3)(-,e,f)(4)(/,(2),(3))(5)(-,(1),(4))顯然，每一個三元式對應一棵子樹，子樹的根便是三元式的運算符，三元式的運算對象是子樹兩個分枝。70第五章語法制導翻譯及中間代碼生成§5.2中間語言一、引言1.什么是中間語言2.為什么要引入中間語言二、逆波蘭表示1.表達式逆波蘭表示2.逆波蘭表示的擴充3.語法制導翻譯生成后綴式三、三元式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是一個指示器，指向樹一個結點。NODE(OP，LEFT，RIGHT)是一個函數子程序，OP是一個二元運算符，LEFT，RIGHT為指示器，每調用此函數一次,就建立一個新結點，其標記為OP，LEFT和RIGHT分別指向左右子樹根結點指針，從NODE回送的值是一個指示器，指向這棵新樹的根。LEAF(i)是建立一個末端結點(葉結點)72第五章語法制導翻譯及中間代碼生成§5.2中間語言一、引言1.什么是中間語言2.為什么要引入中間語言二、逆波蘭表示1.表達式逆波蘭表示2.逆波蘭表示的擴充3.語法制導翻譯生成后綴式三、三元式1.三元式2.間接三元式

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

2.樹表示生成

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

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

2.樹表示生成

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

五、四元式表示四元式是一種用得比較多的一種中間語言代碼形式，四元式一般形式是(OP，ARG1，ARG2，RESULT)其中：OP是運算符，其含義與三元式中OP類似；ARG1和ARG2是運算對象，RESULT是運算結果例如：賦值語句a:=-b*(c+d)用四元式表示，則可寫成(1)(-,b,,T1)(2)(+,c,d,T2)(3)(*,T1,T2,T3)(4)(:=,T3,,a)

四元式之間聯系是通過臨時變量實現的，調整四元式之間相對位置并不意味著一定要改變一系列指示器值。因此，對中間代碼進行優化處理時，四元式比三元式方便得多。下面主要討論如何用四元式表示各種語句，并產生四元式語義子程序。75第五章語法制導翻譯及中間代碼生成本節內容§5.3自底向上語法制導翻譯一、簡單算術表達式和賦值語句的翻譯二、布爾表達式的翻譯三、控制語句翻譯四、數組元素的翻譯五、過程語句的翻譯六、說明語句的翻譯§5.4自頂向下語法制導翻譯一、遞歸下降的語法制導翻譯二、LL(1)語法制導翻譯§5.5屬性文法與屬性翻譯一、屬性文法與L屬性文法二、屬性翻譯76第五章語法制導翻譯及中間代碼生成

§5.3自底向上語法制導翻譯一、簡單算術表達式和賦值語句的翻譯

1.翻譯成四元式2.類型檢查與類型轉換二、布爾表達式的翻譯

1.概述2.布爾表達式的翻譯方法3.翻譯成四元式的實現三、控制語句翻譯1.語句標號和goto語句的翻譯2.條件語句的翻譯3.布爾表達式的翻譯方法4.while循環語句翻譯5.for循環語句的翻譯四、數組元素的翻譯1.下標變量地址的計算2.數組元素的翻譯五、過程語句的翻譯1.參數傳遞方式2.過程語句的翻譯六、說明語句的翻譯1.變量說明的翻譯2.數組說明的翻譯3.過程說明的翻譯

77第五章語法制導翻譯及中間代碼生成

§5.3自底向上語法制導翻譯一、簡單算術表達式和賦值語句的翻譯

1.翻譯成四元式2.類型檢查與類型轉換二、布爾表達式的翻譯

1.概述2.布爾表達式的翻譯方法

3.翻譯成四元式的實現三、控制語句翻譯1.語句標號和goto語句的翻譯2.條件語句的翻譯3.布爾表達式的翻譯方法4.while循環語句翻譯5.for循環語句的翻譯四、數組元素的翻譯1.下標變量地址的計算2.數組元素的翻譯五、過程語句的翻譯1.參數傳遞方式2.過程語句的翻譯六、說明語句的翻譯1.變量說明的翻譯2.數組說明的翻譯3.過程說明的翻譯

78第五章語法制導翻譯及中間代碼生成

§5.3自底向上語法制導翻譯一、簡單算術表達式和賦值語句的翻譯1.翻譯成四元式2.類型檢查與類型轉換二、布爾表達式的翻譯

1.概述2.布爾表達式的翻譯方法

3.翻譯成四元式的實現三、控制語句翻譯1.語句標號和goto語句的翻譯2.條件語句的翻譯3.布爾表達式的翻譯方法4.while循環語句翻譯5.for循環語句的翻譯四、數組元素的翻譯1.下標變量地址的計算2.數組元素的翻譯五、過程語句的翻譯1.參數傳遞方式2.過程語句的翻譯六、說明語句的翻譯1.變量說明的翻譯2.數組說明的翻譯3.過程說明的翻譯

79§5.3自底向上語法制導翻譯

一、簡單算術表達式和賦值語句的翻譯

1.翻譯成四元式

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

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

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

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

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

③X·PLACE是和非終結符X相聯系的語義變量，表示存放X值的變量名在符號表的入口或整數碼(若此變量是一個臨時變量)。如：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)}在進行自底向上語法制導翻譯時，還需一張LR分析表，上述文法G［A］是一個SLR(1)文法，其分析表如下：82（4）文法G[A]SLR(1)分析表狀態ACTIONGOTOi+*():=#AVETF0S2131acc2r83S44S9S85675S10r16r3S11r3r37r5r5r5r58S9S812679r7r7r7r710S9S813711S9S81412S10S1513r2S11r2r214r4r4r4r415r6r6r6r683（5）對x:=a+b*c語法制導翻譯產生四元式過程（以賦值語句x:=a+b*c為例）步驟狀態棧符號棧PLACE輸入串歸約規則調用子程序四元式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分析表幾點說明：在分析表中Vx,Ea,Tb,Fc之類記號，表示與非終結符V,E,T,F相關聯的V·PLACE,E.PLACE,T.PLACE,F.PLACE中存放著ENTRY(x),ENTRY(a),ENTRY(b),ENTRY(c)符號指針，指向符號表。在四元式中，如（*，b,c,T1)，*實際上是某種整數編碼，反映運算符本身及其信息特征，如類型等。b,c實際上也是指示器，指示符號表入口；T1是臨時變量，實際上也是整數碼.85第五章語法制導翻譯及中間代碼生成

§5.3自底向上語法制導翻譯一、簡單算術表達式和賦值語句的翻譯

1.翻譯成四元式

2.類型檢查與類型轉換二、布爾表達式的翻譯

1.概述2.布爾表達式的翻譯方法

3.翻譯成四元式的實現三、控制語句翻譯1.語句標號和goto語句的翻譯2.條件語句的翻譯3.布爾表達式的翻譯方法4.while循環語句翻譯5.for循環語句的翻譯四、數組元素的翻譯1.下標變量地址的計算2.數組元素的翻譯五、過程語句的翻譯1.參數傳遞方式2.過程語句的翻譯六、說明語句的翻譯1.變量說明的翻譯2.數組說明的翻譯3.過程說明的翻譯

86§5.3自底向上語法制導翻譯

一、簡單算術表達式和賦值語句的翻譯

2.類型檢查與類型轉換

(1)目的1)類型檢查是編譯程序語義檢查不可缺少的一部分。類型檢查就是對訪問數據的操作和被訪問數據的類型進行檢查檢查操作的合法性和數據類型的相容性。例如，在PASCAL語言中，若算術運算符的操作數為布爾量，或者賦給實型變量值是個指針，則編譯程序報告“類型不相容”的診斷信息。

2)允許類型混合，但在處理時要統一，所以必須進行類型轉換。例如，加法運算“+”允許運算對象是整型數或實型數,如果一個運算對象是實型，另一個運算對象是整型，其運算結果的類型是實型，由于實型數和整型數的內部表示不相同，因此為了使整型數能參加實型數運算，必須事先將整型數轉換成實型數。87

(2)類型檢查

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

X·MODE的值或為r(實型)或為int(整型)。原來X的信息除X.PLACE，還有X.MODE。②對表達式的每一規則的語義子程序進行修改，增加關于類型信息的語義規則。③必要時應產生對運算量進行類型轉換的四元式，(itr,A,,T)把整型變量A轉換成實型變量，結果存在T中。此外，在書寫語義子程序時，為閱讀上的直觀性，我們用+i,*i等表示整型運算符，用+r,*r等表示實型運算符。現以規則E∷=E(1)OPE(2)為例，給出語義子程序的具體描述如下：89現以規則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為實型量,則產生四元式序列為(itr,2,-,T1)(*r,X,T１,T２)(+i,I,1,T3)(itr,T3,-,T４)(*r,A,T4,T5)(+r,T2,T5,T6)91第五章語法制導翻譯及中間代碼生成

§5.3自底向上語法制導翻譯一、簡單算術表達式和賦值語句的翻譯

1.翻譯成四元式2.類型檢查與類型轉換二、布爾表達式的翻譯

1.概述2.布爾表達式的翻譯方法

3.翻譯成四元式的實現三、控制語句翻譯1.語句標號和goto語句的翻譯2.條件語句的翻譯3.布爾表達式的翻譯方法4.while循環語句翻譯5.for循環語句的翻譯四、數組元素的翻譯1.下標變量地址的計算2.數組元素的翻譯五、過程語句的翻譯1.參數傳遞方式2.過程語句的翻譯六、說明語句的翻譯1.變量說明的翻譯2.數組說明的翻譯3.過程說明的翻譯

92第五章語法制導翻譯及中間代碼生成

§5.3自底向上語法制導翻譯一、簡單算術表達式和賦值語句的翻譯

1.翻譯成四元式2.類型檢查與類型轉換二、布爾表達式的翻譯

1.概述2.布爾表達式的翻譯方法3.翻譯成四元式的實現三、控制語句翻譯1.語句標號和goto語句的翻譯2.條件語句的翻譯3.布爾表達式的翻譯方法4.while循環語句翻譯5.for循環語句的翻譯四、數組元素的翻譯1.下標變量地址的計算2.數組元素的翻譯五、過程語句的翻譯1.參數傳遞方式2.過程語句的翻譯六、說明語句的翻譯1.變量說明的翻譯2.數組說明的翻譯3.過程說明的翻譯

93§5.3自底向上語法制導翻譯

二、布爾表達式的翻譯

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

說明：1）布爾表達式的文法是一個二義文法例如：該文法的一個句子a∧b∨c有兩棵不同的語法樹與之對應，所以該文法是一個二義文法。EEE∨EE∧abcEEE∧aEE∨bc952）規定布爾運算符的優先順序是:、∧、∨。并假定∧和∨為左結合。所有關系運算符優先級相同,且高于任何布爾運算符,低于算術運算符。3）i可認為是布爾表達式也可視為數值（1為真true,0為假false)。4）

iropi中rop是關系運算符，i是布爾變量或算術值96(3)布爾表達式求值方法

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

2）采取某種優化措施，有時并不需要將一個布爾表達式從頭算到尾，而只須計算它的一個子表達式，便能確定整個布爾表達式真和假。例如，對于A∨B，只要計算出A為真，則不管B值如何，A∨B之值一定為真。又如對A∧B，只要計算出A為假，則A∧B必然為假，等等。對于三種邏輯運算，可作如下等價的解釋：A∨B:ifAthentrueelseBA∧B:ifAthenBelsefalseA:ifAthenfalseelsetrue用這種方式實現控制語句的布爾表達式尤其方便。對應上述兩種計算方法，其布爾表達式有兩種不同的翻譯方法。97第五章語法制導翻譯及中間代碼生成

§5.3自底向上語法制導翻譯一、簡單算術表達式和賦值語句的翻譯

1.翻譯成四元式2.類型檢查與類型轉換二、布爾表達式的翻譯

1.概述

2.布爾表達式的翻譯方法

3.翻譯成四元式的實現三、控制語句翻譯1.語句標號和goto語句的翻譯2.條件語句的翻譯3.布爾表達式的翻譯方法4.while循環語句翻譯5.for循環語句的翻譯四、數組元素的翻譯1.下標變量地址的計算2.數組元素的翻譯五、過程語句的翻譯1.參數傳遞方式2.過程語句的翻譯六、說明語句的翻譯1.變量說明的翻譯2.數組說明的翻譯3.過程說明的翻譯

98§5.3自底向上語法制導翻譯

二、布爾表達式的翻譯

2.布爾表達式的翻譯方法

（1）如同翻譯算術表達式一樣，用于求值例如，布爾表達式a∧(b∨c=d)將被翻譯成如下四元式：1)(,a,-,T1)2)(=,c,d,T2)3)(∨,b,T2,T3)4)(∧,T1,T3,T4)99仿照翻譯算術表達式的方法，很容易寫出布爾表達式文法G［E］的每個規則用于求值的語義動作。(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)作為條件控制的布爾表達式的翻譯

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

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

103第五章語法制導翻譯及中間代碼生成

§5.3自底向上語法制導翻譯一、簡單算術表達式和賦值語句的翻譯

1.翻譯成四元式2.類型檢查與類型轉換二、布爾表達式的翻譯

1.概述2.布爾表達式的翻譯方法

3.翻譯成四元式的實現三、控制語句翻譯1.語句標號和goto語句的翻譯2.條件語句的翻譯3.布爾表達式的翻譯方法4.while循環語句翻譯5.for循環語句的翻譯四、數組元素的翻譯1.下標變量地址的計算2.數組元素的翻譯五、過程語句的翻譯1.參數傳遞方式2.過程語句的翻譯六、說明語句的翻譯1.變量說明的翻譯2.數組說明的翻譯3.