屬性文法和語法制導(dǎo)翻譯

第六章屬性文法和語法制導(dǎo)翻譯6.1屬性文法6.2語法制導(dǎo)翻譯6.3S-屬性文法的自下而上計(jì)算6.4L-屬性文法和自頂向下翻譯6.5自下而上計(jì)算繼承屬性第六章屬性文法和語法制導(dǎo)翻譯16.1屬性文法文法的屬性定義：是在上下文無關(guān)文法的基礎(chǔ)上為每個文法符號（終結(jié)符或非終結(jié)符）配備的若干個相關(guān)的“值”（稱為屬性）。內(nèi)容：屬性代表與文法符號相關(guān)的信息，描述了處理對象的特征，即語義。例如，一個變量的屬性有類型，層次，存儲地址等。表達(dá)式的屬性有類型，值等。屬性和變量一樣，可以進(jìn)行計(jì)算和傳遞。6.1屬性文法文法的屬性2屬性文法定義： 屬性文法是在上下文無關(guān)文法的基礎(chǔ)上，為每個終結(jié)符和非終結(jié)符配備一些屬性及其計(jì)算規(guī)則的文法。屬性的形式與變量X相關(guān)聯(lián)的屬性記為X.type、X.place和X.val等，屬性計(jì)算規(guī)則的形式根據(jù)產(chǎn)生式所包含的含義，給出每個文法符號屬性的求值規(guī)則（即語義規(guī)則）。它既能描述程序設(shè)計(jì)語言的語法,又為其語義描述提供了手段。語義規(guī)則它是為文法的每個產(chǎn)生式配備的一組屬性的計(jì)算規(guī)則，它是屬性加工的過程即語義處理的過程。它建立了屬性之間的依賴關(guān)系語義規(guī)則所描述的工作可以包括屬性計(jì)算、靜態(tài)語義檢查、符號表操作、代碼生成等。屬性文法3語義規(guī)則（屬性計(jì)算規(guī)則）的特點(diǎn)封裝：一條產(chǎn)生式對應(yīng)的語義規(guī)則中只能使用相應(yīng)產(chǎn)生式的文法符號的屬性，這有利于產(chǎn)生式范圍內(nèi)“封裝”屬性的依賴性。一個產(chǎn)生式右邊符號的繼承屬性和其左邊符號的綜合屬性都必須提供一個計(jì)算規(guī)則。產(chǎn)生式左邊符號的繼承屬性和產(chǎn)生式右邊符號的綜合屬性不能由此產(chǎn)生式對應(yīng)的屬性計(jì)算規(guī)則進(jìn)行計(jì)算。語義規(guī)則（屬性計(jì)算規(guī)則）的特點(diǎn)4在一個屬性文法中，對應(yīng)于每個產(chǎn)生式A都有一套與之相關(guān)聯(lián)的語義規(guī)則，每條語義規(guī)則的形式為：b:=f(c1,c2,…,ck)

這里f是一個函數(shù)，b,c1,c2,…ck是產(chǎn)生式文法符號的屬性；我們稱屬性b依賴于屬性c1,c2,…ck。由于屬性依賴性需封裝，此語義規(guī)則中b,ci滿足下面條件：

（1）b是A的一個綜合屬性并且c1,c2,…ck是產(chǎn)生式右邊文法符號的屬性；或（2）b是產(chǎn)生式右邊某個文法符號的一個繼承屬性并且c1,c2,…ck是A或產(chǎn)生式右邊任何文法符號的屬性。語義規(guī)則中屬性的依賴在一個屬性文法中，對應(yīng)于每個產(chǎn)生式A都有一套與之相關(guān)聯(lián)的5

