1、第8章 語法制導翻譯法(1) 翻譯程序：它將用某種源語言寫的程序(源程序)轉換成等價的用某種目標語言寫的程序(目標程序)，其中的目標程序可以是某種中間語言程序。中間語言:如匯編語言程序、四元式形式的程序等等；語法制導翻譯:就是先給文法中的每個產生式添加一個成分，這個成分常稱為語義動作或翻譯子程序，在執行語法分析的同時，執行相應產生式的語義動作。這些語義動作不僅指明了該產生式所生成的符號串的意義，而且還根據這種意義規定了對應的加工動作。這些加工動作包括查填各類表格、改變編譯程序的某些變量之值、打印各種錯誤信息以及生成中間語言程序等等。一旦某個產生式選用之后，接著就執行相應的語義動作，完成預定的翻

2、譯工作。第8章 語法制導翻譯法(2)編譯程序翻譯程序：源程序=等價的目標程序。目標程序可以是中間代碼：匯編語言程序、四元式、三元式、逆波蘭表示等。語法制導翻譯：給文法中的每個產生式添加一個成分語義動作或翻譯子程序。8.1 一般原理和樹變換語法制導翻譯法(SDTS) 一個源語言 一個目標語言 一組翻譯規則SDTS是一個CFG(Context Free Grammar) 上下文無關文法。SDTS是一個上下文無關文法T=(VT, VN, , R , S) VT: 有窮輸入字母表 VN: 有窮非終結符號集合 : 有窮輸出字母表 R : 一組Aw,y 規則的有窮集合 AVN, w(VTVN)*, y(V

3、N)* S : 開始符號8.1一般原理和樹變換8.1.1 一般原理(1)直觀地說，語法制導翻譯法(SDTS)由一個源語言、一個目標語言和一組翻譯規則組成，這組規則可將任何源語言符號串翻譯成對應的目標語言串。SDTS的翻譯規則是文法中的產生式再添加上語義動作。作為一個概念模型，SDTS提供了一個極好的框架以理解翻譯程序的某些基本原理。因此，我們首先給出SDTS的定義并討論它的特性，然后，再介紹實現它的方法。SDTS也是一個CFG，其形式定義如下：SDTS是一個五元組T=(VT，VN，R，S)8.1一般原理和樹變換8.1.1 一般原理(2)SDTS是一個五元組 T=(VT，VN，R，S)VT是一個

4、有窮的輸人字母表，包含源語言中的符號：VN是一個有窮的非終結符號集合：是一個有窮的輸出字母表，包含出現在翻譯串或輸出串中的那些符號；R是形如Aw，y的規則的有窮集合(這種規則的定義見后)：SVN是一個開始符號，其含義和用法如同CFG中的開始符號。8.1一般原理和樹變換8.1.1 一般原理(3)R中的規則形如 Aw，y AVNw是由終結符和(或)非終結符組成的串：y則是由VN和(或)中的符號組成的串。注意：出現在w和y中的非終結符必須是一一對應的。串w稱為規則的源成分；串y稱為規則的翻譯成分。R中的規則有時也稱為翻譯規則。T的基礎源文法是一個CFG：(VN，VT，P，S)，其中:P是形如Aw(即

5、T中源成分)的產生式的集合;Aw，y是T中R的一個規則也就是說，從T中去掉輸出字母表，再從T的規則中移走翻譯成分，就可得到T的基礎源文法。類似地，也可以定義T的基礎目標文法，即從T中去掉輸入字母表VT并從丁的規則中移去源成分。 8.1一般原理和樹變換8.1.1 一般原理(4)例如，考慮SDTS T1=(a，b，c，+，-，E，T，A，ADD，SUB，NEG，x，y，z，R，E)，其中R由下列翻譯規則組成： EE+T，T E ADD EE-T，E T SUB E-T，T NEG ET，T TE，E TA，A Aa，x Ab，y Ac，zT1的基礎源文法是： EE+T|E-T|-T|T TE|A

