語法制導(dǎo)翻譯技術(shù)PPT課件

1、6.1 6.1 翻譯文法翻譯文法 翻譯文法是上下文無關(guān)文法的推廣，是在描述語言文法規(guī)則的右部適當(dāng)位置加入語義動作得到的。為了區(qū)分文法符號與語義動作，在文法的表示中，將代表語義動作的符號前面加符號來表示。如何來設(shè)計(jì)翻譯文法呢？ 假設(shè)我們要設(shè)計(jì)一個翻譯器，它能將中綴表達(dá)式翻譯成波蘭后綴表達(dá)式。我們可以想象該翻譯器將如何進(jìn)行這種翻譯。假設(shè)輸入串是a+b*c，則翻譯器的輸入輸出動作是：READ(a)PRINT(a)READ(+)READ(b)PRINT(b) READ(*)READ(C)PRINT(C)PRINT(*)PRINT(+)其中READ表示輸入操作，PRINT表示輸出操作。在該序列中，若用輸

2、入符號本身直接表示讀操作，用表示表示輸出操作，則上述序列可簡化為：aa+bb*cc*+ 這種帶有的符號串稱為活動序列。由PRINT操作所確定的輸出結(jié)果是由緊跟在符號之后的各符號組成，即abc*+。我們稱為動作符號標(biāo)記，由符號開始的符號串稱為一個動作符號。這樣，上面的活動序列中就有5個動作符號，分別為：a、b、c、*和+。在這個例子中，我們可以把這些動作符號看成一些子程序的名字。這些子程序的功能就是打印動作符號中的輸出符號。在有些應(yīng)用中，動作符號用來表示更一般的具有特殊功能的子程序。 第1頁/共61頁6.1 6.1 翻譯文法翻譯文法上面的活動序列只說明了如何具體處理一個中綴表達(dá)式。為了能對所有中

3、綴表達(dá)式翻譯，就必須研究中綴表達(dá)式文法，考慮能否在適當(dāng)位置加入動作符號，使得能夠產(chǎn)生含有能翻譯成波蘭后綴表達(dá)式的活動序列。假設(shè)中綴算術(shù)表達(dá)式文法為： 為了構(gòu)造能產(chǎn)生活動序列的文法，只需在規(guī)則右部的適當(dāng)位置加入動作符號。對于該文法，為了讀a之后能打印a，產(chǎn)生式可寫成：Faa。為了在打印兩個操作數(shù)之后打印加法運(yùn)算符，產(chǎn)生式將變?yōu)椋篍E+T +，這個產(chǎn)生式可解釋為：“對非終結(jié)符號E的分析可以看成是處理E，讀+，再處理T并打印+”。對其他產(chǎn)生式作類似的改變以后可得文法為這種帶有動作符號的文法就是我們稱為翻譯文法的一個例子。 E E + T F(E) ET Fa TT*F Fb TF Fc EE+T+

4、F(E) ET Faa TT*F* Fbb TF Fcc第2頁/共61頁6.1 6.1 翻譯文法翻譯文法從上例中我們可看到，中綴表達(dá)式文法和其翻譯文法的產(chǎn)生式之間有對應(yīng)關(guān)系，為了和翻譯文法的稱呼對應(yīng)，現(xiàn)在，我們把中綴表達(dá)式文法叫做輸入文法，使用中綴表達(dá)式文法通過推導(dǎo)可以得到終結(jié)符號串叫做輸入序列，而通過翻譯文法得到的符號串稱為活動序列。因此通過輸入文法推導(dǎo)能得到的輸入序列，那么就能通過翻譯文法得到相應(yīng)的活動序列。從該活動序列中去掉所有動作符號就是輸入序列，而所有動作符號組成的符號串稱為動作序列。 例如，對于符號串(a+b)*b用輸入文法推導(dǎo)輸入序列(a+b)*c的過程如下:E =T=T*F=F

5、*F=(E)*F=(E+T)*F=(T+T)*F=(F+T)*F=(a+T)*F =(a+F)*F=(a+b)*F=(a+b)*c用翻譯文法推導(dǎo)得到活動序列(a a +b b+)*c c*的過程如下:E =T=T*F*=F*F*=(E)*F*=(E+T+)*F*=(T+T+)*F* =(F+T+)*F*=(aa+T+)*F*=(a a +F+)*F* =(a a +b b+)*F*=(a a +b b+)*c c*將活動序列(aa+bb+)*cc*中的動作符號去掉就得到輸入序列：(a+b)*c ，而所有動作符號組成的符號串即動作序列為：a b+c* 第3頁/共61頁6.1 6.1 翻譯文法翻譯

6、文法翻譯文法是上下無關(guān)文法。在這個文法中，終結(jié)符號集由輸入符號和動作符號組成。由翻譯文法確定的語言中的符號串稱為活動序列。例如，有文法G(E)=Vn,Vt,P,E，其中Vn=E, T, FVt=a, b, c, +, *, (, ), +, *, a, b, c P = E E + T + , F ( E ) , E T , F a a ,TT*F*,Fbb,TF,Fcc這個文法的終結(jié)符號集由輸入符號和動作符號組成，因此是翻譯文法。從上面介紹得知，翻譯文法就是在原有的輸入文法基礎(chǔ)上，在規(guī)則右部適當(dāng)位置加入動作符號所得。在高級程序設(shè)計(jì)語言的翻譯中有各種各樣的翻譯文法，其中的動作符號代表不同的語義

7、動作。在翻譯文法中,如果的動作就是輸出其后的符號,可稱為符號串翻譯文法。符號串翻譯文法是翻譯文法中的一種特定類型。 第4頁/共61頁6.2 6.2 語法制導(dǎo)翻譯語法制導(dǎo)翻譯 有了翻譯文法，我們就可以根據(jù)輸入符號串用翻譯文法得到一個活動序列。執(zhí)行其中的動作符號串，就可獲得一個新的符號串。這個新符號串就是翻譯的結(jié)果。 例如:根據(jù)前面的算術(shù)表達(dá)式翻譯文法，對于輸入符號串a(chǎn)+b*c，我們推導(dǎo)出活動序列：aa+bb*cc*+ 其中： a+b*c 為輸入序列 abc*+ 為動作序列如果執(zhí)行該動作序列中的動作，則產(chǎn)生輸出序列abc*+,這就是輸入序列a+b*c的翻譯結(jié)果。由于這種翻譯結(jié)果是通過翻譯文法獲得的

