語(yǔ)法制導(dǎo)的翻譯

1、第五章 語(yǔ)法制導(dǎo)的翻譯趙建華南京大學(xué)計(jì)算機(jī)系2010年3月介紹 使用上下文無(wú)關(guān)文法引導(dǎo)語(yǔ)言的翻譯 CFG的非終結(jié)符號(hào)代表了語(yǔ)言的某個(gè)構(gòu)造 程序設(shè)計(jì)語(yǔ)言的構(gòu)造由更小的構(gòu)造組合而成 一個(gè)構(gòu)造的語(yǔ)義可以由小構(gòu)造的含義綜合而來(lái) 比如：表達(dá)式x+y的類(lèi)型由x、y的類(lèi)型和運(yùn)算符+決定。 也可以從附近的構(gòu)造繼承而來(lái) 比如：聲明int x;中x的類(lèi)型由它左邊的類(lèi)型表達(dá)式?jīng)Q定。語(yǔ)法制導(dǎo)定義和語(yǔ)法制導(dǎo)翻譯 語(yǔ)法制導(dǎo)定義： 將文法符號(hào)和某些屬性相關(guān)聯(lián)， 并通過(guò)語(yǔ)義規(guī)則來(lái)描述如何計(jì)算屬性的值 EE1+TE.code=E1.code|T.code | + 屬性code代表中綴表達(dá)式的逆波蘭表示，規(guī)則說(shuō)明加法表達(dá)式的逆波

2、蘭表示由兩個(gè)分量的逆波蘭表示并置，然后加上+得到。 語(yǔ)法制導(dǎo)翻譯： 在產(chǎn)生式體中加入語(yǔ)義動(dòng)作，并在適當(dāng)?shù)臅r(shí)候執(zhí)行這些語(yǔ)義動(dòng)作 EE1+Tprint +;語(yǔ)法制導(dǎo)的定義（SDD） SDD是上下文無(wú)關(guān)文法和屬性/規(guī)則的結(jié)合； 屬性和文法符號(hào)相關(guān)聯(lián)，按照需要來(lái)確定各個(gè)文法符號(hào)需要哪些屬性 規(guī)則和產(chǎn)生式相關(guān)聯(lián) 對(duì)于文法符號(hào)X和屬性a，我們用X.a表示分析樹(shù)中的某個(gè)標(biāo)號(hào)為X的結(jié)點(diǎn)的值。 一個(gè)分析樹(shù)結(jié)點(diǎn)和它的分支對(duì)應(yīng)于一個(gè)產(chǎn)生式規(guī)則，而對(duì)應(yīng)的語(yǔ)義規(guī)則確定了這些結(jié)點(diǎn)上的屬性的取值。分析樹(shù)和屬性值(1) 假設(shè)我們需要知道一個(gè)表達(dá)式的類(lèi)型，以及對(duì)應(yīng)代碼將它的值存放在何處，我們就需要兩個(gè)屬性：type，place