6、Aa|b|cT1的基礎目標文法則是： ET E ADD | E T SUB | T NEG | T TE | A Ax|y|z 一個翻譯模式是一個形如(u,v)的串對，其中：u是SDTS基礎源文法的一個句型,它是由VN和VT中元素組成的串。而v稱為與其對應的翻譯,它是由VN和中元素組成的串。翻譯模式的定義如下：(S,S)是一個翻譯模式，且這兩個S是相關的(S是SDTS的開始符號) (aAb，aAb)是一個翻譯模式，且兩個A是相關的：此外，若Ag，g是R中的一條規則，那么(agb，agb)也是一個翻譯模式。規則中g和g的非終結符之間的相關性也必須帶進這種翻譯模式之中。8.1一般原理和樹變換8.1

7、.1 一般原理(5)8.1一般原理和樹變換8.1.1 一般原理(6)表示法 (aAb，aAb) = (agb，agb) 表示一種翻譯模式到另一種翻譯模式的變換。不難看出，一個翻譯模式的第一部分恰好是SDTS中基礎源文法(是一個CFG)的一個句型：而第二部分是其對應的翻譯，即基礎目標文法的一個句型。 由一個SDTS T所定義的翻譯是下述對偶集： (x,y) |( S,S) =* (x,y),xVT* & y*顯然，它類似于CFG中“語言”的定義 例如，考慮輸入串 -a+c-b 它是可從SDTS T1的基礎源文法推出的，即E = E-T = -T-T = -E-T = -E+T-T = -T+T-

8、T = -A+T-T = -a+T-T = -a+A-T = -a+c-T = -a+c-A = -a+c-a 基礎文法T 1(E): EE+T | E-T | -T | T TE | A Aa | b | c基礎文法T 1(E): EE+T | E-T | -T | T TE | A Aa | b | cSDTS T1: EE+T,T E ADD EE -T,E T SUB E-T , T NEG ET, T TE , E TA , A Aa , x Ab , y Ac , z 翻譯模式是一個形如(u,v)串對 例如對輸入串 -a+c-b的翻譯過程(E,E)=(E-T2, E T2 SUB)

9、=(-T1-T2, T1 NEG T2 SUB)=(-E-T2, E NEG T2 SUB)=(-E+T1-T2, T1 E ADD NEG T2 SUB)=(-T3+T1-T2, T1 T3 ADD NEG T2 SUB)=(-A+T1-T2, T1A ADD NEG T2 SUB)=(-a+T1-T2, T1 x ADD NEG T2 SUB)=(-a+A-T2, A x ADD NEG T2 SUB)=(-a+c-T2, z x ADD NEG T2 SUB)=(-a+c-A, z x ADD NEG A SUB)=(-a+c-b, z x ADD NEG y SUB)為清楚起見，上述翻

10、譯模式中的某些非終結符寫出了下標，以指明輸入(源)串和輸出(目標)串中所出現的非終結符之間的相關性。因此，出現在第二個翻譯模式中的兩個T是分別用T1和T2來區分的。因此，輸入串-a+c-b所對應的翻譯是： z x ADD NEG y SUB事實上，已經有了將一個(中綴)表示形式的算術表達式翻譯成與其對應的后綴表達式的翻譯器。而且，通過該SDTS中最后的三條規則(Aa,x|b,y|c,z)，引進了某些詞法操作以使這個翻譯過程清晰化。當然，在一個實際的編譯程序中，標識符的集合是由某個終結符(例如id)代表的而且是通過詞法分析程序識別和形成的。 8.1.2 樹變換 語法制導的翻譯過程也可用語法樹來說

11、明。 圖8.1給出了根據T1的基礎源文法推導輸入串 -a+c-b的語法樹。它的翻譯也可看做從一棵樹到另一棵樹的變換，其變換過程如下： 從樹中剪掉終結符符號的結點重新排列結點的孩子添加對應輸出符號的終結符結點例如，圖8.2給出了去掉圖8.1中終結符結點之后的語法樹在這種情形下，兩個本來不同的產生式由于去掉了終結符可能會變得完全相同。例如，產生式 EE+T，T E ADD EE-T，E T SUB E-T，T NEG ET，T TE，E TA，A Aa，X Ab，y Ac，z從樹中剪掉終結符符號的結點重新排列結點的孩子添加對應輸出符號的終結符結點因此，輸入串-a+c-b所對應的翻譯是： z x A

