ch05-語法制導(dǎo)翻譯技術(shù)

1、第5章 語法制導(dǎo)翻譯技術(shù)知識點：語法制導(dǎo)定義、翻譯方案 S-屬性定義、L-屬性定義 S-屬性定義的翻譯 L-屬性定義的翻譯第一頁，編輯于星期六：五點 十九分。語法制導(dǎo)翻譯技術(shù)語義分析涉及到語言的語義形式語義學(xué)的研究開始于20世紀60年代初形式語義學(xué)可以分為三類操作語義學(xué)：通過說明程序在一個機器中是如何執(zhí)行的來定義程序的語義，著重模擬數(shù)據(jù)加工過程中計算機系統(tǒng)的操作指稱語義學(xué)：使用數(shù)學(xué)函數(shù)來描述程序和程序的構(gòu)成，函數(shù)通過把語義值聯(lián)系到正確的語法結(jié)構(gòu)來描述程序的語義，主要描述數(shù)據(jù)加工的結(jié)果公理語義學(xué)：把數(shù)理邏輯應(yīng)用于語言的語義，語言結(jié)構(gòu)與謂詞轉(zhuǎn)換器聯(lián)系在一起，語言結(jié)構(gòu)的行為以命題刻畫，通過描述程序執(zhí)

2、行對程序斷言的影響來定義程序、語句或語言結(jié)構(gòu)的語義，主要用于程序正確性證明語法制導(dǎo)翻譯技術(shù)多數(shù)編譯程序普遍采用的一種技術(shù)比較接近形式化第二頁，編輯于星期六：五點 十九分。2語法制導(dǎo)翻譯技術(shù)根據(jù)翻譯目標的要求確定每個產(chǎn)生式所包含的語義；根據(jù)產(chǎn)生式包含的語義，分析文法中每個符號的語義；把這些語義以屬性的形式附加到相應(yīng)的文法符號上；根據(jù)產(chǎn)生式的語義，給出符號屬性的求值規(guī)則(即語義規(guī)則)，從而形成語法制導(dǎo)定義。在語法分析過程中，當(dāng)使用該產(chǎn)生式時，根據(jù)語義規(guī)則對相應(yīng)的屬性進行求值，從而完成翻譯。例如：考慮算術(shù)表達式文法總目標：計算表達式的值產(chǎn)生式 EE1+T 的語義：表達式的值由兩個子表達式的值相加得到

3、分析每個符號的語義，并以屬性的形式記錄：E.val、E1.val、T.val求值規(guī)則：E.val=E1.val+T.val語法制導(dǎo)定義：產(chǎn)生式 語義規(guī)則EE1+TETTT1*FTFF(E) FdigitE.val=E1.val+T.valE.val=T.valT.val=T1.val*F.valT.val=F.valF.val=E.val F.val=digit.val第三頁，編輯于星期六：五點 十九分。3語法制導(dǎo)翻譯技術(shù)（續(xù)）例如：考慮算術(shù)表達式文法總目標：檢查表達式的類型產(chǎn)生式 EE1+T 的語義：表達式的類型由兩個子表達式的類型綜合得到分析每個符號的語義，并以屬性的形式記錄：E.type

4、、 E1.type、 T.type求值規(guī)則： if (E1.type=integer)&(T.type=integer) E.type=integer; else 第四頁，編輯于星期六：五點 十九分。4翻譯結(jié)果取決于翻譯目標生成代碼可以為源程序產(chǎn)生中間代碼可以直接生成目標機指令對輸入符號串進行解釋執(zhí)行向符號表中存放信息給出錯誤信息翻譯的結(jié)果依賴于語義規(guī)則使用語義規(guī)則進行計算所得到的結(jié)果就是對輸入符號串進行翻譯的結(jié)果。如：EE+T 的翻譯結(jié)果可以是：計算表達式的值、檢查表達式的類型是否合法、為表達式創(chuàng)建語法樹、生成代碼等等。第五頁，編輯于星期六：五點 十九分。5語法制導(dǎo)翻譯技術(shù)（續(xù)）進一步：用一

5、個或多個子程序（稱為語義動作）所要完成的功能描述產(chǎn)生式的語義；把語義動作插入到產(chǎn)生式中相應(yīng)位置，從而形成翻譯方案。在語法分析過程中使用該產(chǎn)生式時，在適當(dāng)?shù)臅r機調(diào)用這些動作，完成所需要的翻譯。語法制導(dǎo)定義是對翻譯的高層次的說明，它隱蔽了一些實現(xiàn)細節(jié)，無須指明翻譯時語義規(guī)則的計算次序。翻譯方案指明了語義規(guī)則的計算次序，規(guī)定了語義動作的執(zhí)行時機。第六頁，編輯于星期六：五點 十九分。6語法制導(dǎo)翻譯的一般步驟輸入符號串 分析樹 依賴圖 語義規(guī)則的計算順序 計算結(jié)果第七頁，編輯于星期六：五點 十九分。7語法制導(dǎo)翻譯技術(shù)5.1 語法制導(dǎo)定義及翻譯方案5.2 S-屬性定義的自底向上翻譯5.3 L-屬性定義的自

