編譯原理 8章

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

2、定的翻譯工作。第第8 8章章 語法制導(dǎo)翻譯法語法制導(dǎo)翻譯法(2)編譯程序編譯程序翻譯程序翻譯程序：源程序=等價的目標(biāo)程序。目標(biāo)程序目標(biāo)程序可以是中間代碼可以是中間代碼：匯編語言程序、四元式、三元式、逆波蘭表示等。語法制導(dǎo)翻譯：語法制導(dǎo)翻譯：給文法中的每個產(chǎn)生式添加一個成分語義動作或翻譯子程序。8.1 8.1 一般原理和樹變換一般原理和樹變換 語法制導(dǎo)翻譯法(SDTS) 一個源語言 一個目標(biāo)語言 一組翻譯規(guī)則 SDTS是一個CFG(Context Free Grammar) 上下文無關(guān)文法。SDTS是一個上下文無關(guān)文法 T=(VT, VN, , R , S) VT: 有窮輸入字母表 VN: 有窮

3、非終結(jié)符號集合 : 有窮輸出字母表 R : 一組Aw,y 規(guī)則的有窮集合 AVN, w(VTVN)*, y(VN)* S : 開始符號8.18.1一般原理和樹變換一般原理和樹變換8.1.1 8.1.1 一般原理一般原理(1)(1) 直觀地說，語法制導(dǎo)翻譯法(SDTS)由一個源語言、一個目標(biāo)語言和一組翻譯規(guī)則組成，這組規(guī)則可將任何源語言符號串翻譯成對應(yīng)的目標(biāo)語言串。 SDTS的翻譯規(guī)則是文法中的產(chǎn)生式再添加上語義動作。作為一個概念模型，SDTS提供了一個極好的框架以理解翻譯程序的某些基本原理。因此，我們首先給出SDTS的定義并討論它的特性，然后，再介紹實現(xiàn)它的方法。 SDTS也是一個CFG，其形

4、式定義如下：SDTS是一個五元組T=(VT，VN，R，S)8.18.1一般原理和樹變換一般原理和樹變換8.1.1 8.1.1 一般原理一般原理(2)(2) SDTS是一個五元組 T=(VT，VN，R，S)VT是一個有窮的輸人字母表，包含源語言中的符號：VN是一個有窮的非終結(jié)符號集合：是一個有窮的輸出字母表，包含出現(xiàn)在翻譯串或輸出串中的那些符號；R是形如Aw，y的規(guī)則的有窮集合(這種規(guī)則的定義見后)：SVN是一個開始符號，其含義和用法如同CFG中的開始符號。8.18.1一般原理和樹變換一般原理和樹變換8.1.1 8.1.1 一般原理一般原理(3)(3) R中的規(guī)則形如 Aw，y AVNw是由終結(jié)

5、符和(或)非終結(jié)符組成的串：y則是由VN和(或)中的符號組成的串。注意：出現(xiàn)在w和y中的非終結(jié)符必須是一一對應(yīng)的。串w稱為規(guī)則的源成分；串y稱為規(guī)則的翻譯成分。R中的規(guī)則有時也稱為翻譯規(guī)則。 T的基礎(chǔ)源文法是一個CFG：(VN，VT，P，S)，其中:P是形如Aw(即T中源成分)的產(chǎn)生式的集合;Aw，y是T中R的一個規(guī)則也就是說，從T中去掉輸出字母表，再從T的規(guī)則中移走翻譯成分，就可得到T的基礎(chǔ)源文法。類似地，也可以定義T的基礎(chǔ)目標(biāo)文法，即從T中去掉輸入字母表VT并從丁的規(guī)則中移去源成分。 8.18.1一般原理和樹變換一般原理和樹變換8.1.1 8.1.1 一般原理一般原理(4)(4) 例如，考