8、，所以就稱為語法制導(dǎo)翻譯。 所謂語法制導(dǎo)翻譯，就是給定一輸入序列，根據(jù)翻譯文法獲得翻譯該符號串的活動序列，從活動序列中分離出動作符號串，然后執(zhí)行該動作符號串所規(guī)定的動作，從而得到翻譯結(jié)果。從形式上看，可以將翻譯看成是對偶的集合。對偶的第一個元素是被翻譯的符號串(即輸入序列)，第二個元素是翻譯成的新符號串。當(dāng)我們是按翻譯文法得到這種對偶時，則稱為語法制導(dǎo)翻譯。如果給出由輸入符號和動作符號所組成的活動序列，通過從活動序列中刪掉所有動作符號則可得到輸入序列，而從活動序列中刪掉所有輸入符號則可得到動作序列，這樣就可得到對偶。而要得到活動序列，就必須借助翻譯文法。 第5頁/共61頁6.2 6.2 語法制

9、導(dǎo)翻譯語法制導(dǎo)翻譯如果給定了一個翻譯文法，就得到一門語言，該語言中的每個句子都是一個活動序列。通過將每個活動序列的輸入序列與動作序列配對可得到對偶的集合，從而得到翻譯。這種對偶集合稱為由給定翻譯文法所定義的翻譯。例如：對偶(a+b*c, abc*+)就是算術(shù)表達(dá)式翻譯文法定義的一個翻譯。 翻譯文法的構(gòu)造方法可通過對輸入文法修改得到。對輸入文法的產(chǎn)生式，在其右部的適當(dāng)位置插入動作符號就形成翻譯文法。因此，翻譯文法產(chǎn)生的動作序列實(shí)際上是受輸入語言的文法控制的。按語法制導(dǎo)翻譯的方法來實(shí)現(xiàn)語言的翻譯，就要根據(jù)輸入語言的文法，分析各條產(chǎn)生式的語義，即分析他們要求計(jì)算機(jī)所完成的操作，分別編出完成這些操作的

10、子程序或程序段(稱為語義子程序或語義動作)，并把這些子程序或程序段的名字作為動作符號插入到輸入文法各產(chǎn)生式右部的適當(dāng)位置上，從而實(shí)現(xiàn)翻譯文法。 第6頁/共61頁6.3 6.3 自頂向下語法制導(dǎo)翻譯自頂向下語法制導(dǎo)翻譯 自頂向下的語法制導(dǎo)翻譯有遞歸下降翻譯和LL(1)翻譯。6.3.1 遞歸下降翻譯遞歸下降翻譯器的實(shí)現(xiàn)思路與遞歸下降分析基本相同，要求也一樣，即不能有左遞歸，頭符號集不能相交，只需在適當(dāng)?shù)奈恢貌迦雽?shí)現(xiàn)動作符號的子程序。 例如，算術(shù)表達(dá)式翻譯文法如下：(為輸出其后的符號串) E-E+T+ E-T T-T*F* T-F F-(E) F-ii由于文法中存在左遞歸，所以要修改文法，去掉左遞歸

11、，修改后文法為： E-T+T+ T-F*F* F-(E)|ii對應(yīng)于每個非終結(jié)符號的遞歸下降翻譯程序流程圖如圖6.1所示。T EINPUTSYM=下一個符號 T OUT(“+”) INPUTSYM=+ 出口 Y N 圖6.1(a) 處理E的遞歸下降翻譯程序流程圖 第7頁/共61頁6.3.1 6.3.1 遞歸下降翻譯遞歸下降翻譯F TINPUTSYM=下一個符號 F OUT(“+”) INPUTSYM=* 出口 Y N T FINPUTSYM=下一個符號 INPUTSYM=) 出口 Y N INPUTSYM=( INPUTSYM=下一個符號 Y N INPUTSYM=下一個符號 INPUTSYM

12、=i T ERRORERRORN 圖6.1(b) 處理T的遞歸下降翻譯程序流程圖 圖6.1(c) 處理F的遞歸下降翻譯程序流程圖 C語言翻譯程序 第8頁/共61頁6.3.2 LL(1)6.3.2 LL(1)翻譯器翻譯器 考慮下面的輸入文法： ac b c a c b 表6.1 輸入文法的LL(1)分析表 符符號號輸入符號輸入符號 abc#ABDabc# POP,PUSH(DcBa)POP,PUSH(Aa) POP,NEXTSYM POP,PUSH(b) POP,PUSH(b) POP,NEXTSYM POP,PUSH(c)POP,PUSH(Dc) POP,NEXTSYM ACCEPT 如果我們

13、在該輸入文法的適當(dāng)?shù)胤讲迦敕g所需要的動作符號，那么，可得到如下的翻譯文法： v awx cyz b cr am Cn s b第9頁/共61頁6.3.2 LL(1)6.3.2 LL(1)翻譯器翻譯器假定動作符號的動作是輸出動作標(biāo)記后面的符號串,其翻譯器的分析表構(gòu)造方法與第四章介紹的相同，只不過加入了動作符號。例如，對上面翻譯文法中的產(chǎn)生式：v awx cy其對應(yīng)的輸入文法的產(chǎn)生式為： ac原來輸入文法的分析表元素為：MA，a= POP,PUSH(DcBa)則翻譯文法的分析表元素為：MA，a= POP,PUSH(zDycxBwav)符符號號 輸入符號輸入符號 abc#ABDabc# POP,PU

14、SH(zDycxBwav)POP,PUSH(Ama) POP,NEXTSYM POP,PUSH(b) POP,PUSH(bs) POP,NEXTSYM POP,PUSH(rc)POP,PUSH(nDc) POP,NEXTSYM ACCEPT 表6.2 翻譯文法的LL(1)分析表 對于翻譯文法，動作符號像其它符號一樣入棧。但當(dāng)動作符號處于棧頂時，無論當(dāng)前的輸入符號是什么，都要執(zhí)行由該動作符號所規(guī)定的操作，并將該動作符號從棧頂彈出，且不移動讀符號指針。 第10頁/共61頁6.3.2 LL(1)6.3.2 LL(1)翻譯器翻譯器假如翻譯器的分析棧的棧頂符號為A A，且當(dāng)前輸入符號為a a，那么將發(fā)生

15、的動作是彈出A A，zDycxBwAvzDycxBwAv入棧。由于此時棧頂為動作符號vv，因此vv出棧，并執(zhí)行由該動作符號所規(guī)定的操作，對于該符號串翻譯文法就是要輸出v v，即out(v)out(v)。緊接著，a a出棧，讀下一個符號。然后，動作符號ww為棧頂，因此ww出棧，并執(zhí)行由該動作符號所規(guī)定的操作，對于該符號串翻譯文法就是要輸出w w，即out(w)out(w)。此時棧的情況和語法語義分析動作如圖6.26.2所示。 aA.#v a w B.#B.#v出棧并執(zhí)行，a出棧，w出棧并執(zhí)行 圖6.2 棧頂?shù)膭幼鞣柍鰲２?zhí)行 將LL(1)分析擴(kuò)充為LL(1)語言的翻譯器，只需擴(kuò)充相應(yīng)分析表的動

