第6章語法制導翻譯技術Nocross,nocrown.

不經(jīng)歷風雨，怎么見彩虹.6.1翻譯文法6.2語法制導翻譯6.3自頂向下語法制導翻譯6.4屬性翻譯文法6.5屬性文法的自頂向下翻譯6.6自底向上語法制導翻譯第6章語法制導翻譯技術語法制導翻譯翻譯文法、屬性翻譯文法及其應用

學習重點第6章語法制導翻譯技術語義：是程序設計語言中按語法規(guī)那么所構成的各個語法成分的含義。例如以下Test語言代碼：{inta;b=a+1;writeb;}一個源程序經(jīng)歷了詞法分析與語法分析，說明它在書寫上和語法上是正確的，但不能保證其在語義上是正確。語義分析的任務：分析程序的含義，并作相應的語義處理。第6章語法制導翻譯技術語義分析的功能

②類型和運算合法性檢查：檢查運算的合法性與運算分量類型的一致性〔或相容性〕，必要時作相應的類型轉(zhuǎn)換。例如，a+b,要求a和b都是算術型〔整型或?qū)嵭汀?，當a和b不是同一種類型時，需進行類型轉(zhuǎn)換。①確定類型：確定標識符所關聯(lián)數(shù)據(jù)對象的數(shù)據(jù)類型〔有時由詞法分析完成〕。③識別含義：確定程序中各構造成分組合到一起的含義，并作相應的語義處理。這時對可執(zhí)行語句生成中間代碼或目標代碼。

第6章語法制導翻譯技術語義分析的功能

⑤一致性檢查：在很多程序設計語言中要求對象只能被說明一次。

④控制流檢查：控制流語句必須轉(zhuǎn)移到合法的地方。例如，在C語言中，break語句使得控制跳離包括該語句的while、for或switch語句，如果不存在包括它的這樣的語句，那么報告錯誤。⑥其它語義檢查：如對象的作用域等。第6章語法制導翻譯技術語義分析的實現(xiàn)

語義分析是以語法分析的輸出〔語法分析樹或其它等價的內(nèi)部中間表示〕作為輸入，輸出那么是中間代碼，甚至是目標代碼。一般情況下，語義分析僅產(chǎn)生中間代碼，即語義分析與目標代碼生成分成兩遍來進行。第6章語法制導翻譯技術語義往往是上下文有關的，只宜于用口語描述，語義形式化很困難。目前，比較流行的語義描述和語義處理方法是語法制導翻譯技術。語法制導翻譯技術根底：形式描述的屬性翻譯文法特點：把語法與語義分開，但又在語法分析的同時進行相應的語義工作提高了實用性6.1翻譯文法

例:設計一個翻譯器，它能將中綴表達式翻譯成波蘭后綴表達式。假設輸入串是a+b*c，那么問題:如何實現(xiàn)這個翻譯過程呢？a+b*c翻譯器abc*+輸入串輸出串先看輸入串a(chǎn)+b*c的推導過程:中綴表達式文法：①E→E+T ⑤F→(E)②E→T ⑥F→a③T→T*F⑦F→b④T→F⑧F→cEE+TE+T*FE+T*cE+F*cE+b*cT+b*cF+b*ca+b*c由推導過程EE+TE+T*FE+T*cE+F*cE+b*cT+b*cF+b*ca+b*c得到輸入串的語法樹：記住翻譯目標是：abc*+EE+TTT*FFEcba添加葉子結點，用@表示輸出操作〔輸出其后的字符〕。EE+TTT*FFEcba@b@a@c@*@+將@符號的葉子結點從左到右連起來，得到@a@b@c@*@+〔注意:這種帶有@的符號串稱為動作序列?！硤?zhí)行這個符號序列，得到abc*+這就是翻譯結果!EE+TTT*FFEcbaEE+TTT*FFEcba@b@a@c@*@+問題：如何得到這棵帶動作符號的語法樹呢？在中綴表達式文法〔輸入文法〕的根底上參加動作符號，得到翻譯文法。①E→E+T ⑤F→(E)②E→T ⑥F→a③T→T*F⑦F→b④T→F⑧F→c

①E→E+T@+⑤F→(E)②E→T⑥F→a@a③T→T*F@*⑦F→b@b④T→F ⑧F→c@c輸入文法翻譯文法例用輸入文法推導a+b*c的過程如下:EE+TE+T*FE+T*cE+F*cE+b*cT+b*cF+b*ca+b*c