綜合屬性(synthesizedattribute)在分析樹中，一個結(jié)點(diǎn)的綜合屬性值是從其子結(jié)點(diǎn)的屬性值計(jì)算出來的。在產(chǎn)生式中，一個文法符號的綜合屬性是由其右部結(jié)點(diǎn)的屬性值計(jì)算出來的。綜合屬性用于“自下而上”傳遞信息繼承屬性(inheritedattribute)一個結(jié)點(diǎn)的繼承屬性值是由該結(jié)點(diǎn)兄弟結(jié)點(diǎn)和父結(jié)點(diǎn)的屬性值計(jì)算出來的。在產(chǎn)生式中，一個文法符號的繼承屬性是由其左部符號或其它右部符號的屬性值計(jì)算出來的。繼承屬性用于“自上而下”傳遞信息屬性的分類綜合屬性(synthesizedattribu6文法符號具有的屬性：(1)終結(jié)符則只能有綜合屬性，而不能有繼承屬性。(2)非終結(jié)符既可有綜合屬性也可有繼承屬性。(3)開始符號沒有繼承屬性，在開始時(shí)要確定；虛綜合屬性（dummysynthesizedattribute）：語義規(guī)則可能產(chǎn)生副作用（如產(chǎn)生代碼），也可能不是變元的嚴(yán)格函數(shù)（如某個規(guī)則給出可用的下一個數(shù)據(jù)單元的地址）。這樣的語義規(guī)則通常寫成過程調(diào)用，或過程段。這個過程段被認(rèn)為是此產(chǎn)生式左部文法符號的的虛屬性。文法符號具有的屬性：(1)終結(jié)符則只能有綜合屬性，而不能有繼7S-屬性文法：僅僅使用綜合屬性的屬性文法。綜合屬性的計(jì)算：使用自底向上的方法在每一個結(jié)點(diǎn)處使用語義規(guī)則計(jì)算綜合屬性的值。綜合屬性的計(jì)算S-屬性文法：僅僅使用綜合屬性的屬性文法。綜合屬性的計(jì)算8綜合屬性的計(jì)算產(chǎn)生式語義規(guī)則L→EnPrint(E.val)E→E1+TE.val:=E1.val+T.valE→TE.val:=T.valT→T1*FT.val:=T1.val*F.valT→FT.val:=F.valF→(E)F.val:=E.valF→digitF.val:=digit.lexval表6.1一個簡單臺式計(jì)算器的S-屬性文法綜合屬性的計(jì)算產(chǎn)生式語義規(guī)則L→EnPrint(E.v9P137[例6.1]用上圖的屬性文法計(jì)算3*5＋4n，n為一個換行符。見圖6.1。3*5＋4n的帶注釋的語法樹LnE.val=15+*E.val=19F.val=5T.val=3T.val=15F.val=4T.val=4F.val=3digit.lexval=4digit.lexval=5digit.lexval=3從詞法分析器中得到值從詞法分析器中得到值從詞法分析器中得到值Print19P1373*5＋4n的帶注釋的語法樹LnE.val=15+*10在語法樹中，一個結(jié)點(diǎn)的繼承屬性由此結(jié)點(diǎn)的父結(jié)點(diǎn)和/或兄弟結(jié)點(diǎn)的某些屬性確定。用繼承屬性可用來表示程序語言結(jié)構(gòu)中的上下文依賴關(guān)系。[例6.2](P138)繼承屬性在說明中為各種標(biāo)識符提供類型信息。產(chǎn)生式語義規(guī)則D→TLL.in:=T.typeT→intT.type:=integerT→realT.type:=realL→L1,idL1.in:=L.inAddtype(id.entry,L.in）L→idAddtype(id.entry,L.in）把說明中的類型賦值給繼承屬性L.in把標(biāo)識符的類型填入符號表相應(yīng)項(xiàng)繼承屬性的計(jì)算在語法樹中，一個結(jié)點(diǎn)的繼承屬性由此結(jié)點(diǎn)的父結(jié)點(diǎn)和/或兄弟結(jié)點(diǎn)11句子realid1,id2,id3的分析P139圖6.2DL.in=realL.in=realL.in=realT.type=realrealid1id3id2,,addtypeaddtypeaddtype①②③④在每個L結(jié)點(diǎn)都帶有繼承屬性的語法樹句子realid1,id2,id3的分析DL.in=rea12翻譯的任務(wù)語義分析和正確性檢查，若正確，則翻譯成中間代碼或目標(biāo)代碼。使用的方法:語法制導(dǎo)翻譯。因?yàn)槭潜辉闯绦虻恼Z法結(jié)構(gòu)所驅(qū)動的處理辦法所以稱語法制導(dǎo)翻譯法。語法制導(dǎo)翻譯也就是在屬性文法的基礎(chǔ)上，按一定的順序執(zhí)行語義規(guī)則，得出計(jì)算結(jié)果。語義規(guī)則的計(jì)算可能產(chǎn)生代碼、在符號表中存放信息、給出錯誤信息或執(zhí)行任何其它動作6.2語法制導(dǎo)翻譯翻譯的任務(wù)6.2語法制導(dǎo)翻譯13語法制導(dǎo)翻譯的處理過程：對單詞符號串進(jìn)行語法分析，構(gòu)造語法分析樹，然后根據(jù)需要遍歷語法樹并在語法樹的各結(jié)點(diǎn)處按語義規(guī)則進(jìn)行計(jì)算。也可以一遍掃描實(shí)現(xiàn)屬性文法的語義規(guī)則計(jì)算，即在語法分析的同時(shí)完成語義規(guī)則的計(jì)算。輸入串語法樹依賴圖語義規(guī)則計(jì)算次序語法制導(dǎo)翻譯的處理過程：對單詞符號串進(jìn)行語法分析，構(gòu)造語法分14定義：如果在一棵語法樹中一個結(jié)點(diǎn)的屬性b依賴于屬性c，那么這個結(jié)點(diǎn)處計(jì)算b的屬性計(jì)算規(guī)則必須在確定c的語義規(guī)則之后使用。在一顆語法樹中描述這種結(jié)點(diǎn)的繼承屬性和綜合屬性之間的相互依賴關(guān)系的有向圖稱作依賴圖。構(gòu)造依賴圖的預(yù)處理：在為一棵語法樹構(gòu)造依賴圖以前，我們?yōu)槊恳粋€包含過程調(diào)用的語義規(guī)則引入一個虛綜合屬性b，這樣每一個語義規(guī)則都可統(tǒng)一寫成b:=f(c1,c2,…ck)的形式為畫依賴圖做好準(zhǔn)備。6.2.1用依賴圖的屬性計(jì)算方法定義：6.2.1用依賴圖的屬性計(jì)算方法15在語法樹中，為每一個屬性設(shè)置一個結(jié)點(diǎn)，如果屬性b依賴屬性c，則從屬性c的結(jié)點(diǎn)畫一條有向邊連到屬性b的結(jié)點(diǎn)。例產(chǎn)生式AXY對應(yīng)的1.語義規(guī)則A.a:=f(X.x,Y.y)這條語義規(guī)則確定了依賴于屬性X.x和Y.y的綜合屬性A.a。

①依賴圖中會有三個結(jié)點(diǎn)A.a,X.x,和Y.y。

②X.x到A.a，Y.y到A.a各有一條有向邊，表示依賴關(guān)系。2.若還有另一語義規(guī)則：X.i:=g(A.a,Y.y)那么，又有兩條有向邊，從A.a連到X.i，從Y.y連到X.i。AYXA.aX.xY.yX.i依賴圖的構(gòu)造在語法樹中，為每一個屬性設(shè)置一個結(jié)點(diǎn)，如果屬性b依賴屬性16依賴圖的構(gòu)造算法

for語法樹中每一結(jié)點(diǎn)ndofor結(jié)點(diǎn)n的文法符號的每一個屬性ado為a在依賴圖中建立一個結(jié)點(diǎn)；for語法樹中每一個結(jié)點(diǎn)ndofor結(jié)點(diǎn)n所用產(chǎn)生式對應(yīng)的每一條語義規(guī)則b:＝f（c1，c2，…，ck)dofori:=1tokdo從結(jié)點(diǎn)ci到結(jié)點(diǎn)b構(gòu)造一條有向邊；依賴圖的構(gòu)造算法for語法樹中每一結(jié)點(diǎn)n17[例6.3]當(dāng)下面的產(chǎn)生式應(yīng)用于語法樹時(shí)，把有向邊加到依賴圖中。產(chǎn)生式語義規(guī)則EE1+E2E.val:=E1.val+E2.val[例6.3]當(dāng)下面的產(chǎn)生式應(yīng)用于語法樹時(shí)，把有向邊加到依賴圖18[例6.4]：畫出例6.2的帶注釋語法樹的依賴圖。依賴圖中的結(jié)點(diǎn)由數(shù)字來標(biāo)識。6,8,10是對應(yīng)addtype(id.entry,L.in)產(chǎn)生的虛屬性，[例6.4]：畫出例6.2的帶注釋語法樹的依賴圖。依賴圖中的19良定義文法如果一屬性文法不存在屬性之間的循環(huán)依賴關(guān)系，那么該文法為良定義的。為了設(shè)計(jì)編譯程序，我們只處理良定義的屬性文法。拓?fù)渑判蛞粋€有向非循環(huán)圖的拓?fù)湫蚴菆D中結(jié)點(diǎn)的序列m1,m2,…mk,圖中的邊必須是從序列中前面的結(jié)點(diǎn)指向后面的結(jié)點(diǎn)。也就是說，如果mimj是mi到mj的一條邊，那么在序列中mi必須出現(xiàn)在mj之前。屬性的計(jì)算次序一個依賴圖的任何拓?fù)渑判蚨冀o出一個語法樹中結(jié)點(diǎn)的語義規(guī)則計(jì)算的有效順序。這就是說，在拓?fù)渑判蛑?，在一個結(jié)點(diǎn)上，語義規(guī)則b:=f（c1,c2,…ck)中的屬性c1,c2…ck在計(jì)算b以前都是可用的。屬性的計(jì)算順序良定義文法屬性的計(jì)算順序20[例6.5]：前6.4的依賴圖中，拓?fù)渑判蚩蓮牡托蛱柕礁咝蛱栱樞驅(qū)懗?。an代表結(jié)點(diǎn)n的屬性計(jì)算順序?yàn)椋篴4:=reala5:=a4addtype(id3.entry,a5);a7:=a5addtype(id2.entry,a7);a9:=a7addtype(id1.entry,a9);拓?fù)湫虿晃ㄒ籟例6.5]：前6.4的依賴圖中，拓?fù)渑判蚩蓮牡托蛱柕礁咝?16.2.2樹遍歷的屬性計(jì)算方法前提是假設(shè)語法樹已經(jīng)建立起了，并且樹中已帶有開始符號的繼承屬性和終結(jié)符的綜合屬性。然后以某種次序遍歷語法樹，如果需要，可遍歷多次。直至計(jì)算出所有的屬性。通過樹遍歷計(jì)算屬性值的方法有多種。最常用的遍歷方法是深度優(yōu)先，從左到右的遍歷方法。6.2.2樹遍歷的屬性計(jì)算方法前提是假設(shè)語法樹已經(jīng)建立起了22[例6.6]表6.3的屬性文法中的屬性計(jì)算S繼承屬性a,初始值為0.產(chǎn)生式語義規(guī)則S→XYZZ.h:=S.aX.c:=Z.gS.b:=X.d-2