16、作部分并具體實(shí)現(xiàn)完成每個動作符號的子程序，就可得到翻譯文法所確定語言的翻譯程序。下面對翻譯文法的LL(1)翻譯的總控程序總結(jié)： 1） 當(dāng)翻譯器的控制執(zhí)行程序根據(jù)棧頂符號和當(dāng)前輸入符號查該表得到元素為空時，則轉(zhuǎn)錯誤處理程序。 2)若控制執(zhí)行程序識別棧頂符號為動作符號時，不管當(dāng)前輸入符號是什么，將該動作符號從棧中彈出并轉(zhuǎn)相應(yīng)的子程序以完成所需的翻譯。對于符號串翻譯文法，其語義動作為輸出動作符號中的符號串。 第11頁/共61頁6.4 6.4 屬性翻譯文法屬性翻譯文法 我們見到的文法的所有符號(非終結(jié)符號,終結(jié)符號,動作符號)都沒有值的概念。而屬性文法中的符號可以有值,這個值就叫做該符號的屬性。 在詞

17、法分析中,所有無符號整數(shù)這一類單詞符號都用NUM作為記號,而具體的數(shù)值實(shí)際是符號NUM的屬性。如對于表達(dá)式3+5，經(jīng)詞法分析輸出為NUM3 + NUM5,其中3和5就是屬性的表示，意味著第一個NUM符號的值是3，第二個NUM符號的值是5。符號不但可以有屬性，而且其屬性還有類型。符號的屬性分綜合屬性和繼承屬性兩種。 第12頁/共61頁6.4.1 6.4.1 綜合屬性綜合屬性 假設(shè)我們要設(shè)計(jì)一個語法分析程序，該語法分析程序接受算術(shù)表達(dá)式，并通過添加動作符號輸出這個表達(dá)式的值。能夠完成輸出表達(dá)式值的符號串翻譯文法如下： SEANSWER EE+T ET TT*F TF F(E) FNUM 文法中的動

18、作符號ANSWER的動作是輸出表達(dá)式的計(jì)算結(jié)果。比如對于3+2*3，希望能得到結(jié)果9?，F(xiàn)在的問題是如何將表達(dá)式的值傳遞給動作符號ANSWER呢？ 假設(shè)對于表達(dá)式3+2*3，詞法分析后的結(jié)果如下： NUM3+ NUM2* NUM3 其中NUM代表無符號整數(shù)， “數(shù)字串”是該符號的屬性部分，對應(yīng)于原表達(dá)式，可見詞法分析將所有無符號整數(shù)用一個統(tǒng)一符號NUM表示，而具體的數(shù)值則在屬性中體現(xiàn)。根據(jù)所給定的翻譯文法，可畫出該輸入符號串的語法樹如圖6.3(a)所示。 第13頁/共61頁6.4.1 6.4.1 綜合屬性綜合屬性SET+EANSWER F*TTFNUM3 FNUM2 NUM3 圖6.3(a) N

19、UM3+ NUM2* NUM3的語法樹 NUM3 SE9 T6 +E3 ANSWER9 F3 *T2 T3 F3 F2 NUM2 NUM3 圖6.3(a) NUM3+ NUM2* NUM3的語法樹 第14頁/共61頁6.4.1 6.4.1 綜合屬性綜合屬性為了計(jì)算表達(dá)式的值，我們要先分別計(jì)算各子表達(dá)式的值，然后再計(jì)算父表達(dá)式的值，直到求得整個表達(dá)式的值。語法樹中非終結(jié)符E、T、F的每次出現(xiàn)都表示該輸入表達(dá)式的一個子表達(dá)式，所以其值部分應(yīng)是其子表達(dá)式的計(jì)算結(jié)果。根據(jù)這個思想，若有產(chǎn)生式FNUM，TF，則F的值部分應(yīng)等于NUM的值部分，T的值部分應(yīng)等于F的值部分。同理：若有產(chǎn)生式EE+T，則產(chǎn)生式

20、左邊的E的值部分等于產(chǎn)生式右邊E的值部分加上T的值部分，其余類推。從語法樹上看，F(xiàn)、T、E這些符號的屬性符合自底向上的求值法則，所以用表示。最后對文法的第1個產(chǎn)生式，提供這樣的規(guī)則，即ANSWER的值部分等于E的值部分，這不符合自底向上的求值法則，所以，我們引進(jìn)一個向下的箭頭表示動作符號ANSWER的屬性值。這樣，就可自底向上地將代表子表達(dá)式的計(jì)算結(jié)果作為屬性分別加到各非終結(jié)符上，從而得到圖6.3(b)所示的帶有屬性計(jì)算的語法樹。 第15頁/共61頁6.4.1 6.4.1 綜合屬性綜合屬性為了形式地表示上述表達(dá)式的求值過程，必須改寫每一個產(chǎn)生式，使得對出現(xiàn)在產(chǎn)生式中的每個屬性值都給它一個不同的

21、名字，并使用這些名字定義這個產(chǎn)生式中各符號的屬性之間的關(guān)系即屬性求值規(guī)則。上述計(jì)算表達(dá)式值的符號串翻譯文法可改寫為(右邊為屬性求值規(guī)則)： SEqANSWERrr=q Ep Eq+ Trp=q+r Ep Tq p=q Tp Tq* Frp=q*r Tp Fqp=q Fp (Eq)p=q Fp NUMq p=q 產(chǎn)生式中出現(xiàn)的p、q、r稱為屬性變量名，且規(guī)定屬性變量名都局部于每個產(chǎn)生式。在圖6.3(b)所示的語法樹中，每個非終結(jié)符的屬性值都是由它下面的那些符號來確定。這種可通過自底向上進(jìn)行求值的屬性，就稱為綜合屬性，用“”來表示。對于處于語法樹葉結(jié)點(diǎn)的終結(jié)符號，其綜合屬性具有初始值。如圖6.3(

22、b)中的NUM3，綜合屬性3由詞法分析給出。 第16頁/共61頁6.4.2 6.4.2 繼承屬性繼承屬性 在圖6.3(b)所示語法樹，其中動作符號ANSWER的屬性來源于左邊非終結(jié)符號E的屬性，這不符合自底向上的求值法則，所以，我們用一個向下的箭頭表示該動作符號的屬性值，這就是繼承屬性的一個例子。 考慮下列聲明語句文法 TYPE Id ; ，Id 其中TYPE代表類型，其值可為INT或 REAL或BOOL。 假設(shè)詞法分析程序在輸出單詞符號時，對變量名V除返回一個單詞記號外，同時返回一個值部分，它就是變量名。在返回TYPE的同時還返回其類型值。 第17頁/共61頁6.4.2 6.4.2 繼承屬性