用翻譯文法進行相同的推導:EE+T@+E+T*F@*@+E+T*c@c@*@+

E+F*c@c@*@+

E+b@b*c@c@*@+

T+b@b*c@c

@*@+

F+b@b*c@c@*@+

a@a+b@b*c@c@*@+①E→E+T ⑤F→(E)②E→T ⑥F→a③T→T*F⑦F→b④T→F⑧F→c

①E→E+T@+⑤F→(E)②E→T⑥F→a@a③T→T*F@*⑦F→b@b④T→F ⑧F→c@c輸入文法翻譯文法輸入序列活動序列將活動序列中的輸入序列去掉，得到動作序列：@a@b@c@*@+6.1翻譯文法

翻譯文法是上下文無關文法的推廣，是在描述語言文法規(guī)那么的右部適當位置參加語義動作得到的。為了區(qū)分文法符號與語義動作，在文法的表示中，將代表語義動作的符號前面加動作符號標記@來表示。輸入序列：用輸入文法通過推導可以得到的終結符號串?；顒有蛄校河梅g文法通過推導得到的符號串。動作序列：從某活動序列中去掉所有輸入序列，即由所有動作符號組成的符號串。6.1翻譯文法

6.1翻譯文法上例的翻譯文法可表示成：

G(E)={Vn,Vt,P,E}，其中Vn={E,T,F}Vt={a,b,c,+,*,

@+,@*,@a,@b,@c}

P={E→E+T@+，E→T，T→F，

F→a@a，

T→T*F@*,F→b@b，F(xiàn)→c@c}在高級程序設計語言的翻譯中有各種各樣的翻譯文法，其中的動作符號代表不同的語義動作。在翻譯文法中,如果@的動作就是輸出其后的符號,可稱該文法為符號串翻譯文法。符號串翻譯文法是翻譯文法中的一種特定類型。

6.2語法制導翻譯例：根據(jù)前面的算術表達式翻譯文法，對于輸入符號串a(chǎn)+b*c，推導出的活動序列為：a@a+b@b*c@c@*@+其中：a+b*c為輸入序列@a@b@c@*@+為動作序列如果執(zhí)行該動作序列中的動作，那么產(chǎn)生輸出序列abc*+，這就是輸入序列a+b*c的翻譯結果。由于這種翻譯結果是通過翻譯文法獲得的，所以就稱為語法制導翻譯。語法制導翻譯：就是給定一輸入序列，根據(jù)翻譯文法獲得翻譯該符號串的活動序列，從活動序列中別離出動作符號串，然后執(zhí)行該動作符號串所規(guī)定的動作，從而得到翻譯結果。6.2語法制導翻譯按語法制導翻譯的方法來實現(xiàn)語言的翻譯首先要根據(jù)輸入語言的文法，分析各條產(chǎn)生式的語義，即分析他們要求計算機所完成的操作。分別編出完成這些操作的子程序或程序段(稱為語義子程序或語義動作)把這些子程序或程序段的名字作為動作符號插入到輸入文法各產(chǎn)生式右部的適當位置上，從而實現(xiàn)翻譯文法。

6.3自頂向下語法制導翻譯自頂向下的語法制導翻譯有遞歸下降翻譯和LL(1)翻譯。遞歸下降翻譯：遞歸下降翻譯器的實現(xiàn)思路與遞歸下降分析根本相同，要求也一樣，即不能有左遞歸，頭符號集不能相交，只需在適當?shù)奈恢貌迦雽崿F(xiàn)動作符號的子程序。6.3自頂向下語法制導翻譯例算術表達式翻譯文法如下：

E→E+T@+E→TT→T*F@*T→FF→(E)F→i@i注：@為輸出其后的符號串。解：去掉文法中的左遞歸，修改后文法為：

E→T{+T@+}T→F{*F@*}F→(E)|i@i處理E的遞歸下降翻譯程序流程圖

處理T的遞歸下降翻譯程序流程圖

T→F{*F@*}處理F的遞歸下降翻譯程序流程圖

F→(E)|i@i6.3自頂向下語法制導翻譯自頂向下的語法制導翻譯有遞歸下降翻譯和LL(1)翻譯。LL(1)翻譯：LL(1)翻譯器的實現(xiàn)思路與LL(1)分析法根本相同，要求也一樣，即不能有左遞歸，頭符號集不能相交，只需在文法適當?shù)奈恢貌迦雽崿F(xiàn)動作符號的子程序，并在LL(1)分析表中參加相應的動作符號。6.3自頂向下語法制導翻譯例(P126)考慮下面的輸入文法：①A→aBcD②A→b③B→c④B→aA⑤D→cD⑥D(zhuǎn)→b