6、頂向下翻譯5.4 L-屬性定義的自底向上翻譯 小 結(jié)第八頁，編輯于星期六：五點 十九分。85.1 語法制導(dǎo)定義及翻譯方案對上下文無關(guān)文法的推廣每個文法符號都可以有一個屬性集，其中可以包括兩類屬性：綜合屬性和繼承屬性。左部符號的綜合屬性是從該產(chǎn)生式右部文法符號的屬性值計算出來的；在分析樹中，一個內(nèi)部結(jié)點的綜合屬性是從其子結(jié)點的屬性值計算出來的。出現(xiàn)在產(chǎn)生式右部的某文法符號的繼承屬性是從其所在產(chǎn)生式的左部非終結(jié)符號和/或右部文法符號的屬性值計算出來的；在分析樹中，一個結(jié)點的繼承屬性是從其兄弟結(jié)點和/或父結(jié)點的屬性值計算出來的。分析樹中某個結(jié)點的屬性值是由與在這個結(jié)點上所用產(chǎn)生式相應(yīng)的語義規(guī)則決定的

7、。和產(chǎn)生式相聯(lián)系的語義規(guī)則建立了屬性之間的關(guān)系，這些關(guān)系可用有向圖（即：依賴圖）來表示。第九頁，編輯于星期六：五點 十九分。9本節(jié)內(nèi)容安排一、語法制導(dǎo)定義二、依賴圖三、計算次序四、S屬性定義和L屬性定義五、翻譯方案第十頁，編輯于星期六：五點 十九分。10一、語法制導(dǎo)定義在一個語法制導(dǎo)定義中，對應(yīng)于每一個文法產(chǎn)生式A，都有與之相聯(lián)系的一組語義規(guī)則，其形式為：b=(c1,c2,ck) 這里，是一個函數(shù)，而且或者(1) b是A的一個綜合屬性，且c1、c2、ck是產(chǎn)生式右部文法符號的屬性，或者(2) b是產(chǎn)生式右部某個文法符號的一個繼承屬性，且c1、c2、ck是A或產(chǎn)生式右部任何文法符號的屬性。 屬性

8、b依賴于屬性c1、c2、ck。 語義規(guī)則函數(shù)都不具有副作用的語法制導(dǎo)定義稱 為屬性文法第十一頁，編輯于星期六：五點 十九分。11語義規(guī)則一般情況：語義規(guī)則函數(shù)可寫成表達式的形式。某些情況下：一個語義規(guī)則的唯一目的就是產(chǎn)生某個副作用，如打印一個值、向符號表中插入一條記錄等；這樣的語義規(guī)則通常寫成過程調(diào)用或程序段?？闯墒窍鄳?yīng)產(chǎn)生式左部非終結(jié)符號的虛擬綜合屬性。虛屬性和符號=都沒有表示出來。第十二頁，編輯于星期六：五點 十九分。12簡單算術(shù)表達式求值的語法制導(dǎo)定義綜合屬性val與每一個非終結(jié)符號E、T、F相聯(lián)系表示相應(yīng)非終結(jié)符號所代表的子表達式的整數(shù)值LE的語義規(guī)則是一個過程，打印出由E產(chǎn)生的算術(shù)表

9、達式的值，可以認為是非終結(jié)符號L的一個虛擬綜合屬性。 產(chǎn)生式 LE EE1+T ET TT1*F TF F(E) Fdigit 語義規(guī)則 print(E.val) E.val=E1.val+T.val E.val=T.val T.val=T1.val*F.val T.val=F.val F.val=E.val F.val=digit.lexval 第十三頁，編輯于星期六：五點 十九分。13綜合屬性分析樹中，如果一個結(jié)點的某一屬性由其子結(jié)點的屬性確定，則這種屬性為該結(jié)點的綜合屬性。如果一個語法制導(dǎo)定義僅僅使用綜合屬性，則稱這種語法制導(dǎo)定義為S-屬性定義。對于S-屬性定義，通常采用自底向上的方法對

10、其分析樹加注釋，即從樹葉到樹根，按照語義規(guī)則計算每個結(jié)點的屬性值。簡單臺式計算機的語法制導(dǎo)定義是S-屬性定義第十四頁，編輯于星期六：五點 十九分。143*5+4的分析樹加注釋的過程屬性值的計算可以在語法分析過程中進行。LE E + TT FT * F digitF digitdigit.lexval=3.val=3.val=3.lexval=5.val=5.val=15.val=15.lexval=4.val=4.val=4.val=19Print (19)第十五頁，編輯于星期六：五點 十九分。15繼承屬性分析樹中，一個結(jié)點的繼承屬性值由該結(jié)點的父結(jié)點和/或它的兄弟結(jié)點的屬性值決定?？捎美^承屬

11、性表示程序設(shè)計語言結(jié)構(gòu)中上下文之間的依賴關(guān)系可以跟蹤一個標識符的類型可以跟蹤一個標識符，了解它是出現(xiàn)在賦值號的右邊還是左邊，以確定是需要該標識符的值還是地址。第十六頁，編輯于星期六：五點 十九分。16用繼承屬性L.in傳遞類型信息的語法制導(dǎo)定義D產(chǎn)生的聲明語句包含了類型關(guān)鍵字int或real，后跟一個標識符表。T有綜合屬性type，其值由聲明中的關(guān)鍵字確定。L的繼承屬性L.in，產(chǎn)生式DTL, L.in 表示從其兄弟結(jié)點T繼承下來的類型信息。產(chǎn)生式LL1,id， L1.in 表示從其父結(jié)點L繼承下來的類型信息 產(chǎn)生式 DTL Tint Treal LL1,id Lid 語義規(guī)則 L.in=T.