6、慮SDTS T1=(a，b，c，+，-，E，T，A，ADD，SUB，NEG，x，y，z，R，E)，其中R由下列翻譯規(guī)則組成： 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 T1的基礎(chǔ)源文法是： EE+T|E-T|-T|T TE|A Aa|b|c T1的基礎(chǔ)目標(biāo)文法則是： ET E ADD | E T SUB | T NEG | T TE | A Ax|y|z 一個翻譯模式是一個形如(u,v)的串對，其中：u是SDTS基礎(chǔ)源文法的一個句型,它是由VN和VT中元素組成的串。而v稱為與其對應(yīng)的翻譯,它是由VN和中元

7、素組成的串。 翻譯模式的定義如下：(S,S)是一個翻譯模式，且這兩個S是相關(guān)的(S是SDTS的開始符號) (aAb，aAb)是一個翻譯模式，且兩個A是相關(guān)的：此外，若Ag，g是R中的一條規(guī)則，那么(agb，agb)也是一個翻譯模式。規(guī)則中g(shù)和g的非終結(jié)符之間的相關(guān)性也必須帶進(jìn)這種翻譯模式之中。8.18.1一般原理和樹變換一般原理和樹變換8.1.1 8.1.1 一般原理一般原理(5)(5)8.18.1一般原理和樹變換一般原理和樹變換8.1.1 8.1.1 一般原理一般原理(6)(6) 表示法 (aAb，aAb) = (agb，agb) 表示一種翻譯模式到另一種翻譯模式的變換。不難看出，一個翻譯模

8、式的第一部分恰好是SDTS中基礎(chǔ)源文法(是一個CFG)的一個句型：而第二部分是其對應(yīng)的翻譯，即目標(biāo)文法的一個句型。 由一個SDTS T所定義的翻譯是下述對偶集： (x,y) |( S,S) =* (x,y),xVT* & y*顯然，它類似于CFG中“語言”的定義 例如，考慮輸入串 -a+c-b 它是可從SDTS T1的基礎(chǔ)源文法推出的，即E = E-T = -T-T = -E-T = -E+T-T = -T+T-T = -A+T-T = -a+T-T = -a+A-T = -a+c-T = -a+c-A = -a+c-b 基礎(chǔ)文法T 1(E): EE+T | E-T | -T | T

9、TE | A Aa | b | c 基礎(chǔ)文法T 1(E): EE+T | E-T | -T | T TE | A Aa | b | c SDTS 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)=(-T1-T2, T1 NEG T2 SUB)=(-E-T2, E NEG T2 SUB)=(-E+T1-T2, T1 E ADD NEG T2 SUB)=(-T3+T1

10、-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) 為清楚起見，上述翻譯模式中的某些非終結(jié)符寫出了下標(biāo)，以指明輸入(源)串和輸出(目標(biāo))串中所出現(xiàn)的非終結(jié)符之間的相關(guān)性。因此，出現(xiàn)在第二個翻譯模式中的兩個T是分別用T1和T2來區(qū)分的。 因此

11、，輸入串-a+c-b所對應(yīng)的翻譯是： z x ADD NEG y SUB 事實上，已經(jīng)有了將一個(中綴)表示形式的算術(shù)表達(dá)式翻譯成與其對應(yīng)的后綴表達(dá)式的翻譯器。 而 且 ， 通 過 該 S D T S 中 最 后 的 三 條 規(guī) 則(Aa,x|b,y|c,z)，引進(jìn)了某些詞法操作以使這個翻譯過程清晰化。 當(dāng)然，在一個實際的編譯程序中，標(biāo)識符的集合是由某個終結(jié)符(例如id)代表的而且是通過詞法分析程序識別和形成的。 8.1.2 8.1.2 樹變換樹變換 語法制導(dǎo)的翻譯過程也可用語法樹來說明。 圖8.1給出了根據(jù)T1的基礎(chǔ)源文法推導(dǎo)輸入串 -a+c-b的語法樹。它的翻譯也可看做從一棵樹到另一棵樹的