輸入文法的LL(1)分析表

設其翻譯文法為：①A→@va@wB@xc@yD@z②A→b③B→c@r④B→a@mA⑤D→cD@n⑥D(zhuǎn)→@sb6.3自頂向下語法制導翻譯翻譯文法的LL(1)分析表

注意：對于翻譯文法，動作符號像其它符號一樣入棧。但當動作符號處于棧頂時，無論當前的輸入符號是什么，都要執(zhí)行由該動作符號所規(guī)定的操作，并將該動作符號從棧頂彈出，且不移動讀符號指針。

6.3自頂向下語法制導翻譯假設翻譯器的分析棧的棧頂符號為A，且當前輸入符號為a，那么將發(fā)生的動作是彈出A，@zD@yc@xB@wa@v入棧。由于此時棧頂為動作符號@v，因此@v出棧，并執(zhí)行由該動作符號所規(guī)定的操作，對于該符號串翻譯文法就是要輸出v，即out(v)。緊接著，a出棧，讀下一個符號c。然后，動作符號@w為棧頂，因此@w出棧，并執(zhí)行由該動作符號所規(guī)定的操作，對于該符號串翻譯文法就是要輸出w，即out(w)。ac……#A..#@v

a

@w

B..#B..#@v出棧并執(zhí)行，a出棧，讀入c,@w出棧并執(zhí)行ac……#6.3自頂向下語法制導翻譯翻譯文法的LL(1)翻譯的總控程序總結：1)當翻譯器的控制執(zhí)行程序根據(jù)棧頂符號和當前輸入符號查該表得到元素為空時，那么轉(zhuǎn)錯誤處理程序。2)假設控制執(zhí)行程序識別棧頂符號為動作符號時，不管當前輸入符號是什么，將該動作符號從棧中彈出并轉(zhuǎn)相應的子程序以完成所需的翻譯〔執(zhí)行動作〕。對于符號串翻譯文法，其語義動作為輸出動作符號中的符號串。6.4屬性翻譯文法引例聲明語句文法： ①<聲明語句>→TYPEID<變量表>; ②<變量表>→，ID<變量表> ③<變量表>→ε

其中TYPE代表類型，其值可為int或real或bool。

問題：將輸入符號串“inta,b;”翻譯為:intaintb思考：能否通過在文法產(chǎn)生式右部添加動作符號實現(xiàn)該翻譯？6.4屬性翻譯文法引例聲明語句文法： ①<聲明語句>→TYPEID<變量表>; ②<變量表>→，ID<變量表> ③<變量表>→ε

其中TYPE代表類型，其值可為int或real或bool。

輸入：inta,b;輸出：intaintb輸入串inta,b;”的推導過程：<聲明語句>TYPEID<變量表>;TYPEID，ID<變量表>;TYPEID,ID問題：無法將文法符號TYPE、ID與輸入符號int、a、b關聯(lián)起來！6.4屬性翻譯文法6.4屬性翻譯文法

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

綜合屬性：綜合屬性的計算規(guī)那么是按“自下而上”方式進行，即文法產(chǎn)生式左部符號的某些屬性根據(jù)其右部符號的屬性和/或自己的其它屬性計算而得。在語法樹中，如果一個結點的某一屬性，其值由子結點的屬性值來計算，那么該屬性為綜合屬性。綜合屬性可用“↑”來表示。對終結符號其綜合屬性具有指定的初始值,該初始值由詞法分析程序提供。例Ap→Xq,rYs,tp=q+s,r=p+t其中，p是綜合屬性，r不是綜合屬性，q,s,t不能確定，需參考其它產(chǎn)生式的屬性計算規(guī)那么才能確定。6.4屬性翻譯文法

繼承屬性：繼承屬性的計算規(guī)那么是按“自上而下”方式進行，即文法產(chǎn)生式右部符號的某些屬性根據(jù)其左部符號的屬性和/或右部的其它符號的某些屬性計算而得。在語法中，如果一個結點的某一屬性，其值由該結點的父結點和/或兄弟結點的屬性值來計算，那么該屬性為繼承屬性。繼承屬性可用“↓”來表示。開始符號的繼承屬性具有初始值。例Ap→Xq,rYs,tp=q+s,r=p+t

