Chapt6_第6章語法制導(dǎo)翻譯技術(shù)

1、第第6 6章章 語法制導(dǎo)翻譯技術(shù)語法制導(dǎo)翻譯技術(shù) No cross, no crown. 不經(jīng)歷風(fēng)雨，怎么見彩虹不經(jīng)歷風(fēng)雨，怎么見彩虹.n6.1 翻譯文法翻譯文法n6.2 語法制導(dǎo)翻譯語法制導(dǎo)翻譯n6.3 自頂向下語法制導(dǎo)翻譯自頂向下語法制導(dǎo)翻譯n6.4 屬性翻譯文法屬性翻譯文法n6.5 屬性文法的自頂向下翻譯屬性文法的自頂向下翻譯n6.6 自底向上語法制導(dǎo)翻譯自底向上語法制導(dǎo)翻譯第第6 6章章 語法制導(dǎo)翻譯技術(shù)語法制導(dǎo)翻譯技術(shù)n語法制導(dǎo)翻譯語法制導(dǎo)翻譯n翻譯文法、屬性翻譯文法及其應(yīng)用翻譯文法、屬性翻譯文法及其應(yīng)用 學(xué)習(xí)重點學(xué)習(xí)重點第第6 6章章 語法制導(dǎo)翻譯技術(shù)語法制導(dǎo)翻譯技術(shù)n語義語義：是

2、程序設(shè)計語言中按語法規(guī)則所構(gòu)成的各：是程序設(shè)計語言中按語法規(guī)則所構(gòu)成的各個語法成分的含義。個語法成分的含義。例如下列例如下列Test語言代碼語言代碼： int a; b= a+1; write b;n一個源程序經(jīng)歷了詞法分析與語法分析，表明它一個源程序經(jīng)歷了詞法分析與語法分析，表明它在書寫上和語法上是正確的在書寫上和語法上是正確的，但不能保證其在語義，但不能保證其在語義上是正確。上是正確。語義分析的任務(wù)語義分析的任務(wù)：分析程序的含義，分析程序的含義，并作相應(yīng)的語義處并作相應(yīng)的語義處理。理。第第6 6章章 語法制導(dǎo)翻譯技術(shù)語法制導(dǎo)翻譯技術(shù)n語義分析的功能語義分析的功能 類型和運算合法性檢查類型和

3、運算合法性檢查：檢查運算的合法性與運：檢查運算的合法性與運算分量類型的一致性（或相容性），必要時作相應(yīng)的算分量類型的一致性（或相容性），必要時作相應(yīng)的類型轉(zhuǎn)換。例如，類型轉(zhuǎn)換。例如，a+b,要求要求a和和b都是算術(shù)型（整型或都是算術(shù)型（整型或?qū)嵭停?，?dāng)實型），當(dāng)a和和b不是同一種類型時，需進行類型轉(zhuǎn)換。不是同一種類型時，需進行類型轉(zhuǎn)換。 確定類型確定類型：確定標(biāo)識符所關(guān)聯(lián)數(shù)據(jù)對象的數(shù)據(jù)類：確定標(biāo)識符所關(guān)聯(lián)數(shù)據(jù)對象的數(shù)據(jù)類型（有時由詞法分析完成）。型（有時由詞法分析完成）。識別含義識別含義：確定程序中各構(gòu)造成分組合到一起的：確定程序中各構(gòu)造成分組合到一起的含義，并作相應(yīng)的語義處理。這時對可執(zhí)行語

4、句生成含義，并作相應(yīng)的語義處理。這時對可執(zhí)行語句生成中間代碼或目標(biāo)代碼。中間代碼或目標(biāo)代碼。 第第6 6章章 語法制導(dǎo)翻譯技術(shù)語法制導(dǎo)翻譯技術(shù)n語義分析的功能語義分析的功能 一致性檢查一致性檢查：在很多程序設(shè)計語言中要求對象只：在很多程序設(shè)計語言中要求對象只能被說明一次。能被說明一次。 控制流檢查控制流檢查：控制流語句必須轉(zhuǎn)移到合法的地方。：控制流語句必須轉(zhuǎn)移到合法的地方。例如，在例如，在C語言中，語言中，break語句使得控制跳離包括該語語句使得控制跳離包括該語句的句的while、for或或switch語句，如果不存在包括它的這語句，如果不存在包括它的這樣的語句，則報告錯誤。樣的語句，則報告

5、錯誤。其它語義檢查其它語義檢查：如對象的作用域等。：如對象的作用域等。第第6 6章章 語法制導(dǎo)翻譯技術(shù)語法制導(dǎo)翻譯技術(shù)n語義分析的實現(xiàn)語義分析的實現(xiàn) 語義分析是以語法分析的輸出（語法分析樹或其它語義分析是以語法分析的輸出（語法分析樹或其它等價的內(nèi)部中間表示）作為輸入，輸出則是中間代碼，等價的內(nèi)部中間表示）作為輸入，輸出則是中間代碼，甚至是目標(biāo)代碼。一般情況下，語義分析僅產(chǎn)生中間代甚至是目標(biāo)代碼。一般情況下，語義分析僅產(chǎn)生中間代碼，即碼，即語義分析與目標(biāo)代碼生成分成兩遍來進行。語義分析與目標(biāo)代碼生成分成兩遍來進行。第第6 6章章 語法制導(dǎo)翻譯技術(shù)語法制導(dǎo)翻譯技術(shù)n語義往往是上下文有關(guān)的，只宜于用

6、口語描述，語義往往是上下文有關(guān)的，只宜于用口語描述，語語義形式化很困難義形式化很困難。目前，比較流行的語義描述和語義。目前，比較流行的語義描述和語義處理方法是處理方法是語法制導(dǎo)翻譯技術(shù)語法制導(dǎo)翻譯技術(shù)。n語法制導(dǎo)翻譯技術(shù)語法制導(dǎo)翻譯技術(shù)l基礎(chǔ)：基礎(chǔ)：形式描述的屬性翻譯文法形式描述的屬性翻譯文法l特點：把語法與語義分開，但又特點：把語法與語義分開，但又在語法分析的同在語法分析的同時進行相應(yīng)的語義工作時進行相應(yīng)的語義工作l提高了實用性提高了實用性6.1 6.1 翻譯文法翻譯文法 n例例: 設(shè)計一個翻譯器，它能將中綴表達(dá)式翻譯成波蘭后設(shè)計一個翻譯器，它能將中綴表達(dá)式翻譯成波蘭后綴表達(dá)式。綴表達(dá)式。

7、假設(shè)輸入串是假設(shè)輸入串是a+b*c，則，則問題問題: 如何實現(xiàn)這個翻譯過程呢？如何實現(xiàn)這個翻譯過程呢？a+b*c翻譯器翻譯器abc*+輸入串輸入串輸出串輸出串先看輸入串先看輸入串a(chǎn)+b*c的推導(dǎo)過程的推導(dǎo)過程:中綴表達(dá)式文法：中綴表達(dá)式文法： EE+T F(E) ET Fa TT*F Fb TF FcEE+TE+T*FE+T*c E+F*c E+b*c T+b*c F+b*c a+b*c由推導(dǎo)過程由推導(dǎo)過程 EE+TE+T*FE+T*c E+F*c E+b*c T+b*c F+b*c a+b*c得到輸入串的語法樹：得到輸入串的語法樹： 記住翻譯目標(biāo)是：記住翻譯目標(biāo)是：abc*+EE+TTT*F