3、； 產(chǎn)生式規(guī)則：EE1+T 語(yǔ)義規(guī)則：(假設(shè)只有int/float類(lèi)型） E.type = if (E1.type=T.type) T.type else float E.place = newTempPlace(); /返回一個(gè)新的內(nèi)存位置； 產(chǎn)生式規(guī)則：Fid F.type = lookupIDTable(id.lexValue)-type; F.place = lookupIDTable(id.lexValue)-address;分析樹(shù)和屬性值(2) a+b*c的語(yǔ)法分析樹(shù)以及屬性值EET+TFidTF*Fididid.lexValue=aF.Type = FLOATF.Place =

4、&aT.Type = FLOATT.Place = &aE.Type = FLOATE.Place = &aT.Type = INTT.Place = &tmpF.Type = INTF.Place = &cid.lexValue=cid.lexValue=b假設(shè)a,b,c是已經(jīng)聲明的全局變量，a的類(lèi)型為FLOAT，b,c的類(lèi)型為INT中間未標(biāo)明的T和F的type和address都是INT和&b;E.Type = FLOATE.Place = &tmp2繼承屬性和綜合屬性 綜合屬性(synthesized attribute)：在分析樹(shù)結(jié)點(diǎn)N上的非終結(jié)符號(hào)A的屬性值由N對(duì)應(yīng)的產(chǎn)生式所關(guān)聯(lián)的語(yǔ)義

5、規(guī)則來(lái)定義。 通過(guò)N的子結(jié)點(diǎn)或N本身的屬性值來(lái)定義 繼承屬性(inherited attribute)：結(jié)點(diǎn)N的屬性值由N的父結(jié)點(diǎn)所關(guān)聯(lián)的語(yǔ)義規(guī)則來(lái)定義。 依賴(lài)于N的父結(jié)點(diǎn)、N本身和N的兄弟結(jié)點(diǎn)上的屬性值。 不允許N的繼承屬性通過(guò)N的子結(jié)點(diǎn)上的屬性來(lái)定義，但是允許N的綜合屬性依賴(lài)于N本身的繼承屬性。 終結(jié)符號(hào)有綜合屬性（由詞法分析獲得），但是沒(méi)有繼承屬性。SDD的例子 目標(biāo)：計(jì)算表達(dá)式行L的值（屬性val） 計(jì)算L的val值需要E的val值 E的val值又依賴(lài)于E和T的val值 終結(jié)符號(hào)digit有綜合屬性lexval。S屬性的SDD 只包含綜合屬性的SDD稱(chēng)為S屬性的SDD。 每個(gè)語(yǔ)義規(guī)則都

6、根據(jù)產(chǎn)生式體中的屬性值來(lái)計(jì)算頭部非終結(jié)符號(hào)的屬性值。 S屬性的SDD可以和LR語(yǔ)法分析器一起實(shí)現(xiàn) 棧中的狀態(tài)可以附加相應(yīng)的屬性值 在進(jìn)行歸約時(shí)，按照語(yǔ)義規(guī)則計(jì)算歸約得到的符號(hào)的屬性值。 語(yǔ)義規(guī)則不應(yīng)該有復(fù)雜的副作用 要求副作用不影響其它屬性的求值 沒(méi)有副作用的SDD稱(chēng)為屬性文法。語(yǔ)法分析樹(shù)上的SDD求值（1） 實(shí)踐中很少先構(gòu)造語(yǔ)法分析樹(shù)再進(jìn)行SDD求值 但在分析樹(shù)上求值有助于翻譯方案的可視化，便于理解。 注釋語(yǔ)法分析樹(shù) 包含了各個(gè)結(jié)點(diǎn)的各屬性值的語(yǔ)法分析樹(shù) 步驟： 對(duì)于任意的輸入串，首先構(gòu)造出相應(yīng)的分析樹(shù)。 給各個(gè)結(jié)點(diǎn)（根據(jù)其文法符號(hào)）加上相應(yīng)的屬性值 按照語(yǔ)義規(guī)則計(jì)算這些屬性值即可語(yǔ)法分析樹(shù)

7、上的SDD求值（2） 按照分析樹(shù)中的分支對(duì)應(yīng)的文法產(chǎn)生式，應(yīng)用相應(yīng)的語(yǔ)義規(guī)則計(jì)算屬性值 計(jì)算順序問(wèn)題： 如果某個(gè)結(jié)點(diǎn)N的屬性a為f(N1.b1,N2.b2,Nk.bk)，那么我們需要先算出N1.b1,N2.b2,Nk.bk的值。 如果我們可以給各個(gè)屬性值排出計(jì)算順序，那么這個(gè)注釋分析樹(shù)就可以計(jì)算得到。 S屬性的SDD一定可以按照自底向上的方式求值。 下面的SDD不能計(jì)算 ABA.s=B.i；B.i=A.s+1；注釋分析樹(shù)的例子適用于自頂向下分析的SDD 前面的表達(dá)式文法存在直接左遞歸，因此無(wú)法直接用自頂向下方法處理。 消除左遞歸之后，我們無(wú)法直接使用屬性val進(jìn)行處理： 比如規(guī)則：TFTT*F

8、T T對(duì)應(yīng)的項(xiàng)中，第一個(gè)因子對(duì)應(yīng)于F，而運(yùn)算符卻在T中。 需要繼承屬性來(lái)完成這樣的計(jì)算相同表達(dá)式的不同文法的比較 輸入串：3*4*5 請(qǐng)觀察左邊的T對(duì)應(yīng)的部分，和右邊的T對(duì)應(yīng)部分 Ti和Ti恰好互補(bǔ) 計(jì)算方法：把T之外部分的值繼承給T。T3F*digit:4digit:5T2T1Fdigit:3F*TF*T3FF*digit:3digit:4T2T1digit:5適用于自頂向下分析的SDD 注意：T的屬性inh實(shí)際上繼承了相應(yīng)的*號(hào)的左運(yùn)算分量。3*5的注釋分析樹(shù) 請(qǐng)觀察inh屬性是如何傳遞的。消直接左遞歸時(shí)語(yǔ)義規(guī)則的處理 假設(shè)： AA1YA.a = g(A1.a, Y.a) AXA.a =

9、f(X.x) 那么 A XRR.i = f(X.x); A.a = R.s R YR1R1.i = g(R.i, Y.y); R.s=R1.s R R.s = R.i 新文法中R對(duì)應(yīng)的部分和原文法中A對(duì)應(yīng)的部分互補(bǔ)； 對(duì)于AXY1Y2Yn；如果R對(duì)應(yīng)于YYiYn；互補(bǔ)的A對(duì)應(yīng)于AY1Yi-1 R.i等于互補(bǔ)的A的A.sSDD的求值順序 在對(duì)SDD的求值過(guò)程中，如果結(jié)點(diǎn)N的屬性a依賴(lài)于結(jié)點(diǎn)M1的屬性a1，M2的屬性a2，。那么我們必須先計(jì)算出Mi的屬性，才能計(jì)算N的屬性a。 使用依賴(lài)圖來(lái)表示計(jì)算順序。 顯然，這些值的計(jì)算順序應(yīng)該形成一個(gè)偏序關(guān)系。如果依賴(lài)圖中出現(xiàn)了環(huán)，表示屬性值無(wú)法計(jì)算依賴(lài)圖 描

10、述了某棵特定的分析樹(shù)上各個(gè)屬性實(shí)例之間的信息流（計(jì)算順序） 從實(shí)例a1到實(shí)例a2的有向邊表示計(jì)算a2時(shí)需要a1的值。（必須先計(jì)算a2，再計(jì)算a1） 對(duì)于標(biāo)號(hào)為X的分析樹(shù)結(jié)點(diǎn)N，和X關(guān)聯(lián)的每個(gè)屬性a都對(duì)應(yīng)依賴(lài)圖的一個(gè)結(jié)點(diǎn)N.a。 結(jié)點(diǎn)N對(duì)應(yīng)的產(chǎn)生式的語(yǔ)義規(guī)則通過(guò)X.c計(jì)算了A.b的值，且在分析樹(shù)中X和A分別對(duì)應(yīng)于N1和N2，那么從N1.c到N2.b有一條邊。 N1和N2可以等于/不等于N。依賴(lài)圖的例子 3*2的注釋分析樹(shù)；TFT T.val = T.syn; T.inh = F.val; 邊e1、e2。 可能的計(jì)算順序： 1,2,3,4,5,6,7,8.9 1,3,5,2,4,6,7,8,9屬性

11、值的計(jì)算順序 各個(gè)屬性的值需要按照依賴(lài)圖的拓?fù)漤樞蛴?jì)算。 如果依賴(lài)圖中存在環(huán)，則屬性計(jì)算無(wú)法進(jìn)行。 給定一個(gè)SDD，很難判定是否存在一棵分析樹(shù)，其對(duì)應(yīng)的依賴(lài)圖包含環(huán)。 但是特定類(lèi)型的SDD一定不包含環(huán)，且有固定的排序模式 S屬性的SDD L屬性的SDD 對(duì)于這些類(lèi)型的SDD，我們可以確定屬性的計(jì)算順序，且可以把不需要的屬性（及分析樹(shù)結(jié)點(diǎn)）拋棄以提高效率S屬性的SDD 每個(gè)屬性都是綜合屬性 都是根據(jù)子構(gòu)造的屬性計(jì)算出父構(gòu)造的屬性。 在依賴(lài)圖中，總是通過(guò)子結(jié)點(diǎn)的屬性值來(lái)計(jì)算父結(jié)點(diǎn)的屬性值。可以和自頂向下、自底向上的語(yǔ)法分析過(guò)程一起計(jì)算 自底向上： 在構(gòu)造分析樹(shù)的結(jié)點(diǎn)的同時(shí)計(jì)算相關(guān)的屬性（此時(shí)其子結(jié)