顯然，r是繼承屬性。6.4屬性翻譯文法例算術表達式的屬性翻譯文法:①S→E↑q@ANSWER↓r r=q②E↑p→E↑q+T↑r

p=q+r③E↑p→T↑q

p=q④T↑p→T↑q*F↑r

p=q*r⑤T↑p→F↑q

p=q⑥F↑p→(E↑q) p=q⑦F↑p→NUM↑q

p=q

6.4屬性翻譯文法語義規(guī)那么(語義動作或翻譯子程序)：為輸入文法配備計算屬性的計算規(guī)那么，稱為語義規(guī)那么。如上例中，p=q+r就是語義規(guī)那么。產(chǎn)生式只能產(chǎn)生符號串，它并未指明所產(chǎn)生的符號串的含義是什么。語義規(guī)那么給出了一個產(chǎn)生式所產(chǎn)生的符號串的含義，而且還根據(jù)這種含義規(guī)定了對應的加工動作。這些加工動作包括查填各類表格、改變編譯程序的某些變量的值、打印各種錯誤信息以及生成中間形式代碼等。6.4屬性翻譯文法屬性翻譯文法〔或?qū)傩晕姆ā常簩τ谀硞€壓縮的上下文無關文法，當為文法符號引進一組屬性，且讓該文法中的產(chǎn)生式附加上語義規(guī)那么時，稱該上下文無關文法為屬性翻譯文法。6.4屬性翻譯文法語義分析的翻譯過程：步驟1分析輸入符號串，建立語法樹；步驟2從語法樹得到描述結點屬性間依賴關系的依賴圖，由此依賴圖得到語義規(guī)那么的計算次序；步驟3進行語義規(guī)那么計算，得到翻譯結果。語義分析翻譯過程的分類：自頂向下的翻譯自底向上的翻譯6.4屬性翻譯文法自頂向下的語義分析翻譯過程的例如聲明語句文法： ①<聲明語句>→TYPEID<變量表>; ②<變量表>→，ID<變量表> ③<變量表>→ε

其中TYPE代表類型，其值可為int或real或bool。

屬性翻譯文法：

1)<聲明語句>→TYPE↑tID↑n@SET_TYPE↓n1,t1<變量表t2>

；

t2=t，t1=t，n1=n2)<變量表↓t>→，ID↑n@SET_TYPE↓n1,t1<變量表↓t2

>

t2=t，t1=t，n1=n3)<變量表>→ε

其中，過程SET_TYPE輸出變量名及其類型。給出輸入符號串“inta,b;”的語義分析翻譯過程。輸入：inta,b;輸出：aintbint6.4屬性翻譯文法聲明語句

；ID↑a

TYPE↑int

變量表ID↑b變量表，εinta,b；的語法樹

解：輸入符號串“inta,b;”的語義分析翻譯過程：聲明語句

；@SET_TYPE↓n1,t2

ID↑n

TYPE↑t

變量表↓t2

@SET_TYPE↓n1,t1

ID↑n變量表↓t2

，εinta,b；的語法樹加入動作符號和屬性t2=t，t1=t，n1=nt2=t，t1=t，n1=n6.4屬性翻譯文法聲明語句

；@SET_TYPE↓a,int

ID↑a

TYPE↑int

變量表↓int

@SET_TYPE↓b,int

ID↑b變量表↓int

，εinta,b；的翻譯樹解：輸入符號串“inta,b;”的語義分析翻譯過程：輸出aintbint聲明語句

；@SET_TYPE↓n1,t2

ID↑n

TYPE↑t

變量表↓t2

@SET_TYPE↓n1,t1

ID↑n變量表↓t2

，εinta,b；的語法樹加入動作符號和屬性t2=t，t1=t，n1=nt2=t，t1=t，n1=n6.4屬性翻譯文法自底向上的語義分析翻譯過程的例如輸入算術表達式3+2*3，應輸出9，給出輸入符號串3+2*3的語義分析翻譯過程。①S→E@ANSWER②E→E+T③E→T④T→T*F⑤T→F⑥F→(E)⑦F→NUM

①S→E↑q@ANSWER↓r r=q②E↑p→E↑q+T↑r

p=q+r③E↑p→T↑q

p=q④T↑p→T↑q*F↑r

p=q*r⑤T↑p→F↑q

p=q⑥F↑p→(E↑q) p=q⑦F↑p→NUM↑q

p=q翻譯文法屬性翻譯文法SET+EF*TTFNUM↑3