8、FEcba添加葉子結(jié)點，用添加葉子結(jié)點，用表示輸出操作（輸出表示輸出操作（輸出其后的字符）。其后的字符）。EE+TTT*FFEcbabac*+將將符號的葉子結(jié)點從左到右連起來，得到符號的葉子結(jié)點從左到右連起來，得到abc*+（注意注意:這種帶有這種帶有的符號串稱為的符號串稱為動作序列動作序列。 ）執(zhí)行這個符號序列，得到執(zhí)行這個符號序列，得到abc*+這就是翻譯這就是翻譯結(jié)果結(jié)果!EE+TTT*FFEcbaEE+TTT*FFEcbabac*+問題：問題：如何得到這棵帶動作符號的語法樹呢？如何得到這棵帶動作符號的語法樹呢？ 在中綴表達(dá)式文法（輸入文法）的基礎(chǔ)上加入在中綴表達(dá)式文法（輸入文法）的基礎(chǔ)

9、上加入動作符號動作符號，得到翻譯文法。得到翻譯文法。 EE+T F(E) ET Fa TT*F Fb TF Fc EE+T+ F(E) ET Faa TT*F* Fbb TF Fcc輸入文法輸入文法翻譯文法翻譯文法n例例 用輸入文法推導(dǎo)用輸入文法推導(dǎo)a+b*c的過程如下的過程如下:EE+TE+T*FE+T*c E+F*c E+b*c T+b*c F+b*c a+b*c 用翻譯文法進行相同的推導(dǎo)用翻譯文法進行相同的推導(dǎo):EE+T+E+T*F*+E+T*cc *+ E+F*cc *+ E+bb*cc *+ T+bb*cc *+ F+bb*cc *+ aa+bb*cc *+ EE+T F(E) ET

10、 Fa TT*F Fb TF Fc EE+T+ F(E) ET Faa TT*F* Fbb TF Fcc輸入文法輸入文法翻譯文法翻譯文法輸入序列輸入序列活動序列活動序列將活動序列中的輸入序?qū)⒒顒有蛄兄械妮斎胄蛄腥サ?，得到動作序列：列去掉，得到動作序列?abc*+6.1 6.1 翻譯文法翻譯文法 n翻譯文法翻譯文法是上下文無關(guān)文法的推廣，是上下文無關(guān)文法的推廣，是在描述語言文法是在描述語言文法規(guī)則的右部適當(dāng)位置加入規(guī)則的右部適當(dāng)位置加入語義動作語義動作得到的。得到的。為了區(qū)分文法為了區(qū)分文法符號與語義動作，在文法的表示中，將代表語義動作的符符號與語義動作，在文法的表示中，將代表語義動作的符號前

11、面加號前面加動作符號標(biāo)記動作符號標(biāo)記來表示。來表示。n輸入序列輸入序列：用輸入：用輸入文法通過推導(dǎo)可以得文法通過推導(dǎo)可以得到的終結(jié)符號串。到的終結(jié)符號串。n活動序列活動序列：用翻譯：用翻譯文法通過推導(dǎo)得到的文法通過推導(dǎo)得到的符號串。符號串。n動作序列動作序列：從某活：從某活動序列中去掉所有輸動序列中去掉所有輸入序列，即由所有動入序列，即由所有動作符號組成的符號串。作符號組成的符號串。 輸入文法輸入序列（終結(jié)符號串）推導(dǎo)翻譯文法活動序列（終結(jié)符號串）推導(dǎo)添加語義動作輸入動作序列（終結(jié)符號串）輸出包括包括6.1 6.1 翻譯文法翻譯文法 6.1 6.1 翻譯文法翻譯文法n上例的翻譯文法可表示成：上

12、例的翻譯文法可表示成： G(E)=Vn,Vt,P,E，其中其中Vn=E, T, FVt=a, b, c, +, *, +, *, a, b, c P= EE+T+， ET， TF， Faa， TT*F*, Fbb，F(xiàn)cc n在高級程序設(shè)計語言的翻譯中有各種各樣的翻譯文法，在高級程序設(shè)計語言的翻譯中有各種各樣的翻譯文法，其中的動作符號代表不同的語義動作。其中的動作符號代表不同的語義動作。n在翻譯文法中在翻譯文法中,如果如果的動作就是輸出其后的符號的動作就是輸出其后的符號,可可稱該文法為稱該文法為符號串翻譯文法符號串翻譯文法。符號串翻譯文法是翻譯符號串翻譯文法是翻譯文法中的一種特定類型。文法中的一

13、種特定類型。 6.2 6.2 語法制導(dǎo)翻譯語法制導(dǎo)翻譯n例：例：根據(jù)前面的算術(shù)表達(dá)式翻譯文法，對于輸入符號串根據(jù)前面的算術(shù)表達(dá)式翻譯文法，對于輸入符號串a(chǎn)+b*c， 推導(dǎo)出的活動序列為：推導(dǎo)出的活動序列為：aa+bb*cc*+其中：其中： a+b*c 為輸入為輸入序列序列 abc*+ 為動作為動作序列序列 如果執(zhí)行該動作序列如果執(zhí)行該動作序列中中的動作，則產(chǎn)生輸出序列的動作，則產(chǎn)生輸出序列abc*+，這就是輸入序列，這就是輸入序列a+b*c的翻譯結(jié)果。的翻譯結(jié)果。 由于這種翻譯結(jié)果是通過翻譯文法獲得的，所以就稱由于這種翻譯結(jié)果是通過翻譯文法獲得的，所以就稱為為語法制導(dǎo)翻譯語法制導(dǎo)翻譯。 n語法

14、制導(dǎo)翻譯語法制導(dǎo)翻譯：就是給定一輸入：就是給定一輸入序列序列，根據(jù)，根據(jù)翻譯文法翻譯文法獲獲得翻譯該符號得翻譯該符號串的活動序列，從活動序列中分離出動作符串的活動序列，從活動序列中分離出動作符號串，然后執(zhí)行該動作符號串所規(guī)定的動作，從而得到翻號串，然后執(zhí)行該動作符號串所規(guī)定的動作，從而得到翻譯結(jié)果。譯結(jié)果。6.2 6.2 語法制導(dǎo)翻譯語法制導(dǎo)翻譯按按 語法制導(dǎo)翻譯語法制導(dǎo)翻譯的方法來實現(xiàn)語言的翻譯的方法來實現(xiàn)語言的翻譯1. 首先要根據(jù)輸入語言的文法，分析各條產(chǎn)生式的語義，首先要根據(jù)輸入語言的文法，分析各條產(chǎn)生式的語義，即分析他們即分析他們要求計算機所完成的操作要求計算機所完成的操作。2. 分別