12、DD NEG y SUB EE+T，T E ADD EE-T，E T SUB E-T，T NEG ET，T TE，E TA，A Aa，X Ab，y Ac，z8.2 簡單SDTS和自上而下翻譯器如果每一規則的翻譯成分中，非終結符出現的次序與它們在源成分出現的次序相同，則稱一個SDTS是簡單的(simple)；但是，如果 AA1+A2， A2 A1 ADD是SDTST的一個規則，那么，該SDTS T就不是簡單的。顯然，利用簡單的SDTS進行翻譯不需要重排語法樹的結點，只要去掉源成分中的終結符(結點)并插入相應的翻譯成分中的終結符即可。 定理8.1 如果T=(VN,VT,R,S)是其基礎源文法為LL

13、(K)的簡單SDTS，那么，存在一個自上而下的確定的下推翻譯器PDT(Push-Down Translater)，它接收T的輸入語言中的任何符號串并產生對應的輸出串。PDT P的定義如下：P的一個構形是一個四元組(q,x,y,z),其中，q是它的有窮控制器的狀態，x是尚待掃描的輸入串，y是下推棧，z是此時被打印出的輸出符號串。于是，在某次移動中，便有 (q,ax,Yy,z)(r,x,gy,zz) 其中，存在一條翻譯器規則 (q,a,Y)包含(r,g,z)換言之，在狀態q面臨輸入符號a且棧頂符號為Y時，P才允許移動到狀態r，這一移動的結果是：輸人符號a被去掉，棧頂符號Y被g所替換，而且串z已作為

14、輸出串打印出。 稱w是關于x的輸出，如果對于某個狀態q和棧符號串u，存在(q0,x,z0,) * (q,u,w)。其中，q0是初態；z0是棧的初始內容；為空串。若u=，則稱P停止于空棧；若q是某個終態，則稱P停止于終態。如果P滿足下述兩個條件，則稱P是確定的： 對所有的狀態q，輸入串a和棧符號Z，(q,a,Z)至多只包含一個元素。 若(q,Z)非空，則不存在符號a(a) 使得(q,a,Z)非空，即對于某個狀態和棧符號，在空移動和非窯移動之間不應存在沖突。給定SDTS T，其中，T的基礎源文法是LL(1)，我們可以描述一個PDT P的構造，使得這個P：接收T的基礎源文法中每一個串；恰好打印出T中

15、與每個這種串對應的翻譯串。 典型的自上而下LL(1)識別器有兩類移動: 應用移動。位于棧頂的非終結符A被符號串w所替換。 其中，Aw是文法中的一個產生式；利用棧頂非終結符A和下一輸入符號去查看對應的LL(1)分析表，可使這種操作確定化。 匹配移動。棧頂的終結符號a與下一輸入符號匹配。 經過該操作之后，去掉了棧頂符號并使讀頭前進到下一位置。匹配失敗即說明輸入串有語法錯。 通過上面的分析，現定義PDTP的操作為： 在一應用移動中，非終結符A已位于棧頂；借助分析表，就知道選用產生式Aw來進行歸約現假定R中的翻譯規則是Aw,z其中, w=a0B1a1B2a2BkaK，而z=b0B1b1B2Bkbk。這

16、里；Bi是非終結符，ai是輸人符號串(或空)，bi是輸出符號串(或空)，且k0(注意：這個翻譯規則是簡單的)。 假定輸入和輸出符號是可區分的，那么，在一次應用移動中，位于棧頂的A就由下面的復合串 b0a0B1b1a1B2BkaKbk 所替代，而b0變成棧頂符號。 若棧頂符號是輸出字母表的一個元素。則從棧中逐出它，并將它作為輸出符號打印出。 若棧頂符號是輸入字母表VT的一個元素，則它應與下一個輸入符號匹配(否則為語法錯)。從棧中逐出它，并使讀頭前進一位置(即掃描下的輸入符號)。 例如，考慮簡單的SDTS：S1S2S,xSySz S0,w注意：此時,不必用下標來區分S,因為這個SDTS是簡單的。它

