第七章語法制導(dǎo)翻譯技術(shù)及中間代碼

1、第七章第七章 語法制導(dǎo)翻譯技術(shù)及中間語法制導(dǎo)翻譯技術(shù)及中間代碼的生成代碼的生成 主主 要要 內(nèi)內(nèi) 容容1.語義翻譯的方法：采用語法制導(dǎo)翻譯技術(shù)的方法。語義翻譯的方法：采用語法制導(dǎo)翻譯技術(shù)的方法。 依據(jù)的文法依據(jù)的文法(描述文法的語義描述文法的語義)：屬性文法。：屬性文法。(一般掌握一般掌握) 語法制導(dǎo)翻譯過程：根據(jù)已有的屬性文法，生成句子的語法制導(dǎo)翻譯過程：根據(jù)已有的屬性文法，生成句子的 中間代碼過程。中間代碼過程。(重點掌握重點掌握)2.語義翻譯結(jié)果的表示：中間代碼語義翻譯結(jié)果的表示：中間代碼 。(重點掌握重點掌握) 常見：常見： 逆波蘭表示逆波蘭表示四元式表示和三地址代碼四元式表示和三地址

2、代碼 三元式和樹形表示三元式和樹形表示1. 語義分析概述語義分析概述一、語義分析的任務(wù)一、語義分析的任務(wù)任務(wù)有：1.審查每一個語法結(jié)構(gòu)的靜態(tài)語義，即驗證語法正確的結(jié)構(gòu)是否有意義。如：賦值語句：x:=x+y,左邊變量類型與右邊變量類型是否一致。2.在語義正確的基礎(chǔ)上生成一種中間代碼或目標(biāo)代碼。二、語義分析的范圍二、語義分析的范圍1o.確定類型：確定標(biāo)識符所關(guān)聯(lián)的數(shù)據(jù)類型。2o.類型檢查：按語言的類型規(guī)則，檢查運算的合法性與運算分量類型的一致性，必要時作類型轉(zhuǎn)換。3o.識別含義：根據(jù)語言的語義定義（形式或非形式），識別程序中各構(gòu)造成分組合到一起的含義。，并作相應(yīng)的語義處理（生成中間代碼或目標(biāo)代碼）

3、4o.控制流檢查：控制流語句必須轉(zhuǎn)移到合法的地方。如：c中，break語句規(guī)定跳出最內(nèi)層的循環(huán)或switch語句.5o.一致性檢查：在很多場合要求對象只能被說明一次，如：pascal語言規(guī)定同一個標(biāo)識符在一個分程序中只能被說明一次等。6o.相關(guān)名字檢查：如：ada，循環(huán)或塊可以有一個名字，它出現(xiàn)在這些結(jié)構(gòu)的開頭或結(jié)尾。編譯程序必須檢查這兩個地方用的名字是否相同。 其它：如名字的作用域分析等也是語義分析的工作。三、語義描述工具和語義分析方法三、語義描述工具和語義分析方法1.語義描述工具 目前流行：用屬性文法作為描述語義的工具。2.語義分析方法根據(jù)描述屬性文法的語義規(guī)則的方式不同，語義分析方法分為

4、：語法制導(dǎo)定義方法翻譯方案2. 屬屬 性性 文文 法法一、屬性一、屬性屬性常用來描述事物或人的特征。如：人的姓名，性別等，商品的顏色、重量、單位等。v屬性：屬性：在編譯中，對文法的每一個符號，引進一些屬性，用這些屬性描述文法符號相關(guān)的信息，如：類型、值或存儲位置等。如：a:=x ，在語法推導(dǎo)或歸約時，有時結(jié)合x的類型，位置，值,考慮語法分析的正確性，即語法分析中有語義檢查。如:x的屬性：xtype，xplace，xval分別表示x的類型，位置，值等語義。v屬性值：可以在語法分析過程中計算和傳遞。v屬性的加工過程就是語義的處理過程。二、屬性文法二、屬性文法1.語義規(guī)則語義規(guī)則在對文法符號屬性處理

5、過程中，必須遵守一定義的規(guī)則語義規(guī)則。為文法的每一產(chǎn)生式定義一組屬性的計算規(guī)則，稱為語義規(guī)則。2.屬性文法屬性文法形式定義：一個屬性文法是一個三元組a，a=(g,v,f)其中：g為一個上下文無關(guān)文法； v 表示屬性的有窮集合； f表示屬性的斷言或謂詞的有窮集。v在屬性文法中：每個屬性與文法中某個符號相關(guān)聯(lián)，用“符號屬性”表示。如：xtype,xint,xbool等。每個斷言與文法的某產(chǎn)生式相關(guān)聯(lián)。斷言就是產(chǎn)生式上定義的一組語義規(guī)則。例：一個簡單表達式方法：e:=t1+t2|t1ort2t:=num|true|falsev根據(jù)程序語言中有關(guān)類型的檢驗原則，可以得到關(guān)于類型檢驗的屬性文法：1.e:

6、=t1+t2 t1.type=int and t1.type=int2.e:=t1ort2 t1.type=bool and t1.type=bool3.t:=num t.type=int4.t:=true t.type=bool5.t:=false t.type=boolv屬性分類：綜合屬性 繼承屬性綜合屬性：從語法分析角度看，如果一個結(jié)點的某一屬性，其值由子結(jié)點的屬性的值來計算，稱該屬性為綜合屬性。例：已知上例屬性文法的輸入串3+4語法樹。其中：e中語義規(guī)則中的t1.type和t2.type中的type屬性的值分別由子結(jié)點t1.type=int和t2.type=int中的int值來計算，使