12、type T.type=integer T.type=real L1.in=L.in addtype(id.entry,L.in) addtype(id.entry,L.in) 第十七頁，編輯于星期六：五點 十九分。17語句real id1,id2,id3的注釋分析樹L產(chǎn)生式的語義規(guī)則使用繼承屬性L.in把類型信息在分析樹中向下傳遞；并通過調(diào)用過程addtype，把類型信息填入標識符在符號表中相應(yīng)的表項中。 DT LL , id2L , id3id1real.type=real.in=real.in=real.in=realaddtype(id3.entry,L.in)addtype(id1.

13、entry,L.in)addtype(id2.entry,L.in)第十八頁，編輯于星期六：五點 十九分。18二、依賴圖分析樹中，結(jié)點的繼承屬性和綜合屬性之間的相互依賴關(guān)系可以由依賴圖表示。為每個包含過程調(diào)用的語義規(guī)則引入一個虛擬綜合屬性b，以便把語義規(guī)則統(tǒng)一為b=(c1,c2,ck)的形式。依賴圖中：為每個屬性設(shè)置一個結(jié)點如果屬性b依賴于c，那么從屬性c的結(jié)點有一條有向邊連到屬性b的結(jié)點。第十九頁，編輯于星期六：五點 十九分。19算法5.1 構(gòu)造依賴圖輸入：一棵分析樹輸出：一張依賴圖方法： for (分析樹中每一個結(jié)點n) for (結(jié)點n處的文法符號的每一個屬性a) 為a在依賴圖中建立一個

14、結(jié)點; for (分析樹中每一個結(jié)點n) for (結(jié)點n處所用產(chǎn)生式對應(yīng)的每一個 語義規(guī)則 b=(c1,c2,ck) for (i=1;i=k;i+) 從ci結(jié)點到b結(jié)點構(gòu)造一條有向邊;第二十頁，編輯于星期六：五點 十九分。20依賴圖構(gòu)造舉例產(chǎn)生式 依賴規(guī)則 AXY A.a=(X.x,Y.y) X.i=g(A.a,Y.y) AX Y.a.x.i.yDT LL , id2L , id3id1real4 type9 in10 addtype7 in 8 addtype5 in6 addtype 1 entry 2 entry 3 entry第二十一頁，編輯于星期六：五點 十九分。21三、計算次序

15、有向非循環(huán)圖的拓撲排序圖中結(jié)點的一種排序m1,m2,mk有向邊只能從這個序列中前邊的結(jié)點指向后面的結(jié)點如果mimj是從mi指向mj的一條邊，那么在序列中mi必須出現(xiàn)在mj之前。依賴圖的任何拓撲排序給出了分析樹中結(jié)點的語義規(guī)則計算的有效順序在拓撲排序中，一個結(jié)點上語義規(guī)則 b=(c1,c2,ck) 中的屬性c1,c2,ck在計算b時都是可用的。拓撲排序：1、2、3、4、5、6、7、8、9、104、5、3、6、7、2、8、9、1、10第二十二頁，編輯于星期六：五點 十九分。22計算順序從拓撲排序中可以得到下面的程序，an代表依賴圖中與序號n的結(jié)點有關(guān)的屬性：type=real；in5=type；a

16、ddtype(id3.entry,in5)；in7=in5；addtype(id2.entry,in7)；in9=in7；addtype(id1.entry,in9)；第二十三頁，編輯于星期六：五點 十九分。23語法制導(dǎo)翻譯過程最基本的文法用于建立輸入符號串的分析樹；為分析樹構(gòu)造依賴圖；對依賴圖進行拓撲排序；從這個序列得到語義規(guī)則的計算順序；照此計算順序進行求值，得到對輸入符號串的翻譯。輸入符號串 分析樹 依賴圖 語義規(guī)則的計算順序 計算結(jié)果第二十四頁，編輯于星期六：五點 十九分。24四、S屬性定義和L屬性定義 S屬性定義：僅涉及綜合屬性的語法制導(dǎo)定義 L屬性定義：一個語法制導(dǎo)定義是L屬性定義

17、，如果與每個產(chǎn)生式AX1X2Xn相應(yīng)的每條語義規(guī)則計算的屬性都是A的綜合屬性，或是Xj（1jn）的繼承屬性，而該繼承屬性僅依賴于：A的繼承屬性；產(chǎn)生式中Xj左邊的符號X1、X2、Xj-1的屬性； 每一個S屬性定義都是L屬性定義第二十五頁，編輯于星期六：五點 十九分。25例：非L屬性定義的 語法制導(dǎo)定義產(chǎn)生式 語義規(guī)則 ALM L.i=l(A.i) M.i=m(L.s) A.s=f(M.s) AQR R.i=r(A.i) Q.i=q(R.s) A.s=f(Q.s) 產(chǎn)生式 DTL Tint Treal LL1,id Lid 語義規(guī)則 L.in=T.type T.type=integer T.ty

18、pe=real L1.in=L.in addtype(id.entry,L.in) addtype(id.entry,L.in) 例：是L屬性定義的 語法制導(dǎo)定義 第二十六頁，編輯于星期六：五點 十九分。26屬性計算順序深度優(yōu)先遍歷分析樹 void deepfirst (n: node) for (n的每一個子結(jié)點m，從左到右) 計算m的繼承屬性; deepfirst(m); ; 計算n的綜合屬性;.以分析樹的根結(jié)點作為實參L屬性定義的屬性都可以用深度優(yōu)先的順序計算。進入結(jié)點前，計算它的繼承屬性從結(jié)點返回時，計算它的綜合屬性第二十七頁，編輯于星期六：五點 十九分。27五、翻譯方案上下文無關(guān)文法

19、的一種便于翻譯的書寫形式屬性與文法符號相對應(yīng)語義動作括在花括號中，并插入到產(chǎn)生式右部某個合適的位置上給出了使用語義規(guī)則進行屬性計算的順序分析過程中翻譯的注釋第二十八頁，編輯于星期六：五點 十九分。28例：一個簡單的翻譯方案 ETR R+T print（+） R1 | -T print（-） R1 | Tnum print(num.val) 9-5+2的分析樹：ET R9 - T R5 + T R2 語義動作作為相應(yīng)產(chǎn)生式左部符號對應(yīng)結(jié)點的子結(jié)點深度優(yōu)先遍歷樹中結(jié)點，執(zhí)行其中的動作，打印出95-2+print(9) print(-) print(5) print(+) print(2) 第二十九

20、頁，編輯于星期六：五點 十九分。29翻譯方案的設(shè)計對于S屬性定義：為每一個語義規(guī)則建立一個包含賦值的動作把這個動作放在相應(yīng)的產(chǎn)生式右邊末尾例：產(chǎn)生式 語義規(guī)則 TT1*F T.val=T1.val*F.val如下安排產(chǎn)生式和語義動作： TT1*FT.val=T1.val*F.val 第三十頁，編輯于星期六：五點 十九分。30為L屬性定義設(shè)計翻譯方案的原則產(chǎn)生式右部文法符號的繼承屬性必須在這個符號以前的動作中計算出來計算該繼承屬性的動作必須出現(xiàn)在相應(yīng)文法符號之前一個動作不能引用這個動作右邊的文法符號的綜合屬性產(chǎn)生式左邊非終結(jié)符號的綜合屬性只有在它所引用的所有屬性都計算出來之后才能計算這種屬性的計

21、算動作放在產(chǎn)生式右端末尾第三十一頁，編輯于星期六：五點 十九分。31例：考慮如下翻譯方案 SA1A2 A1.in=1；A2.in=2 Aa print(A.in)SA1 A2 A1.in=1;A2.in=2a print(A.in)a print(A.in)a print(A.in)S A1.in=1;A2.in=2 A1 A2 a print(A.in)第三十二頁，編輯于星期六：五點 十九分。32L屬性定義翻譯方案設(shè)計舉例語法制導(dǎo)定義翻譯方案 產(chǎn)生式 DTL Tint Treal LL1,id Lid 語義規(guī)則 L.in=T.type T.type=integer T.type=real L

22、1.in=L.in addtype(id.entry,L.in) addtype(id.entry,L.in) DT L.in=T.type LTint T.type=integer Treal T.type=real L L1.in=L.in L1,id addtype(id.entry, L.in) Lid addtype(id.entry, L.in) 第三十三頁，編輯于星期六：五點 十九分。33例：為如下L屬性定義設(shè)計翻譯方案L屬性定義唯一的繼承屬性是非終結(jié)符號B的ps屬性依賴于左部符號的繼承屬性，或者常數(shù) 產(chǎn)生式 語義規(guī)則 SB B.ps=10 S.ht=B.ht BB1B2 B1.

23、ps=B.ps B2.ps=B.ps B.ht=max(B1.ht,B2.ht) BB1subB2 B1.ps=B.ps B2.ps=shrink(B.ps) B.ht=disp(B1.ht,B2.ht) Btext B.ht=text.hB.ps第三十四頁，編輯于星期六：五點 十九分。34把語義規(guī)則插入到產(chǎn)生式中適當(dāng)?shù)奈恢肧B.ps=10 B S.ht=B.htS B.ps=10 B S.ht=B.htB B1.ps=B.psB1 B2.ps=B.psB2 B.ht=max(B1.ht,B2.ht)B B1.ps=B.ps B1 sub B2.ps=shrink(B.ps) B2 B.ht=