15、編出完成這些操作的子程序或程序段分別編出完成這些操作的子程序或程序段(稱為稱為語義子語義子程序程序或或語義動作語義動作)3. 把這些子程序或程序段的名字把這些子程序或程序段的名字作為動作符號作為動作符號插入到輸插入到輸入文法各產(chǎn)生式右部的適當(dāng)位置上，從而實現(xiàn)翻譯文入文法各產(chǎn)生式右部的適當(dāng)位置上，從而實現(xiàn)翻譯文法。法。 6.3 6.3 自頂向下語法制導(dǎo)翻譯自頂向下語法制導(dǎo)翻譯n自頂向下的語法制導(dǎo)翻譯有自頂向下的語法制導(dǎo)翻譯有遞歸下降翻譯遞歸下降翻譯和和LL(1)翻譯。翻譯。遞歸下降翻譯遞歸下降翻譯：遞歸下降翻譯器的實現(xiàn)思路與：遞歸下降翻譯器的實現(xiàn)思路與遞歸下降分析基本相同，要求也一樣，即不能有遞

16、歸下降分析基本相同，要求也一樣，即不能有左遞歸，頭符號集不能相交，左遞歸，頭符號集不能相交，只需在適當(dāng)?shù)奈恢弥恍柙谶m當(dāng)?shù)奈恢貌迦雽崿F(xiàn)動作符號的子程序插入實現(xiàn)動作符號的子程序。 6.3 6.3 自頂向下語法制導(dǎo)翻譯自頂向下語法制導(dǎo)翻譯n例例 算術(shù)表達(dá)式算術(shù)表達(dá)式翻譯文法如下：翻譯文法如下： EE+T+ ET TT*F* TF F(E) Fii注：注：為輸出為輸出其后的符號串。其后的符號串。解：去掉文法解：去掉文法中的左遞歸，中的左遞歸，修改后文法為：修改后文法為： ET+T+ TF*F* F(E)|ii處理處理E的遞歸下降翻譯程序流程圖的遞歸下降翻譯程序流程圖 處理處理T的遞歸下降翻譯程序流程圖

17、的遞歸下降翻譯程序流程圖 TF*F*處理處理F的遞歸下降翻譯程序流程圖的遞歸下降翻譯程序流程圖 F(E)|iiFINPUTSYM=(INPUTSYM=下 一 個 符 號INPUTSYM=iINPUTSYM=)EINPUTSYM=下 一 個 符 號出 口errorOUT(i)INPUTSYM=下 一 個 符 號NYYNYerrorN6.3 6.3 自頂向下語法制導(dǎo)翻譯自頂向下語法制導(dǎo)翻譯n自頂向下的語法制導(dǎo)翻譯有遞歸下降翻譯和自頂向下的語法制導(dǎo)翻譯有遞歸下降翻譯和LL(1)翻譯。翻譯。LL(1)翻譯翻譯：LL(1)翻譯器的實現(xiàn)思路與翻譯器的實現(xiàn)思路與LL(1)分分析法基本相同，要求也一樣，即不能

18、有左遞歸，析法基本相同，要求也一樣，即不能有左遞歸，頭符號集不能相交，只需在文法適當(dāng)?shù)奈恢貌迦腩^符號集不能相交，只需在文法適當(dāng)?shù)奈恢貌迦雽崿F(xiàn)動作符號的子程序，并在實現(xiàn)動作符號的子程序，并在LL(1)分析表中加分析表中加入相應(yīng)的動作符號。入相應(yīng)的動作符號。 6.3 6.3 自頂向下語法制導(dǎo)翻譯自頂向下語法制導(dǎo)翻譯n例例(P126) 考考慮下面的輸入慮下面的輸入文法：文法： AaBcD Ab Bc BaA DcD Db 輸入文法的輸入文法的LL(1)分析表分析表 設(shè)其翻譯文法為：設(shè)其翻譯文法為： AvawBxcyDz Ab Bcr BamA DcDn Dsb6.3 6.3 自頂向下語法制導(dǎo)翻譯自頂

19、向下語法制導(dǎo)翻譯翻譯文法的翻譯文法的LL(1)LL(1)分析表分析表 注意：注意：對于翻譯文法，動作符號像其它符號一樣入棧。但對于翻譯文法，動作符號像其它符號一樣入棧。但當(dāng)當(dāng)動作符號處于棧頂動作符號處于棧頂時，時，無論當(dāng)前的輸入符號是什么，都無論當(dāng)前的輸入符號是什么，都要要執(zhí)行由該動作符號所規(guī)定的操作執(zhí)行由該動作符號所規(guī)定的操作，并將該動作符號從棧，并將該動作符號從棧頂彈出，且不移動讀符號指針。頂彈出，且不移動讀符號指針。 6.3 6.3 自頂向下語法制導(dǎo)翻譯自頂向下語法制導(dǎo)翻譯 假如翻譯器的分析棧的棧頂符號為假如翻譯器的分析棧的棧頂符號為A，且當(dāng)前輸入符號為，且當(dāng)前輸入符號為a，那么將發(fā)生的

20、動作是彈出，那么將發(fā)生的動作是彈出A，zDycxBwav入棧。入棧。由于此時棧頂為動作符號由于此時棧頂為動作符號v，因此，因此v出棧，并執(zhí)行由該動作出棧，并執(zhí)行由該動作符號所規(guī)定的操作，對于該符號串翻譯文法就是要輸出符號所規(guī)定的操作，對于該符號串翻譯文法就是要輸出v，即，即out(v)。緊接著，。緊接著，a出棧，讀下一個符號出棧，讀下一個符號c。然后，動作符號。然后，動作符號w為棧頂，因此為棧頂，因此w出棧，并執(zhí)行由該動作符號所規(guī)定的操作，出棧，并執(zhí)行由該動作符號所規(guī)定的操作，對于該符號串翻譯文法就是要輸出對于該符號串翻譯文法就是要輸出w，即，即out(w)。ac#A.#vv a a ww B

21、.#B.#vv出棧并執(zhí)行，出棧并執(zhí)行，a a出棧，讀入出棧，讀入c,wc,w出棧并執(zhí)出棧并執(zhí)行行ac#6.3 6.3 自頂向下語法制導(dǎo)翻譯自頂向下語法制導(dǎo)翻譯n翻譯文法的翻譯文法的LL(1)翻譯的總控程序總結(jié)翻譯的總控程序總結(jié)：1) 當(dāng)翻譯器的控制執(zhí)行程序根據(jù)當(dāng)翻譯器的控制執(zhí)行程序根據(jù)棧頂符號棧頂符號和和當(dāng)前輸當(dāng)前輸入符號入符號查該表得到元素為空時，則轉(zhuǎn)錯誤處理程序。查該表得到元素為空時，則轉(zhuǎn)錯誤處理程序。2)若控制執(zhí)行程序識別若控制執(zhí)行程序識別棧頂符號為動作符號棧頂符號為動作符號時，不時，不管當(dāng)前輸入符號是什么，將該動作符號從棧中彈出并管當(dāng)前輸入符號是什么，將該動作符號從棧中彈出并轉(zhuǎn)相應(yīng)的子