7、得e中的語義規(guī)則（斷言）為真。因此：type是綜合屬性。綜合屬性用于“自下向上”傳遞信息。 e t t 4 3 + t1type=int t2type=int t1 type=int,t2 type=int 繼承屬性：在語法分析樹中，結(jié)點的某個屬性值由該結(jié)點的兄弟結(jié)點和（或）父結(jié)點的屬性值來計算，此結(jié)點的屬性稱為繼承屬性。繼承屬性用于“自上而下”傳遞信息。v注意：注意：終結(jié)符號只有綜合屬性，他由詞法分析器提供。非終結(jié)符號既有綜合屬性，也可有繼承屬性。文法識別符號（開始符號）的所有繼承屬性作為屬性計算前的初始值。根據(jù)處理不同的要求，屬性和斷言可以多種形式出現(xiàn)，如：語義規(guī)則或者程序段等。例：簡單表

8、達式求值的屬性文法。產(chǎn)生式：1.l:=eprint(e.val)2.e:=e1+te.val:=e1.val+t.val3.e:=te.val:=t.val4.t:=t1*fe.val:=t1.val*f.val5.t:=ft.val:=f.val6.f:=(e)f.val:=e.val7.f:=digitf.val:= digit.lexval例：描述說明語句中簡單變量類型信息的屬性文法產(chǎn)生式語義規(guī)則1.d:=tll.in:=t.type2.t:=intt.type :=integer3.t:=realt.type :=real 4.l:=l1，id l1.in:=l.inaddtype(i

9、d.entry,l.in)5.l:=idaddtype(id.entry,l.in)文法定義了一種說明語句，該說明語句的形式是由關(guān)鍵字int或real開頭，后跟一個標(biāo)識符表，每一個標(biāo)識符間用逗號隔開：real id1，id2，idn或 int id1，id2，idn屬性文法中，非終結(jié)符t有綜合屬性type，其值由關(guān)鍵字int和real決定。v語義規(guī)則l.in:=t.type將l的屬性值置為該說明語句指定的類型。 l.in將被沿著語法樹傳遞到下邊的結(jié)點使用，與l產(chǎn)生式相聯(lián)的規(guī)則里使用了它。如：句子int id1，id2語法樹：圖2 d t l l int , id2 id1 一、基本思想對文法中

10、的每個產(chǎn)生式都附加上一個語義動作或語義子程序，伴隨著語法分析，每當(dāng)使用一條產(chǎn)生式進行推導(dǎo)或歸約時，就執(zhí)行相應(yīng)產(chǎn)生式的語義動作（包括：查填表格，改變變量的求值，打印信息和生成中間代碼等），從而完成預(yù)定的翻譯工作。即在語法翻譯過程中伴隨部分語義的檢查工作。3. 語法制導(dǎo)翻譯概述語法制導(dǎo)翻譯概述v語法制導(dǎo)翻譯方法：自底向上的語法制導(dǎo)翻譯方法自頂向下的語法制導(dǎo)翻譯方法二、語法制導(dǎo)翻譯的步驟1、為所給文法每個產(chǎn)生式設(shè)計相應(yīng)的語義規(guī)則。例：為一個簡單表達式計值的文法：e = e+e|e*e|(e)|digit設(shè)計計值的語義規(guī)則如下：1. e =e(1)+e(2)eval:=e(1)val+e(2)val