Y.e:=S.bX→xY→yZ→zX.d:=2*X.cY.f:=Y.e*3Z.g:=Z.h+1繼承屬性綜合屬性[例6.6]表6.3的屬性文法中的屬性計(jì)算產(chǎn)生式語義規(guī)則23S:a=0XYZxyz(a)S:a=0X:c=1d=2YZ:h=0g=1xyz(c)S:a=0XYZ:h=0g=1xyz(b)S:a=0,b=0X:c=1d=2Y:e=0f=0Z:h=0g=1xyz(d)(a)初始狀態(tài)(b)一次遍歷后的狀態(tài)(c)二次遍歷后的狀態(tài)(d)三次遍歷后的狀態(tài)產(chǎn)生式語義規(guī)則S→XYZZ.h:=S.aX.c:=Z.gS.b:=X.d-2

Y.e:=S.bX→xY→yZ→zX.d:=2*X.cY.f:=Y.e*3Z.g:=Z.h+1S:a=0XYZxyz(a)S:a=0X:c=1YZ:h24樹遍歷的屬性計(jì)算實(shí)現(xiàn)算法：P142樹遍歷的屬性計(jì)算實(shí)現(xiàn)算法：256.2.3一遍掃描的處理方法樹遍歷的屬性計(jì)算方法是在語法分析構(gòu)造語法樹之后進(jìn)行屬性的計(jì)算，而一遍掃描的方法要在語法分析的同時(shí)計(jì)算屬性值。如果按這種一遍掃描的編譯程序模型來理解語法制導(dǎo)翻譯方法的話，所謂語法制導(dǎo)翻譯法，直觀上說是為文法中每個產(chǎn)生式配上一組語義規(guī)則，并且在語法分析的同時(shí)執(zhí)行這些語義規(guī)則。在自上而下的語義分析中,若一個產(chǎn)生式匹配輸入串成功,或者在自下而上分析中,當(dāng)一個產(chǎn)生式被用于進(jìn)行歸約時(shí),此產(chǎn)生式相應(yīng)的語義規(guī)則就被計(jì)算,完成有關(guān)語義分析和代碼生成的工作。6.2.3一遍掃描的處理方法樹遍歷的屬性計(jì)算方法是在語法分析26一遍掃描的特點(diǎn)：優(yōu)點(diǎn)：無需構(gòu)造語法樹缺點(diǎn)：有條件限制。