24、disp(B1.ht,B2.ht)Btext B.ht=text.hB.ps 第三十五頁，編輯于星期六：五點 十九分。355.2 S-屬性定義的自底向上翻譯S屬性定義：只用綜合屬性的語法制導(dǎo)定義一、構(gòu)造表達式的語法樹二、構(gòu)造表達式的語法樹的語法制導(dǎo)定義三、S屬性定義的自底向上實現(xiàn)第三十六頁，編輯于星期六：五點 十九分。36一、構(gòu)造表達式的語法樹把語法規(guī)則中對語義無關(guān)緊要的具體規(guī)定去掉，剩下來的本質(zhì)性的東西稱為抽象語法。如：賦值語句：x=y、x:=y、或yx抽象形式：assignment(variable,expression)語法樹：分析樹的抽象（或壓縮）形式。也稱為語法結(jié)構(gòu)樹或結(jié)構(gòu)樹。內(nèi)部結(jié)

25、點表示運算符號，其子結(jié)點表示它的運算分量。第三十七頁，編輯于星期六：五點 十九分。37語法樹示例Sif E then S1 else S2 的語法樹if - then - elseE S1 S2+ * 4 3 5表達式 3*5+4 的語法樹LE nE + TT FT * F digitF digitdigit第三十八頁，編輯于星期六：五點 十九分。38構(gòu)造表達式的語法樹表達式的語法樹的形式每一個運算符號或運算分量都對應(yīng)樹中的一個結(jié)點運算符號結(jié)點的子結(jié)點分別是與該運算符的各個運算分量相應(yīng)的子樹的根。每一個結(jié)點可包含若干個域：標識域、指針域、屬性值域等在運算符結(jié)點中一個域標識運算符號其它各域包含指