11、2. e =e(1)*e(2)eval:=e(1)val*e(2)val 3. e =(e(1)eval:=e(1)val4. e =digiteval:=lexdigit為文法產(chǎn)生式寫語義規(guī)則或語義子程序是本章的難點.2.采用lr分析方法，則構(gòu)造lr分析表狀態(tài)actiongoto+digit*()#e0s3s211s4s5acc2s3s263r4r4r4r44s3s275s3s286s4s5s97r1s5r1r18r2r2r2r29r3r3r3r33. 將原lr語法分析棧擴充，增加語義值棧。4. 根據(jù)語義分析棧的工作過程設(shè)計總控程序，使語法分析與語義分析工作同時完成。例：計算表達式7+8*5

12、的語法樹，以及用lr語法制導(dǎo)翻譯法得到該表達式的計值過程：snxnxnvals1x1s0#x1val狀態(tài)棧文法符號棧語義值棧步驟狀態(tài)棧語義棧符號棧輸入符號棧主要動作10_#7+8*5#s3203_#7+8*5#r4301_7#e+8*5#s44014_7_#e+8*5#s350143_7_#e+8*5#r460147_7_8#e+e*5#s5701475_7_8#e+e*5#s38014753_7_8_#e+e*5#r49014758_7_8_5#e+e*e#r2100147_7_40#e+e#r11101_47#e#acc 7 + eval=47 eval=7 eval=40 + eval=

13、8 eval=5 8 5 注：自底向上語法制導(dǎo)翻譯的特點：當(dāng)棧頂形成句柄執(zhí)行歸約時，調(diào)用相應(yīng)的語義動作。語法分析與語義分析同步操作。*v說明：若把計值的動作改為產(chǎn)生某種中間代碼的子程序，那么，就能在伴隨著語法分析的制導(dǎo)下，隨著分析的進展逐步生成中間代碼。v問題：1.什么是中間代碼？它有哪幾種形式表示源程序語言的句子？ 4.4.中間語言中間語言 2.在語義規(guī)則語義規(guī)則中，怎么樣定義生成中間代碼（主要是四元式或三地址式）的一些語義規(guī)則？ 5. 表達式及語句的語義翻譯 3.根據(jù)具有生成中間代碼的屬性文法，生成中間代碼的過程是怎樣的？一、中間語言概述1 中間語言v中間語言：它介于源程序到目標(biāo)語言程序中

14、間程序的語言v中間語言程序：用中間語言表示的程序。v作用：用于編譯程序，將源程序翻譯成等價的中間語言程序，再將中間語言程序轉(zhuǎn)化成目標(biāo)程序（即將語義分析和目標(biāo)代碼生成分開處理）v源程序中間語言程序目標(biāo)程序v中間語言是表示語法制導(dǎo)翻譯的結(jié)果。等價變換轉(zhuǎn)化4. 4. 中中 間間 語語 言言好處：v中間語言與機器無關(guān)，使采用中間語言進行翻譯的編譯程序系統(tǒng)易于移植。v易于優(yōu)化翻譯后的代碼。v使編譯程序的結(jié)構(gòu)在邏輯上更簡單明確。2 中間語言的表示常見：逆波蘭表示 四元式表示和三地址代碼 三元式和樹形表示二、逆波蘭表示由波蘭邏輯學(xué)家j.lukasiewicz(盧卡西維茲)首先提出用來表示表達式的方法，后來推

15、廣到表示程序設(shè)計語言中的其它語法成分。1.表達式的逆波蘭表示表達式的表示：v中綴表示：運算符居中，運算對象在左右兩邊:a+bv波蘭表示：前綴表示：運算符在前，運算對象在后：+ab后綴表示：運算對象在前，運算符在后：ab+(逆波蘭表示)v例：逆波蘭表示的例子(1)表達式逆波蘭表示的定義： 設(shè)e是一般表達式，則： 一般表達式一般表達式逆波蘭表達式逆波蘭表達式v若e為變量或常量ev（e）e的逆波蘭式ve(1)ope(2)(二目運算) e(1)的逆波蘭式e(2)的逆波蘭式opvope(單目運算) e的逆波蘭式op中綴表示(一般表示)逆波蘭表示a+b*cabc*+a*(b+c/d)abcd/+*a*b+

16、cab*c+a*b+(c-d)/eab*cd-e/+ 在編譯過程中，在編譯過程中，生成逆波蘭表示的語義規(guī)則描述生成逆波蘭表示的語義規(guī)則描述： 產(chǎn)生式 語義規(guī)則 e:=e(1)ope(2) e.code=e(1).code|e(2).code|op e:=(e(1) ) e.code=e(1).code e:=i e.code=i 其中：e.code表示e的逆波蘭式；|表示逆波蘭式的連接。(2)逆波蘭表示的特點逆波蘭表示的特點a.標(biāo)識符標(biāo)識符(運算對象運算對象)出現(xiàn)的順序（從左到右）和原有順序相同。出現(xiàn)的順序（從左到右）和原有順序相同。b. 運算符是按實際計算順序（從左到右）出現(xiàn)的。運算符是按實

17、際計算順序（從左到右）出現(xiàn)的。c. 運算符緊跟在運算對象的后面出現(xiàn)，并且沒有括號。運算符緊跟在運算對象的后面出現(xiàn)，并且沒有括號。(3) 好處：易于對表達式的計算處理v對于中綴表達式的計算，系統(tǒng)需要用兩個工作棧分別處理運算對象和運算符。v對于逆波蘭表示的表達式計算處理只用一個工作棧。例：逆波蘭式ab+c*的計算處理過程遇運算對象a,b入棧掃描ab+c*ba棧遇運算符+取出a,b，運算結(jié)果t入棧tctc*遇運算對象c入棧*遇運算法*取出c,t作運算，設(shè)結(jié)果t1t12. 形成逆波蘭表示怎樣將一般表達式轉(zhuǎn)換成逆波蘭表示？基本思想:從左到右掃描表達式，每遇到：1o 表達式中的運算對象則往左去。2o 表達

18、式中的運算符，則與運算符棧頂元素比較優(yōu)先數(shù)：逆波蘭表示表達式運算對象運算符進棧出棧運算符棧如果運算符棧頂元素的優(yōu)先數(shù)大于或等于表達式中當(dāng)前的運算符優(yōu)先數(shù)，則棧頂元素退棧向左去。然后當(dāng)然運算符繼續(xù)與棧頂?shù)男略乇容^優(yōu)先數(shù)。直到棧頂元素的優(yōu)先數(shù)小于表達式中當(dāng)前運算符為止。此時，才將表達式中當(dāng)前運算符進棧。例：畫出形成表達式a*(b+c/d)的逆波蘭表示過程a*(b+c/d)#a(b+c/d)#*#ab+c/d)#(*#ab+c/d)#(*#abc/d)#+(*#abc/d)#+(*#步驟步驟步驟步驟步驟步驟abcd)#abcd)#/+(*#/+(*#/+(*#abcd/)#+(*#abcd/+)#

19、*#abcd/+*#步驟步驟步驟步驟 步驟形成逆波蘭表示的過程，實質(zhì)上是表達式的翻譯過程。（算法不難寫出）例：a/b/c+d = ab/c/d+(a+b)*(c-d/e) = ab+cde/-*3. 擴充的逆波蘭表示逆波蘭不僅僅用來表示計算表達式，而且可以推廣到其它語法成分的表示。v賦值語句：a := e (其中e是表達式)逆波蘭表示：ae:=(其中e應(yīng)該為逆波蘭表示)例：a:=3*(b+c)的逆波蘭表示：a3bc+*:=v條件語句：if u then s1 else s2逆波蘭表示：u l1 jumpf s1 l2 jump s2其中：u為布爾表達式的逆波蘭表示s1,s2均為相應(yīng)語句的逆波蘭