12、變換，其變換過程如下： 從樹中剪掉終結(jié)符符號的結(jié)點重新排列結(jié)點的孩子添加對應(yīng)輸出符號的終結(jié)符結(jié)點例如，圖8.2給出了去掉圖8.1中終結(jié)符結(jié)點之后的語法樹在這種情形下，兩個本來不同的產(chǎn)生式由于去掉了終結(jié)符可能會變得完全相同。例如，產(chǎn)生式 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從樹中剪掉終結(jié)符符號的結(jié)點重新排列結(jié)點的孩子添加對應(yīng)輸出符號的終結(jié)符結(jié)點因此，輸入串-a+c-b所對應(yīng)的翻譯是： z x ADD NEG y SUB EE+T，T E ADD EE-T，E T SUB E-T，T NEG ET，T T

13、E，E TA，A Aa，X Ab，y Ac，z8.2 8.2 簡單簡單SDTSSDTS和自上而下翻譯器和自上而下翻譯器 如果每一規(guī)則的翻譯成分中，非終結(jié)符出現(xiàn)的次序與它們在源成分出現(xiàn)的次序相同，則稱一個SDTS是簡單的(simple)； 但是，如果 AA1+A2， A2 A1 ADD是SDTST的一個規(guī)則，那么，該SDTS T就不是簡單的。 顯然，利用簡單的SDTS進(jìn)行翻譯不需要重排語法樹的結(jié)點，只要去掉源成分中的終結(jié)符(結(jié)點)并插入相應(yīng)的翻譯成分中的終結(jié)符即可。 定理8.1 如果T=(VN,VT,R,S)是其基礎(chǔ)源文法為LL(K)的簡單SDTS，那么，存在一個自上而下的確定的下推翻譯器PDT

14、(Push-Down Translater)，它接收T的輸入語言中的任何符號串并產(chǎn)生對應(yīng)的輸出串。PDT P的定義如下：P的一個構(gòu)形是一個四元組(q,x,y,z),其中，q是它的有窮控制器的狀態(tài)，x是尚待掃描的輸入串，y是下推棧，z是此時被打印出的輸出符號串。 于是，在某次移動中，便有 (q,ax,Yy,z)(r,x,gy,zz) 其中，存在一條翻譯器規(guī)則 (q,a,Y)包含(r,g,z)換言之，在狀態(tài)q面臨輸入符號a且棧頂符號為Y時，P才允許移動到狀態(tài)r，這一移動的結(jié)果是：輸人符號a被去掉，棧頂符號Y被g所替換，而且串z已作為輸出串打印出。 稱w是關(guān)于x的輸出，如果對于某個狀態(tài)q和棧符號串u

15、，存在(q0,x,z0,) * (q,u,w)。 其中，q0是初態(tài)；z0是棧的初始內(nèi)容；為空串。若u=，則稱P停止于空棧；若q是某個終態(tài)，則稱P停止于終態(tài)。 如果P滿足下述兩個條件，則稱P是確定的： 對所有的狀態(tài)q，輸入串a(chǎn)和棧符號Z，(q,a,Z)至多只包含一個元素。 若(q,Z)非空，則不存在符號a(a) 使得(q,a,Z)非空，即對于某個狀態(tài)和棧符號，在空移動和非窯移動之間不應(yīng)存在沖突。 給定SDTS T，其中，T的基礎(chǔ)源文法是LL(1)，我們可以描述一個PDT P的構(gòu)造，使得這個P：接收T的基礎(chǔ)源文法中每一個串；恰好打印出T中與每個這種串對應(yīng)的翻譯串。 典型的自上而下LL(1)識別器有