FNUM↑2

NUM↑3

3+2*3的語法樹

NUM↑3

SE↑9

T↑6

+E↑3

@ANSWER↓9

F↑3

*T↑2

T↑3

F↑3

F↑2

NUM↑2

NUM↑3

3+2*3的翻譯樹

解：輸入符號串3+2*3的語義分析翻譯過程：6.4屬性翻譯文法輸出96.4屬性翻譯文法例設計一個屬性翻譯文法，要求對于輸入的中綴表達式，經(jīng)過翻譯將輸出具有下面性質(zhì)的四元組代碼序列∶

輸出符號串中的每個雙目運算都用一個四元式表示。四元組中的四元式的順序與執(zhí)行時要完成的運算順序相同。每個四元式有四個參數(shù)，自左向右的順序為∶

運算符，左操作數(shù)，右操作數(shù)，運算結果

例如，翻譯器處理表達式a+b將生成如下的四元式∶

ADD,a,b,t1

其中t1是臨時變量，保存表達式的結果。翻譯器處理表達式a+a*b將生成

MULT,a,b,t1ADD,a,t1,t26.4屬性翻譯文法解：第一步先設計滿足上述要求的翻譯文法。翻譯文法：E→E+T@ADDE→TT→T*F@MULTT→FF→(E)F→ID

輸入文法：E→E+TE→TT→T*FT→FF→(E)F→ID

6.4屬性翻譯文法屬性翻譯文法：E↑x→E↑q+T↑r@ADD↓y,z,t

y=q,z=r,t=NEWT，x=tE↑x→T↑p

x=pT↑x→T↑q*F↑r@MULT↓y,z,t

y=q,z=r,t=NEWT，x=tT↑x

→F↑p

x=pF↑x→(E↑p)x=pF↑x

→ID↑p

x=p其中，NEWT是一個函數(shù)，每次調(diào)用它時返回一個新的臨時變量名，臨時變量名按產(chǎn)生順序分別為t1、t2、…等。動作符號@ADD↓y,z,t輸出“ADD,y,z,t”，動作符號@MULT↓y,z,t輸出“MULT,y,z,t”第二步，構造屬性和求值規(guī)那么，把翻譯文法構造成屬性翻譯文法。6.4屬性翻譯文法ID↑a

ET+EF*TTFFID↑a

ID↑b

表達式a+a*b的語法樹ID↑a

E↑t2

T↑t1

+E↑a

F↑b

*T↑a

T↑a

F↑a

F↑a

ID↑a

ID↑b

表達式a+a*b的翻譯樹@MULT↓a,b,t1

@ADD↓a,t1,t2

產(chǎn)生新變量t2，輸出：ADD,a,t1,t2產(chǎn)生新變量t1，輸出：MULT,a,b,t16.5

屬性文法的自頂向下翻譯自頂向下的語義分析翻譯過程例如---回憶屬性翻譯文法：

1)<聲明語句>→TYPE↑tID↑n@SET_TYPE↓n1,t1<變量表t2>

；

t2=t，t1=t，n1=n2)<變量表↓t>→，ID↑n@SET_TYPE↓n1,t1<變量表↓t2

>

t2=t，t1=t，n1=n3)<變量表>→ε

輸入符號串“inta,b;”的翻譯樹如下。聲明語句

；@SET_TYPE↓a,int

ID↑a

TYPE↑int變量表↓int

@SET_TYPE↓b,int

ID↑b變量表↓int

，ε屬性值依賴于上一級的<變量表>屬性值依賴于左邊的a和int6.5

屬性文法的自頂向下翻譯分析按照自頂向下的有序方式對某個屬性求值時，應當確保所需要的根本值。我們需要對屬性計算規(guī)那么設定約束條件！要求文法必須是L-屬性文法。6.5

屬性文法的自頂向下翻譯L-屬性翻譯文法滿足下面三個條件：〔1〕給定一產(chǎn)生式，其右部符號的繼承屬性值是以左部符號的繼承屬性或出現(xiàn)在給定符號左邊的產(chǎn)生式右部符號的任意屬性為變元的函數(shù)?！?〕給定一產(chǎn)生式，其左部符號的綜合屬性值是以左部符號的繼承屬性或某個右部符號的任意屬性為變元的函數(shù)?！?〕給定一動作符號，其綜合屬性值是以該動作符號的繼承屬性為變元的函數(shù)。6.5