23、繼承屬性 語法分析程序在處理該聲明語句時，假定調(diào)用SET_TYPE過程。該過程根據(jù)TYPE的屬性(即具體類型)確定變量的類型，并輸出變量名及類型。調(diào)用SET_TYPE的時間是語法分析程序在讀到一個變量之后，該調(diào)用時間可用以下的翻譯文法來描述，此文法使用動作符號SET_TYPE來表示調(diào)用SET_TYPE。 (1) TYPE ID SET_TYPE ; (2) ，IDSET_TYPE (3) 過程SET_TYPE需要兩個參數(shù)：一個是變量名，另一個是變量的類型，那么，從文法上看，動作符號SET_TYPE有兩個屬性。因此，動作符號SET_TYPE形式為：SET_TYPE變量名，類型其中動作符號后面帶有

24、兩個屬性，即變量名和類型。 第18頁/共61頁6.4.2 6.4.2 繼承屬性繼承屬性 用屬性變量來表示符號的屬性，對第1個產(chǎn)生式，TYPE和ID的屬性值可由詞法分析程序的返回值得到。對第二個產(chǎn)生式，除從詞法分析程序得到V的屬性值(變量名)以外，無法求得動作符號SET_TYPE和變量表的表示類型的屬性值。為了解決這一問題，可令第2個產(chǎn)生式左邊的變量表的屬性值等于第1個產(chǎn)生式右邊變量表的屬性值。這樣，上述翻譯文法可寫成(包括屬性求值規(guī)則)： 1) TYPEtIDnSET_TYPEn1,t1 ；t2=t，t1=t ，n1=n 2) ，IDnSET_TYPEn1,t1 t2=t，t1=t ，n1=n

25、 3 ) 如果輸入符號串為“INT a,b ；” ，詞法分析后輸出為“TYPEint Ida Idb ；” ，則帶有屬性的語法樹如圖6.4所示。我們把這種按自頂向下或自左向右的方式求得的屬性稱為繼承屬性。對這種屬性在其前面冠以“”表示。 聲明語句 ；SET_TYPEa, int IDa TYPEint 變量表int SET_TYPEa, int IDa 變量表int ， 圖6.4 ，“TYPEint Ida Idb ；”的語法樹 第19頁/共61頁6.4.3 6.4.3 屬性翻譯文法屬性翻譯文法 當(dāng)翻譯文法的符號具有屬性，并帶有屬性求值說明時，就稱為屬性翻譯文法。其具體定義如下：1)文法的每個

26、終結(jié)符、非終結(jié)符和動作符號都可以有一個有窮的屬性集。 2)每個非終結(jié)符和動作符號屬性可分為綜合屬性和繼承屬性。3)繼承屬性的求值規(guī)則： 開始符號的繼承屬性具有初始值。 對產(chǎn)生式左部的非終結(jié)符，其繼承屬性則繼承前面產(chǎn)生式中該符號已有的繼承屬性值。 右部的符號，其繼承屬性由產(chǎn)生式中其它符號屬性值進(jìn)行計(jì)算。4)綜合屬性的求值規(guī)則： 對終結(jié)符號其綜合屬性具有指定的初始值。在具體實(shí)現(xiàn)中，該初始值將由詞法分析程序提供。 產(chǎn)生式右部的非終結(jié)符號的綜合屬性值，則取后面以該非終結(jié)符號為產(chǎn)生式左部時求得的綜合屬性值。 產(chǎn)生式的左部的非終結(jié)符號的綜合屬性值，由產(chǎn)生式中左部或右部的某些符號的屬性值進(jìn)行計(jì)算。 給定一動

27、作符號，其綜合屬性值將用該動作符號的其它屬性值進(jìn)行計(jì)算。 第20頁/共61頁6.4.3 6.4.3 屬性翻譯文法屬性翻譯文法在構(gòu)造屬性翻譯文法的產(chǎn)生式時，我們將每個符號的屬性都用一個標(biāo)識符表示，并稱該標(biāo)識符為屬性變量名。用“屬性變量名”表示綜合屬性，用“屬性變量名”表示繼承屬性。例如，一翻譯文法有產(chǎn)生式 XbYZ 可寫成 Xpq,rbsYyuZvw其屬性求值規(guī)則為：q=sin(u+w)，r=s*u , v=s*u，y=p，w=v屬性翻譯文法生成帶有屬性的活動序列。屬性活動序列又分為屬性輸入序列和屬性動作序列。根據(jù)屬性翻譯文法可構(gòu)造出由該文法所定義的任一屬性活動序列的屬性翻譯樹。開始符號的繼承屬

28、性和終結(jié)符號的綜合屬性賦予給定的初始值，然后根據(jù)屬性求值規(guī)則自頂向下和自底向上地計(jì)算語法樹中間結(jié)點(diǎn)的各種屬性值，并附加到語法樹的相應(yīng)結(jié)點(diǎn)上，該過程直到再不能計(jì)算時為止。如果通過上述屬性求值過程，使語法樹上的所有符號的屬性變量都能得到賦值，則稱該樹是完整的；否則是不完整的。 給定一屬性翻譯文法，由該文法可得到由屬性輸入符號和動作符號所組成的屬性活動序列，這個屬性活動序列的動作符號序列稱為對屬性輸入序列的翻譯。從屬性翻譯文法得到的屬性輸入序列和動作序列組成的對偶稱為由該屬性翻譯文法所定義的屬性翻譯。如果屬性翻譯文法是非二義性的，則每個屬性輸入序列至多有一棵語法樹，并至多有一個屬性翻譯。 第21頁/

29、共61頁6.4.46.4.4屬性翻譯文法舉例屬性翻譯文法舉例算術(shù)表達(dá)式的翻算術(shù)表達(dá)式的翻譯譯 假定這個屬性翻譯文法的輸出是四元組代碼。要求翻譯程序產(chǎn)生的四元組具有下面的性質(zhì) 1)輸出符號串中的每個雙目運(yùn)算都用一個四元式表示。2)四元組中的四元式的順序與執(zhí)行時要完成的運(yùn)算順序相同。3)每個四元式有三個參數(shù)，自左向右的順序?yàn)?左操作數(shù)，右操作數(shù)，運(yùn)算結(jié)果。 例如， 翻譯器處理表達(dá)式a+b將生成如下的四元式 ADD , a , b , t1 其中t1是臨時變量，保存表達(dá)式的結(jié)果。 對于表達(dá)式：a+a*b，經(jīng)詞法分析后應(yīng)為IDa*IDa + IDb，其中ID代表標(biāo)識符。希望經(jīng)屬性翻譯文法能輸出： MU