16、兩類移動: 應(yīng)用移動。位于棧頂?shù)姆墙K結(jié)符A被符號串w所替換。 其中，Aw是文法中的一個產(chǎn)生式；利用棧頂非終結(jié)符A和下一輸入符號去查看對應(yīng)的LL(1)分析表，可使這種操作確定化。 匹配移動。棧頂?shù)慕K結(jié)符號a與下一輸入符號匹配。 經(jīng)過該操作之后，去掉了棧頂符號并使讀頭前進(jìn)到下一位置。匹配失敗即說明輸入串有語法錯。 通過上面的分析，現(xiàn)定義PDTP的操作為： 在一應(yīng)用移動中，非終結(jié)符A已位于棧頂；借助分析表，就知道選用產(chǎn)生式Aw來進(jìn)行歸約現(xiàn)假定R中的翻譯規(guī)則是Aw,z其中, w=a0B1a1B2a2BkaK，而z=b0B1b1B2Bkbk。這里；Bi是非終結(jié)符，ai是輸人符號串(或空)，bi是輸出符號

17、串(或空)，且k0(注意：這個翻譯規(guī)則是簡單的)。 假定輸入和輸出符號是可區(qū)分的，那么，在一次應(yīng)用 移 動 中 ， 位 于 棧 頂 的 A 就 由 下 面 的 復(fù) 合 串 b0a0B1b1a1B2BkaKbk 所替代，而b0變成棧頂符號。 若棧頂符號是輸出字母表的一個元素。則從棧中逐出它，并將它作為輸出符號打印出。 若棧頂符號是輸入字母表VT的一個元素，則它應(yīng)與下一個輸入符號匹配(否則為語法錯)。從棧中逐出它，并使讀頭前進(jìn)一位置(即掃描下的輸入符號)。 例如，考慮簡單的SDTS：S1S2S,xSySz S0,w 注意：此時,不必用下標(biāo)來區(qū)分S,因為這個SDTS是簡單的。它的基本源文法顯然是LL

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

19、x1Sy2Sz 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#結(jié)論： 如果SDTS的基礎(chǔ)源文法是二義性的，那

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

21、串。 在選擇產(chǎn)生歸約時，輸出相應(yīng)的輸出終結(jié)符符號。 通過在LR(k)分析器的歸約動作中加入下述操作，很容易將一個LR(k)分析器改造成一個后綴翻譯器。 如果選定產(chǎn)生式i進(jìn)行歸約，則在執(zhí)行歸約操作之后，再打印出與產(chǎn)生式i相關(guān)的翻譯成分中的終結(jié)符部分。 8.3.1 8.3.1 后綴翻譯后綴翻譯 有算術(shù)表達(dá)式，考慮其R部分由下述翻譯規(guī)則組成的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顯然是簡單后綴的，表達(dá)式 aa*(aaa+a) 的翻譯是 aa LOAD aaa LOAD a LOAD ADD

22、 MPY其中，操作符LOAD操作在它前面的標(biāo)識符上。如果希望LOAD操作在它后面的標(biāo)識符上，可用下面兩條規(guī)則替代FA，A LOAD： FL A，L A L，LOAD這樣修改后的文法仍然是LR(1)。產(chǎn)生式L的歸約操作可通過向前查看后面標(biāo)識符的一個符號所確定。于是，表達(dá)式aa*(aaa+a)的翻譯是LOAD aa LOAD aaa LOAD a ADD MPYES1S2TFE； FJP L1；S1;UJF L2;LOC L1；S2; LOC L2;8.3.2 8.3.2 IF-THEN-ElSEIF-THEN-ElSE控制語句控制語句(1)(1) 考慮高級語言中的條件語句 Sif E then

23、S1 else S2其中，E是表達(dá)式；S是一語句。 對于這種形式的輸入串，簡單后綴翻譯器先生成關(guān)于E的計值代碼，然后翻譯那兩個語句。 但這樣一種語句要求在E和第一個S之間產(chǎn)生一個條件分支指令，在兩個語句之間產(chǎn)生一個無條件分支指令。如何來產(chǎn)生這些指令呢? 解決辦法之一是將原來的單產(chǎn)生式拆成三個產(chǎn)生式： ST else S2 TI then S1 Iif E這三個產(chǎn)生式合起來與原來的那個產(chǎn)生式等價。 8.3.2 8.3.2 IF-THEN-ElSEIF-THEN-ElSE控制語句控制語句(2)(2) 經(jīng)這樣變形后，可以構(gòu)造一個簡單的后綴SDTS： ST else S2，T S2； LOC L2;