26、向與各運算分量相應(yīng)的結(jié)點的指針稱運算符號為該結(jié)點的標號第三十九頁，編輯于星期六：五點 十九分。39構(gòu)造函數(shù)makenode (op, left, right)建立一個運算符號結(jié)點，標號是op；域left和right是指向其左右運算分量結(jié)點的指針。makeleaf (id, entry)建立一個標識符結(jié)點，標號是id；域entry是指向該標識符在符號表中的相應(yīng)條目的指針。makeleaf (num, val)建立一個數(shù)結(jié)點，標號為num；域val用于保存該數(shù)的值。第四十頁，編輯于星期六：五點 十九分。40建立表達式a*4+b的語法樹p1=makeleaf(id,entrya);p2=makele

27、af(num,4);p3=makenode(*,p1,p2);p4=makeleaf(id,entryb);p5=makenode(+,p3,p4); id符號表中a的入口P1num 4P2 * P3 id符號表中b的入口P4 + P5+ * b a 4第四十一頁，編輯于星期六：五點 十九分。41二、構(gòu)造表達式語法樹的語法制導(dǎo)定義目標：為表達式創(chuàng)建語法樹產(chǎn)生式語義：創(chuàng)建與產(chǎn)生式左部符號代表的子表達式對應(yīng)的子樹，即創(chuàng)建子樹的根結(jié)點。文法符號的屬性：記錄所建結(jié)點， E.nptr、 T.nptr、F.nptr 指向相應(yīng)子樹根結(jié)點的指針產(chǎn)生式的語義動作舉例： EE1+T E.nptr=makenode

28、(+,E1.nptr,T.nptr)TF T.nptr=F.nptr Fid F.nptr=makeleaf(id, id.entry)Fnum F.nptr=makeleaf(num, num.val)第四十二頁，編輯于星期六：五點 十九分。42構(gòu)造表達式語法樹的語法制導(dǎo)定義 為了記錄在構(gòu)造過程中建立的子樹，為每個非終結(jié)符號引入一個綜合屬性nptr。nptr是一個指針，指向語法樹中相應(yīng)非終結(jié)符號產(chǎn)生的表達式子樹的根結(jié)點。產(chǎn)生式EE1+TETTT1* FTFF(E)FidFnumE.nptr= makenode(+,E1.nptr,T.nptr)E.nptr=T.nptrT.nptr= mak

29、enode(*,T1.nptr,F.nptr)T.nptr= F.nptrF.nptr= E.nptrF.nptr= makeleaf(id,id.entry)F.nptr= makeleaf(num,num.val)語義規(guī)則第四十三頁，編輯于星期六：五點 十九分。43表達式a*4+b的語法樹的構(gòu)造num 4 id符號表中a的入口a E ETFb 4 . nptr. nptr. nptr. nptr. nptr. nptr * id符號表中b的入口 + *F +T EE1+TETTT1*FTFF(E)FidFnumF.nptr=makeleaf(id,entrya)T.nptr=F.nptrF

30、.nptr=makeleaf(num,4)T.nptr=makenode(*,T1.nptr,F.nptr)E.nptr=T.nptrF.nptr=makeleaf(id,entryb)E.nptr=makenode(+,E1.nptr,T.nptr)F . nptrT . nptr第四十四頁，編輯于星期六：五點 十九分。44表達式a*4+b的語法樹的構(gòu)造num 4 id符號表中a的入口a E ETFb 4 . nptr. nptr. nptr. nptr. nptr. nptr * id符號表中b的入口 + *F +T EE1+TETTT1*FTFF(E)FidFnumF . nptrT .

31、 nptr第四十五頁，編輯于星期六：五點 十九分。45表達式的有向非循環(huán)圖(dag)dag與語法樹相同的地方：表達式的每一個子表達式都有一個結(jié)點一個內(nèi)部結(jié)點表示一個運算符號，且它的子結(jié)點表示它的運算分量。dag與語法樹不同的地方：dag中，對應(yīng)一個公共子表達式的結(jié)點具有多個父結(jié)點語法樹中，公共子表達式被表示為重復(fù)的子樹為表達式創(chuàng)建dag的函數(shù)makenode和makeleaf建立新結(jié)點之前先檢查是否已經(jīng)存在一個相同的結(jié)點若已存在，返回一個指向先前已構(gòu)造好的結(jié)點的指針；否則，創(chuàng)建一個新結(jié)點，返回指向新結(jié)點的指針。第四十六頁，編輯于星期六：五點 十九分。46為表達式 a+a*(b-c)+(b-c)

32、*d 構(gòu)造dag函數(shù)調(diào)用p1=makeleaf(id,a)；p2=makeleaf(id,a)；p3=makeleaf(id,b)；p4=makeleaf(id,c)；p5=makenode(-,p3,p4)；p6=makenode(*,p2,p5)；p7=makenode(+,p1,p6)；p8=makeleaf(id,b)；p9=makeleaf(id,c)；p10=makenode(-,p8,p9)；p11=makeleaf(id,d)；p12=makenode(*,p10,p11)；p13=makenode(+,p7,p12)；abc -*+d*+ p1 p2 p3 p4 p5 p6