屬性文法的自頂向下翻譯例假設文法中有產(chǎn)生式為：A↓I1↑S2,S3→B↓I4C↑S5D↑S6↓I7,I8E↓I9根據(jù)L-屬性的限制條件，I4=F(I1)、I4=123、I7=G(I1)合法，而I4=H(S2)、I4=K(S6,I4)那么不合法。

例(P134)假設文法中有產(chǎn)生式為：

A↓a1↑a2→B↓b1↑b2C↓c1↑c2A、B和C的屬性可以按下面的順序進行求值∶

1)A的繼承屬性a1

；2)B的繼承屬性b1

；

3)B的綜合屬性b2；4)C的繼承屬性c1

；

5)C的綜合屬性c2

；6)A的綜合屬性a2

。

6.5

屬性文法的自頂向下翻譯為了進行屬性翻譯的程序設計，我們采用下述約定：1)產(chǎn)生式中的屬性名字用作變量和參數(shù)的名字。例：L↑a↓b→E↓iR↓j寫成子程序〔函數(shù)〕時，表示為：intL(inta,intb){inti,j;…}6.5

屬性文法的自頂向下翻譯為了進行屬性翻譯的程序設計，我們采用下述約定：2)所有出現(xiàn)在左部的同名非終結符，應具有相同的屬性名表。在左部同名非終結符屬性名表的同一化過程中，屬性名稱的改動范圍僅局限于產(chǎn)生式左部。屬性重新命名以后，應修改某些屬性求值規(guī)那么。例產(chǎn)生式L↑a↓b

→E↓iR↓ji,j=b，a=i+2L↑x↓y→H↑z↓ww=y，z=2，x=z+y

按約定2，應改成L↑a↓b→E↓iiR↓ji,j=b，a=i+2L↑a↓b→H↑z↓ww=b，z=2，a=z+b6.5

屬性文法的自頂向下翻譯為了進行屬性翻譯的程序設計，我們采用下述約定：3)如果兩個屬性有相同的值，那么可給它們相同的名字，但對于左部符號的屬性值相等時，不能改變成相同的名字。

例對規(guī)那么L↓a↑b→aB↓cC↓d,當c,d=a時，可寫成:L↓a↑b→aB↓aC↓a但當b=a時，上式不能寫成L↓a↑a→aB↓aC↓a這是因為過程L(inta,intb)不可寫成L(inta,inta)。6.5

屬性文法的自頂向下翻譯采用C語言編寫L-屬性文法遞歸下降翻譯程序時采用的方法：1)形式參數(shù)：產(chǎn)生式左部非終結符的屬性名表設計成相應過程的形式參數(shù)表。繼承屬性→值形參(即簡單變量)

綜合屬性→指針變量。2)局部變量：在產(chǎn)生式中，與左部屬性名不同的屬性名變成相應過程的局部變量。3)非終結符的代碼：產(chǎn)生式右部的每個非終結符的過程調(diào)用，該非終結符的屬性作為實參。要注意：如果實參是簡單變量，形參是指針變量，調(diào)用時實參應為簡單變量的地址。6.5

屬性文法的自頂向下翻譯采用C語言編寫L-屬性文法遞歸下降翻譯程序時采用的方法：4)輸入符號的代碼：對文法中出現(xiàn)的每個輸入符號(即終結符號)，將賦值語句插入到過程中它所對應的NEXTSYM之前，把保存在讀符號程序NEXTSYM中的終結符號屬性(某個全局變量中)賦給輸入符號屬性中的每個屬性變量。5)動作符號的代碼：對出現(xiàn)在文法中的每個動作符號，插入代碼便于對動作符號的綜合屬性進行計算，并且把結果賦給對應于該綜合屬性的變量，然后輸出相應的符號。6.5

屬性文法的自頂向下翻譯采用C語言編寫L-屬性文法遞歸下降翻譯程序時采用的方法：4)輸入符號的代碼：對文法中出現(xiàn)的每個輸入符號(即終結符號)，將賦值語句插入到過程中它所對應的NEXTSYM之前，把保存在讀符號程序NEXTSYM中的終結符號屬性(某個全局變量中)賦給輸入符號屬性中的每個屬性變量。5)動作符號的代碼：對出現(xiàn)在文法中的每個動作符號，插入代碼便于對動作符號的綜合屬性進行計算，并且把結果賦給對應于該綜合屬性的變量，然后輸出相應的符號。6.5