24、TI then S1, I S1； UJP L2; LOC L1; Iif E，E；FJP Ll；ES 1S 2TFE； FJP L1；S1;UJF L2;LOC L1；S2; LOC L2;8.3.2 8.3.2 IF-THEN-ElSEIF-THEN-ElSE控制語句控制語句(3)(3) 另一種解決辦法是引進(jìn)含“then和“else”鍵字的產(chǎn)生式： Sif E H S L S，E H S L S；LOC L2; Hthen，；FJP L1； Lelse, ；UJP L2；LOC L1； 這些附加的產(chǎn)生式的作用在于；在分析該語句的過程中，能在適當(dāng)?shù)奈恢貌迦胨枰姆g串。 當(dāng)然，也可以使用空

25、產(chǎn)生式來實現(xiàn)同樣的目的： Sif E then H S else L S, E H S L S；LOC L2； H，；FJP L1； L，；UJP L2；LOC Ll； 這三種解決辦法產(chǎn)生同樣的效果。 for(初值表達(dá)式; 循環(huán)判定式; 更新表達(dá)式) 循環(huán)體語句; E1；LOC L1 E2; FJP L4 UJF L3 ；LOC L2 E3; UJF L1; LOC L3 S1; UJF L2; LOC L4；ST1 T2 T3 S1 ， T1 T2 T3 S1 UJF L2; LOC L4；T1for(E1; , E1 LOC L1;T2E2; , E2 FJP L4 UJF L3 ；LOC

26、 L2 T3E3) ，E3； UJF L1; LOC L3 while(循環(huán)判定式) 循環(huán)體語句;LOC L1 E; FJP L2 ； S1; UJF L1; LOC L2；ST S1 ，T S1 UJF L1; LOC L2；TW(E) , W E FJP L2 ；Wwhile , LOC L1 do 循環(huán)體語句 while(循環(huán)判定式);LOC L1 S1; E; FJF L1; SD1 W ，D1 W FJF L1;D1D S1 , D S1 ；Ddo , LOC L1 W(E) , E8.3.3 8.3.3 函數(shù)調(diào)用函數(shù)調(diào)用 考慮函數(shù)調(diào)用的情況，假定有關(guān)的基礎(chǔ)源文法是FN(L) LL；

27、E LE AAa Aa NA 注意：這里實參表列由分號隔開的若干個E組成。 如果允許CALL和過程名都出現(xiàn)在實在參數(shù)代碼之后，就需要一個非簡單的翻譯器。 下面的簡單后綴的SDTS可用來產(chǎn)生過程的后綴調(diào)用形式：FN(L),N L;CALL LL;E，L E NA,A LOADLE,E AAa,Aa Aa，a那么，函數(shù)調(diào)用：aa(a;a+aaa) 將翻譯成aa；LOAD a；LOAD a；LOAD aaa；ADD；CALL而且CALL將操作在第一個標(biāo)識符aa上。8.4 抽象語法樹的構(gòu)造(1) 抽象語法樹AST(Abstract-Syntax Tree)是某個語言結(jié)構(gòu)的一種簡潔的樹形表示形式，它只需

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