30、LT , a , b , t1 ADD , a , t1 , t2 第22頁/共61頁6.4.46.4.4屬性翻譯文法舉例屬性翻譯文法舉例算術(shù)表達(dá)式的翻算術(shù)表達(dá)式的翻譯譯下面根據(jù)上述要求進(jìn)行翻譯程序的設(shè)計(jì)：第一步先設(shè)計(jì)滿足上述要求翻譯文法：對規(guī)則E-E+T添加動作符號ADD成為：E-E+TADD；對T-T*F添加動作符號MULT成為：T-T*FMULT;得到的翻譯文法如下：EE+TADDETTT*FMULTTFF(E)FID 第23頁/共61頁6.4.46.4.4屬性翻譯文法舉例屬性翻譯文法舉例算術(shù)表達(dá)式的翻算術(shù)表達(dá)式的翻譯譯第二步，構(gòu)造屬性和求值規(guī)則，把翻譯文法構(gòu)造成屬性翻譯文法。1)令每個

31、非終結(jié)符有一個綜合屬性，該屬性為一個臨時變量，保存由它產(chǎn)生的表達(dá)式的結(jié)果。2)輸入符號ID有一個綜合屬性，它是該符號的變量名。3)每個動作符號有三個繼承屬性，它們分別是指向左操作數(shù)、右操作數(shù)和運(yùn)算結(jié)果。E為文法的開始符號，則實(shí)現(xiàn)這個方案的屬性翻譯文法如下：Ex -Eq +Tr ADDy,z,t ， y=q, z=r, t=NEWV，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其中，NEWT是一個函數(shù)，每次調(diào)用它時返回一個新的臨時變量名，臨時變量名按產(chǎn)

32、生順序分別為t1、t2、等等。動作符號ADDy,z,t 輸出“ADD y,z,t”，動作符號MULTy,z,t 輸出 “MULT y,z,t”第24頁/共61頁6.4.46.4.4屬性翻譯文法舉例屬性翻譯文法舉例算術(shù)表達(dá)式的翻算術(shù)表達(dá)式的翻譯譯為了說明這些動作符號與特定的語法樹有關(guān)的屬性，圖6.5給出了對輸入符號串a(chǎn)+a*b翻譯的屬性語法樹。 IDa Et2 Tt1 +Ea Fb *Ta Ta Fa Fa IDa IDb 圖6.5 表達(dá)式a+a*b的屬性語法樹 MULTa,b,t1 ADDa,t1,t2 產(chǎn)生新變量t2 產(chǎn)生新變量t1 第25頁/共61頁6. 5 6. 5 屬性文法的自頂向下翻

33、譯屬性文法的自頂向下翻譯 屬性翻譯文法由翻譯文法和有關(guān)的屬性計(jì)算規(guī)則組成。如果屬性計(jì)算規(guī)則給的不當(dāng)，就不能保證所有的屬性計(jì)算出來。那么如何才能保證所有屬性都能計(jì)算出來呢？對于不同的分析方法有不同的要求，下面我們介紹對于自頂向下的分析方法，如何保證所有屬性能計(jì)算出來，這就是L-屬性翻譯文法 6.5.1 L-屬性翻譯文法 L-屬性的作用是保證可以按照自頂向下的有序方式來計(jì)算屬性值，即按照自頂向下的有序方式對某個屬性求值時,所需要的基本值已知。一屬性翻譯文法稱為L-屬性的，當(dāng)且僅當(dāng)下面三個條件成立：1)給定一產(chǎn)生式，其右部符號的繼承屬性值是以左部符號的繼承屬性或出現(xiàn)在給定符號左邊的產(chǎn)生式右部符號的任

34、意屬性為變元的函數(shù)。2)給定一產(chǎn)生式，其左部符號的綜合屬性值是以左部符號的繼承屬性或某個右部符號的任意屬性為變元的函數(shù)。3)給定一動作符號，其綜合屬性值是以該動作符號的繼承屬性為變元的函數(shù)。 將L-屬性翻譯文法與前面6.4.3小節(jié)的屬性文法定義比較可以發(fā)現(xiàn)： 1)是對繼承屬性求值規(guī)則第條的限制；2)是對綜合屬性求值規(guī)則第條的限制；3)是對綜合屬性求值規(guī)則第條的限制；在L屬性文法中沒有對初始化規(guī)則加以限制。 第26頁/共61頁6.5.1 L-6.5.1 L-屬性翻譯文法屬性翻譯文法 如果一個求值規(guī)則滿足上述三個條件中的任何一個，那么稱該求值規(guī)則為L-屬性的。如果一產(chǎn)生式或動作符號的所有屬性的求值

35、規(guī)則都是L-屬性的，那么稱該產(chǎn)生式或動作符號是L-屬性的。因此，如果一個屬性文法的所有產(chǎn)生式和動作符號都是L-屬性的，那么該屬性文法是L-屬性翻譯文法。 例如，文法中有產(chǎn)生式為： AI1S2,S3BI4CS5DS6I7,I8EI9那么，根據(jù)L-屬性的限制條件，I4=F(I1)、 I4=123、 I7=G(I1)合法，而I4=H(S2)、 I4=K(S6,I4)則不合法。 L-屬性翻譯文法中的條件1的重要性在于：使符號的繼承屬性只依賴于該符號左邊的信息(“L-屬性”中的“L”表示左邊的意思)。這有利于自頂向下地對屬性求值。因?yàn)槊總€符號都是在它右邊的輸入符號讀入之前進(jìn)行處理，而條件2和3是保證在求

36、值過程中避免出現(xiàn)循環(huán)依賴性。綜合上述，L屬性的三個條件保證了當(dāng)我們按自頂向下的方式進(jìn)行翻譯時，所有屬性值都能夠被計(jì)算。對于形式為ABC的產(chǎn)生式，A、B和C的屬性可以按下面的順序進(jìn)行求值 1) A的繼承屬性；2) B的繼承屬性；3) B的綜合屬性； 4) C的繼承屬性；5) C的綜合屬性；6) A的綜合屬性。 第27頁/共61頁6.5.2 L-6.5.2 L-屬性文法翻譯的實(shí)現(xiàn)屬性文法翻譯的實(shí)現(xiàn)遞歸下降遞歸下降翻譯翻譯 1)若該非終結(jié)符具有屬性，那么該非終結(jié)符的分析過程就有形參，且形參的數(shù)目就是該非終結(jié)符的屬性個數(shù)。 2)對于繼承屬性，采用值形參的傳參方式將繼承屬性值傳入被調(diào)過程，即在過程調(diào)用中