12、點(diǎn)的屬性必然已經(jīng)計(jì)算完畢） 自頂向下： 遞歸子程序法中，在過(guò)程A()的最后計(jì)算A的屬性（此時(shí)A調(diào)用的其他過(guò)程（對(duì)應(yīng)于子結(jié)構(gòu)）已經(jīng)調(diào)用完畢）在分析樹(shù)上計(jì)算SDD 按照后序遍歷的順序計(jì)算屬性值即可postorder(N)for(從左邊開(kāi)始，對(duì)N的每個(gè)子結(jié)點(diǎn)C)postorder(c); /遞歸調(diào)用返回時(shí)，各子結(jié)點(diǎn)的屬性計(jì)算完畢對(duì)N的各個(gè)屬性求值； 在LR分析過(guò)程中，我們實(shí)際上不需要構(gòu)造分析樹(shù)的結(jié)點(diǎn)。L屬性的SDD 每個(gè)屬性 要么是綜合屬性， 要么是繼承屬性，且產(chǎn)生式AX1X2Xn中計(jì)算Xi.a的規(guī)則只能使用 A的繼承屬性 Xi左邊的文法符號(hào)Xj的繼承屬性或綜合屬性。 Xi自身的繼承或綜合屬性。且這

13、些屬性之間的依賴(lài)關(guān)系不形成環(huán)。 特點(diǎn)： 依賴(lài)圖的邊： 繼承屬性從左到右，從上到下。 綜合屬性從下到上 在掃描過(guò)程中，計(jì)算一個(gè)屬性值時(shí)，和它相關(guān)的依賴(lài)屬性都已經(jīng)計(jì)算完畢。L屬性SDD和自頂向下語(yǔ)法分析 在遞歸子程序法中實(shí)現(xiàn)L屬性 對(duì)于每個(gè)非終結(jié)符號(hào)A，其對(duì)應(yīng)的過(guò)程的參數(shù)為繼承屬性，返回值為綜合屬性 在處理規(guī)則AX1X2Xn時(shí)， 在調(diào)用Xi()之前計(jì)算Xi的繼承屬性值，然后以它們?yōu)閰?shù)調(diào)用Xi()； 在產(chǎn)生式對(duì)應(yīng)代碼的最后計(jì)算A的綜合屬性 注意：如果所有的文法符號(hào)的屬性計(jì)算按上面的方式進(jìn)行，計(jì)算順序必然和依賴(lài)關(guān)系一致。L屬性SDD的例子 非L屬性的例子： ABCA.s=B.b；B.i=f(C.c,

14、 A.s)各子程序的類(lèi)型 int T( ); int T1(int inh); int F( );文法符文法符號(hào)號(hào)函數(shù)名函數(shù)名 綜合屬性綜合屬性/類(lèi)類(lèi)型型返回類(lèi)返回類(lèi)型型繼承屬性繼承屬性/類(lèi)型類(lèi)型參數(shù)類(lèi)型參數(shù)類(lèi)型TTval / intint無(wú)無(wú)TT1syn / int intinh / intintFFval / intint無(wú)無(wú)考慮一下：如果有多個(gè)繼承屬性/多個(gè)綜合屬性是如何處理遞歸子程序法中實(shí)現(xiàn)L屬性SDDint T( )if(curToken = digit) /digit是first(FT)中唯一的符號(hào)/處理規(guī)則TFT。intfval = F( );/F的綜合屬性Value；intt1