因?yàn)橐槐閽呙璧奶幚矸椒ㄅc語法分析器的相互作用，它與兩個因素密切相關(guān)：所采用的語法分析方法屬性的計(jì)算次序一遍掃描的特點(diǎn)：27從語法分析樹中去掉那些對翻譯不必要的信息，獲得的源程序中間表示，這種經(jīng)變換后的語法樹稱之為抽象語法樹。例：產(chǎn)生式S→ifBthenS1elseS2；表達(dá)式3*5+4的抽象語法樹if_then_elseBS1S2+534*6.2.4抽象語法樹特點(diǎn)：是結(jié)構(gòu)緊湊，容易構(gòu)造且結(jié)點(diǎn)數(shù)較少。從語法分析樹中去掉那些對翻譯不必要的信息，獲得的源程序中間表28抽象語法樹的建立：建立表達(dá)式的抽象語法樹,操作符和關(guān)鍵字都不作為葉子結(jié)點(diǎn)出現(xiàn)，而是作為內(nèi)部結(jié)點(diǎn)。計(jì)算機(jī)表示中，抽象語法樹中的每一個結(jié)點(diǎn)可以由包含幾個域的記錄來實(shí)現(xiàn)。在一個運(yùn)算符號對應(yīng)的結(jié)點(diǎn)中,一個域標(biāo)識運(yùn)算符號，其它域包含指向運(yùn)算分量的結(jié)點(diǎn)的指針。運(yùn)算符號通常叫做這個結(jié)點(diǎn)的標(biāo)號。進(jìn)行翻譯時(shí)，抽象語法樹中的結(jié)點(diǎn)可以用附加域來存放結(jié)點(diǎn)的屬性值(或指向?qū)傩缘闹羔槪?。抽象語法樹的建立：29P145[例6.7]a-4+c的抽象語法樹計(jì)算機(jī)表示，見P146圖6.7idtoentryanum4–idtoentryc+P145[例6.7]a-4+c的抽象語法樹計(jì)算機(jī)表示，idt30用語義規(guī)則為表達(dá)式建立抽象語法樹：屬性文法（表6.4）

產(chǎn)生式語義規(guī)則E

E1+TE.nptr:=mknode('+',E1.nptr,T.nptr)E

E1-TE.nptr:=mknode('-',E1.nptr,T.nptr)E

TE.nptr:=T.nptrT

(E)T.nptr:=E.nptrT

idT.nptr:=mkleaf(id,id.entry)T

numT.nptr:=mkleaf(num,num.val)用語義規(guī)則為表達(dá)式建立抽象語法樹：產(chǎn)生式31根據(jù)屬性文法構(gòu)造表達(dá)式的抽象語法樹。根據(jù)屬性文法構(gòu)造表達(dá)式的抽象語法樹。326.3S-屬性文法的自下而上計(jì)算S-屬性文法：只含有綜合屬性的文法。綜合屬性可以在分析輸入符號串的同時(shí)由自下而上的分析器來計(jì)算，所以S-屬性文法的屬性計(jì)算可以用自下而上的語法分析一遍實(shí)現(xiàn)。自下而上分析時(shí)處理語義規(guī)則方法是：每當(dāng)進(jìn)行歸約時(shí)，利用語義規(guī)則計(jì)算新的屬性值。6.3S-屬性文法的自下而上計(jì)算S-屬性文法：只含有綜合屬33分析棧中的綜合屬性自底向上分析時(shí)，使用分析棧，為了同時(shí)對屬性值進(jìn)行計(jì)算，在分析棧中增加了屬性項(xiàng)。即棧內(nèi)有state和val兩個部分。當(dāng)?shù)趇個state對應(yīng)的符號為A時(shí)，val[i]中就存放語法樹中與結(jié)點(diǎn)A對應(yīng)的綜合屬性值。棧的使用例一條產(chǎn)生式及其相應(yīng)語義規(guī)則的歸約及計(jì)算：產(chǎn)生式AXYZ對應(yīng)語義規(guī)則A.a:=f(X.x,Y.y,Z.z)棧的變化過程：分析棧中的綜合屬性自底向上分析時(shí)，使用分析棧，為了同時(shí)對屬性34statevalZZ.ZYY.YXX.X……top前提設(shè)當(dāng)棧頂由指針top指示。假設(shè)綜合屬性是剛好在每次歸約前計(jì)算的。假設(shè)語義規(guī)則A.a:=f(X.x,Y.y,Z.z)是對應(yīng)于產(chǎn)生式AXYZ的。歸約前屬性Z.z的值放在val[top]中，Y.y的值放在val[top-1]中，X.x的值放在val[top-2]中。如果一個符號沒有綜合屬性，那么數(shù)組val中相應(yīng)的元素就不定義。歸約后top值減2，A的狀態(tài)存放在state[top]中（也就是X的位置）,綜合屬性A.a的值存放在相應(yīng)的val[top]中。AXYZAa:=f(Xx,Yy,Zz)statevalAA.a……topstatevalZZ.ZYY.YXX.X……top前提AX35[例6.9]臺式計(jì)算器結(jié)合棧后改寫的屬性文法產(chǎn)生式語義規(guī)則L→EnPrint(val[top])E→E1+Tval[ntop]:=val[top-2]+val[top]E→TT→T1*Fval[ntop]:=val[top-2]*val[top]T→FF→(E)val[ntop]:=val[top-1]F→digit此文法輸入符號串3*5+4n，自底向上分析分析過程：[例6.9]臺式計(jì)算器結(jié)合棧后改寫的屬性文法產(chǎn)生式語義規(guī)則36輸入stateval使用的產(chǎn)生式3*5+4n--*5+4n33*5+4nF3Fdigit