29、下方式將這棵語法樹簡化成一個AST。 首先，去掉與單非產(chǎn)生式,上提終結(jié)符結(jié)點。 第二，上提運(yùn)算符并讓它取代其父結(jié)點。 第三，去掉括號，并上提運(yùn)算符。 最后得到的語法樹便是一個AST。 TEaF*)(+aa圖8.5 圖8.4去掉單 非產(chǎn)生式ETEETTTFFF*a)(+Faa圖8.4 a+(a+a)的語法樹aF*)(+aa圖8.6 運(yùn)算符上提a*+aa圖8.7 去掉括號，運(yùn)算符上提 這棵樹也是下述表達(dá)式的抽象語法樹： a*(a)+a) a*(a+(a) (a*(a+a) 注意：AST并不是一種規(guī)范形式，它并沒有指明運(yùn)算符的交換律和結(jié)合律例如，a*b+c、c+b*a、c+a*b等表達(dá)式在數(shù)學(xué)上是等

30、價的，但可生成不同的AST 只要稍微改變一下SDTS的實現(xiàn)方式，就可不必生成一個完整的語法樹而直接構(gòu)造一個AST a*+aa圖8.7 去掉括號，運(yùn)算符上提8.4.1 8.4.1 自下而上自下而上構(gòu)造構(gòu)造ASTAST 對于一個自下而上分析器.考慮產(chǎn)生式EE+T，當(dāng)E+T作為句柄出現(xiàn)在棧頂時，已存在兩棵子樹E和T，但并無以“+”為根的子樹。這條規(guī)則是說：構(gòu)造以“+”為根的一棵子樹，并將E和T子樹作為它的兩個孩子(左孩子和右孩子)。于是，得到以“+”為根的一棵新子樹，將它連到E以替代棧頂?shù)腅和T。對于規(guī)則ET，當(dāng)T是句柄時，它本身已連在某棵子樹上，將這棵子樹連到E以替代棧頂上的T。最后，規(guī)則F(E)

31、告訴我們將E子樹連到F以取代棧頂?shù)?E)，而Fa則指明將由終結(jié)符a構(gòu)成的單一結(jié)點的樹連到F并用F取代a。當(dāng)?shù)竭_(dá)接收狀態(tài)時，已構(gòu)造好一棵AST，且它已連到位于棧頂?shù)拈_始符號上。 +ET*TF表表8.2 8.2 根據(jù)文法根據(jù)文法G G0 0及其分析器直接產(chǎn)生一個及其分析器直接產(chǎn)生一個ASTAST文法中的產(chǎn)生式文法中的產(chǎn)生式ASTAST的成分的成分EE+TEE+TETETT TTTTT* *F FTFTFF FF(E)F(E)E EFaFaa a8.4.2 8.4.2 ASTAST的拓廣的拓廣 AST的一般形式是：其中間結(jié)點是運(yùn)算符，而它的葉子為簡單變量或常數(shù)。事實上，運(yùn)算符號可以是任何單目運(yùn)算符、

32、二日運(yùn)算符或n目運(yùn)算符。 例如，一個類似于X(el,e2,en) 的數(shù)組元素可表示成圖8.8所示形式的AST，其中，X是多維數(shù)組的名字，el，e2，en為其下標(biāo)。 AST也可表示控制結(jié)構(gòu)和說明(略)。 XARRAY 訪問e1e2en圖8.8 數(shù)組訪問(或過程調(diào)用)的AST8.5 8.5 屬性文法屬性文法(1)(1) 屬性文法(Attribute Grammar)是Knuth于1968年提出的，也有人稱它為屬性翻譯文法。屬性文法以上下文無關(guān)文法為基礎(chǔ)，只不過為每個文法符號配備了一些屬性。屬性同變量一樣，可以進(jìn)行計算和傳遞。屬性加工的過程即是語義處理的過程。屬性加工同語法分析同時進(jìn)行，加工規(guī)則也附

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

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