37、所對應(yīng)的實(shí)在參數(shù)是繼承屬性的值。 3)對于綜合屬性，采用變量形參的傳參方式以便將值回傳給主調(diào)過程，即所對應(yīng)的實(shí)在參數(shù)是一個變量，在過程返回之前，把綜合屬性的值賦給這個變量。如果用C語言實(shí)現(xiàn)屬性文法的翻譯，可用指針變量代表綜合屬性的形參。 為了進(jìn)行屬性翻譯的程序設(shè)計(jì)，我們采用下述約定： 1) 可以把屬性產(chǎn)生式中的屬性名字用作變量和參數(shù)的名字。這樣可以將屬性的命名和遞歸下降過程的實(shí)現(xiàn)聯(lián)系起來。 2) 除屬性翻譯使用的常用記法約定以外，還必須加上一些屬性命名約定。這些約定是：所有出現(xiàn)在左部的同名非終結(jié)符，應(yīng)具有相同的屬性名表。在左部同名非終結(jié)符屬性名表的同一化過程中，屬性名稱的改動范圍僅局限于產(chǎn)生式

38、左部。為了保證一致性，左部屬性重新命名以后，可使用新的記法約定來簡化或刪去某些屬性求值規(guī)則。 3) 如果兩個屬性有相同的值，那么可給它們相同的名字，但對于左部符號的屬性值相等時，不能改變成相同的名字。 第28頁/共61頁例如，產(chǎn)生式 Lab-e i Rj ， i,j=b,a=i+2 L xy-H zw ， w=y,z=2,x=z+y 按約定的第2條，必須改成 L ab-e iiRj ， i,j=b,a=j+2 L ab-H zw ， w=b,z=2,a=z+b注意當(dāng)x、y改成a，b后，相應(yīng)的屬性求值規(guī)則中涉及x、y的屬性名也要進(jìn)行變化。 而對規(guī)則S-AaB bC c ，當(dāng)b，c=a時，可寫成S

39、-A a B a C a對規(guī)則La-A bf c ，當(dāng)a=b,c=b時，也可寫成L a -A a f a但對規(guī)則Lab-aBcCd ,當(dāng)c,d=a時，可寫成L ab -aB a C a但當(dāng)b=a時，不能寫成Laa-aB a C a這是因?yàn)樽蟛糠墙K結(jié)符號的屬性將作為該非終結(jié)符號分析過程的形參，而一個過程的形參不能重名，如過程L(int a,int b)不可寫成L(int a,int a)。 6.5.2 L-6.5.2 L-屬性文法翻譯的實(shí)現(xiàn)屬性文法翻譯的實(shí)現(xiàn)遞歸下降遞歸下降翻譯翻譯 第29頁/共61頁6.5.2 L-6.5.2 L-屬性文法翻譯的實(shí)現(xiàn)屬性文法翻譯的實(shí)現(xiàn)遞歸下降遞歸下降翻譯翻譯 下

40、面給出采用C語言編寫屬性翻譯程序時采用的方法：1)形式參數(shù)：產(chǎn)生式左部非終結(jié)符的屬性名表設(shè)計(jì)成相應(yīng)過程的形式參數(shù)表。將繼承屬性的形參名說明為值形參(即簡單變量)，綜合屬性形參名說明為指針變量。2)局部變量：在產(chǎn)生式中，與在左部出現(xiàn)的屬性名不同的屬性名變成相應(yīng)過程的局部變量。3)非終結(jié)符的代碼：對應(yīng)于右部出現(xiàn)的每個非終結(jié)符的過程調(diào)用，該非終結(jié)符的屬性作為實(shí)參。要注意：如果實(shí)參是簡單變量，形參是指針變量，調(diào)用時實(shí)參應(yīng)為簡單變量的地址。4)輸入符號的代碼：對文法中出現(xiàn)的每個輸入符號(即終結(jié)符號)，將賦值語句插入到過程中它所對應(yīng)的NEXTSYM之前，把保存在讀符號程序NEXTSYM中的終結(jié)符號屬性(某

41、個全局變量中)賦給輸入符號屬性中的每個屬性變量。5)動作符號的代碼：對出現(xiàn)在文法中的每個動作符號，插入代碼便于對動作符號的綜合屬性進(jìn)行計(jì)算，并且把結(jié)果賦給對應(yīng)于該綜合屬性的變量，然后輸出相應(yīng)的符號。第30頁/共61頁6.5.2 L-6.5.2 L-屬性文法翻譯的實(shí)現(xiàn)屬性文法翻譯的實(shí)現(xiàn)遞歸下降遞歸下降翻譯翻譯 6)屬性規(guī)則的代碼：與每個產(chǎn)生式有關(guān)的屬性求值規(guī)則，插入其代碼以便對屬性求值規(guī)則的右部求值，并把結(jié)果賦給該規(guī)則左部的每個變量。可以把這些代碼放在屬性計(jì)算規(guī)則的所有自變量已知之后，且函數(shù)值被使用之前的任何地方。7)主程序：C語言都是從MAIN函數(shù)開始運(yùn)行。在MAIN函數(shù)中，對文法的開始符號，

42、其相應(yīng)的每一個綜合屬性的名字變成主程序的局部變量，然后調(diào)用開始符號對應(yīng)的過程。在調(diào)用時，如果實(shí)參對應(yīng)開始符號的繼承屬性，則對每個繼承屬性以該屬性的初始值作為值參傳入，對每個綜合屬性取該屬性的局部變量的地址傳入。 EtTpEptEpt+Tr ADDp,r,t0 E t0t t0=NEWT Ept t=pTtFpTptTpt*Fr MULTp,r,t0 Tt0t t0=NEWT Tpt t=pFp -(Ep) | IDp 下面，以算術(shù)表達(dá)式的屬性翻譯文法為例，用C語言實(shí)現(xiàn)屬性翻譯器。算術(shù)表達(dá)式屬性翻譯文法如下：第31頁/共61頁6.5.2 L-6.5.2 L-屬性文法翻譯的實(shí)現(xiàn)屬性文法翻譯的實(shí)現(xiàn)遞

43、歸下降遞歸下降翻譯翻譯 主程序：C語言都是從MAIN函數(shù)開始運(yùn)行。在MAIN函數(shù)中，對文法的開始符號，其相應(yīng)的每一個綜合屬性的名字變成主程序的局部變量，然后調(diào)用開始符號對應(yīng)的過程。在調(diào)用時，如果實(shí)參對應(yīng)開始符號的繼承屬性，則對每個繼承屬性以該屬性的初始值作為值參傳入，對每個綜合屬性取該屬性的局部變量的地址傳入。 EtTpEpt/主程序main()int es=0,t; printf(請輸入算術(shù)表達(dá)式(操作數(shù)只能是單個字母)：);ch=getchar();printf(輸出四元式為：n);es=E(&t);/調(diào)分析表達(dá)式E的翻譯程序if (es=0) printf(n翻譯成功!n);el