*5+4nT3TF

5+4nT*3-+4nT*53-5+4nT*F3-5Fdigit

+4nT15T

T*F+4nE15E

T4nE+15-nE+415-4nE+F15-4F

digitnE+T15-4T

FnE19E

E+TEn19-L19L

Enval[ntop]:=val[top-2]*val[top]val[ntop]:=val[top-2]＋val[top]Print(val[top])相應(yīng)的語義規(guī)則輸入stateval37S-屬性文法的一遍翻譯的實(shí)現(xiàn)采用自底向上分析，例如LR分析，首先給出文法的S-屬性定義，然后，把S-屬性定義變成可執(zhí)行的代碼段，這就構(gòu)成了翻譯程序。S-屬性文法的一遍翻譯的實(shí)現(xiàn)采用自底向上分析，例如LR分析，386.4L-屬性文法及其自頂向下翻譯L-屬性文法：一個屬性文法，如果對于每個產(chǎn)生式AX1X2…Xn其每個語義規(guī)則中的每個屬性或者是綜合屬性，或者是Xj(1<=j<=n)的一個繼承屬性且這個繼承屬性僅依賴于：（1）產(chǎn)生式Xj的左邊符號X1,X2,…Xj-1的屬性（2）A的繼承屬性。則稱為L-屬性文法。？

S-屬性文法是L-屬性文法？是判斷：(P137表6.1)與(P139表6.2)及(P150表6.7)是否L-屬性文法?6.4L-屬性文法及其自頂向下翻譯L-屬性文法：？S-屬396.4.1翻譯模式屬性文法可以看成是關(guān)于語言翻譯的高級規(guī)范說明，其中隱去實(shí)現(xiàn)細(xì)節(jié)，用戶未明確說明翻譯順序。翻譯模式是一種語法分析和語義動作交錯的表示法，它表達(dá)在按深度優(yōu)先遍歷分析樹的過程中何時(shí)執(zhí)行語義動作。在翻譯模式中，和文法符號相關(guān)的屬性和語義規(guī)則（這里也稱語義動作），用花括號{}括起來，插入到產(chǎn)生式右部的合適位置上。有了計(jì)算次序就可以把某些實(shí)現(xiàn)細(xì)節(jié)表示出來。6.4.1翻譯模式屬性文法可以看成是關(guān)于語言翻譯的高級規(guī)范40例：把帶加號和減號的中綴表達(dá)式翻譯成相應(yīng)的后綴表達(dá)式。翻譯模式為：E→TRR→addopT{print(addop.lexeme)}R1|εT→num{print(num.val)}其對應(yīng)的關(guān)于輸入串9-5+2的翻譯的語法分析樹(P150)例：把帶加號和減號的中綴表達(dá)式翻譯成相應(yīng)的后綴表達(dá)式。41原則：要保證當(dāng)某個動作引用一個屬性時(shí)必須是有定義的。即要求是L-屬性文法。兩種情況下的設(shè)計(jì)：1.只有綜合屬性2.既有綜合屬性又有繼承屬性翻譯模式的設(shè)計(jì)原則：翻譯模式的設(shè)計(jì)421.只有綜合屬性：為每一個語義規(guī)則建立一個包含賦值的動作，并把這個動作放在相應(yīng)的產(chǎn)生式右邊的末尾。例：產(chǎn)生式T→T1*F，對應(yīng)語義規(guī)則T.val:=T1.val×F.val翻譯模式為：T→T1*F{T.val:=T1.val×F.val}1.只有綜合屬性：43S-屬性方法：

產(chǎn)生式語義規(guī)則E→E1+TE.val:=E1.val+T.valE→E1-TE.val:=E1.val-T.valE→T E.val:=T.valT→(E)T.val:=E.valT→numT.val:=num.val對應(yīng)的翻譯模式：E→E1+T{E.val:=E1.val+T.val}E→E1-T{E.val:=E1.val-T.val}E→T{E.val:=T.val}T→(E){T.val:=E.val}T→num{T.val:=num.val}S-屬性方法：對應(yīng)的翻譯模式：442.既有綜合屬性又有繼承屬性這時(shí)要滿足3點(diǎn)要求：（1）產(chǎn)生式右邊的符號的繼承屬性必須在這個符號以前的動作中計(jì)算出來。（2）一個動作不能引用這個動作右邊符號的綜合屬性。（3）產(chǎn)生式左邊非終結(jié)符的綜合屬性只有在它所引用的所有屬性都計(jì)算出來后才能計(jì)算。計(jì)算這種屬性的動作通?？煞旁诋a(chǎn)生式右端的末尾?？偨Y(jié)：每個動作引用一個屬性時(shí)必須是有定義的。？為什么應(yīng)按照此原則設(shè)計(jì)？因?yàn)檫@樣設(shè)計(jì)的翻譯模式，能夠在深度優(yōu)先遍歷時(shí)一次遍歷計(jì)算出全部屬性。從而能夠?qū)崿F(xiàn)語法語義一遍掃描。2.既有綜合屬性又有繼承屬性？為什么應(yīng)按照此原則設(shè)計(jì)？因?yàn)檫@45判斷下面翻譯模式是否滿足要求？S→A1A2{A1.in=1;A2.in=2}A→a{print(A.in)}改寫后：S→{A1.in=1}A1{A2.in=2}A2