15、inh = fval;/計(jì)算T的繼承屬性intt1syn = T1(t1inh);/計(jì)算得到T的綜合屬性inttval = t1syn;/計(jì)算得到T的綜合屬性returntval;/返回T的綜合屬性elseerror();/報(bào)錯(cuò)注意：if(curToken = )肯定不對(duì)，因?yàn)椴皇且粋€(gè)符號(hào)對(duì)規(guī)則中某個(gè)文法符號(hào)X的處理：1、計(jì)算X的所有繼承屬性的值2、用這些值調(diào)用子函數(shù)X；返回值保存在某個(gè)變量中。具有受控副作用的語(yǔ)義規(guī)則 屬性文法沒(méi)有副作用，但增加了描述的復(fù)雜度 比如語(yǔ)法分析時(shí)如果沒(méi)有副作用，標(biāo)識(shí)符表就必須作為屬性傳遞。 可以把標(biāo)識(shí)符表作為全局變量，然后通過(guò)副作用函數(shù)來(lái)添加新標(biāo)識(shí)符； 受控的副作

16、用 不會(huì)對(duì)屬性求值產(chǎn)生約束，即可以按照任何拓?fù)漤樞蚯笾?，不?huì)影響最終結(jié)果。 或者對(duì)求值過(guò)程添加簡(jiǎn)單的約束。受控副作用的例子 LE nprint(E.val) 通過(guò)副作用打印出E的值 總是在最后執(zhí)行，而且不會(huì)影響其它屬性的求值 變量聲明的SDD中的副作用 addType將標(biāo)識(shí)符的類(lèi)型信息加入到標(biāo)識(shí)符表中。 只要標(biāo)識(shí)符不被重復(fù)聲明，標(biāo)識(shí)符的類(lèi)型信息總是正確的。語(yǔ)法制導(dǎo)翻譯的應(yīng)用例子 抽象語(yǔ)法樹(shù)的構(gòu)造 基本類(lèi)型和數(shù)組類(lèi)型的L屬性定義構(gòu)造抽象語(yǔ)法樹(shù)的SDD 抽象語(yǔ)法樹(shù) 每個(gè)結(jié)點(diǎn)代表一個(gè)語(yǔ)法結(jié)構(gòu)；對(duì)應(yīng)于一個(gè)運(yùn)算符； 結(jié)點(diǎn)的每個(gè)子結(jié)點(diǎn)代表其子結(jié)構(gòu)；對(duì)應(yīng)于運(yùn)算分量； 表示這些子結(jié)構(gòu)按照特定方式組成了較大的結(jié)