44、se printf(n表達(dá)式有語法錯誤!n);第32頁/共61頁6.5.2 L-6.5.2 L-屬性文法翻譯的實(shí)現(xiàn)屬性文法翻譯的實(shí)現(xiàn)遞歸下降遞歸下降翻譯翻譯 /產(chǎn)生式EtTpEp的翻/譯子程序，t為綜合屬性,形參/用指針變量int E(int *t) int es=0; int p; es=T(&p);/調(diào)分析T子程序 es=E1(p,t);/調(diào)分析E1子程序 return(es);E(int *t)Int pT(&p)E(p,t)return第33頁/共61頁/產(chǎn)生式Ept+Tr ADDp,r,t Et0t 和Ept翻譯子程序/p為繼承屬性,形參用整型變量,t為綜合屬性,形參

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

46、,t0;+?nextsymT(&r)t0=NEWT()E(t0,t)return*t=pNy第34頁/共61頁6.5.2 L-6.5.2 L-屬性文法翻譯的實(shí)現(xiàn)屬性文法翻譯的實(shí)現(xiàn)遞歸下降遞歸下降翻譯翻譯 /產(chǎn)生式TpFpTp的翻譯子程序，t為綜合屬性,形參用指針變量int T(int *t) int es=0,p; es=F(&p);/調(diào)分析F子程序 es=T1(p,t);/調(diào)分析T1子程序 EpTpEp return(es);T(int *t)Int pF(&p)T(p,t)return第35頁/共61頁/產(chǎn)生式Tpt*Fr MULTp,r,t E 和Tpt翻譯子程序

47、/p為繼承屬性,形參用整型變量,t為綜合屬性,形參用指針變量int T1(int p,int *t) int r,es,t0;if (ch=*) ch=getchar(); es=F(&r); t0=NEWT();/產(chǎn)生一個臨時變量 printf( MULT %c,%c,%cn,p,r,t0); es=T1(t0,t); return(es); else *t=p; return(0);6.5.2 L-6.5.2 L-屬性文法翻譯的實(shí)現(xiàn)屬性文法翻譯的實(shí)現(xiàn)遞歸下降遞歸下降翻譯翻譯 T(int p,int *t)Int r,t0;*?nextsymF(&r)t0=NEWT()F(t

48、0,t)return*t=pNy第36頁/共61頁6.5.2 L-6.5.2 L-屬性文法翻譯的實(shí)現(xiàn)屬性文法翻譯的實(shí)現(xiàn)遞歸下降遞歸下降翻譯翻譯 /產(chǎn)生式Fp -(Ep) | ip的翻譯子程序，p為綜合屬性,形參用指針變量int F(int *p)/分析F子程序 int es=0; if (ch=( ) ch=getchar(); es=E(p);/調(diào)分析E子程序 if (ch!=) return(3); else ch=getchar();return(es); else if (isalpha(ch) /判斷是否為字母 *p=ch; ch=getchar(); return(es); els

49、e return(4); F(int *p)(?nextsymE(p)nextsymreturn*p=chNy)?nextsym字母?yy第37頁/共61頁6.5.2 L-6.5.2 L-屬性文法翻譯的實(shí)現(xiàn)屬性文法翻譯的實(shí)現(xiàn)遞歸下降遞歸下降翻譯翻譯 其中，NEWT是一個函數(shù)，每次調(diào)用它時返回一個新的臨時變量名，為了編程方便，臨時變量名按產(chǎn)生順序分別為A、B、等等。動作符號ADDy,z,t 輸出 ADD y,z,t，而MULTy,z,t 輸出 MULT y,z,t。ID的屬性p只能是一個小寫字母，表示表達(dá)式中的操作數(shù)都是變量，且變量名只能是一個小寫字母，如a+b、c*d都可以。這個屬性翻譯文法是

50、6.4.4小節(jié)的屬性翻譯文法去掉左遞歸后得到的，由于用擴(kuò)充的BNF表示無法進(jìn)行屬性的表示，所以，改成了右遞歸的形式。對于產(chǎn)生式EtTpEpt ,左部符號E有一個綜合屬性，因此，子程序的形參用指針變量，形式為：int E(int *t)；而對于產(chǎn)生式Ept+Tr ADDp,r,t0 Et0t,左部符號E有一個綜合屬性p、一個繼承屬性t，因此，子程序有兩個形參，一個用指針變量，另一個為整型變量，形式為：int E1(int p,int *t)，其它產(chǎn)生式的子程序也是如此 。具體實(shí)現(xiàn)C程序 ,運(yùn)行這段程序，輸入：a*(b+c)+b*d輸出四元式序列為：其中A、B、C、D都是臨時變量。 ADD b,c

51、,AMULT a,A,BMULT b,d,CADD B,C,D第38頁/共61頁6.5.3 L-6.5.3 L-屬性文法翻譯的實(shí)現(xiàn)屬性文法翻譯的實(shí)現(xiàn)LL(1)LL(1)法法 在前面翻譯文法的LL(1)翻譯器的基礎(chǔ)上，進(jìn)一步對分析器擴(kuò)充，就可以實(shí)現(xiàn)對屬性翻譯文法的翻譯。對翻譯文法，允許動作符號入棧，當(dāng)棧頂是動作符號時，就執(zhí)行動作，同時棧頂動作符號出棧，從而構(gòu)造出翻譯文法的翻譯器。對于屬性翻譯文法，其擴(kuò)充方法是：對于所有符號，不僅符號進(jìn)分析棧，其屬性也同時進(jìn)棧。為此，對每個入棧的符號在棧中的表示(稱為棧符號)要進(jìn)行擴(kuò)充，將棧符號設(shè)計(jì)為兩部分，符號名和屬性域。任何棧符號的域都是在棧內(nèi)的一些存貯單元。

52、例如，對符號串ABC，假定A有兩個屬性，B有一個屬性而C沒有任何屬性。若符號名也占用一個存貯單元，則相應(yīng)A的棧符號用三個存貯單元，B用二個，C用一個。壓入堆棧以后的情況如圖6.6所示。其中“#”為棧底符號。 考慮如下文法： SEpANSWERr r=p Ep+EqErADDA1,A2R A1=q,A2=r,R=A1+A2,p=R Ep*EqErMULTA1,A2R A1=q,A2=r,R=A1*A2,p=R EpNUMq p=q 如何構(gòu)造該屬性翻譯文法的翻譯器呢？ A屬性 A1屬性 A2B屬性B1C#第39頁/共61頁首先，如果把屬性刪除，則該文法變成普通的符號串翻譯文法，那么，在LL(1)分

53、析器的基礎(chǔ)上加進(jìn)動作符號就可構(gòu)造出一個LL(1)翻譯器的分析表，實(shí)現(xiàn)由該符號串翻譯文法所定義的翻譯，如表6.3所示。該文法為符號串翻譯文法。所以當(dāng)動作符號處在棧頂時，不管輸入符號是什么，翻譯器將輸出動作符號中的符號串 符號 輸入符號 +*NUM#SE+*NUM#125 13 5 14 5 ACCEPT 表6.3 LL(1)翻譯器的分析表 1:POP,PUSH(ANSWER E)2:POP,PUSH(ADD E E+)3:POP,PUSH(MULT E E*)4:POP,PUSH(NUM)5:POP,NEXTSYM6.5.3 L-6.5.3 L-屬性文法翻譯的實(shí)現(xiàn)屬性文法翻譯的實(shí)現(xiàn)LL(1)LL

54、(1)法法 擴(kuò)充這個機(jī)器就可得到處理屬性文法的翻譯器，其方法如下。第40頁/共61頁6.5.3 L-6.5.3 L-屬性文法翻譯的實(shí)現(xiàn)屬性文法翻譯的實(shí)現(xiàn)LL(1)LL(1)法法 1、棧符號設(shè)計(jì)屬性文法的每個符號有屬性，所以每個符號入棧時，必須連屬性一起入棧，這樣，棧符號就由文法符號及存放該符號屬性的域所組成。由于屬性類型不同，屬性域存放的內(nèi)容就要根據(jù)屬性的類型來定。有的可能直接存放屬性值，也有的存放的是指向?qū)傩灾档闹羔?。對于綜合屬性，其屬性域不存放其屬性值，而是存放一個指針，指向存貯該屬性值的單元。對于繼承屬性，其屬性域直接保存其屬性值。繼承屬性的屬性域剛?cè)霔r為空，但是在該棧符號變成棧頂符號