S→{A1.in=1；A2.in=2}A1A2

如何改寫？翻譯模式進(jìn)行寫法規(guī)范：將文法符號寫在單獨(dú)的一行，相應(yīng)的動作寫在其右邊。S→{A1.in=1}

A1{A2.in=2}

A2

判斷下面翻譯模式是否滿足要求？改寫后：如何改寫？翻譯模式進(jìn)行46[例6.10]（P151）給定一個L-屬性文法，建立一個滿足設(shè)計(jì)原則的翻譯模式。產(chǎn)生式語義規(guī)則S→B

B.ps:=10S.ht:=B.htB→B1B2

B1.ps:=B.ps

B2.ps:=B.psB.ht:=max(B1.ht,B2.ht)B→B1subB2

B1.ps:=B.ps

B2.ps:=shrink(B.ps)B.ht:=disp(B1.ht,B2.ht)B→textB.ht:=text.h×B.ps高度的影響系數(shù)縮小30％高度B2向下放并算總高B的實(shí)際高度[例6.10]（P151）給定一個L-屬性文法，建立一個滿47設(shè)計(jì)的翻譯模式：S→{B.ps:=10}B{S.ht:=B.ht}B→{B1.ps:=B.ps}B1{B2.ps:=B.ps}

B2{B.ht:=max(B1.ht,B2.ht)}B→{B1.ps:=B.ps}B1sub{B2.ps:=shrink(B.ps)}B2{B.ht:=disp(B1.ht,B2.ht)}B→text{B.ht:=text.h×B.ps}S→BB.ps:=10S.ht:=B.htB→B1B2B1.ps:=B.psB2.ps:=B.psB.ht:=max(B1.ht,B2.ht)B→B1subB2B1.ps:=B.psB2.ps:=shrink(B.ps)B.ht:=disp(B1.ht,B2.ht)B→textB.ht:=text.h×B.ps設(shè)計(jì)的翻譯模式：S→BB.ps:=10S.ht:=B.h486.4.2L-屬性文法的自頂向下翻譯前提已構(gòu)造L-屬性文法的翻譯模式。目的與自頂向下語法分析一遍實(shí)現(xiàn)自頂向下翻譯。6.4.2L-屬性文法的自頂向下翻譯前提49翻譯模式中左遞歸的消除前提為了構(gòu)造不帶回溯的自頂向下語法分析，必須消除文法中的左遞歸，同樣翻譯模式中的左遞歸也需要消除。方法把前面消除左遞歸的文法加以擴(kuò)充,當(dāng)消除此翻譯模式的基本語法的左遞歸時(shí)同時(shí)考慮屬性。這樣使得許多不適于采用自頂向下翻譯的文法可采用自頂向下分析一遍來實(shí)現(xiàn)。翻譯模式中左遞歸的消除前提50左遞歸翻譯模式轉(zhuǎn)換的一般方法：翻譯模式的一般形式：AA1Y{A.a:=g(A1.a,Y.y)}AX{A.a:=f(X.x)}其每個文法符號都有一個綜合屬性，用小寫字母表示，g和f是任意函數(shù)。利用消除左遞歸的算法，其文法可轉(zhuǎn)換如下： AXRRYR|ε左遞歸翻譯模式轉(zhuǎn)換的一般方法：翻譯模式的一般形式：51同時(shí)考慮語義動作，翻譯模式變?yōu)椋?/p>

A→X{R.i:=f(X.x)}R{A.a:=R.s}R→Y{R1.i:=g((R.i),Y.y)}R1{R.s:=R1.s}R→ε{R.s:=R.i}