22、程序以完成所需的翻譯（轉(zhuǎn)相應(yīng)的子程序以完成所需的翻譯（執(zhí)行動作執(zhí)行動作）。對）。對于符號串翻譯文法，其語義動作為輸出動作符號中的于符號串翻譯文法，其語義動作為輸出動作符號中的符號串。符號串。 6.4 6.4 屬性翻譯文法屬性翻譯文法n引例引例聲明語句文法：聲明語句文法： TYPE ID ; ，ID 其中其中TYPE代表類型，其值可為代表類型，其值可為int或或 real或或bool。 問題：問題：將輸入符號串將輸入符號串“int a,b;”翻譯為翻譯為: int a int b思考：思考：能否通過在文法產(chǎn)生式右部添加動作符號能否通過在文法產(chǎn)生式右部添加動作符號實現(xiàn)該翻譯？實現(xiàn)該翻譯？6.4 6

23、.4 屬性翻譯文法屬性翻譯文法n引例引例聲明語句文法：聲明語句文法： TYPE ID ; ，ID 其中其中TYPE代表類型，其值可為代表類型，其值可為int或或 real或或bool。 輸入：輸入：int a,b;輸出：輸出：int a int b輸入串輸入串int a,b;”的推導(dǎo)過程：的推導(dǎo)過程： TYPE ID ; TYPE ID，ID ; TYPE ID, ID 問題：問題：無法將文法符號無法將文法符號TYPE、ID與輸入符號與輸入符號int、a、b關(guān)聯(lián)起來！關(guān)聯(lián)起來！6.4 6.4 屬性翻譯文法屬性翻譯文法6.4 6.4 屬性翻譯文法屬性翻譯文法 n屬性：屬性：對文法符號引進一些屬性

24、，這些屬性代表與對文法符號引進一些屬性，這些屬性代表與文法符號相關(guān)的信息，如類型、值、代碼序列、符號文法符號相關(guān)的信息，如類型、值、代碼序列、符號表內(nèi)容等。表內(nèi)容等。n屬性值可以在語法分析過程中計算和傳遞。屬性值可以在語法分析過程中計算和傳遞。n屬性一般用標(biāo)識符表示，通常寫在相應(yīng)文法符號的屬性一般用標(biāo)識符表示，通常寫在相應(yīng)文法符號的下邊，它的意義局限于它所在的產(chǎn)生式。下邊，它的意義局限于它所在的產(chǎn)生式。屬性加工的屬性加工的過程就是語義的處理過程。過程就是語義的處理過程。n屬性的分類屬性的分類綜合屬性綜合屬性繼承屬性繼承屬性 通常規(guī)定，每個文法符號的綜合屬性和繼承屬性通常規(guī)定，每個文法符號的綜合

25、屬性和繼承屬性的交集為空。的交集為空。6.4 6.4 屬性翻譯文法屬性翻譯文法 n綜合屬性綜合屬性：綜合屬性的計算規(guī)則是按：綜合屬性的計算規(guī)則是按“自下而上自下而上”方式進行，即文法產(chǎn)生式左部符號的某些屬性方式進行，即文法產(chǎn)生式左部符號的某些屬性根據(jù)其根據(jù)其右部符號的屬性和右部符號的屬性和/ /或自己的其它屬性計算而得或自己的其它屬性計算而得。n在語法樹中，如果一個結(jié)點的某一屬性，其值由子在語法樹中，如果一個結(jié)點的某一屬性，其值由子結(jié)點的屬性值來計算，則該屬性為綜合屬性。結(jié)點的屬性值來計算，則該屬性為綜合屬性。n綜合屬性可用綜合屬性可用“”來表示。來表示。對終結(jié)符號其綜合屬對終結(jié)符號其綜合屬性

26、具有指定的初始值性具有指定的初始值, ,該初始值由詞法分析程序提供。該初始值由詞法分析程序提供。n例例 ApXq,rYs,t p=q+s,r=p+t 其中，其中，p是綜合屬性，是綜合屬性，r不是綜合屬性，不是綜合屬性，q,s,t不能不能確定，需參考其它產(chǎn)生式的屬性計算規(guī)則才能確定。確定，需參考其它產(chǎn)生式的屬性計算規(guī)則才能確定。6.4 6.4 屬性翻譯文法屬性翻譯文法 n繼承屬性繼承屬性：繼承屬性的計算規(guī)則是按：繼承屬性的計算規(guī)則是按“自上而下自上而下”方式進行，即方式進行，即文法產(chǎn)生式右部符號的某些屬性根據(jù)其文法產(chǎn)生式右部符號的某些屬性根據(jù)其左部符號的屬性和左部符號的屬性和/ /或右部的其它符

27、號的某些屬性計算或右部的其它符號的某些屬性計算而得。而得。n在語法中，如果一個結(jié)點的某一屬性，其值由該結(jié)在語法中，如果一個結(jié)點的某一屬性，其值由該結(jié)點的父結(jié)點和點的父結(jié)點和/ /或兄弟結(jié)點的屬性值來計算，則該屬性或兄弟結(jié)點的屬性值來計算，則該屬性為繼承屬性。為繼承屬性。n繼承屬性可用繼承屬性可用“”來表示。開始符號的繼承屬性來表示。開始符號的繼承屬性具有初始值。具有初始值。n例例 ApXq,rYs,t p=q+s,r=p+t 顯然，顯然，r是繼承屬性。是繼承屬性。6.4 6.4 屬性翻譯文法屬性翻譯文法n例例 算術(shù)表達(dá)式的屬性翻譯文法算術(shù)表達(dá)式的屬性翻譯文法: SEqANSWERr r=q E

28、p Eq+ Tr p=q+r Ep Tq p=q Tp Tq* Fr p=q*r Tp Fq p=q Fp (Eq) p=q Fp NUMq p=q 6.4 6.4 屬性翻譯文法屬性翻譯文法n語義規(guī)則語義規(guī)則 (語義動作語義動作或或翻譯子程序翻譯子程序)：為輸入文：為輸入文法配備計算屬性的計算規(guī)則，稱為語義規(guī)則。法配備計算屬性的計算規(guī)則，稱為語義規(guī)則。 如上例中，如上例中， p=q+r就是語義規(guī)則。就是語義規(guī)則。n產(chǎn)生式只能產(chǎn)生符號串，它并未指明所產(chǎn)生的產(chǎn)生式只能產(chǎn)生符號串，它并未指明所產(chǎn)生的符號串的含義是什么。符號串的含義是什么。語義規(guī)則給出了一個產(chǎn)生語義規(guī)則給出了一個產(chǎn)生式所產(chǎn)生的符號串的