17、的基本源文法顯然是LL(1)。以一個輸入串為例,假定輸入串為1102020，可以定義與(8.1)對應的PDT如下： 若棧頂為S，并且 1) 如果輸入符號為1, 則從棧中逐出S，并將x1Sy2Sz下推進棧(x位于棧頂)； 2) 如果輸人符號為0，則從棧中逐出S，并將w0下推進棧(w位于棧頂)。 若棧頂符號tx,y,z,w，則從棧中逐出t，并輸出t。 若棧頂符號t0,1,2，則讓t繼續與下一輸入符號匹配。在翻譯過程中，可以根據情況選用上述規則直至該PDT停止或發現語法錯誤。規則變換：Aa0B1a1B2a2, b0B1b1B2b2=Ab0a0B1b1a1B2b2a2例如： S1S2S, xSySz

18、S0, w= Sx1Sy2Sz Sw0012#Sw0 x1Sy2Sz操作棧輸出輸入串S#1102020#x1Sy2Sz#1102020#1Sy2Sz#x1102020#Sy2Sz#102020#x1Sy2Szy2Sz#102020#1Sy2Szy2Sz#x102020#Sy2Szy2Sz#02020#w0y2Szy2Sz#02020#0y2Szy2Sz#w02020#y2Szy2Sz#2020#2Szy2Sz#y2020#Szy2Sz#020#w0zy2Sz#020#0zy2Sz#w020#zy2Sz#20#2Sz#zy20#Sz#0#w0z#0#0z#w0#z#結論：如果SDTS的基礎源文法

19、是二義性的，那么就不存在確定的PDT。若SDTS的基礎源文法是LL(1)，那么，它的PDT是確定的，而且對每一個可接收的輸入串恰好存在一個翻譯。雖然我們只是討論了符號串到符號串的翻譯器，但如果在輸出串中再添加一些語義操作，例如查填符號表、修改編譯程序的變量等等，就可能構造一個實用的翻譯程序。 8.3 簡單后綴SDTS和自下而上翻譯器 如果SDTS是簡單的，且規則有如下形式 Aa0B1a1B2a2, B1B2w 則稱SDTS是簡單后綴的SDTS。定理 8.2 對于基礎文法為LR(k)簡單后綴的SDTS，則存在一確定的LR(k) PDT，它接受輸入語句并產生對應輸出串。在選擇產生歸約時，輸出相應的

20、輸出終結符符號。通過在LR(k)分析器的歸約動作中加入下述操作，很容易將一個LR(k)分析器改造成一個后綴翻譯器。如果選定產生式i進行歸約，則在執行歸約操作之后，再打印出與產生式i相關的翻譯成分中的終結符部分。 8.3.1 后綴翻譯 有算術表達式，考慮其R部分由下述翻譯規則組成的SDTS： EE+T,E T ADD ET,T TT*F,T F MPY TF,F FA,A LOAD F(E)，E AAa,Aa Aa,a該SDTS顯然是簡單后綴的，表達式 aa*(aaa+a) 的翻譯是 aa LOAD aaa LOAD a LOAD ADD MPY其中，操作符LOAD操作在它前面的標識符上。如果希

21、望LOAD操作在它后面的標識符上，可用下面兩條規則替代FA，A LOAD： FL A，L A L，LOAD這樣修改后的文法仍然是LR(1)。產生式L的歸約操作可通過向前查看后面標識符的一個符號所確定。于是，表達式aa*(aaa+a)的翻譯是LOAD aa LOAD aaa LOAD a ADD MPYE； FJP L1；S1;UJF L2;LOC L1；S2; LOC L2;8.3.2 IF-THEN-ElSE控制語句(1) 考慮高級語言中的條件語句 Sif E then S1 else S2其中，E是表達式；S是一語句。對于這種形式的輸入串，簡單后綴翻譯器先生成關于E的計值代碼，然后翻譯那兩