經(jīng)過轉(zhuǎn)換的翻譯模式，使用了R的繼承屬性i和綜合屬性s。同時(shí)考慮語義動作，翻譯模式變?yōu)椋?2消除左遞歸前后翻譯模式中屬性值傳遞和計(jì)算：（P155圖6.16）A.a=g(g(f(X.x),Y1.y),Y2.y)A.a=f(X.x)A.a=g(f(X.x),Y1.y)Y1Y2XR.i=g(g(f(X.x),Y1.y),Y2.y)R.i=g(f(X.x),Y1.y)R.i=f(X.x)εAXY1Y2R.s=R.iR.s=R1.sA.a=R.sRRR.s=R1.sR消除左遞歸前后翻譯模式中屬性值傳遞和計(jì)算：A.a=g(g(f53A.a=g(g(f(X.x),Y1.y),Y2.y)A.a=f(X.x)A.a=g(f(X.x),Y1.y)Y1Y2XAAAR.i=g(g(f(X.x),Y1.y),Y2.y)R.i=g(f(X.x),Y1.y)R.i=f(X.x)εAXY1Y2R.s=R.iR.s=R1.sA.a=R.sRRR.s=R1.sRA.a=g(g(f(X.x),Y1.y),Y2.y)A.a=54例消除下面翻譯模式左遞歸：

E→E1+T{E.val:=E1.val+T.val}E→E1-T{E.val:=E1.val-T.val}E→T {E.val:=T.val}T→(E){T.val:=E.val}T→num{T.val:=num.val}消除左遞歸后的新的翻譯模式：E→T{R.i:=T.val}R{E.val:=R.s}R→+T{R1.i:=R.i+T.val}R1{R.s:=R1.s}R→-T{R1.i:=R.I-T.val}R1{R.s:=R1.s}R→ε{R.s:=R.i}T→(E){T.val:=E.val}T→num{T.val:=num.val}例消除下面翻譯模式左遞歸：消除左遞歸后的新的翻譯模式：55可結(jié)合自頂向下分析方法加深理解。可結(jié)合自頂向下分析方法加深理解。56[例6.11]P154構(gòu)造抽象語法樹的翻譯模式產(chǎn)生式E→E1+TE→E1*TE→TT→(E)T→num求其消除左遞歸后的翻譯模式：語義動作E.nptr:=mknode(‘+’,E1.nptr,T.nptr)E.nptr:=mknode(‘*’,E1.nptr,T.nptr)E.nptr:=T.nptrT.nptr:=E.nptrT.npter:=mknode(num,num.val)[例6.11]P154構(gòu)造抽象語法樹的翻譯模式57解：E→T{R.i:=T.type}R{E.nptr:=R.s}R→+T{R1.i:=mknode(‘+’,R.i,T.nptr)}R1{R.s:=R1.s}R→*T{R1.i:=mknode(‘*’,R.i,T.nptr)}R1{R.s:=R1.s}R→ε{R.s:=R.i}T→(E){T.nptr:=E.nptr}T→num{T.nptr:=mknode(num,num.val)}屬性文法和語法制導(dǎo)翻譯58屬性文法和語法制導(dǎo)翻譯59要點(diǎn)將語義規(guī)則的計(jì)算代碼按照其在翻譯模式中的位置插入到產(chǎn)生式對應(yīng)的右部子程序的相應(yīng)位置。例前抽象語法樹的翻譯模式對應(yīng)的遞歸下降分析器程序。（P157）6.4.3遞歸下降翻譯器的設(shè)計(jì)要點(diǎn)6.4.3遞歸下降翻譯器的設(shè)計(jì)60functionT:↑AST-node; varnptr,s:↑AST-node; val:integer;beginifsym=(thenbeginadvance;nptr:=E;ifsym=)thens:=nptr;returns;endelseifsym=numthenbegins:=mkleaf(num,val)returns;endelseerror;endfunctionE:↑AST-node; vari1,s:↑AST-node;begini1:=T;s:=R(i1);returns;end

functionT:↑AST-node;function61functionR(in:↑AST-node):↑AST-node; varnptr,i1,s1,s:↑AST-node; addoplexeme:char;beginifsym=addopthenbeginaddoplexeme=lexval;advance;nptr:=T;i1=mknode(addoplemexe,in,nptr);s1:=R(i1);s:=s1;endelses:=in;returns;end

functionR(in:↑AST-node):↑AST626.5自下而上計(jì)算繼承屬性處理的對象：任何基于LL(1)文法的L-屬性文法，許多（不是所有）基于LR(1)文法的L-屬性文法。需用要點(diǎn)回顧：自下而上分析中語義規(guī)則的計(jì)算是由產(chǎn)生式歸約時(shí)觸發(fā)的。問題：嵌入在中間的產(chǎn)生式?jīng)]有觸發(fā)點(diǎn)繼承屬性的處理6.5自下而上計(jì)算繼承屬性處理的對象：63目標(biāo)：自下而上的翻譯方法中，要求把所有的語義動作都放在產(chǎn)生式的末尾，這樣每當(dāng)歸約時(shí)，正好觸發(fā)語義規(guī)則。方法：使所有嵌入的動作都出現(xiàn)在產(chǎn)生式末尾的轉(zhuǎn)換方法是引入標(biāo)記非終結(jié)符。步驟：在基礎(chǔ)文法中加入新的產(chǎn)生式，這種產(chǎn)生式的形式為M→ε，其中M為新引入的一個標(biāo)記非終結(jié)符。將每個語義動作用不同的標(biāo)記非終結(jié)符M代替，并把這個動作放在產(chǎn)生式M→ε的末尾。6.5.1從翻譯模式中去掉嵌入在產(chǎn)生式中間的動作目標(biāo)：6.5.1從翻譯模式中去掉嵌入在產(chǎn)生式中間的動作64E→TRR→+TMR|-TNR|εT→num{print(num.val)}M→ε{print(‘+’)}N→ε{print(‘-’)}