35、述兩種屬性值中的一種： 1) 產(chǎn)生式左部的繼承屬性； 2) 產(chǎn)生式右部但位于V左邊的符號的任何屬性 產(chǎn)生式左部符號的綜合屬性僅依賴于下面的屬性值中的一種： 1) 產(chǎn)生式左部符號的繼承屬性： 2) 產(chǎn)生式右部符號(除自身外)的任意屬性。8.5.2 8.5.2 S S屬性文法屬性文法 S屬性文法也稱為自下而上的屬性翻譯文法，它適用于指導(dǎo)自下而上的分析過程，其定義如下： 全部非終結(jié)符的屬性是綜合屬性； 同一產(chǎn)生式中相同符號的各綜合屬性之間無相互依賴關(guān)系： 如果q是某個產(chǎn)生式中文法符號V的繼承屬性，那么，屬性q的值僅依賴于該產(chǎn)生式右部位于V左邊的符號的屬性。8.6 8.6 中間代碼形式中間代碼形式 在

36、討論屬性翻譯文法的具體用法之前，先介紹編譯程序中的中間代碼形式所謂中間代碼形式是指用來表述源程序并與之等效的一種編碼方式，可根據(jù)具體情況將它設(shè)計成各種形式。例如，匯編語言程序就可看做一種中間代碼形式。一般說來，對于一個多遍掃描的編譯程序，越到后面階段，所產(chǎn)生的中間代碼也就越接近于機(jī)器代碼，于是，編譯程序首先將源程序翻譯成中間代碼形式，然后，再把中間代碼翻譯成目標(biāo)代碼，也就是把語義分析和代碼生成分開處理比較常用的中間代碼形式有逆波蘭表示、四元式、三元式和樹形表示等等下面，我們討論這幾種典型的中間代碼形式。8.6.1 8.6.1 逆波蘭表示法逆波蘭表示法 (1) 逆波蘭表示法是由波蘭邏輯學(xué)家J.L

37、ukasiewicz首先提出來的一種表示表達(dá)式的方法在這種表示法中，運(yùn)算符直接跟在其運(yùn)算量(操作數(shù))的后面。因此，逆波蘭表示法有時也稱為后綴(post fix)表示法下面是一些逆波蘭表示法的例子： AB* 表示A*B AB*C+ 表示A*B+C ABCD+* 表示A*(B+CD) AB*CD*+ 表示A*B+C*D8.6.1 8.6.1 逆波蘭表示法逆波蘭表示法 (2) 與習(xí)慣的中綴表示法相比，逆波蘭表示法有兩個明顯的特點：第一，不再有括號，而且既簡明又確切地規(guī)定了運(yùn)算的計算順序。第二，運(yùn)算處理極為方便，只需從左至右掃描表達(dá)式中的符號 當(dāng)遇到運(yùn)算量時，就把它存到運(yùn)算量棧中， 當(dāng)遇到雙目(單目)

38、運(yùn)算符時，就取出最近存人運(yùn)算量棧中的兩個(一個)運(yùn)算對象進(jìn)行運(yùn)算處理，并把計算的結(jié)果作為一個新的運(yùn)算量存人運(yùn)算量棧，再繼續(xù)向右掃描表達(dá)式中的符號，直至整個表達(dá)式處理完畢只要遵守在運(yùn)算量之后直接緊跟它們的運(yùn)算符這樣的規(guī)則，就能很容易地將逆波蘭表示推廣到其它非表達(dá)式結(jié)構(gòu)。 8.6.2 8.6.2 逆波蘭表示法的推廣逆波蘭表示法的推廣(1)(1) 考慮賦值語句，其一般形式為 :=表達(dá)式)如果把“:=”看做一個進(jìn)行賦值運(yùn)算的雙目運(yùn)算符，那么，賦值語句的逆波蘭表示式為 :=而多重賦值可表示為 :=例如，賦值語句A:=B*C+D可寫做 ABC*D+:=注意：當(dāng)處理到“:=”這個運(yùn)算符時，在表達(dá)式賦值執(zhí)行完