29、含義，而且還根據(jù)這種含義式所產(chǎn)生的符號串的含義，而且還根據(jù)這種含義規(guī)定了對應(yīng)的加工動作。規(guī)定了對應(yīng)的加工動作。n這些加工動作包括查填各類表格、改變編譯程這些加工動作包括查填各類表格、改變編譯程序的某些變量的值、打印各種錯誤信息以及生成序的某些變量的值、打印各種錯誤信息以及生成中間形式代碼等。中間形式代碼等。6.4 6.4 屬性翻譯文法屬性翻譯文法n屬性翻譯文法屬性翻譯文法（或（或?qū)傩晕膶傩晕姆ǚǎ海?對于某個壓縮的上下文對于某個壓縮的上下文無關(guān)文法，當(dāng)無關(guān)文法，當(dāng)為文法符號為文法符號引進一組屬性引進一組屬性，且讓該文，且讓該文法中的產(chǎn)生式法中的產(chǎn)生式附加上語義附加上語義規(guī)則時規(guī)則時，稱該上

30、下文無關(guān)，稱該上下文無關(guān)文法為屬性翻譯文法。文法為屬性翻譯文法。輸 入 文 法屬 性 翻 譯 文 法添 加 屬 性 和語 義 動 作翻 譯 文 法添 加 語義 動 作添 加 屬 性 及其 計 算 規(guī) 則6.4 6.4 屬性翻譯文法屬性翻譯文法n語義分析的翻譯過程：語義分析的翻譯過程：步驟步驟1 1 分析輸入符號串，建立語法樹；分析輸入符號串，建立語法樹；步驟步驟2 2 從語法樹得到描述結(jié)點屬性間依賴關(guān)系的依賴從語法樹得到描述結(jié)點屬性間依賴關(guān)系的依賴圖，由此依賴圖得到語義規(guī)則的計算次序；圖，由此依賴圖得到語義規(guī)則的計算次序；步驟步驟3 3 進行語義規(guī)則計算，得到翻譯結(jié)果。進行語義規(guī)則計算，得到翻

31、譯結(jié)果。 n語義分析翻譯過程的分類：語義分析翻譯過程的分類：自頂向下的翻譯自頂向下的翻譯自底向上的翻譯自底向上的翻譯6.4 6.4 屬性翻譯文法屬性翻譯文法n自頂向下的語義分析翻譯過程的示例自頂向下的語義分析翻譯過程的示例聲明語句文法：聲明語句文法： TYPE ID ; ，ID 其中其中TYPE代表類型，其值可為代表類型，其值可為int或或 real或或bool。 屬性翻譯文法：屬性翻譯文法： 1) TYPEtIDnSET_TYPEn1,t1 ； t2=t，t1=t ，n1=n 2) ，IDnSET_TYPEn1,t1 t2=t，t1=t ，n1=n 3 ) 其中，過程其中，過程SET_TYP

32、E輸出變量名及其類型。輸出變量名及其類型。給出輸入符號串給出輸入符號串“int a,b;”的語義分析翻譯過程。的語義分析翻譯過程。輸入：輸入：int a,b;輸出：輸出： a int b int6.4 6.4 屬性翻譯文法屬性翻譯文法聲明語句 ；IDa TYPEint 變量表IDb變量表， int a ,b ；的語法樹；的語法樹 解：輸入符號串解：輸入符號串“int a,b;”的語義分析翻譯過程：的語義分析翻譯過程：聲明語句 ；SET_TYPEn1,t2 IDn TYPEt 變量表t2 SET_TYPEn1, t1 IDn變量表t2 ， int a ,b ；的語法樹的語法樹加入動作符號和屬性加

33、入動作符號和屬性t2=t，t1=t ，n1=nt2=t，t1=t ，n1=n6.4 6.4 屬性翻譯文法屬性翻譯文法聲明語句 ；SET_TYPEa, int IDa TYPEint 變量表int SET_TYPEb, int IDb變量表int ， int a ,b ；的翻譯樹的翻譯樹解：輸入符號串解：輸入符號串“int a,b;”的語義分析翻譯過程：的語義分析翻譯過程：聲明語句 ；SET_TYPEn1,t2 IDn TYPEt 變量表t2 SET_TYPEn1, t1 IDn變量表t2 ， int a ,b ；的語法樹的語法樹加入動作符號和屬性加入動作符號和屬性t2=t，t1=t ，n1=n

34、t2=t，t1=t ，n1=n6.4 6.4 屬性翻譯文法屬性翻譯文法n自底向上的語義分析翻譯過程的示例自底向上的語義分析翻譯過程的示例 輸入算術(shù)表達(dá)式輸入算術(shù)表達(dá)式3+2*3，應(yīng)輸出，應(yīng)輸出9，給出輸入符號串，給出輸入符號串3+2*3的語義分析翻譯過程。的語義分析翻譯過程。 SEANSWER EE+T ET TT*F TF F(E) FNUM SEqANSWERr r=q Ep Eq+ Tr p=q+r Ep Tq p=q Tp Tq* Fr p=q*r Tp Fq p=q Fp (Eq) p=q Fp NUMq p=q 翻譯文法翻譯文法屬性翻譯文法屬性翻譯文法SET+EF*TTFNUM3

35、FNUM2 NUM3 3+ 2* 3的語法樹的語法樹 NUM3 SE9 T6 +E3 ANSWER9 F3 *T2 T3 F3 F2 NUM2 NUM3 3+ 2* 3的翻譯樹的翻譯樹 解：輸入符號串解：輸入符號串3+2*3的語義分析翻譯過程：的語義分析翻譯過程：6.4 6.4 屬性翻譯文法屬性翻譯文法6.4 6.4 屬性翻譯文法屬性翻譯文法n 例例 設(shè)計一個屬性翻譯文法，要求對于輸入的中綴表設(shè)計一個屬性翻譯文法，要求對于輸入的中綴表達(dá)式，經(jīng)過翻譯將輸出具有下面性質(zhì)的四元組代碼達(dá)式，經(jīng)過翻譯將輸出具有下面性質(zhì)的四元組代碼序列序列 1) 輸出符號串中的每個雙目運算都用一個四元式表示。輸出符號串中

36、的每個雙目運算都用一個四元式表示。2) 四元組中的四元式的順序與執(zhí)行時要完成的運算順?biāo)脑M中的四元式的順序與執(zhí)行時要完成的運算順序相同。序相同。3) 每個四元式有四個參數(shù)，自左向右的順序為每個四元式有四個參數(shù)，自左向右的順序為 運算符，左操作數(shù)，右操作數(shù)，運算結(jié)果運算符，左操作數(shù)，右操作數(shù)，運算結(jié)果 例如，翻譯器處理表達(dá)式例如，翻譯器處理表達(dá)式a+b將生成如下的四元式將生成如下的四元式 ADD , a , b , t1 其中其中t1是臨時變量，保存表達(dá)式的結(jié)果。是臨時變量，保存表達(dá)式的結(jié)果。翻譯器處理表達(dá)式翻譯器處理表達(dá)式a+a*b將生成將生成 MULT , a , b , t1 ADD ,