屬性文法的自頂向下翻譯采用C語言編寫L-屬性文法遞歸下降翻譯程序時采用的方法：6)屬性規(guī)那么的代碼：與每個產(chǎn)生式有關的屬性求值規(guī)那么，插入其代碼以便對屬性求值規(guī)那么的右部求值，并把結果賦給該規(guī)那么左部的每個變量。可以把這些代碼放在屬性計算規(guī)那么的所有自變量之后，且函數(shù)值被使用之前的任何地方。7)主程序：C語言都是從MAIN函數(shù)開始運行。在MAIN函數(shù)中，對文法的開始符號，其相應的每一個綜合屬性的名字變成主程序的局部變量，然后調(diào)用開始符號對應的過程。在調(diào)用時，如果實參對應開始符號的繼承屬性，那么對每個繼承屬性以該屬性的初始值作為值參傳入，對每個綜合屬性取該屬性的局部變量的地址傳入。6.5

屬性文法的自頂向下翻譯例算術表達式屬性翻譯文法如下,用C語言實現(xiàn)其遞歸下降翻譯器。E↑t→T↑pE'↓p↑tE'↓p↑t→+T↑r

@ADD↓p,r,t0E'↓t0↑t

t0=NEWT

E'↓p↑t→εt=pT↑t→F↑pT'↓p↑tT'↓p↑t→*F↑r

@MULT↓p,r,t0T'↓t0↑t

t0=NEWT

T'↓p↑t→εt=pF↑p->(E↑p)|ID↑p

6.5

屬性文法的自頂向下翻譯main()//主程序{ intes=0,t;printf("請輸入算術表達式(操作數(shù)只能是單個字母)："); ch=getchar(); printf("輸出四元式為：\n");

es=E(&t);

//調(diào)分析表達式E的翻譯程序，

E↑t→T↑pE'↓p↑t if(es==0)printf("\n翻譯成功!\n"); elseprintf("\n表達式有語法錯誤!\n");}6.5

屬性文法的自頂向下翻譯//產(chǎn)生式E↑t→T↑pE'↓p↑t的翻譯子程序，t為綜合屬性,形參用指針變量intE(int*t)

{intes=0;

intp;es=T(&p);//調(diào)分析T子程序

es=E1(p,t);//調(diào)分析E'子程序，t是指針

return(es);}E(int*t)intpT(&p)E’(p,t)return//產(chǎn)生式E'↓p↑t→+T↑r

@ADD↓p,r,t0E'↓t0↑t|ε的翻譯子程序，其中，p為繼承屬性，形參用整型變量，t為綜合屬性，形參用指針變量intE1(intp,int*t)

{intr,es=0,t0;if(ch=='+'){ch=getchar();es=T(&r);

t0=NEWT();

//產(chǎn)生一個臨時變量

printf("ADD,%c,%c,%c\n",p,r,t0);es=E1(t0,t);return(es);}else {*t=p; return(0);}}E’(intp,int*t)intr,t0;‘+’?nextsymT(&r)t0=NEWT()E’(t0,t)return*t=pnyn//返回一個臨時變量,順序產(chǎn)生A、B、...、Z，最多產(chǎn)生26個臨時變量intNEWT(){staticinti=64;//設置i為靜態(tài)變量確保下次調(diào)用時i為上次調(diào)用的結果

i=i+1;return(i);}6.5屬性文法的自頂向下翻譯6.5

屬性文法的自頂向下翻譯//產(chǎn)生式T↑t→F↑pT'↓p↑t的翻譯子程序，t為綜合屬性,形參用指針變量intT(int*t)