17、構(gòu)。 可以忽略掉一些標(biāo)點(diǎn)符號(hào)等非本質(zhì)的東西。 語(yǔ)法樹(shù)的表示方法 每個(gè)結(jié)點(diǎn)用一個(gè)對(duì)象表示 對(duì)象有多個(gè)域 葉子結(jié)點(diǎn)中只存放詞法值； 內(nèi)部結(jié)點(diǎn)中存放了op值和參數(shù)（通常指向其它結(jié)點(diǎn)）；構(gòu)造簡(jiǎn)單表達(dá)式的語(yǔ)法樹(shù)的SDD 屬性E.node指向E對(duì)應(yīng)的語(yǔ)法樹(shù)的根結(jié)點(diǎn)；表達(dá)式語(yǔ)法樹(shù)的構(gòu)造過(guò)程 輸入：a-4+c 步驟： p1=new Leaf(id, entry_a) p2=new Leaf(num, 4); p3=new Node(-, p1,p2); p4=new Leaf(id, entry_c); p5=new Node(+, p3,p4);自頂向下方式處理的L屬性定義（1） 在消左遞歸時(shí)，按照規(guī)則得到

18、此SDD自頂向下方式處理的L屬性定義（2） 對(duì)于這個(gè)SDD，各屬性值的計(jì)算過(guò)程實(shí)際上和原來(lái)S屬性定義中的計(jì)算過(guò)程一致。 繼承屬性可以把值從一個(gè)結(jié)構(gòu)傳遞到另一個(gè)并列的結(jié)構(gòu)；也可把值從父結(jié)構(gòu)傳遞到子結(jié)構(gòu)。 抽象語(yǔ)法樹(shù)和分析樹(shù)不一致時(shí)，繼承屬性很有用。類(lèi)型結(jié)構(gòu) 簡(jiǎn)化的類(lèi)型表達(dá)式的語(yǔ)法 TB CBint | float CnumC | 生成類(lèi)型表達(dá)式的SDD類(lèi)型的含義 類(lèi)型包括兩個(gè)部分：TB C 基本類(lèi)型B 分量C 分量形如34 表示3X4的二維數(shù)組 int 34 數(shù)組構(gòu)造算符array array(3,array(4,int)表示抽象的3X4的二維數(shù)組類(lèi)型表達(dá)式的生成過(guò)程 輸入：int 23語(yǔ)法制導(dǎo)

19、的翻譯方案 語(yǔ)法制導(dǎo)的翻譯方案（SDT）是在產(chǎn)生式體中嵌入程序片斷（語(yǔ)義動(dòng)作）的上下文無(wú)關(guān)文法 SDT的基本實(shí)現(xiàn)方法： 建立語(yǔ)法分析樹(shù)； 將語(yǔ)義動(dòng)作看作是虛擬的結(jié)點(diǎn)； 從左到右、深度優(yōu)先地遍歷分析樹(shù)，在訪(fǎng)問(wèn)虛擬結(jié)點(diǎn)時(shí)執(zhí)行相應(yīng)動(dòng)作 用SDT實(shí)現(xiàn)兩類(lèi)重要的SDD 基本文法是LR的，SDD是S屬性的 基本文法是LL的，SDD是L屬性的例子 語(yǔ)句3*4*5的分析樹(shù)如右 DFS可知?jiǎng)幼鲌?zhí)行順序 A71,A5, A72, A41, A73, A42, A2 注意，一個(gè)動(dòng)作的不同實(shí)例所訪(fǎng)問(wèn)的屬性值屬于不同的結(jié)點(diǎn)T3F*digit:4digit:5T2T1Fdigit:3F*EA7A71A72A5A41A42