39、畢后，必須把和從棧中消除，因為，此時不產(chǎn)生結(jié)果值。對于多重賦值的情形，則需要把這個量保存下來，直到整個多重賦值語句處理完畢后才能退掉。此外，因為要把之值送到該中去，所以在棧中只需的地址而不需其值。8.6.2 8.6.2 逆波蘭表示法的推廣逆波蘭表示法的推廣(2)(2) 下面，討論如何用逆波蘭表示法表示轉(zhuǎn)向語句、條件語句和條件表達(dá)式。 為此，先引進(jìn)幾個運(yùn)算：Jump 是一個單目運(yùn)算符，“jump”表示無條件轉(zhuǎn)到去,“jump”表示無條件轉(zhuǎn)到去。jumpf是一個雙目運(yùn)算符,“ jumpf” 表示當(dāng) 為假時，轉(zhuǎn)移到 處；否則，按原順序執(zhí)行。 那么，轉(zhuǎn)向語句的逆波蘭表示就是jump;8.6.2 8.6

40、.2 逆波蘭表示法的推廣逆波蘭表示法的推廣(3)(3) 條件語句的逆波蘭表示是 jumpfjump，其中,指的是開始符號的序號,指的是緊接在之后的那個符號的序號。 高級語言中的數(shù)組說明array All，u1，lnun可用l1u1lnunA ADEC來表示，其中，只有ADEC是運(yùn)算符，它的運(yùn)算對象的個數(shù)是可變的，由其下標(biāo)的個數(shù)決定。類似地，下標(biāo)變量A，可用A SUBS表示。 高級語言中的其它成分也可用類似的表示法表示，不在此一一討論。 一個用逆波蘭表示法表示程序段的例子(例8.1)begin integer k； k:=100；h: if ki+j thenbegin k:=k-1； goto

41、 hend 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) ki2*j2*-:=(32) ij0:=:=(37) Blockend if E then S1 else S2blockE jumpfS1 jump S2blockendwhile E do S E jumpf S jump 5210121expnn1001nnsumfor k:= k1 step k3 until k2 do Sk:=k1; kk2-sign(

42、k3)*0 jumpf Skkk3+:= jump5210121expnn1001nnsum8.6.3 8.6.3 四元式（四元式（1 1） 四元式的一般形式是四元式的一般形式是 當(dāng)當(dāng) 為單目運(yùn)算時，總認(rèn)為為單目運(yùn)算時，總認(rèn)為 2為空，即此為空，即此時施運(yùn)算于時施運(yùn)算于 1，運(yùn)算結(jié)果放在，運(yùn)算結(jié)果放在 中。中。 例如，例如，A AB B的四元式是的四元式是 * * A B TA B T 這里這里T T是暫存是暫存A A* *B B之計算結(jié)果的臨時變量按此方式。之計算結(jié)果的臨時變量按此方式。 表達(dá)式表達(dá)式A A* *B+CB+C* *D D的四元式為的四元式為* * A B T1A B T1*

43、* C D T2 C D T2+ T1 T2 T3+ T1 T2 T3 其中其中T1,T2,T3T1,T2,T3都是計算結(jié)果的臨時變量。和逆波蘭表示相仿，都是計算結(jié)果的臨時變量。和逆波蘭表示相仿，四元式也是按照表達(dá)式的執(zhí)行順序組合起來的。四元式也是按照表達(dá)式的執(zhí)行順序組合起來的。 8.6.3 8.6.3 四元式（四元式（2 2） -(A/B-C) -(A/B-C) 的四元式為的四元式為 / / A B T1A B T1 - T1 C T2 - T1 C T2 T2 _ T3 T2 _ T3 表示單目運(yùn)算符表示單目運(yùn)算符- -，對于無運(yùn)算結(jié)果的運(yùn)算符，其四元式中，對于無運(yùn)算結(jié)果的運(yùn)算符，其四元式中的的 處規(guī)定為空。處規(guī)定為空。-運(yùn)算符運(yùn)算對象1運(yùn)算對象2結(jié)果含 義p1 Tp1 = Tp1 p2Tp1p2 = Tp1Tp1 = TjumpA