55、之前的某一時刻，它們必須接受相應(yīng)的屬性值，即在成為棧頂時，繼承屬性的屬性域必須有值。對于本文法中出現(xiàn)的所有符號，其相應(yīng)的棧符號如圖6.7所示。 第41頁/共61頁6.5.3 L-6.5.3 L-屬性文法翻譯的實(shí)現(xiàn)屬性文法翻譯的實(shí)現(xiàn)LL(1)LL(1)法法 MULTMULT 繼承屬性繼承屬性1 1 繼承屬性繼承屬性2 2 綜合屬性指針綜合屬性指針 addadd繼承屬性繼承屬性1 1 繼承屬性繼承屬性2 2 綜合屬性指針綜合屬性指針 ANSWER 繼承屬性繼承屬性NUM NUMNUM屬性指針屬性指針EE E屬性指針屬性指針S SS的棧符號 E的棧符號 NUM的棧符號 ANSWER的棧符號 ADD的

56、棧符號 MULT的棧符號 圖6.7 棧符號 第42頁/共61頁6.5.3 L-6.5.3 L-屬性文法翻譯的實(shí)現(xiàn)屬性文法翻譯的實(shí)現(xiàn)LL(1)LL(1)法法 根據(jù)設(shè)計(jì)好的棧符號，我們可以對屬性翻譯文法構(gòu)造分析表，如表6.4所示。 符號 輸入符號 +*NUM#SE+*NUM#125 13 5 14 5 ACCEPT 表6.4 LL(1)翻譯器的分析表 1:POP,PUSH(ANSWERr Ep)2:POP,PUSH(ADDA1,A2R Er Eq+)3:POP,PUSH(MULTA1,A2R Er Eq*)4:POP,PUSH(NUMq),把NUM的屬性值q放入NUM的屬性域指向的單元.5:POP

57、,NEXTSYM 第43頁/共61頁6.5.3 L-6.5.3 L-屬性文法翻譯的實(shí)現(xiàn)屬性文法翻譯的實(shí)現(xiàn)LL(1)LL(1)法法 2、語義動作設(shè)計(jì)下面給出當(dāng)動作符號出現(xiàn)在棧頂時，根據(jù)翻譯的具體要求所要完成的語義動作。假定要求翻譯器所要完成的工作是計(jì)算由文法定義的表達(dá)式的值并輸出。那么三個動作符號的翻譯動作為：1) ADD：把頭兩個域的內(nèi)容相加，并把計(jì)算結(jié)果存貯在第三個域所指的單元中；POP；2) MULT：把頭兩個域的內(nèi)容相乘，并把積存貯在第三個域所指的單元中；POP；3) ANSWER：輸出屬性域的內(nèi)容結(jié)果；POP； 3、輸入符號串+NUM2NUM3#的分析過程為了理解LL(1)的工作過程中

58、對屬性的處理，“+NUM2NUM3#”對應(yīng)的表達(dá)式為+23，這是一種前綴表示。NUM為詞法分析輸出的整數(shù)記號。分析過程如下： 第44頁/共61頁6.5.3 L-6.5.3 L-屬性文法翻譯的實(shí)現(xiàn)屬性文法翻譯的實(shí)現(xiàn)LL(1)LL(1)法法 1)#入棧，文法的開始符號S入棧，輸入指針指向符號+，見圖6.8(a)。+NUM2 2NUMNUM2 2# # S# #符號棧： 圖6.8( a )+NUM2 2NUMNUM3 3# # E EppANSWERrr# #符號棧： 圖6.( b )2)查分析表S行+列，執(zhí)行動作POP,PUSH(ANSWERr Ep)：因?yàn)閞=p，所以，E屬性域p為指向ANSWE

59、R屬性r的指針，結(jié)果見圖6.8 (b)。 第45頁/共61頁6.5.3 L-6.5.3 L-屬性文法翻譯的實(shí)現(xiàn)屬性文法翻譯的實(shí)現(xiàn)LL(1)LL(1)法法 NUMNUM3 3# # E ErrADDADD2 2AA2 2RRANSWERrr# #符號棧： 圖6.8( d )4)查分析表E行NUM列，執(zhí)行動作POP,PUSH(NUMq)：E出棧前，E的屬性p指向ADD的屬性A1，而p等于NUM的屬性值q，所以，NUMq入棧，把NUM的屬性值2放入原來E出棧前的屬性p指向的單元，即ADD的屬性A1。然后，NUM符號出棧，讀下一個符號, 結(jié)果見圖6.8 (d)。 NUM2 2NUMNUM2 2# #

60、E EppE ErrADDADDAA1 1AA2 2RRANSWERrr# #符號棧： 圖6.8( c )3)查分析表E行+列，執(zhí)行動作POP,PUSH(ADDA1,A2R Er Eq+)：E出棧前，屬性p指向ANSWER的屬性r，因?yàn)镋的屬性p等于ADD的屬性R，所以ADD的屬性R也指向ANSWER的屬性r，對于新入棧的兩個E的屬性r和q，其屬性分別指向ADD的屬性A1和A2。然后，因棧頂為+，+出棧，讀下一個符號，結(jié)果見圖6.8 (c)。 第46頁/共61頁6.5.3 L-6.5.3 L-屬性文法翻譯的實(shí)現(xiàn)屬性文法翻譯的實(shí)現(xiàn)LL(1)LL(1)法法 # # ANSWER5 5# #符號棧： 圖6.8( f )6)棧頂為動作符號ADD：把頭兩個域的內(nèi)容2和