37、a , t1 , t2 6.4 6.4 屬性翻譯文法屬性翻譯文法解：第一步先設(shè)計滿足上述要求的翻譯文法。解：第一步先設(shè)計滿足上述要求的翻譯文法。翻譯文法：翻譯文法：EE+TADDETTT*FMULTTFF(E)FID 輸入文法：輸入文法：EE+TETTT*FTFF(E)FID 6.4 6.4 屬性翻譯文法屬性翻譯文法屬性翻譯文法：屬性翻譯文法：Ex Eq +Tr ADDy,z,t y=q, z=r, t=NEWT，x=tEx Tp x=pTx Tq *Fr MULTy,z,t y=q, z=r, t=NEWT，x=tTx Fp x=pFx (Ep) x=pFx IDp x=p其中，其中，NEW

38、T是一個函數(shù)，每次調(diào)用它時返回一個新的臨是一個函數(shù)，每次調(diào)用它時返回一個新的臨時變量名，臨時變量名按產(chǎn)生順序分別為時變量名，臨時變量名按產(chǎn)生順序分別為t1、t2、等。等。動作符號動作符號ADDy,z,t 輸出輸出“ADD,y,z,t”，動作符號動作符號MULTy,z,t 輸出輸出 “MULT,y,z,t”第二步，構(gòu)造屬性和求值規(guī)則，把翻譯文法構(gòu)造成屬性翻第二步，構(gòu)造屬性和求值規(guī)則，把翻譯文法構(gòu)造成屬性翻譯文法。譯文法。6.4 6.4 屬性翻譯文法屬性翻譯文法IDa ET+EF*TTFFIDa IDb 表達(dá)式表達(dá)式a+a*b的語法樹的語法樹 IDa Et2 Tt1 +Ea Fb *Ta Ta F

39、a Fa IDa IDb 表達(dá)式表達(dá)式a+a*b的翻譯樹的翻譯樹 MULTa,b,t1 ADDa,t1,t2 6. 5 屬性文法的自頂向下翻譯屬性文法的自頂向下翻譯n自頂向下的語義分析翻譯過程示例自頂向下的語義分析翻譯過程示例-回顧回顧屬性翻譯文法：屬性翻譯文法： 1) TYPEtIDnSET_TYPEn1,t1 ； t2=t，t1=t ，n1=n 2) ，IDnSET_TYPEn1,t1 t2=t，t1=t ，n1=n 3 ) 輸入符號串輸入符號串“int a,b;”的翻譯樹如下。的翻譯樹如下。聲明語句聲明語句 ；SET_TYPEa,int IDa TYPEint變量表變量表int SET_

40、TYPEb, int IDb變量表變量表int ， 屬性值依賴于屬性值依賴于上一級的上一級的屬性值依賴于左屬性值依賴于左邊的邊的a和和int6. 5 屬性文法的自頂向下翻譯屬性文法的自頂向下翻譯n分析分析l 按照自頂向下的有序方式對某個屬性求值時，應(yīng)按照自頂向下的有序方式對某個屬性求值時，應(yīng)當(dāng)確保所需要的當(dāng)確保所需要的基本值已知基本值已知。n我們需要我們需要對屬性計算規(guī)則設(shè)定約束條件對屬性計算規(guī)則設(shè)定約束條件！l 要求文法必須是要求文法必須是L-屬性文法。屬性文法。6. 5 屬性文法的自頂向下翻譯屬性文法的自頂向下翻譯nL- -屬性翻譯文法屬性翻譯文法滿足下面三個條件：滿足下面三個條件：（1

41、1）給定一產(chǎn)生式，其）給定一產(chǎn)生式，其右部符號的繼承屬性值右部符號的繼承屬性值是以左是以左部符號的繼承屬性或出現(xiàn)在給定符號左邊的產(chǎn)生式右部部符號的繼承屬性或出現(xiàn)在給定符號左邊的產(chǎn)生式右部符號的任意屬性為變元的函數(shù)。符號的任意屬性為變元的函數(shù)。（2 2）給定一產(chǎn)生式，其）給定一產(chǎn)生式，其左部符號的綜合屬性值左部符號的綜合屬性值是以左是以左部符號的繼承屬性或某個右部符號的任意屬性為變元的部符號的繼承屬性或某個右部符號的任意屬性為變元的函數(shù)。函數(shù)。（3 3）給定）給定一動作符號，其綜合屬性值一動作符號，其綜合屬性值是以該動作符號是以該動作符號的繼承屬性為變元的函數(shù)。的繼承屬性為變元的函數(shù)。 6. 5

42、 屬性文法的自頂向下翻譯屬性文法的自頂向下翻譯n例例 假設(shè)文法中有產(chǎn)生式為：假設(shè)文法中有產(chǎn)生式為： AI1S2,S3BI4CS5DS6I7,I8EI9 根據(jù)根據(jù)L-屬性的限制條件，屬性的限制條件，I4=F(I1)、 I4=123、 I7=G(I1)合法，而合法，而I4=H(S2)、 I4=K(S6,I4)則不合則不合法。法。 n 例例(P134) 假設(shè)文法中有產(chǎn)生式為：假設(shè)文法中有產(chǎn)生式為： Aa1a2Bb1b2Cc1c2A、B和和C的屬性可以按下面的順序進行求值的屬性可以按下面的順序進行求值 1)A的繼承屬性的繼承屬性a1 ； 2) B的繼承屬性的繼承屬性b1 ； 3) B的綜合屬性的綜合屬

43、性b2； 4) C的繼承屬性的繼承屬性c1 ； 5) C的綜合屬性的綜合屬性c2 ； 6) A的綜合屬性的綜合屬性a2 。 6. 5 屬性文法的自頂向下翻譯屬性文法的自頂向下翻譯n為了進行屬性翻譯的程序設(shè)計，我們采用下述為了進行屬性翻譯的程序設(shè)計，我們采用下述約定約定：1) 產(chǎn)生式中的產(chǎn)生式中的屬性名字屬性名字用作用作變量和參數(shù)的名字。變量和參數(shù)的名字。n例：例： Lab Ei Rj 寫成子程序（函數(shù)）時，表示為：寫成子程序（函數(shù)）時，表示為：int L(int a, int b) int i, j; 6. 5 屬性文法的自頂向下翻譯屬性文法的自頂向下翻譯n為了進行屬性翻譯的程序設(shè)計，我們采用

44、下述為了進行屬性翻譯的程序設(shè)計，我們采用下述約定約定：2) 所有出現(xiàn)在左部的同名非終結(jié)符，應(yīng)具有相同的所有出現(xiàn)在左部的同名非終結(jié)符，應(yīng)具有相同的屬性名表。屬性名表。在左部同名非終結(jié)符屬性名表的同一化過在左部同名非終結(jié)符屬性名表的同一化過程中，程中，屬性名稱的改動范圍僅局限于產(chǎn)生式左部。屬性名稱的改動范圍僅局限于產(chǎn)生式左部。屬屬性重新命名以后，應(yīng)修改性重新命名以后，應(yīng)修改某些屬性求值規(guī)則。某些屬性求值規(guī)則。n例例 產(chǎn)生式產(chǎn)生式 Lab EiRj i,j=b，a=i+2 L xyHzw w=y，z=2，x=z+y 按約定按約定2，應(yīng)改成，應(yīng)改成 LabEiiRj i,j=b，a=i+2 LabHz