22、個語句。但這樣一種語句要求在E和第一個S之間產生一個條件分支指令，在兩個語句之間產生一個無條件分支指令。如何來產生這些指令呢?解決辦法之一是將原來的單產生式拆成三個產生式： ST else S2 TI then S1 Iif E這三個產生式合起來與原來的那個產生式等價。 8.3.2 IF-THEN-ElSE控制語句(2)經這樣變形后，可以構造一個簡單的后綴SDTS： ST else S2，T S2； LOC L2; TI then S1, I S1； UJP L2; LOC L1; Iif E，E；FJP Ll；E； FJP L1；S1;UJF L2;LOC L1；S2; LOC L2;8.3

23、.2 IF-THEN-ElSE控制語句(3)另一種解決辦法是引進含“then和“else”鍵字的產生式： Sif E H S L S，E H S L S；LOC L2; Hthen，；FJP L1； Lelse, ；UJP L2；LOC L1； 這些附加的產生式的作用在于；在分析該語句的過程中，能在適當的位置插入所需要的翻譯串。當然，也可以使用空產生式來實現同樣的目的： Sif E then H S else L S, E H S L S；LOC L2； H，；FJP L1； L，；UJP L2；LOC Ll；這三種解決辦法產生同樣的效果。 for(初值表達式; 循環判定式; 更新表達式) 循

24、環體語句;8.3.3 函數調用 考慮函數調用的情況，假定有關的基礎源文法是FA(L) LL；E LE AAa Aa注意：這里實參表列由分號隔開的若干個E組成。如果允許CALL和過程名都出現在實在參數代碼之后，就需要一個非簡單的翻譯器。下面的簡單后綴的SDTS可用來產生過程的后綴調用形式：FA(L),A L;CALL LL;E，L ELE,E AAa,Aa Aa，a那么，函數調用：aa(a;a+aaa) 將翻譯成aa；LOAD a；LOAD a；LOAD aaa；ADD；CALL而且CALL將操作在第一個標識符aa上。8.4 抽象語法樹的構造(1)抽象語法樹AST(Abstract-Syntax

25、 Tree)是某個語言結構的一種簡潔的樹形表示形式，它只需包含該結構尚須轉換或歸約的信息。一般說來，任何語法結構(例如表達式、控制結構和說明)都可以用AST表示。AST也可作為一個多遍編譯程序的中間語言結構。采用AST表示法有助于代碼的產生和優化。8.4 抽象語法樹的構造(2)考慮文法G0： EE+T ET TT*F TF F（E） Fa利用該文法構造的每個簡單表達式的語法樹都比較大。例如，簡單表達式a*(a+a)的語法樹如圖8.4所示。這棵樹有7個末結點和11個中間結點，但所給表達式本身卻只有兩個運算符和三個操作數為什么差別如此之大呢? 8.4 抽象語法樹的構造(3)可按如下方式將這棵語法樹