20、A2A73可在語(yǔ)法分析過(guò)程中實(shí)現(xiàn)的SDT 實(shí)現(xiàn)SDT時(shí)，實(shí)際上并不會(huì)真的構(gòu)造語(yǔ)法分析樹(shù)，而是在分析過(guò)程中執(zhí)行語(yǔ)義動(dòng)作 即使基礎(chǔ)文法可以應(yīng)用某種分析技術(shù)，仍可能因?yàn)閯?dòng)作的緣故導(dǎo)致此技術(shù)不可應(yīng)用 判斷是否可在分析過(guò)程中實(shí)現(xiàn) 將每個(gè)語(yǔ)義動(dòng)作替換為一個(gè)獨(dú)有的標(biāo)記非終結(jié)符號(hào)；每個(gè)標(biāo)記非終結(jié)符號(hào)M的產(chǎn)生式為M。 如果新的文法可以由某種方法進(jìn)行分析，那么這個(gè)SDT就可以在這個(gè)分析過(guò)程中實(shí)現(xiàn)。 注意：這個(gè)方法沒(méi)有考慮變量值的傳遞等要求。判斷SDT可否用特定分析技術(shù)實(shí)現(xiàn)例子 LE n M1M1 EE+T M2M2 ET M3M3 后綴翻譯方案 文法可以自底向上分析且SDD是S屬性的，比然可以構(gòu)造出后綴SDT 后