E→TRR→+T{print(‘+’)}R|-T{print(‘-’)}R|εT→num{print(num.val)}？兩個翻譯模式中的文法接受的語言相同嗎？？語義規(guī)則計(jì)算順序相同嗎？引入標(biāo)記非終結(jié)符改寫文法：標(biāo)記非終結(jié)符M、NE→TRE→TR？兩個翻譯模式中的文法接受的語言相同65對象：自下而上分析器中繼承屬性由復(fù)寫規(guī)則計(jì)算時(shí)。方法設(shè)有前提：自下而上分析器對產(chǎn)生式A→XY的右部歸約。假設(shè)X有綜合屬性X.s，則在擴(kuò)展的分析棧里，它與X一起放在棧中；Y有繼承屬性Y.i是由復(fù)寫規(guī)則Y.i=X.s定義，因?yàn)槭抢^承屬性，所以不在棧內(nèi)。分析過程：是通過把X和Y從分析棧中移出并用A代替它們。在需要Y.i值的地方直接使用棧內(nèi)X.s的值。6.5.2利用分析棧處理繼承屬性？這樣處理為什么可以實(shí)現(xiàn)一遍的自下而上翻譯。答：不再有繼承屬性的計(jì)算。對象：自下而上分析器中繼承屬性由復(fù)寫規(guī)則計(jì)算時(shí)。6.5.266例：一個有復(fù)寫規(guī)則的翻譯模式：D→T {L.in:=T.type}LT→int {T.type:=integer}T→real {T.type:=real}L→{L1.in:=L.in}L1,id {addtype(id.entry,L.in)}L→id {addtype(id.entry,L.in)}復(fù)寫規(guī)則1復(fù)寫規(guī)則2例：一個有復(fù)寫規(guī)則的翻譯模式：D→T {L.in:=T.67繼承屬性L.in都是由復(fù)寫規(guī)則傳遞,值都是T.typeDLLLTintprq,,typeininin輸入句子為：intp,q,r屬性傳遞圖（P159）繼承屬性L.in都是由復(fù)寫規(guī)則傳遞,值都是T.typeDLL68分析過程輸入串狀態(tài)所有產(chǎn)生式Intp,q,r-p,q,rintp,q,rTT→int,q,rTp,q,r

TLL→idaddtype(id.entry,L.in)q,rTL,,r

TL,q,r

TLL→{L1.in:=L.in}L1,id{addtype(id.entry,L.in)}rTL,

TL,r

TLL→{L1.in:=L.in}L1,id{addtype(id.entry,L.in)}DD→TLL.In使用時(shí)，T正好在其下方L.In使用時(shí)，T正好在其下方L.In使用時(shí)，T正好在其下方分析過程輸入串狀態(tài)所有產(chǎn)生式Intp,q,r69由分析過程可改寫語義規(guī)則：產(chǎn)生式語義規(guī)則D→TLT→intval[ntop]:=integerT→realval[ntop]:=realL→L1,idaddtype(val[top],val[top-3])L→idaddtype(val[top],val[top-1])由分析過程可改寫語義規(guī)則：產(chǎn)生式語義規(guī)則D→TLT→intv70只有根據(jù)文法預(yù)知繼承屬性值在棧中的存放位置時(shí)，才能有效地在分析棧中處理屬性值。背景根據(jù)文法無法預(yù)知繼承屬性與相關(guān)的綜合屬性相對位置解決方法通過引入標(biāo)記非終結(jié)符改寫文法來確定位置。6.5.3模擬繼承屬性的計(jì)算問題1：替代繼承屬性的綜合屬性位置不確定只有根據(jù)文法預(yù)知繼承屬性值在棧中的存放位置時(shí)，才能有71兩個C.i都是通過復(fù)寫規(guī)則繼承綜合屬性A.s，在棧中，A.s可能在val[top-1]也可能在val[top-2]，不能確定C→c歸約時(shí)應(yīng)采用哪一個值。解決方法是在C前插入一個新的標(biāo)記非終結(jié)符。產(chǎn)生式語義規(guī)則S→aACC.i=A.sS→bABCC.i=A.sC→cC.s=g(C.i)產(chǎn)生式語義規(guī)則S→aACC.i=A.sS→bABMCM.i=A.s；C.i=M.sC→cC.s=g(C.i)M→εM.s=M.i例兩個C.i都是通過復(fù)寫規(guī)則繼承綜合屬性A.s，在棧中，A.s72CSbABsiSbABMsiCsi通過標(biāo)記M傳遞屬性，此時(shí)棧中A.s的值一定在C的下面SaACsi初始依賴圖修改后的依賴圖另一個含C.i的依賴圖CSbABsiSbABMsiCsi通過標(biāo)記M傳遞屬性，此時(shí)棧73背景文法中沒有此繼承屬性的復(fù)寫規(guī)則解決方法引入標(biāo)記非終結(jié)符將計(jì)算函數(shù)改寫到標(biāo)記非終結(jié)符的屬性中問題2：繼承屬性不是由復(fù)寫規(guī)則計(jì)算背景問題2：繼承屬性不是由復(fù)寫規(guī)則計(jì)算74初始文法和語義規(guī)則S→aACC.i:=f(A.s)改寫后的文法和語義規(guī)則S→aANCN.i:=A.s;C.i:=N.sN→ε

N.s:=f(N.i)同樣可在val[top-1]中找到c.i實(shí)例初始文法和語義規(guī)則改寫后的文法和語義規(guī)則同樣可在val[to75

標(biāo)記非終結(jié)符的作用將語義動作放在最后調(diào)整繼承屬性值在分析棧中的位置計(jì)算非復(fù)寫的繼承屬性一種帶繼承屬性的自下而上分析的翻譯方法恰當(dāng)引入標(biāo)記非終結(jié)符一個屬性文法的改寫例子(P162)將所有的繼承屬性都改寫為可由復(fù)寫規(guī)則賦值將其與分析棧結(jié)合改寫語義規(guī)則結(jié)論標(biāo)記非終結(jié)符的作用結(jié)論76產(chǎn)生式語義規(guī)則S→B

B.ps:=10S.ht:=B.htB→B1B2

B1.ps:=B.ps

B2.ps:=B.psB.ht:=max(B1.ht,B2.ht)B→B1subB2

B1.ps:=B.ps

B2.ps:=shrink(B.ps)B.ht:=disp(B1.ht,B2.ht)B→textB.ht:=text.h×B.ps產(chǎn)生式語義規(guī)則S→BB.ps:=10S77產(chǎn)生式語義規(guī)則S→LB

B.ps:=L.sS.ht:=B.htL→εL.s=10B→B1MB2

B1.ps:=B.psM.i=B.psB2.ps:=M.sB.ht:=max(B1.ht,B2.ht)B→B1subNB2B1.ps:=B.psN.i=B.psB2.ps=N.sB.ht:=disp(B1.ht,B2.ht)