26、簡化成一個AST。首先，去掉與單非產生式,上提終結符結點。第二，上提運算符并讓它取代其父結點。第三，去掉括號，并上提運算符。最后得到的語法樹便是一個AST。 這棵樹也是下述表達式的抽象語法樹： a*(a)+a) a*(a+(a) (a*(a+a)注意：AST并不是一種規范形式，它并沒有指明運算符的交換律和結合律例如，a*b+c、c+b*a、c+a*b等表達式在數學上是等價的，但可生成不同的AST只要稍微改變一下SDTS的實現方式，就可不必生成一個完整的語法樹而直接構造一個AST 8.4.1 自下而上構造AST 對于一個自下而上分析器.考慮產生式EE+T，當E+T作為句柄出現在棧頂時，已存在兩棵

27、子樹E和T，但并無以“+”為根的子樹。這條規則是說：構造以“+”為根的一棵子樹，并將E和T子樹作為它的兩個孩子(左孩子和右孩子)。于是，得到以“+”為根的一棵新子樹，將它連到E以替代棧頂的E和T。對于規則ET，當T是句柄時，它本身已連在某棵子樹上，將這棵子樹連到E以替代棧頂上的T。最后，規則F(E)告訴我們將E子樹連到F以取代棧頂的(E)，而Fa則指明將由終結符a構成的單一結點的樹連到F并用F取代a。當到達接收狀態時，已構造好一棵AST，且它已連到位于棧頂的開始符號上。 表8.2 根據文法G0及其分析器直接產生一個AST文法中的產生式AST的成分EE+TETTTT*FTFFF(E)EFaa8.

28、4.2 AST的拓廣 AST的一般形式是：其中間結點是運算符，而它的葉子為簡單變量或常數。事實上，運算符號可以是任何單目運算符、二日運算符或n目運算符。例如，一個類似于X(el,e2,en) 的數組元素可表示成圖8.8所示形式的AST，其中，X是多維數組的名字，el，e2，en為其下標。 AST也可表示控制結構和說明(略)。 8.5 屬性文法(1) 屬性文法(Attribute Grammar)是Knuth于1968年提出的，也有人稱它為屬性翻譯文法。屬性文法以上下文無關文法為基礎，只不過為每個文法符號配備了一些屬性。屬性同變量一樣，可以進行計算和傳遞。屬性加工的過程即是語義處理的過程。屬性加

29、工同語法分析同時進行，加工規則也附加于語法規則之上。在構造語法樹時，諸屬性之值通過文法中的產生式而層層傳遞(有時從產生式的左邊向右或從右向左傳遞)。當語法樹最終構造完成時，就得到文法開始符號的屬性值，它也是該文法所描述的對象的最終語義。屬性一般用標識符(或數)表示，通常寫在相應文法的下邊，它的意義局部于它所在的產生式。 8.5 屬性文法(2)屬性分為兩種:一種稱為繼承屬性(Iherited Attribute)，其計算規則按“自上而下”方式進行，即文法產生式右部符號的某些屬性根據其左部符號的屬性和(或)右部的其它符號的某些屬性計算而得。這種屬性也稱為推導型.另一種稱為綜合屬性(Synthesi

30、zed Attribute)，其計算規則按“自下而上”方式進行，即產生式左部符號的某些屬性根據其右部符號的屬性和(或)自己的其它屬性計算而得這種屬性也稱為歸約型例如， ApXq,r,Ys,t p=q+s，r=p+t其中，p、q、r、s、t是屬性，分別屬于A、X和Y。p是綜合屬性，r是繼承屬性，而q、s、t的性質則需要與其它產生式的屬性計算規則一起加以考慮才能確定通常規定：每個文法符號的繼承屬性和綜合屬性之交集為空 8.5.1 L屬性文法 L屬性文法也稱為自上而下的屬性翻譯文法，它特別適合于用來指導自上而下的分析過程其定義如下： 產生式右部任一文法符號V的繼承屬性僅依賴于下述兩種屬性值中的一種：

31、 1) 產生式左部的繼承屬性； 2) 產生式右部但位于V左邊的符號的任何屬性 產生式左部符號的綜合屬性僅依賴于下面的屬性值中的一種： 1) 產生式左部符號的繼承屬性： 2) 產生式右部符號(除自身外)的任意屬性。8.5.2 S屬性文法 S屬性文法也稱為自下而上的屬性翻譯文法，它適用于指導自下而上的分析過程，其定義如下： 全部非終結符的屬性是綜合屬性； 同一產生式中相同符號的各綜合屬性之間無相互依賴關系： 如果q是某個產生式中文法符號V的繼承屬性，那么，屬性q的值僅依賴于該產生式右部位于V左邊的符號的屬性。8.6 中間代碼形式 在討論屬性翻譯文法的具體用法之前，先介紹編譯程序中的中間代碼形式所謂