21、綴SDT：所有動(dòng)作都在產(chǎn)生式最右端的SDT 構(gòu)造方法： 將每個(gè)語(yǔ)義規(guī)則看作是一個(gè)賦值語(yǔ)義動(dòng)作 將所有的語(yǔ)義動(dòng)作放在規(guī)則的最右端后綴翻譯方案的例子 實(shí)現(xiàn)桌上計(jì)算器的后綴SDT注意動(dòng)作中對(duì)屬性值的引用： 我們?cè)试S語(yǔ)句引用全局變量，局部變量，文法符號(hào)的屬性。 文法符號(hào)的屬性只能被賦值一次；后綴SDT的語(yǔ)法分析棧實(shí)現(xiàn) 可以在LR語(yǔ)法分析的過(guò)程中實(shí)現(xiàn) 歸約時(shí)執(zhí)行相應(yīng)的語(yǔ)義動(dòng)作 定義用于記錄各文法符號(hào)的屬性的union結(jié)構(gòu) 棧中的每個(gè)文法符號(hào)（或者說(shuō)狀態(tài)）都附帶一個(gè)這樣的union類(lèi)型的值； 在按照產(chǎn)生式AXYZ歸約時(shí)，Z的屬性可以在棧頂找到，Y的屬性可以在下一個(gè)位置找到，X的屬性可以在再下一個(gè)位置找到。

22、分析棧實(shí)現(xiàn)的例子 假設(shè)語(yǔ)法分析棧存放在一個(gè)被稱(chēng)為stack的記錄數(shù)組中，下標(biāo)top指向棧頂； stacktop是這個(gè)棧的棧頂； stacktop-1指向棧頂下一個(gè)位置； 如果不同的文法符號(hào)有不同的屬性集合，我們可以使用union來(lái)保存這些屬性值。 歸約時(shí)能夠知道棧頂向下的各個(gè)符號(hào)分別是什么；因此我們也能夠確定各個(gè)union中究竟存放了什么樣的值后綴SDT的棧實(shí)現(xiàn) 這個(gè)SDT中沒(méi)有局部變量，不會(huì)產(chǎn)生和局部變量有關(guān)的問(wèn)題注意：stacktop-i和文法符號(hào)的對(duì)應(yīng)產(chǎn)生式內(nèi)部帶有語(yǔ)義動(dòng)作的SDT 動(dòng)作左邊的所有符號(hào)（以及動(dòng)作）處理完成后，就立刻執(zhí)行這個(gè)動(dòng)作 BXaY 自底向上分析時(shí)，在X出現(xiàn)在棧頂時(shí)執(zhí)

23、行動(dòng)作a 自頂向下分析時(shí)，在試圖展開(kāi)Y或者在輸入中檢測(cè)到Y(jié)的時(shí)刻執(zhí)行a 不是所有的SDT都可以在分析過(guò)程中實(shí)現(xiàn) 但是后綴SDT以及L屬性對(duì)應(yīng)的SDT可以在分析時(shí)完成。 對(duì)于一般的SDT，都可以先建立分析樹(shù)（語(yǔ)義動(dòng)作作為虛擬的結(jié)點(diǎn)），然后進(jìn)行前序遍歷并執(zhí)行動(dòng)作。消左遞歸時(shí)SDT的轉(zhuǎn)換 如果動(dòng)作不涉及屬性值，可以把動(dòng)作當(dāng)作終結(jié)符號(hào)進(jìn)行處理，然后消左遞歸 原始的產(chǎn)生式 EE1+T print(+); ET 轉(zhuǎn)換后得到 E T R R + T print (+); R R L屬性的SDT 從L屬性到SDT的轉(zhuǎn)換 將每個(gè)語(yǔ)義規(guī)則看作是一個(gè)賦值語(yǔ)義動(dòng)作 將賦值語(yǔ)義動(dòng)作放到相應(yīng)產(chǎn)生式的適當(dāng)位置 計(jì)算A的繼承