{

int

es=0,p;

es=F(&p);

//調(diào)分析F子程序

es=T1(p,t);//調(diào)分析T'子程序return(es);}T(int*t)intpF(&p)T’(p,t)return//產(chǎn)生式T'↓p↑t→*F↑r

@MULT↓p,r,t0T'↓t0↑t

|ε的翻譯子程序intT1(intp,int*t)

{

intr,es=0,t0; if(ch=='*') {ch=getchar();es=F(&r);

t0=NEWT();//產(chǎn)生一個臨時變量

printf("MULT,%c,%c,%c\n",p,r,t0);

es=T1(t0,t); return(es);}else{*t=p;return(0);}}T’(intp,int*t)intr,t0;‘*’?nextsymF(&r)t0=NEWT()T’(t0,t)return*t=pny//產(chǎn)生式F↑p→(E↑p)|ID↑p

的翻譯子程序intF(int*p)

//分析F子程序{intes=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); }elsereturn(4);}}F(int*p)‘(’?nextsymE(p)nextsymreturn*p=chny‘)’?nextsym字母?yy6.5

屬性文法的自頂向下翻譯運行這段程序，假設輸入：a*(b+c)+b*dADD,b,c,AMULT,a,A,BMULT,b,d,CADD,B,C,D輸出四元式序列為：其中A、B、C、D都是臨時變量。6.5

屬性文法的自頂向下翻譯要實現(xiàn)屬性翻譯文法的LL(1)翻譯器，是對翻譯文法的LL(1)翻譯器進行擴充,方法是(P139)：對于所有符號，不僅符號進分析棧，其屬性也同時進棧。即將棧符號設計為兩局部，符號名和屬性域。任何棧符號的域都是在棧內(nèi)的一些存貯單元。A屬性A1屬性A2B屬性B1C…#例(P139)對符號串ABC，假定A有兩個屬性，B有一個屬性而C沒有任何屬性。假設符號名也占用一個存貯單元，那么相應A的棧符號用三個存貯單元，B用二個，C用一個。6.5

屬性文法的自頂向下翻譯例(P139)文法：S→E↑p@ANSWER↓rr=pE↑p→+E↑qE↑r@ADD↓A1,A2↑RA1=q,A2=r,R=A1+A2,p=RE↑p→*E↑qE↑r@MULT↓A1,A2↑RA1=q,A2=r,R=A1*A2,p=RE↑p→NUM↑qp=q

構造該屬性翻譯文法的LL(1)翻譯器。符號輸入符號

+*NUM#SE+*NUM#125

13

5

14

5

ACCEPTLL(1)翻譯器的分析表1:POP,PUSH(@ANSWERE)2:POP,PUSH(@ADDEE+)3:POP,PUSH(@MULTEE*)4:POP,PUSH(NUM)5:POP,NEXTSYM6.5

屬性文法的自頂向下翻譯解：第一步獲得其翻譯文法的LL(1)分析表。6.5

屬性文法的自頂向下翻譯1、棧符號設計屬性文法的每個符號有屬性，所以每個符號入棧時，必須連屬性一起入棧?！?〕綜合屬性：其屬性域存放一個指針，指向存貯該屬性值的單元；〔2〕繼承屬性：其屬性域直接保存其屬性值。繼承屬性的屬性域剛?cè)霔r為空，但是在該棧符號變成棧頂符號之前的某一時刻，它們必須接受相應的屬性值，即在成為棧頂時，繼承屬性的屬性域必須有值。第二步擴充翻譯文法的LL(1)翻譯器6.5

屬性文法的自頂向下翻譯@MULT

繼承屬性A1

繼承屬性A2

綜合屬性R(指針)@ADD繼承屬性A1

繼承屬性A2綜合屬性R(指針)

@ANSWER

繼承屬性rNUM

綜合屬性q(指針)E綜合屬性p(指針)SS的棧符號

E的棧符號

NUM的棧符號

@ANSWER的棧符號

@ADD的棧符號

@MULT的棧符號

根據(jù)設計好的棧符號，對屬性翻譯文法構造LL(1)分析表。

符號輸入符號

+*NUM#SE+*NUM#125

13

5

14

5

ACCEPT屬性翻譯文法的LL(1)分析表1:POP,PUSH(@ANSWER↓rE↑p)2:POP,PUSH(@ADD↓A1,A2↑RE↑rE↑q+)3:POP,PUSH(@MULT↓A1,A2↑RE↑rE↑q*)4:POP,PUSH(NUM↑q),把NUM的屬性值q放入NUM的屬性域指向的單元.5:POP,NEXTSYM

6.5

屬性文法的自頂向下翻譯2、語義動作設計假定要求翻譯器所要完成的工作是計算由文法定義的表達式的值并輸出，那么三個動作符號的翻譯動作為：1)@ADD：把頭兩個域的內(nèi)容相加，并把計算結果存貯在第三個域所指的單元中〔由R=A1+A2〕；POP。2)@MULT：把頭兩個域的內(nèi)容相乘，并把積存貯在第三個域所指的單元中〔由R=A1*A2〕；POP。3)@ANSWER：輸出屬性域r的內(nèi)容結果；POP。6.5

屬性文法的自頂向下翻譯1)初始狀態(tài)+NUM↑2NUM↑3#

S#符號棧：

+NUM↑2NUM↑3#

E↑p@ANSWER↓r#符號棧：

2)查分析表S