33、p7 p8 p9 p10 p11 p12 p13第四十七頁，編輯于星期六：五點 十九分。47三、S-屬性定義的自底向上實現(xiàn)已知自底向上的分析方法中，分析程序使用一個棧來存放已經(jīng)分析過的子樹的信息。分析樹中某結(jié)點的綜合屬性由其子結(jié)點的屬性值計算得到自底向上的分析程序在分析輸入符號串的同時可以計算綜合屬性考慮如何保存文法符號的綜合屬性值？保存屬性值的數(shù)據(jù)結(jié)構(gòu)怎樣與分析棧相聯(lián)系？怎樣保證：每當(dāng)進行歸約時，由棧中正在歸約的產(chǎn)生式右部符號的屬性值計算其左部符號的綜合屬性值。第四十八頁，編輯于星期六：五點 十九分。48擴充分析棧目的：使之能夠保存綜合屬性做法：在分析棧中增加一個域，來存放綜合屬性值例：帶有

34、綜合屬性域的分析棧棧由一對數(shù)組state和val實現(xiàn)state元素是指向LR(1)分析表中狀態(tài)的指針（或索引）如果statei對應(yīng)的符號為A，vali中就存放分析樹中與結(jié)點A對應(yīng)的屬性值。假設(shè)綜合屬性剛好在每次歸約前計算AXYZ對應(yīng)的語義規(guī)則是A.a=(X.x, Y.y, Z.z) Z Z.z Y Y.y X X.x topstate val第四十九頁，編輯于星期六：五點 十九分。49修改分析程序?qū)τ诮K結(jié)符號其綜合屬性值由詞法分析程序產(chǎn)生當(dāng)分析程序執(zhí)行移進操作時，其屬性值隨終結(jié)符號（或狀態(tài)符號）一起入棧。為每個語義規(guī)則編寫一段代碼，以計算屬性值對每一個產(chǎn)生式AXYZ把屬性值的計算與歸約動作聯(lián)系

35、起來歸約前，執(zhí)行與產(chǎn)生式相關(guān)的代碼段歸約：右部符號及其屬性出棧 左部符號及其屬性入棧LR分析程序中應(yīng)增加計算屬性值的代碼段Z Z.zY Y.y X X.xtop . . . . . .state val A A.a第五十頁，編輯于星期六：五點 十九分。50例：用LR分析程序?qū)崿F(xiàn)表達式求值棧指針變量top和ntop的控制：當(dāng)用 A 歸約時，若|=r，在執(zhí)行相應(yīng)的代碼段之前， ntop=top-r+1。在每一個代碼段被執(zhí)行之后，top=ntop 產(chǎn)生式 LE EE1+T ET TT1*F TF F(E) Fdigit 語義規(guī)則 print(E.val) E.val=E1.val+T.val E.v

36、al=T.val T.val=T1.val*F.val T.val=F.val F.val=E.val F.val=digit.lexval 代碼段 print(valtop) valntop=valtop-2+valtop valntop=valtop-2*valtop valntop=valtop-1 第五十一頁，編輯于星期六：五點 十九分。51對 3*5+4 進行分析的動作序列 (見表4.8) 步驟 輸入 分析棧 分析動作 (1) 3*5+4$ state: 0 val: - 移進 5 (2) *5+4$ state: 0 5 val: - 3 歸約，用Fdigit goto0,F=3

37、(3) *5+4$ state: 0 3 val: - 3 歸約，用TF goto0,T=2 (4) *5+4$ state: 0 2 val: - 3 移進 7 (5) 5+4$ state: 0 2 7 val: - 3 - 移進 5 (6) +4$ state: 0 2 7 5 val: - 3 - 5 歸約，用Fdigit goto7,F=10 (7) +4$ state: 0 2 7 10 val: - 3 - 5 歸約，用TT*F goto0,T=2第五十二頁，編輯于星期六：五點 十九分。52步驟 輸入 分析棧 分析動作(8) +4$ state: 0 2 val: - 15 歸約

38、，用ET goto0,E=1(9) +4$ state: 0 1 val: - 15 移進 6(10) 4$ state: 0 1 6 val: - 15 - 移進 5(11) $ state: 0 1 6 5 val: - 15 - 4 歸約，用Fdigit goto6,F=3(12) $ state: 0 1 6 3 val: - 15 - 4 歸約，用TF goto6,T=9(13) $ state: 0 1 6 9 val: - 15 - 4 歸約，用EE+T goto0,E=1(14) $ state: 0 1 val: - 19 接受第五十三頁，編輯于星期六：五點 十九分。535.

39、3 L-屬性定義的自頂向下翻譯在自頂向下的分析過程中實現(xiàn)L屬性定義的翻譯預(yù)測分析方法對文法的要求不含左遞歸A FIRST()FIRST()=一、消除翻譯方案中的左遞歸二、預(yù)測翻譯程序的設(shè)計第五十四頁，編輯于星期六：五點 十九分。54一、消除翻譯方案中的左遞歸例：考慮對簡單表達式求值的語法制導(dǎo)定義 產(chǎn)生式 語義規(guī)則 LE print(E.val) EE1+T E.val=E1.val+T.val ET E.val=T.val TT1*F T.val=T1.val*F.val TF T.val=F.val F(E) F.val=E.val Fdigit F.val=digit.val 翻譯方案：(

40、1) LE print(E.val) (2) EE1+T E.val=E1.val+T.val (3) ET E.val=T.val (4) TT1*F T.val=T1.val*F.val (5) TF T.val=F.val (6) F(E) F.val=E.val (7) Fdigit F.val=digit.val 由(2)和(3)有：(2) ET E.val=T.val M(3) M+T E.val=E1.val+T.val M1(3) M繼承屬性M.i：表示在M之前已經(jīng)推導(dǎo)出的子表達式的值綜合屬性M.s：表示在M完全展開之后得到的表達式的值消除左遞歸的方法： AA|替換為：AR R