24、屬性的動(dòng)作插入到產(chǎn)生式體中對(duì)應(yīng)的A的左邊 如果A的繼承屬性之間具有依賴(lài)關(guān)系，則需要對(duì)計(jì)算動(dòng)作進(jìn)行排序 計(jì)算產(chǎn)生式頭的綜合屬性的動(dòng)作在產(chǎn)生式的最右邊。L屬性的SDT的例子 SDD 繼承屬性： next：語(yǔ)句結(jié)束后應(yīng)該跳轉(zhuǎn)到的標(biāo)號(hào) true、false：C為真/假時(shí)應(yīng)該跳轉(zhuǎn)到的標(biāo)號(hào) 綜合屬性code表示代碼轉(zhuǎn)換 語(yǔ)義動(dòng)作 (a) L1=new( )和L2=new( )：計(jì)算臨時(shí)值 (b) C.false = S.next; C.true = L2：計(jì)算C的繼承屬性 (c) S1.next = L1：計(jì)算S1的繼承屬性 (d) S.code= ：計(jì)算S的綜合屬型 根據(jù)放置語(yǔ)義動(dòng)作的規(guī)則得到如下SDT

25、 b在C之前；c在S1之前；d在最右端 a可以放在最前面L屬性的SDD的實(shí)現(xiàn) 使用遞歸下降的語(yǔ)法分析器 每個(gè)非終結(jié)符號(hào)對(duì)應(yīng)一個(gè)函數(shù) 函數(shù)的參數(shù)接受繼承屬性 返回值包含了綜合屬性 在函數(shù)體中 首先選擇適當(dāng)?shù)漠a(chǎn)生式 使用局部變量來(lái)保存屬性 對(duì)于產(chǎn)生式體中的終結(jié)符號(hào)，讀入符號(hào)并獲取其（經(jīng)詞法分析得到的）綜合屬性 對(duì)于非終結(jié)符號(hào)，使用適當(dāng)?shù)姆绞秸{(diào)用相應(yīng)函數(shù)，并記錄返回值。遞歸下降法實(shí)現(xiàn)L屬性SDD的例子邊掃描邊生成屬性（1） 當(dāng)屬性值的體積很大時(shí)，對(duì)屬性值進(jìn)行運(yùn)算的效率很低 比如code（代碼）可能是一個(gè)上百K的串，對(duì)其進(jìn)行并置等運(yùn)算會(huì)比較低效 可以逐步生成屬性的各個(gè)部分，并增量式添加到最終的屬性值中

26、 條件： 存在一個(gè)主屬性，且主屬性是綜合屬性 在各產(chǎn)生式中，主屬性是通過(guò)產(chǎn)生式體中各個(gè)非終結(jié)符號(hào)的主屬性連接（并置）得到的。同時(shí)還會(huì)連接一些其它的元素。 各非終結(jié)符號(hào)的主屬性的連接順序和它在產(chǎn)生式體中的順序相同邊掃描邊生成屬性（2） 基本思想 只需要在適當(dāng)?shù)臅r(shí)候“發(fā)出”非主屬性的元素，即把這些元素拼接到適當(dāng)?shù)牡胤?舉例說(shuō)明 假設(shè)我們?cè)趻呙枰粋€(gè)非終結(jié)符號(hào)對(duì)應(yīng)的語(yǔ)法結(jié)構(gòu)時(shí)，調(diào)用相應(yīng)的函數(shù)，并生成主屬性； S while (C) S1 S.code = Label | L1 |C.code |Label | L2 | S1.code 處理S時(shí)，先調(diào)用C，再調(diào)用S（對(duì)應(yīng)于S1） 如果各個(gè)函數(shù)把主屬性打印出來(lái)，我們處理while語(yǔ)句時(shí)，只需要先打印Label L1，再調(diào)用C（打印了C的代碼），再打印Label L2，再調(diào)用S（打印S1的代碼） 對(duì)于這個(gè)規(guī)則而言，只需要打印Label L1和Label L2。當(dāng)然，