45、w w=b，z=2，a=z+b6. 5 屬性文法的自頂向下翻譯屬性文法的自頂向下翻譯n為了進行屬性翻譯的程序設(shè)計，我們采用下述為了進行屬性翻譯的程序設(shè)計，我們采用下述約定約定：3) 如果兩個屬性有相同的值，那么可給它們相同的如果兩個屬性有相同的值，那么可給它們相同的名字，但對于左部符號的屬性值相等時，不能改變成名字，但對于左部符號的屬性值相等時，不能改變成相同的名字。相同的名字。 n例例 對規(guī)則對規(guī)則LabaBcCd ,當(dāng)當(dāng)c,d=a時，可寫成時，可寫成: LabaBaCa但當(dāng)?shù)?dāng)b=a時，上式時，上式不能寫成不能寫成LaaaBaCa這是因為過程這是因為過程L(int a,int b)不可寫成

46、不可寫成L(int a,int a)。 6. 5 屬性文法的自頂向下翻譯屬性文法的自頂向下翻譯n采用采用C語言編寫語言編寫L-屬性文法遞歸下降翻譯程序時采用屬性文法遞歸下降翻譯程序時采用的方法：的方法：1)1)形式參數(shù)：形式參數(shù)：產(chǎn)生式左部非終結(jié)符的產(chǎn)生式左部非終結(jié)符的屬性名表屬性名表設(shè)計設(shè)計成相應(yīng)過程的成相應(yīng)過程的形式參數(shù)表形式參數(shù)表。 繼承屬性繼承屬性值形參值形參( (即簡單變量即簡單變量) ) 綜合屬性綜合屬性指針變量。指針變量。2)2)局部變量：局部變量：在產(chǎn)生式中，與左部屬性名不同的屬在產(chǎn)生式中，與左部屬性名不同的屬性名變成相應(yīng)過程的性名變成相應(yīng)過程的局部變量局部變量。3)3)非終結(jié)

47、符的代碼：非終結(jié)符的代碼：產(chǎn)生式右部的每個非終結(jié)符的產(chǎn)生式右部的每個非終結(jié)符的過程調(diào)用，過程調(diào)用，該非終結(jié)符的屬性作為實參該非終結(jié)符的屬性作為實參。要注意：。要注意：如如果實參是簡單變量，形參是指針變量，調(diào)用時實參應(yīng)果實參是簡單變量，形參是指針變量，調(diào)用時實參應(yīng)為簡單變量的地址。為簡單變量的地址。6. 5 屬性文法的自頂向下翻譯屬性文法的自頂向下翻譯n采用采用C語言編寫語言編寫L-屬性文法遞歸下降翻譯程序時采屬性文法遞歸下降翻譯程序時采用的方法：用的方法：4)輸入符號的代碼：輸入符號的代碼：對文法中出現(xiàn)的每個輸入符號對文法中出現(xiàn)的每個輸入符號(即終結(jié)符號即終結(jié)符號)，將賦值語句插入到過程中它所

48、對應(yīng)的，將賦值語句插入到過程中它所對應(yīng)的NEXTSYM之前，把保存在讀符號程序之前，把保存在讀符號程序NEXTSYM中的中的終結(jié)符號屬性終結(jié)符號屬性(某個全局變量中某個全局變量中)賦給輸入符號屬性中的賦給輸入符號屬性中的每個屬性變量。每個屬性變量。5)動作符號的代碼：動作符號的代碼：對出現(xiàn)在文法中的每個動作符號，對出現(xiàn)在文法中的每個動作符號，插入代碼便于對動作符號的綜合屬性進行計算，并且把插入代碼便于對動作符號的綜合屬性進行計算，并且把結(jié)果賦給對應(yīng)于該綜合屬性的變量，然后輸出相應(yīng)的符結(jié)果賦給對應(yīng)于該綜合屬性的變量，然后輸出相應(yīng)的符號。號。6. 5 屬性文法的自頂向下翻譯屬性文法的自頂向下翻譯n

49、采用采用C語言編寫語言編寫L-屬性文法遞歸下降翻譯程序時采用屬性文法遞歸下降翻譯程序時采用的方法：的方法：4)輸入符號的代碼：輸入符號的代碼：對文法中出現(xiàn)的每個輸入符號對文法中出現(xiàn)的每個輸入符號(即即終結(jié)符號終結(jié)符號)，將賦值語句插入到過程中它所對應(yīng)的，將賦值語句插入到過程中它所對應(yīng)的NEXTSYM之前，把保存在讀符號程序之前，把保存在讀符號程序NEXTSYM中的中的終結(jié)符號屬性終結(jié)符號屬性(某個全局變量中某個全局變量中)賦給輸入符號屬性中的賦給輸入符號屬性中的每個屬性變量。每個屬性變量。5)動作符號的代碼：動作符號的代碼：對出現(xiàn)在文法中的每個動作符號，對出現(xiàn)在文法中的每個動作符號，插入代碼便

50、于對動作符號的綜合屬性進行計算，并且把插入代碼便于對動作符號的綜合屬性進行計算，并且把結(jié)果賦給對應(yīng)于該綜合屬性的變量，然后輸出相應(yīng)的符結(jié)果賦給對應(yīng)于該綜合屬性的變量，然后輸出相應(yīng)的符號。號。6. 5 屬性文法的自頂向下翻譯屬性文法的自頂向下翻譯n采用采用C語言編寫語言編寫L-屬性文法遞歸下降翻譯程序時采屬性文法遞歸下降翻譯程序時采用的方法：用的方法：6)屬性規(guī)則的代碼：屬性規(guī)則的代碼：與每個產(chǎn)生式有關(guān)的屬性求值規(guī)與每個產(chǎn)生式有關(guān)的屬性求值規(guī)則，插入其代碼以便對屬性求值規(guī)則的右部求值，并把則，插入其代碼以便對屬性求值規(guī)則的右部求值，并把結(jié)果賦給該規(guī)則左部的每個變量?？梢园堰@些代碼放在結(jié)果賦給該規(guī)

51、則左部的每個變量。可以把這些代碼放在屬性計算規(guī)則的所有自變量已知之后，且函數(shù)值被使用屬性計算規(guī)則的所有自變量已知之后，且函數(shù)值被使用之前的任何地方。之前的任何地方。7)主程序：主程序：C語言都是從語言都是從MAIN函數(shù)開始運行。在函數(shù)開始運行。在MAIN函數(shù)中，對文法的開始符號，其相應(yīng)的每一個綜函數(shù)中，對文法的開始符號，其相應(yīng)的每一個綜合屬性的名字變成主程序的局部變量，然后調(diào)用開始符合屬性的名字變成主程序的局部變量，然后調(diào)用開始符號對應(yīng)的過程。在調(diào)用時，如果實參對應(yīng)開始符號的繼號對應(yīng)的過程。在調(diào)用時，如果實參對應(yīng)開始符號的繼承屬性，則對每個繼承屬性以該屬性的初始值作為值參承屬性，則對每個繼承屬