41、R|第五十五頁，編輯于星期六：五點 十九分。55M1 .i的語義規(guī)則為：M1.i=M.i+T.valM.s的語義規(guī)則為：M.s=M1.s于是得到：(3) M+T M1.i=M.i+T.val M1 M.s=M1.s同樣，通過引入非終結(jié)符號N， 可以得到(4)和(5)的變換結(jié)果 為(3)設(shè)置把M.i傳遞給M.s的語義動作，得到： (3) M M.s=M.i對于(2)， ET E.val=T.val M 通過M的屬性M.s和M.i完成E和T的綜合屬性的傳遞E.val=T.val，得到：(2) ET M.i=T.val M E.val=M.s對于(3) M+T E.val=E1.val+T.val

42、M1ET M. val. i. s. val. sET M. val. i. val+ T M. val. i. s第五十六頁，編輯于星期六：五點 十九分。56翻譯方案L E print(E.val)E T M.i=T.val M E.val=M.sM + T M1.i=M.i+T.val M1 M.s=M1.sM M.s=M.iTF N.i=F.val N T.val=N.sN * F N1.i=N.i*F.val N1 N.s=N1.sN N.s=N.iF( E ) F.val=E.valFdigit F.val=digit.lexval 表達式3*5+4的翻譯過程N digitFN *

43、F N digitFM + T MELTdigit.val=3.val=3.i=15.val=5.val=5.val=4.val=4.i=4.s=4.s=15.i=3.s=15.val=15.i=15.val=4.i=19.s=19.s=19.val=19第五十七頁，編輯于星期六：五點 十九分。57消除翻譯方案中左遞歸的一般方法翻譯方案：AA1Y A.a=g(A1.a,Y.y)AX A.a=f(X.x)為R設(shè)置繼承屬性R.i和綜合屬性R.sR.i：表示在R之前已經(jīng)掃描過的符號串的屬性值R.s：表示在R完全展開為終結(jié)符號之后得到的符號串的屬性值。消除基本文法中的左遞歸：AXRRYR|翻譯方案轉(zhuǎn)換

44、為：AX R.i=f(X.x) R A.a=R.sRY R1.i=g(R.i,Y,y) R1 R.s=R1.sR R.s=R.i AX R. x. i. s. aAX R. x. i. s. aY R. y. i. s第五十八頁，編輯于星期六：五點 十九分。58計算屬性的兩種方法A.a=g(g(f(X.x),Y1.y),Y2.y)A.a=g(f(X.x),Y1.y) Y2.yA.a=f(X.x) Y1.yX.xAX.x R.i=f(X.x)Y1.y R.i=g(f(X.x),Y1.yY2.y R .i=g(g(f(X.x),Y1.y),Y2.y)e R.sR.sR.s.a第五十九頁，編輯于星期

45、六：五點 十九分。59二、預(yù)測翻譯程序的設(shè)計從翻譯方案出發(fā)構(gòu)造自頂向下的語法制導(dǎo)翻譯程序算法5.2：構(gòu)造語法制導(dǎo)的預(yù)測翻譯程序輸入：基礎(chǔ)文法適合于預(yù)測分析的語法制導(dǎo)翻譯方案輸出：語法制導(dǎo)翻譯程序方法：（修改預(yù)測分析程序的構(gòu)造技術(shù)）(1) 為每個非終結(jié)符號A建立一個函數(shù)(可以是遞歸函數(shù))A的每一個繼承屬性對應(yīng)函數(shù)的一個形參A的綜合屬性作為函數(shù)的返回值A(chǔ)產(chǎn)生式中的每個文法符號的每個屬性都對應(yīng)一個局部變量(2) A的函數(shù)的代碼由多個分支組成第六十頁，編輯于星期六：五點 十九分。60按照從左到右的順序考慮產(chǎn)生式右部的記號、非終結(jié)符號和語義動作對帶有綜合屬性x的記號X把屬性x的值保存于為X.x聲明的變量

46、中產(chǎn)生一個匹配記號X的調(diào)用推進掃描指針對非終結(jié)符號B產(chǎn)生一個函數(shù)調(diào)用語句c=B(b1,b2,bk)bi(i=1,2,k)是對應(yīng)于B的繼承屬性的變量c是對應(yīng)于B的綜合屬性的變量對每一個語義動作把動作代碼復(fù)制到分析程序中用代表屬性的變量代替翻譯方案中引用的屬性(3) 與每個產(chǎn)生式相關(guān)的程序代碼第六十一頁，編輯于星期六：五點 十九分。61例：為簡單表達式求值的翻譯方案 構(gòu)造翻譯程序為每個非終結(jié)符號構(gòu)造一個函數(shù)void L(void)int E(void)int M(int in)int T(void)int N(int in)int F(void)第六十二頁，編輯于星期六：五點 十九分。62分別與E

47、TM、M+TM| 相應(yīng)的分析過程/M+TM|void proc_M(void) if (lookahead= +) match( + ); proc_T(); proc_M(); ;/ETMvoid proc_E(void) proc_T(); proc_M();第六十三頁，編輯于星期六：五點 十九分。63實現(xiàn)翻譯方案的函數(shù)int E(void) int eval, tval, mi, ms; tval=T(); mi=tval; ms=M(mi); eval=ms; return eval; E T M.i=T.val M E.val=M.s第六十四頁，編輯于星期六：五點 十九分。64實現(xiàn)翻

48、譯方案的函數(shù)int M(int in) int tval, i1, s1, s; char addoplexeme; if (lookahead= +) / 產(chǎn)生式M+TM addoplexeme=lexval; match( + ); tval=T(); i1=in+tval; s1=M(i1); s=s1; ; else s=in; / 產(chǎn)生式M return s M+ T M1.i=M.i+T.val M1 M.s=M1.s M M.s=M.i 第六十五頁，編輯于星期六：五點 十九分。655.4 L屬性定義的自底向上翻譯在自底向上的分析過程中實現(xiàn)L屬性定義的翻譯可以實現(xiàn)任何基于LL(1)

49、文法的L屬性定義可以實現(xiàn)許多（不是全部）基于LR(1)文法的L屬性定義一、從翻譯方案中去掉嵌入的動作二、分析棧中的繼承屬性三、模擬繼承屬性的計算四、用綜合屬性代替繼承屬性第六十六頁，編輯于星期六：五點 十九分。66一、從翻譯方案中去掉嵌入的動作自底向上地處理繼承屬性等價變換：使所有嵌入的動作都出現(xiàn)在產(chǎn)生式的右端末尾方法：在基礎(chǔ)文法中引入新的產(chǎn)生式，形如：MM：標記非終結(jié)符號，用來代替嵌入在產(chǎn)生式中的動作把被M替代的動作放在產(chǎn)生式M的末尾第六十七頁，編輯于星期六：五點 十九分。67例：去掉如下翻譯方案中嵌入的動作： ETR R+T print(+) R |-T print(-) R | Tnum

50、 print(num.val)標記非終結(jié)符號M和N，及產(chǎn)生式 M 和 N用M和N替換出現(xiàn)在R產(chǎn)生式中的動作新的翻譯方案ETRR+TMR | -TNR | Tnum print(num.val)M print(+)N print(-)第六十八頁，編輯于星期六：五點 十九分。68變換前、后的翻譯方案是等價的num print(num.val) - T print(-) R 4num print(num.val) 5num print(num.val) + T print(+) R 3ET R深度優(yōu)先的順序進行遍歷print(num1.val) print(num2.val) print(+) pr

51、int(num3.val) print(-)動作執(zhí)行的結(jié)果是：34+5-變換前，表達式3+4-5的分析樹：第六十九頁，編輯于星期六：五點 十九分。69變換后，表達式3+4-5的分析樹：深度優(yōu)先的順序進行遍歷print(num1.val) print(num2.val) print(+) print(num3.val) print(-)動作執(zhí)行的結(jié)果是：34+5-Num print(num.val) print(+) - T N R 4Num print(num.val) print(-) 5Num print(num.val) + T M R 3ET R第七十頁，編輯于星期六：五點 十九分。7

52、0二、分析棧中的繼承屬性LR分析程序?qū)Ξa(chǎn)生式AXY的歸約topYX考慮分析過程中屬性的計算XX1X2XnYY1Y2YkY.i=X.stopAstate valX1 X1.xX2 X2.xXn Xn.xY Y .y X X .sY1 Y1.yY2 Y2.y Yk Yk.y第七十一頁，編輯于星期六：五點 十九分。71復(fù)制規(guī)則的重要作用翻譯方案：DT L.in=T.type LTint T.type=integerTreal T.type=realL L1.in=L.in L1,id addtype(id.entry,L.in)Lid addtype(id.entry,L.in)DT Lreal L