32、中間代碼形式是指用來表述源程序并與之等效的一種編碼方式，可根據具體情況將它設計成各種形式。例如，匯編語言程序就可看做一種中間代碼形式。一般說來，對于一個多遍掃描的編譯程序，越到后面階段，所產生的中間代碼也就越接近于機器代碼，于是，編譯程序首先將源程序翻譯成中間代碼形式，然后，再把中間代碼翻譯成目標代碼，也就是把語義分析和代碼生成分開處理比較常用的中間代碼形式有逆波蘭表示、四元式、三元式和樹形表示等等下面，我們討論這幾種典型的中間代碼形式。8.6.1 逆波蘭表示法 (1)逆波蘭表示法是由波蘭邏輯學家J.Lukasiewicz首先提出來的一種表示表達式的方法在這種表示法中，運算符直接跟在其運算量(

33、操作數)的后面。因此，逆波蘭表示法有時也稱為后綴(post fix)表示法下面是一些逆波蘭表示法的例子： AB* 表示A*B AB*C+ 表示A*B+C ABCD+* 表示A*(B+CD) AB*CD*+ 表示A*B+C*D8.6.1 逆波蘭表示法 (2)與習慣的中綴表示法相比，逆波蘭表示法有兩個明顯的特點：第一，不再有括號，而且既簡明又確切地規定了運算的計算順序。第二，運算處理極為方便，只需從左至右掃描表達式中的符號當遇到運算量時，就把它存到運算量棧中，當遇到雙目(單目)運算符時，就取出最近存人運算量棧中的兩個(一個)運算對象進行運算處理，并把計算的結果作為一個新的運算量存人運算量棧，再繼續

34、向右掃描表達式中的符號，直至整個表達式處理完畢只要遵守在運算量之后直接緊跟它們的運算符這樣的規則，就能很容易地將逆波蘭表示推廣到其它非表達式結構。 8.6.2 逆波蘭表示法的推廣(1) 考慮賦值語句，其一般形式為 :=表達式)如果把“:=”看做一個進行賦值運算的雙目運算符，那么，賦值語句的逆波蘭表示式為 :=而多重賦值可表示為 :=例如，賦值語句A:=B*C+D可寫做 ABC*D+:=注意：當處理到“:=”這個運算符時，在表達式賦值執行完畢后，必須把和從棧中消除，因為，此時不產生結果值。對于多重賦值的情形，則需要把這個量保存下來，直到整個多重賦值語句處理完畢后才能退掉。此外，因為要把之值送到該

35、中去，所以在棧中只需的地址而不需其值。8.6.2 逆波蘭表示法的推廣(2)下面，討論如何用逆波蘭表示法表示轉向語句、條件語句和條件表達式。為此，先引進幾個運算：Jump 是一個單目運算符，“jump”表示無條件轉到去,“jump”表示無條件轉到去。jumpf是一個雙目運算符,“ jumpf” 表示當 為假時，轉移到 處；否則，按原順序執行。那么，轉向語句的逆波蘭表示就是jump;8.6.2 逆波蘭表示法的推廣(3)條件語句的逆波蘭表示是 jumpfjump，其中,指的是開始符號的序號,指的是緊接在之后的那個符號的序號。高級語言中的數組說明array All，u1，lnun可用l1u1lnunA

36、 ADEC來表示，其中，只有ADEC是運算符，它的運算對象的個數是可變的，由其下標的個數決定。類似地，下標變量A，可用A SUBS表示。高級語言中的其它成分也可用類似的表示法表示，不在此一一討論。 一個用逆波蘭表示法表示程序段的例子(例8.1)begin integer k； k:=100； h: if ki+j then begin k:=k-1； goto h end else k:=i*2-j*2； i:=j:=0end 該程序段的逆波蘭表示是(1) Block(2) k 100:=(5) h：(7) kij+(23)jumpf(14) kkl-:=h jump (32)jump(23)

37、 ki2*j2*-:=(32) ij0:=:=(37) Blockend if E then S1 else S2blockE jumpfS1 jump S2blockendwhile E do S E jumpf S jump for k:= k1 step k3 until k2 do Sk:=k1; kk2-sign(k3)*0 jumpf Skkk3+:= jump8.6.3 四元式（1） 四元式的一般形式是 當為單目運算時，總認為為空，即此時施運算于，運算結果放在中。 例如，AB的四元式是 * A B T這里T是暫存A*B之計算結果的臨時變量按此方式。表達式A*B+C*D的四元式為* A B T1* C D T2+ T1 T2 T3其中T1,T2,T3都是計算結果的臨時變量。和逆波蘭表示相仿，四元式也是按照表達式的執行順序組合起來的。 8.6.3 四元式（2）-(A/B-C) 的四元式為 / A B T1 - T1 C T2 T2