52、性以該屬性的初始值作為值參傳入，對每個綜合屬性取該屬性的局部變量的地址傳入。傳入，對每個綜合屬性取該屬性的局部變量的地址傳入。6. 5 屬性文法的自頂向下翻譯屬性文法的自頂向下翻譯n例例 算術(shù)表達(dá)式屬性翻譯文法如下算術(shù)表達(dá)式屬性翻譯文法如下,用用C語言實現(xiàn)其語言實現(xiàn)其遞歸下降翻譯器遞歸下降翻譯器。EtTpEptEpt+Tr ADDp,r,t0 E t0t t0=NEWT Ept t=pTtFpTptTpt*Fr MULTp,r,t0 Tt0t t0=NEWT Tpt t=pFp -(Ep) | IDp 6. 5 屬性文法的自頂向下翻譯屬性文法的自頂向下翻譯main() /主程序主程序int e

53、s=0,t; printf(請輸入算術(shù)表達(dá)式請輸入算術(shù)表達(dá)式(操作數(shù)只能是單個操作數(shù)只能是單個字母字母)：);ch=getchar();printf(輸出四元式為：輸出四元式為：n);es=E(&t); /調(diào)分析表達(dá)式調(diào)分析表達(dá)式E的翻譯程序，的翻譯程序， EtTpEptif (es=0) printf(n翻譯成功翻譯成功!n);else printf(n表達(dá)式有語法錯誤表達(dá)式有語法錯誤!n);6. 5 屬性文法的自頂向下翻譯屬性文法的自頂向下翻譯/產(chǎn)生式產(chǎn)生式EtTpEpt的翻譯子程序，的翻譯子程序，t為綜為綜合屬性合屬性,形參用指針變量形參用指針變量int E(int *t) in

54、t es=0; int p; es=T(&p); /調(diào)分析調(diào)分析T子程序子程序 es=E1(p,t); /調(diào)分析調(diào)分析E子程序子程序 ，t是指針是指針 return(es);E(int *t)int pT(&p)E(p,t)return/產(chǎn)生式產(chǎn)生式Ept+Tr ADDp,r,t0 Et0t|的的翻譯子程序，其翻譯子程序，其中，中，p為繼承屬性，形參用整型變量，為繼承屬性，形參用整型變量，t為綜合屬性，形參為綜合屬性，形參用指針變量用指針變量int E1(int p,int *t) int r,es=0,t0; if (ch=+) ch=getchar(); es=T(&

55、;r); t0=NEWT(); /產(chǎn)生一個臨時變量產(chǎn)生一個臨時變量 printf(ADD,%c,%c,%cn,p,r,t0); es=E1(t0,t); return(es); else *t=p;return(0);E(int p,int *t)int r,t0;+?nextsymT(&r)t0=NEWT()E(t0,t)return*t=pnyn n/返回一個臨時變量返回一個臨時變量,順序產(chǎn)生順序產(chǎn)生A、B、.、Z，最，最多產(chǎn)生多產(chǎn)生26個臨時變量個臨時變量int NEWT() static int i=64;/設(shè)置設(shè)置i為靜態(tài)變量確保下次調(diào)用為靜態(tài)變量確保下次調(diào)用 時時i為上次調(diào)

56、用的結(jié)果為上次調(diào)用的結(jié)果 i=i+1; return(i);6. 5 6. 5 屬性文法的自頂向下翻譯屬性文法的自頂向下翻譯6. 5 屬性文法的自頂向下翻譯屬性文法的自頂向下翻譯/產(chǎn)生式產(chǎn)生式TtFpTpt的翻譯子程序，的翻譯子程序，t為為綜合屬性綜合屬性,形參用指針變量形參用指針變量int T(int *t) int es=0,p; es=F(&p); /調(diào)分析調(diào)分析F子程序子程序 es=T1(p,t); /調(diào)分析調(diào)分析T子程序子程序 return(es);T(int *t)int pF(&p)T(p,t)return/產(chǎn)生式產(chǎn)生式Tpt*Fr MULTp,r,t0 Tt0t

57、 |的翻譯子程序的翻譯子程序int T1(int p,int *t) int r,es=0,t0;if (ch=*) ch=getchar(); es=F(&r); t0=NEWT(); /產(chǎn)生一個臨時變量產(chǎn)生一個臨時變量 printf(MULT,%c,%c,%cn,p,r,t0); es=T1(t0,t); return(es); else *t=p; return(0); T(int p,int *t)int r,t0;*?nextsymF(&r)t0=NEWT()T(t0,t)return*t=p ny/產(chǎn)生式產(chǎn)生式Fp (Ep) | IDp 的翻譯子程序的翻譯子程序in

58、t F(int *p) /分析分析F子程序子程序 int es=0; if (ch=( ) ch=getchar(); es=E(p); /調(diào)分析調(diào)分析E子程序子程序 if (ch!=) return(3); else ch=getchar();return(es); else if (isalpha(ch) /判斷是否為字母判斷是否為字母 *p=ch; ch=getchar(); return(es); else return(4); F(int *p)(?nextsymE(p)nextsymreturn*p=ch ny)?nextsym字母?yy6. 5 屬性文法的自頂向下翻譯屬性文法的自

59、頂向下翻譯運行這段程序，若輸入：運行這段程序，若輸入： a*(b+c)+b*dADD,b,c,AMULT,a,A,BMULT,b,d,CADD,B,C,D輸出四元式序列為：輸出四元式序列為： 其中其中A、B、C、D都都是臨時變量。是臨時變量。 6. 5 屬性文法的自頂向下翻譯屬性文法的自頂向下翻譯n要要實現(xiàn)屬性翻譯文法的實現(xiàn)屬性翻譯文法的LL(1)翻譯器翻譯器，是對翻譯文法的是對翻譯文法的LL(1)翻譯器進行擴充翻譯器進行擴充,方法是方法是(P139)：對于所有符號，不僅對于所有符號，不僅符號進分析棧，其屬性也同時進棧。符號進分析棧，其屬性也同時進棧。即將棧符號設(shè)計為兩部分，符號名和即將棧符號

60、設(shè)計為兩部分，符號名和屬性域。任何棧符號的域都是在棧內(nèi)屬性域。任何棧符號的域都是在棧內(nèi)的一些存貯單元。的一些存貯單元。A屬性屬性 A1屬性屬性 A2B屬性屬性B1C#n例例(P139) 對符號串對符號串ABC，假定，假定A有有兩個屬性，兩個屬性，B有一個屬性而有一個屬性而C沒有任何沒有任何屬性。若符號名也占用一個存貯單元，屬性。若符號名也占用一個存貯單元，則相應(yīng)則相應(yīng)A的棧符號用三個存貯單元，的棧符號用三個存貯單元，B用二個，用二個，C用一個。用一個。6. 5 屬性文法的自頂向下翻譯屬性文法的自頂向下翻譯n例例(P139) 已知文法：已知文法： SEpANSWERr r=p Ep+EqErADDA1,A2R A1=q,A2=r,R=A1+A2,p=R Ep*