53、 , rL , qp. type. in. in. in. s. entry. s. entry. s. entry輸入符號串：real p,q,r第七十二頁，編輯于星期六：五點 十九分。72例：應(yīng)用繼承屬性，用復(fù)制規(guī)則傳遞標識符的類型 輸入 棧 分析動作real p,q,r$ state: val: 移進 p,q,r$ state: real val: real 歸約，用Treal p,q,r$ state: T val: real 移進 ,q,r$ state: T p val: real pentry 歸約，用Lid ,q,r$ state: T L val: real - 移進 q,r

54、$ state: T L , val: real - , 移進 ,r$ state: T L , q val: real - , qentry 歸約，用LL,id ,r$ state: T L val: real - 移進 r$ state: T L , val: real - , 移進 $ state: T L , r val: real - , rentry 歸約，用LL,id $ state: T L val: real - 歸約，用DTL $ state: D val: - 接受第七十三頁，編輯于星期六：五點 十九分。73計算屬性值的代碼段top和ntop分別是歸約前和歸約后的棧頂指針

55、當(dāng)用產(chǎn)生式Lid歸約時，L.in 的位置？當(dāng)用產(chǎn)生式LL,id進行歸約時，L.in 的位置？和L.in有關(guān)的動作 ？ 產(chǎn)生式 代碼段 DTL Tint valntop=integer Treal valntop=real LL,id addtype(valtop,valtop-3) Lid addtype(valtop,valtop-1) 第七十四頁，編輯于星期六：五點 十九分。74三、模擬繼承屬性的計算要想從棧中取得繼承屬性，當(dāng)且僅當(dāng)文法允許屬性值在棧中存放的位置可以預(yù)測。例：屬性值在棧中的位置不可預(yù)測的語法制導(dǎo)定義當(dāng)用Zz進行歸約時，Z.i可能在valtop-1處也可能在valtop-2處產(chǎn)生式語義規(guī)則(1)AaXZZ.i=X.s(2)AbXYZZ.i=X.s(3)XxX.s=5(4)YyY.s=7(5)ZzZ.s=g(Z.i)第七十五頁，編輯于星期六：五點 十九分。75模擬繼承屬性的計算引入標記非終結(jié)符號，對原語法制導(dǎo)定義進行等價變換Ab X .s Y .i M .s .i Z產(chǎn)生式語義規(guī)則(1)A