20、表示。jumpf 表示一個雙目運算符：當(dāng)u為假(0)時，它引向標(biāo)號 l1的分支， l1表示語句s2的開始位置。jump表示單目運算符：它無條件的引向標(biāo)號為l2的分支， l2表示語句s2后的符號位置。逆波蘭式表示的語義：當(dāng)u=0(假)轉(zhuǎn)去執(zhí)行s2，否則轉(zhuǎn)向執(zhí)行s1，然后跳到s2之后的語句。有下列源程序段：k := 0;if ij then k := k+6*ai-jelse begini:=i+1;j:=j-1;end;逆波蘭表示：k0:=ijl1 jumpf kk6ij-asubs*+:=l2 jump l1: ii1+:=jj1-:= l2:含義：當(dāng)ij為假便轉(zhuǎn)向l1處執(zhí)行s2;否則執(zhí)行s1

21、后無條件轉(zhuǎn)到l2處即語句s2的后繼部分。三、三元式和樹形表示1。三元式一個三元式由三個主要部分和一個序號組成：(i)(op,arg1,arg2)其中：op是運算符，arg1和arg2是運算對象。當(dāng)op為一目運算符時，只有一個運算對象。(i)表示三元式的序號，三元式的運算結(jié)果由每個三元式前序號(i)指示。序號(i)指向三元式所處的表格位置，因此引用一個三元式的計算結(jié)果是通過引用該三元式的序號實現(xiàn)的。三元式出現(xiàn)的先后順序與表達式的計值順序一致。例：a:=-b*c+b*d三元式：(1)(,b,_)(2)(*,(1),c)(3)(*,b,d)(4)(+,(2),(3)(5)(:=,(4),a)2. 間

22、接三元式由于三元式的先后順序決定了值的順序，因此在產(chǎn)生三元式形式的中間代碼后，對其進行代碼的優(yōu)化時難免涉及到改變?nèi)降捻樞?即三元式表示的中間代碼不利用代碼優(yōu)化),這就要修改三元式表。為了最少改動三元式表，可以另設(shè)一張間接碼表來表示有關(guān)三元式在三元式表的計值順序，用這種辦法處理的中間代碼稱為間接三元式。例：表達式x=a+b*c y=d-b*c其間接三元式表示如下：三元式表間接碼表(1)(*,b,c)(1)(2)(+,a,)(1)(2)(3)(=,x,(2)(3)(4)(-,d,(1)(1)(5)(=,y,(4)(4)(5)由于間接碼表的作用，編譯程序每產(chǎn)生一個三元式時，先查看三元式表中是否存

23、在當(dāng)前三元式，若存在就不需要重復(fù)填寫三元式表，如上例中的三元式(1) (*,b,c)在間接碼表中出現(xiàn)了兩次，但三元式表中實際只有一個三元式。注：三元式表示的中間代碼不利于中間代碼的優(yōu)化。間接三元式表示的中間代碼有利于中間代碼的優(yōu)化。3.樹形表示v樹形結(jié)構(gòu)是三元式的另一種表示形式例如：上例a:=-b*c+b*d的樹形表示(由三元式的下至上畫出) := + a b * * c - d b 樹形表示法很容易表示一個表達式或語句。v一個表達式中簡單變量或常數(shù)的樹形表示就是它們的本身。v如果表達式e1和e2的樹分別為t1和t2,則： e1和e2, e1* e2, -e1的樹分別：注：二目運算對應(yīng)二叉樹三

24、目運算對應(yīng)三叉樹：如條件語句if u then s1 else s2 可看作三目運算。其三目運算符定義為:if then else 則：樹表示 + t2 t1 e1+e2 * t2 t1 e1*e2 - t1 -e1 s2 u s1 注：多叉樹不便于存儲，可以化為二叉樹： s1 s2 u new 四、四元式和三地址代碼四元式是一種比較普遍采用的中間代碼形式。v四元式由四個部分組成：(i)(op,arg1,arg2,result)其中：op為運算符;arg1,arg2為運算對象。result存放結(jié)果的變量。四元式之間的聯(lián)系通過變量來聯(lián)系(而不用三元式中的序號聯(lián)系)例：a:=b*c+b*d四元式表

25、示： (1) (*,b,c,t1) (2) (*,b,d,t2) (3) (+, t1, t2, t3) (4) (:=, t3,_,a)注：四元式和三元式的主要不同在于：四元式之間的聯(lián)系通過中間引用的變量名實現(xiàn)，而三元式之間的聯(lián)系通過三元式序號實現(xiàn)。這說明要更改一張三元式表比較困難，它需要改變一序列的三元式的序號。四元式表的修改比較容易，調(diào)整四元式之間位置，不改變其中的參數(shù)。因此：四元式和三地址代碼表示的中間代碼便于中間代碼的優(yōu)化。而三元式和樹不便于優(yōu)化。有時將四元式表示成更直觀的形式三地址代碼v三地址代碼形式：x:=a op b (賦值形式)與賦值語句的區(qū)別：其右邊最多只能有一個運算符。

26、例：上例的四元式寫成三地址代碼： (1) t1:=b*c (2) t2:=b*d (3) t3:= t1+ t2 (4) a:= t3 v三地址代碼表示的好處：表示中間代碼更直觀，有利于中間代碼的優(yōu)化和目標(biāo)代碼的生成。v四元式的生成算法與逆波蘭式生成算法基本相同。v擴充四元式可表示程序語言的其它語法成分。例：將表達式: a+b*(c-d)-e/f g寫成逆波蘭表示、三元式和四元式逆波蘭表示:abcd-*+efg /-三元式: (1) (-,c,d) (2) (*,b,(1) (3) (+,a,(2) (4) ( ,f ,g) (5) (/,e,(4) (6) (-,(3),(5)四元式：(1)

27、(-,c,d,t1) (2)(*,b, t1, t2) (3)(+,a, t2, t3) (4)( ,f,g, t4) (5)(/,e, t4, t5) (6)(-, t3, t5, t6)三地址代碼： t1:=c-d t2:=b*t1 t3:=a+ t2 t4:=f g t5:=e/ t4 t6:= t3- t5例：將語句:if avbd then i:=i+1 else i:=i-1 寫成四元式。 (1) (,b,d, t1) (2) (v,a, t1, t2) (3) (bmz, t2, ,(7) （t2為假） (4) (+,i,1, t3) (5) (:=, t3, ,i) (6) (

28、jmp,(9) (7) (-,i,1, t4) (8) (:=, t4, , i) (9)三地址代碼：(1) t1:=b, , );i為邏輯變量或邏輯常量；i rop i為關(guān)系表達式。1. 布爾表達式的翻譯v布爾表達式的計值方法：(1)通過逐步計算出各部分的值來計算整個表達式的值.例：假定用1表示true,0表示false，則布爾表達式： 1(0 0) 1 =1 (0 1) 1 =1 0 =1(2)利用邏輯運算符的性質(zhì)計值如：當(dāng)a=1,則ab的值(不管b為何值)一定為1。v布爾表達式計值方法不同，則采用的翻譯方法也不同。例：按第(1)種方法，布爾表達式a=bcd將被翻譯成如下的四元式序列： (

29、1) if a=b goto (4) (a=b為真轉(zhuǎn)（4）) (2) t1=0 (3) goto (5) (4)t1=1 (5) t2=c d (6) t3=t1 t2例：按布爾表達式第(1)種計值法，將文法：e =ee|ee|e|(e)|i rop i|i表示的布爾表達式翻譯成四元式的翻譯方案。e =e(1) e(2)e place=newtemp();emit(e place=e(1) place e(2) place);e =e(1) e(2)e place=newtemp();emit(e place=e(1) place e(2) place);e = e(1) e place=ne

30、wtemp();emit(e place=e(1) place);e = (e(1) e place= e(1) place;e = i(1)rop i(2) e place=newtemp();emit(if i(1) place rop i(2) place goto nextq+3);emit(e place=0);emit(goto nextq+2);emit(e place=1)e = ie place= i place2.控制語句中布爾表達式的翻譯v布爾表達式不僅可以計值，而且其值還決定了程序控制流的轉(zhuǎn)向(如if和while中).v現(xiàn)討論布爾表達式e在if-then,if-then

31、-else和while-do中翻譯。三種語句的語法和代碼結(jié)構(gòu)為：s =if e then s(1)|if e then s(1)else s(2)|while e do s(1) s(1)的代碼e的代碼真假s(1)的代碼e的代碼真假s(1)的代碼e的代碼真假s(2)的代碼if e then s(1) 代碼結(jié)構(gòu)if e then s(1) else s(2)代碼結(jié)構(gòu)while e do s(1) 代碼結(jié)構(gòu)為了將作為條件控制的布爾表達式e正確翻譯成四元式，且e翻譯的代碼是一串條件轉(zhuǎn)移和無條件轉(zhuǎn)移的四元式代碼，則定義下面的一組控制轉(zhuǎn)移的四元式：(1)if e goto li 當(dāng)e為真，轉(zhuǎn)向li ,稱

32、li 為e的真出口，記為e true。(2)if e(1) rop e(2) goto li 當(dāng)e(1) rop e(2)為真，轉(zhuǎn)向li ,li 為關(guān)系運算符rop的真出口。(3)goto lj 無條件轉(zhuǎn)向標(biāo)號lj，稱lj為假出口,記為： e false。例：e的布爾表達式為:abcf,翻譯為如下四元式序列：(1)if ab goto e true (2)goto (3)(3)if cf goto e true(6)goto e false注：布爾表達式計值是采用第二種方式進行。 描述布爾表達式控制功能的語義的四元式序列都是由一串條件轉(zhuǎn)移和無條件轉(zhuǎn)移四元式代碼組成?，F(xiàn)把e布爾式放在條件語句中考

33、察條件語句轉(zhuǎn)移的出口問題例：有條件語句：if abcf then s(1) else s(2)其四元式序列為：(1)if ab goto (7)(2)goto (3)(3)if cf goto (7)(6)goto (p+1)(7)(關(guān)于s(1)的四元式序列)(p)goto (q)(p+1)(關(guān)于s(2)的四元式序列) (q)后繼四元式v四元式中的地址回填問題上述if四元式序列中的(1)和(5)四元式的轉(zhuǎn)移地址(7)不能在產(chǎn)生式(1)和(5)四元式時立即得知，至少要等到if語句的then時才能回填(7)表示的產(chǎn)生s(1)的第一個四元式的地址。同理(4)和(6)四元式中的轉(zhuǎn)移地址(p+1)也需要

34、s(2)的第一個四元式的地址回填。v采用拉鏈技術(shù)解決四元式序列中的地址回填為了記錄需回填地址的四元式，把需回填e true 的四元式拉成一個鏈(為真值的鏈簡稱真鏈)；把需要回填e false 的四元式拉成另一個鏈(為假值的鏈簡稱假鏈)拉鏈的方法：若有四元式序列：(10).goto e true(20).goto e true(30). goto e true則鏈成：(10).goto (0)(20).goto (10)(30). goto (20)其中，地址(30)為鏈頭，0為鏈尾標(biāo)志，地址(10)為鏈尾。v最后，討論用于if 語句和while語句中的布爾表達式的語義翻譯問題。為了回填四元式中

35、地址信息，要用到公共變量，過程和函數(shù)：四元式(標(biāo)號或地址)指針nextqnextq的值表示下一個即將要產(chǎn)生的四元式標(biāo)號，初值為1，每生成一個四元式，其值自動加1。 設(shè)置非終結(jié)符e的語義變量e bcodee bcode表示非終結(jié)符e的第一個四元式標(biāo)號。 回填過程backpatch(p,t) 功能：把p所鏈接的每個四元式的第四區(qū)段都回填為t。若原第四區(qū)段已有信息，應(yīng)保存后再回填為t。 鏈接函數(shù)merge(p1,p2)將p1和p2為鏈?zhǔn)椎膬蓚€鏈合并為一條，返回合并后的鏈?zhǔn)字怠８鶕?jù)布爾運算特性，采用自下而上的語法制導(dǎo)翻譯方法，給出布爾表達式文法中每個產(chǎn)生式相應(yīng)的語義子程序：(1) e =i e tru

36、e=nextq;e fale=nextq+1;e bcode=nextq;emit(if i place goto 0);emit(goto 0);(2)e =i(1) rop i(2) e true=nextq;e bcode=nextq;e fale=nextq+1;emit(if i(1)place rop i(2) place goto 0);emit(goto 0);(3) e =(e(1) etrue = e(1)true ; efalse = e(1)false; ebcode = e(1)bcode;(4) e = e(1) etrue = e(1)false; e false

37、 = e(1)true; e bcode = e(1) bcode (5) e =e(1)e(2) backpatch(e(1) false, e(2) bcode); ebcode=e(1) bcode; etrue=merge(e(1) true, e(2) true); efalse=e(2) false;(6) e =e(1) e(2) backpatch(e(1) true, e(2) bcode); ebcode=e(1) bcode; e true =e(2) true; e false =merge(e(1) false, e(2) false); 產(chǎn)生式(1)(同理(2),(

38、3),(4)式一樣)語義子程序中，可見用e =i歸約后，e的真假鏈都有了具體值。這樣，在用產(chǎn)生式(5)歸約時，e(1)與e（2）的真假鏈分別也有了具體值。根據(jù)布爾運算的特性可知：(1)當(dāng)e(1)為假時，計算e(2)，所以e(2)的第一個四元式地址(這是已記錄在e(2) bcode中) e(2) bcode這時回填為e(1)的假值鏈，因此有backpatch(e(1) false, e(2) bcode)。(2)若e(1)為真時，無須計算e(2)而去執(zhí)行s(1)的第一個四元式，但此時尚未掃描到“then”,因此，保留e(1)已形成的值鏈?zhǔn)譭(1) true；若e(2)為真時，其轉(zhuǎn)移地址用e(1)

39、，所以將e(1)，e(2)兩個真鏈e(1) true， e(2) true合并為e的一個鏈。(3)若e(1)為假，在計算e(2)， e(2)也為假，這時整個布爾式e(1) e(2)為假，可見e(2)的假出口與整個布爾式的假出口一致，此時e(2)的假出口e(2) false業(yè)已形成。因此，有e false= e(2) false。(4)盡管有e(1)，e(2)參與運算，但按掃描順序，首先生成e(1)的四元式。因此，e(1)的第一個四元式也就是整個布爾式的第一個四元式，所以有ebcode=e(1) bcode.同理不難分析(6)產(chǎn)生式的語義子程序。 下面以表達式abd為例，按上面的翻譯方案，說明將

40、它生成四元式的過程。(1)首先指示器nextq賦初值為1，當(dāng)掃描到a時，用e =i歸約，根據(jù)產(chǎn)生式(1)的語義子程序，有：e(1) true=nextq=(1), e(1) false=nextq+1=(2),ebcode=1,生成四元式: (1)if a goto 0 (2)goto 0此時nextq=3(2)繼續(xù)掃描，由自底向上的語法制導(dǎo)翻譯可知，這時應(yīng)歸約bd,用產(chǎn)生式e =e(1) rop e(2) ，有：e(2) true=nextq=(3), e(2) false=nextq+1=(4), e(2) bcode=nextq=(3),生成四元式: (3)if bd goto 0(4)

41、goto 0此時nextq=5 (3)繼續(xù)向上歸約，用e=e(1) e(2)歸約，有：回填backpatch(e(1) false, e(2) bcode)ebcode= e(1) bcode;etrue=merge(e(1) true, e(2) true);efalse=e(2) false;因為e(1) ture=(1), e(2) ture=(3)所以合并后etrue（3），將e(1) true放到e(2)的鏈尾?；靥畹?e(2) bcode=(3),將(3)填入e(1) false中，即goto(3)。合并e(1),e(2)的真鏈將e(2) true填到以e(1) 為真鏈頭的一個四元

42、式區(qū)段中。最后e(2)的假鏈就是e的假鏈：efalse=e(2) false; 得到一組四元式: (1)if a goto 0(2)goto (3)(3) if bd goto(1)(4)goto 0這時，etrue=(3),efalse=(4)三、控制語句的翻譯v在程序設(shè)計語言中，控制語句的一般形式：if-then, if-then-else, while-do這些語句由下列文法定義：gs: (1)s(1)s =if e then s(1)(2)s =if e then s(1) else s(2)(3)s=while e do s(1)(4)s=a(5)s=l(6)l=l(1);s(7)l

43、=s其中：非終結(jié)符l表示語句串，a表示賦值語句，s為語句，e為布爾表達式。下面著重介紹控制語句翻譯過程中涉及的回填和拉鏈技術(shù)。1.if語句的翻譯如：s =if e then s(1) else s(2)翻譯此語句應(yīng)明確以下幾點：(1)布爾表達式e的作用僅在于控制對s(1)或s(2)的選擇。因此，作為轉(zhuǎn)移條件的布爾式e，使用e true和e false分別指出尚待回填“真”,“假”出口的四元式串；(2)e的“真”出口只有在掃描到then時才能知道，而它的“假”出口則需要s(1)并且到達else之后才能明確。這就是說，必須把efalse的值傳下去，以便在到達相應(yīng)的else時才能進行回填。(3)另外

44、，當(dāng)s(1) 執(zhí)行完之后意味著整個if語句也已經(jīng)執(zhí)行完畢，因此在s(1) 的編碼之后產(chǎn)生一條無條件轉(zhuǎn)移指令(goto 0)，但在完成s(2) 的翻譯之前，該無條件轉(zhuǎn)移的轉(zhuǎn)移目標(biāo)無法知道。對于語句嵌套的情況，如：if e(1) then if e(2) then s(1) else s(2) else s(3),在翻譯s(2)后，s(1) 后的無條件轉(zhuǎn)移目標(biāo)仍無法確定，因為它不僅跨越s(2)，還要跨越s(3)?？梢?，轉(zhuǎn)移目標(biāo)的確定與if所處的環(huán)境有關(guān)。因此，對非終結(jié)符s(或l)設(shè)置一個語義變量s chain(或l chain),記憶所有待填信息的四元式鏈，知道翻譯完整個語句后再回填轉(zhuǎn)移目標(biāo)地址。

45、 為了掃描控制語句的每一時刻不失時機地處理和回填有關(guān)信息，將文法改寫，并寫出if 語句各產(chǎn)生式相應(yīng)語義子程序。(1)s =cs(1)(2)c=if e then(3)s=tps(2)(4)tp= cs(1) else根據(jù)程序設(shè)計語言的處理順序，首先用產(chǎn)生式(2)c=if e then 歸約，這時在then后可產(chǎn)生e的真出口地址。因此將then后的第一個四元式回填至e的真出口地址。e的假出口地址作為待填信息放在c的語義變量c chain中，即c=if e then backpatch(etrue,nextq);cchain=efalse;接著用產(chǎn)生式(1) s =cs(1)繼續(xù)向上歸約。此時已經(jīng)

46、處理到c=if e then s(1),注意到歸約時e的真出口已經(jīng)處理，由于e不成立時注意地址v與s(1)語句的待填轉(zhuǎn)移地址相同，e的假出口地址已放在cchain中，但此時轉(zhuǎn)移地址仍未確定，s(1)的待填轉(zhuǎn)移地址的鏈放在s(1) chain中，所以應(yīng)將cchain與s(1) chain一并作為s的待填信息鏈，用函數(shù)merge鏈起來，鏈頭保留在s chain中，即有：s=cs(1) schain=merge(cchain, s(1) chain如果if語句沒有后繼部分，在產(chǎn)生式(1)(2)歸約為s后，隨即可產(chǎn)生后續(xù)第一個四元式地址，以此回填s的語義值schain。即為if e then s(1)

47、語句的語義子程序。如果if 語句為if-then-else 形式，用產(chǎn)生式tp= cs(1) else繼續(xù)歸約。歸約時首先產(chǎn)生s(1)語句序列的最后一個無條件轉(zhuǎn)移四元式，它的標(biāo)號保留在q中。(i) s(1)第一個四元式/*e的真出口*/。(q)goto 0/*q的第四區(qū)段有待回填*/nextq/*else后的第一個四元式，即e的假出口*/q就是整個語句s的語義值schain.因為有待回填q第四區(qū)段的值，它與schain一樣，鏈在以鏈頭為tpchain的鏈中，用merge函數(shù)實現(xiàn)。過程emit產(chǎn)生(q)四元式后，nextq自動加1，這時nextq是else后的第一個四元式地址，也是e的假出口地址

48、，回填該值時efalse即cchain中，因此有 tp= cs(1) else q=nextq;emit(goto 0);backpatch(cchain,nextq);tpchain=merge(schain,q);最后用產(chǎn)生式(3) s=tps(2)歸約。當(dāng)s(2)語句序列處理完后，產(chǎn)生if的后繼語句。這時就有了后繼語句四元式的地址，該地址是整個if語句的出口地址，它與s(2)語句序列的出口一致。s(2)的出口待填信息在s(2) chain中，因此將tpchain和s(2) chain鏈接，并以schain為鏈頭。s=tps(2)schain=merge(tpchain,s(2)chain

49、);2.while語句的翻譯將產(chǎn)生式：s=while e do s(1) 分解如下：(1)s=wds(1)(2) wd=wedo(3)w=while寫出文法各產(chǎn)生式的語義子程序如下：觀察while語句的代碼結(jié)構(gòu)如圖，執(zhí)行到while時，首先記下e的第一條四元式地址，以便歸約到do s(1)后能準(zhǔn)確地轉(zhuǎn)到該入口。其次，語義值w chain仍是待填信息鏈。根據(jù)while語句的語義，s(1)語句序列的最后一條語句要由能轉(zhuǎn)移到e的第一個四元式的功能，以便判斷e是否成立。e成立再執(zhí)行s(1)，e不成立則離開while語句，執(zhí)行后繼語句。因此e的假出口efalse為待填信息存放在wchain與schain

50、中。由while語句執(zhí)行的順序，首先用產(chǎn)生式(3)w =while歸約，這時nextq記下e的第一個四元式地址，并保留在wbcode中，即有：(1)w=while wbcode=nextq;s(1)的代碼e的代碼真假繼續(xù)掃描，用產(chǎn)生式wd=wedo歸約。如前所述，掃描完e后，應(yīng)該會產(chǎn)生etrue和efalse。掃描完do后，可回填etrue值，用backpatch(etrue,nextq)，而efalse要等到s(1)語句序列全部產(chǎn)生后才能回填，因此作為待填信息，由wdchain傳下去，wdchainefalse繼續(xù)傳下去。即有：(2) wd=wedo backpatch(etrue,next

51、q);wdchain=efalse;wdbcode=wbcode;用產(chǎn)生式(1)s=wd s(1)歸約時， s(1)語句序列的全部四元式已產(chǎn)生。應(yīng)無條件返回e的第一個四元式，因此產(chǎn)生四元式（goto wdbcode)，同時回填e的入口地址到s(1)語句序列中所有需要該信息的四元式中，用backpatch(s(1) chain, wdbcode)。即有：(3)s=wds(1) backpatch(s(1) chain, wdbcode);emit(goto wdbcode);schain=wdchain;goto wdbcode是while的后繼語句。后繼語句的第一個四元式地址是e的假出口，已在

52、wdchain中，將該信息作為整個while語句的假出口保留schain中，以便回填。例：將下列語句翻譯成一組四元式，while awhile abd dob6) then x=x-1if (x6) then x=x-1else y=x+1else y=x+1根據(jù)while，if語句的文法中產(chǎn)生式語義動作和布爾表達式以及賦值語句的翻譯方案，翻譯該語句的一組四元式如下： 100 if a goto 104100 if a goto 104 / /* *w wbcodebcode=100=100* */ / 101 goto 101 goto 102 102 102 if bd goto 102

53、if b6 goto 104 if x6 goto 106 106 105 goto 105 goto 109 109 106 t 106 t1 1=x-1=x-1 107 x= t 107 x= t1 1108 goto 111109 t t2 2=x+1=x+1110 y= t110 y= t2 2111 goto111 goto 100 100112112最后，schain112回填在e的假出口中。 a代碼 b6代碼x=x-1代碼y=x+1代碼tfttff代碼結(jié)構(gòu)圖 小結(jié)及舉例一.小結(jié)1.主要內(nèi)容：語義分析采用語法制導(dǎo)翻譯方法以及中間代碼的生成。（1）語義描述的工具屬性文法。 屬性文法定

54、義為三元組ag（g，v，e），它將文法g.屬性v和屬性的斷言e有機的結(jié)合在一起，準(zhǔn)確的描述了處理（歸約或推導(dǎo)）每個產(chǎn)生式時的語義分析工作。 屬性描述了處理對象的特征。屬性的斷言說明了文法符號之間的語義規(guī)則和語義動作。（2）語法制導(dǎo)翻譯方法。兩類翻譯方法：自底向上和自頂向下語法制導(dǎo)翻譯方法翻譯對象：簡單算術(shù)表達式和賦值語句.布爾表達式.條件語句和while語句等。（重點掌握部分）（3）翻譯結(jié)果的形成中間代碼。中間代碼形式：逆波蘭式.三元式.間接三元式.樹形表示.四元式和三地址代碼等。2.主要解決的問題（1）設(shè)計屬性文法設(shè)計文法產(chǎn)生式的語義規(guī)則或語義動作子程序。（難點）*根據(jù)所給的條件，設(shè)計文法符

55、號的屬性。*根據(jù)文法符號屬性的語義關(guān)系設(shè)計語義規(guī)則或語義動作。（2）掌握自底向上翻譯方法中，算術(shù)表達式.布爾表達式.賦值語句.條件語句和while語句的翻譯過程和生成四元式的結(jié)果。（3）掌握給定表達式的各種中間代碼形式的描述方法。二.舉例例：給出adva+be表達式的逆波蘭表示根據(jù)運算符的優(yōu)先級，逆波蘭表示：運算符的優(yōu)先級，逆波蘭表示：abc+adab+ev例：寫出條件表達式：例：寫出條件表達式： if (x+y)*z=5 then x:=(a+b)c else y:=abcc else y:=abc(1)(1)四元式序列四元式序列 (2)(2)逆波蘭表示逆波蘭表示解：解：(1)(1)四元式序

56、列四元式序列(1)(+,x,y,t(1)(+,x,y,t1 1) )(2)(2)(* *,t,t1 1,z,t,z,t2 2) )(3)(=,t(3)(=,t2 2,5,t,5,t3 3) )(4)(jumpf,t(4)(jumpf,t3 3,(9),(9)(5)(+,a,b,t(5)(+,a,b,t4 4) )(6)(,t(6)(,t4 4,c,t,c,t5 5) )(7)(:=,t(7)(:=,t5 5,x),x)(8)(jump,(12)(8)(jump,(12)(9)(,a,b,t(9)(,a,b,t6 6) )(10)(,t(10)(,t6 6,c,t,c,t7 7) )(11)(:=,t(11)