第06章 語(yǔ)法制導(dǎo)翻譯技術(shù)

1S.PO.P語(yǔ)義分析及生成中間代碼程序代碼生成程序代碼優(yōu)化程序語(yǔ)法分析程序詞法分析程序錯(cuò)誤處理符號(hào)表管理2第六章語(yǔ)法制導(dǎo)翻譯技術(shù)教學(xué)目標(biāo)要求理解翻譯文法的概念理解語(yǔ)法制導(dǎo)翻譯和屬性翻譯文法的含義明確自頂向下和自底向上語(yǔ)法制導(dǎo)翻譯的區(qū)別和特點(diǎn)36.1翻譯文法6.2語(yǔ)法制導(dǎo)翻譯6.3自頂向下語(yǔ)法制導(dǎo)翻譯6.4屬性翻譯文法6.5屬性文法的自頂向下翻譯6.6自底向上語(yǔ)法制導(dǎo)翻譯教學(xué)內(nèi)容4第六章語(yǔ)法制導(dǎo)翻譯技術(shù)編譯程序的最終目的是把源程序翻譯成目標(biāo)代碼。詞法分析，語(yǔ)法分析：解決單詞和語(yǔ)言成分的識(shí)別及詞法和語(yǔ)法結(jié)構(gòu)的檢查。語(yǔ)法結(jié)構(gòu)可形式化地用一組產(chǎn)生式來(lái)描述。給定一組產(chǎn)生式，我們能夠很容易地將其分析器構(gòu)造出來(lái)。語(yǔ)義分析和中間代碼生成技術(shù)：程序語(yǔ)言中間代碼目標(biāo)代碼翻譯翻譯5第六章語(yǔ)法制導(dǎo)翻譯技術(shù)在對(duì)源程序的編譯過(guò)程中在有語(yǔ)法制導(dǎo)和非語(yǔ)法制導(dǎo)兩種翻譯方法。語(yǔ)法制導(dǎo)翻譯：以語(yǔ)法分析為主導(dǎo)的語(yǔ)義處理。在語(yǔ)法分析的同時(shí)，根據(jù)文法規(guī)則進(jìn)行語(yǔ)義處理，并生成中間代碼或目標(biāo)代碼。非語(yǔ)法制導(dǎo)翻譯：翻譯方法不依賴(lài)于語(yǔ)言的文法規(guī)則.實(shí)際應(yīng)用中比較流行的語(yǔ)義分析方法：基于屬性文法的語(yǔ)法制導(dǎo)翻譯方法6后綴式中綴表示后綴表示a+bab+a+b*cabc*+(a+b)*cab+c*a:=b*c+b*dabc*bd*+:=特點(diǎn)1、運(yùn)算對(duì)象出現(xiàn)的順序和原有順序（從左到右）相同2、運(yùn)算符按實(shí)際計(jì)算順序（從左到右）出現(xiàn)3、運(yùn)算符緊跟在運(yùn)算對(duì)象的后面出現(xiàn)，且沒(méi)有括號(hào)優(yōu)點(diǎn)：簡(jiǎn)明、便于計(jì)值7分別給出下列表達(dá)式的后綴表示a+b*(c-d)(a-b)*c+d3.-a+b*(-c+d)4.X:=-(a+b)/(c-d)-(a+b*c)1.abcd-*+2.ab-c*d+3.a-bc-d+*+4.Xab+-cd-/abc*+-:=86.1翻譯文法翻譯文法：上下文無(wú)關(guān)文法的推廣，在文法規(guī)則的右部適當(dāng)位置加入語(yǔ)義動(dòng)作得到的。例：中綴表達(dá)式翻譯成波蘭后綴表達(dá)式a@a+b@b*c@c@*@+a+b*c輸入串a(chǎn)bc*+輸出結(jié)果活動(dòng)序列@為動(dòng)作符號(hào)標(biāo)記@+為一個(gè)動(dòng)作符號(hào)9由輸入文法（中綴算術(shù)表達(dá)式）構(gòu)造翻譯文法（后綴算術(shù)表達(dá)式）①E→E+T ②E→T ③T→T*F④T→F⑤F→(E)⑥F→a⑦F→b⑧F→c①E→E+T@＋②E→T ③T→T*F@*④T→F⑤F→(E)⑥F→a@a⑦F→b@b⑧F→c@c翻譯文法就是在原有的輸入文法基礎(chǔ)上，在規(guī)則右部適當(dāng)位置加入動(dòng)作符號(hào)所得。10①E→E+T@＋②E→T ③T→T*F@*④T→F⑤F→(E)⑥F→a@a⑦F→b@b⑧F→c@c其中：

@+,@*,@a為動(dòng)作符號(hào)。@為動(dòng)作符號(hào)標(biāo)記，后面為字符串。在本例中，其對(duì)應(yīng)語(yǔ)義子程序的功能是要輸出打印動(dòng)作符號(hào)標(biāo)記后面的字符串。所以：產(chǎn)生式1：E→E+T@+的語(yǔ)義是分析E,+和T，輸出+產(chǎn)生式6：F→a@a的語(yǔ)義是分析a，輸出a11例：符號(hào)串(a+b)*bE=>T=>T*F=>F*F=>(E)*F=>(E+T)*F=>(T+T)*F=>(F+T)*F=>(a+T)*F=>(a+F)*F=>(a+b)*F=>(a+b)*b用輸入文法推導(dǎo)：ETTF*F(E)E+TTFaFbb12用翻譯文法推導(dǎo)得到活動(dòng)序列(a@a+b@b@+)*b@b@*：E=>T=>T*F@*=>F*F@*=>(E)*F@*=>(E+T@+)*F@*=>(T+T@+)*F@*=>(F+T@+)*F@*=>(a@a+T@+)*F@*=>(a@a+F@+)*F@*=>(a@a+b@b@+)*F@*=>(a@a+b@b@+)*b@b@*ETTF*F(E)E+TTFaFb@*@＋b@b@a@b13下面給出輸入文法和翻譯文法的概念：輸入文法：未插入動(dòng)作符號(hào)時(shí)的文法。由輸入文法可以通過(guò)推導(dǎo)產(chǎn)生輸入序列。翻譯文法：插入動(dòng)作符號(hào)的文法。由翻譯文法可以通過(guò)推導(dǎo)產(chǎn)生活動(dòng)序列。 輸入序列 動(dòng)作序列

14定義

翻譯文法是上下文無(wú)關(guān)文法，其終結(jié)符號(hào)集由輸入符號(hào)和動(dòng)作符號(hào)組成。由翻譯文法所產(chǎn)生的終結(jié)符號(hào)串稱(chēng)為活動(dòng)序列?；顒?dòng)序列：由翻譯文法推導(dǎo)出的符號(hào)串，由終結(jié)符和動(dòng)作符號(hào)組成?！駨幕顒?dòng)序列中，抽去動(dòng)作符號(hào)，則得輸入序列(a+b)*b●從活動(dòng)序列中，抽去輸入序列，則得動(dòng)作序列，執(zhí)行動(dòng)作序列，則完成翻譯任務(wù)：

@a@b@+@b@*ab+b*

(a@a+b@b@+)*b@b@*15例：翻譯文法G(E)={Vn，Vt，P，E}，其中Vn={E,T,F}Vt={a,b,c,+,*,(,),@+,@*,@a,@b,@c}P={E→E+T@+,F→(E),E→T,F→a@a,T→T*F@*,F→b@b,T→F,F→c@c}在高級(jí)程序設(shè)計(jì)語(yǔ)言的翻譯中有各種各樣的翻譯文法，其中的動(dòng)作符號(hào)代表不同的語(yǔ)義動(dòng)作。符號(hào)串翻譯文法：若插入文法中的動(dòng)作符號(hào)對(duì)應(yīng)的語(yǔ)義子程序是輸出動(dòng)作符號(hào)標(biāo)記@后的字符串的文法。166.2語(yǔ)法制導(dǎo)翻譯例：輸入序列：a+b*c活動(dòng)序列：a@a+b@b*c@c@*@+動(dòng)作序列：@a@b@c@*@+翻譯結(jié)果：abc*+語(yǔ)法制導(dǎo)翻譯：按翻譯文法進(jìn)行的翻譯。給定一輸入符號(hào)串，根據(jù)翻譯文法獲得翻譯該符號(hào)串的動(dòng)作序列，并執(zhí)行該序列所規(guī)定的動(dòng)作的過(guò)程。176.2語(yǔ)法制導(dǎo)翻譯語(yǔ)法制導(dǎo)翻譯的主要思想：在文法的適當(dāng)位置插入語(yǔ)義動(dòng)作符號(hào)，當(dāng)按文法分析到動(dòng)作符號(hào)時(shí)就調(diào)用相應(yīng)的語(yǔ)義子程序，完成翻譯任務(wù)。翻譯文法所定義的翻譯是由輸入序列和動(dòng)作序列組成的對(duì)偶集。對(duì)偶：（輸入序列，動(dòng)作序列）如：(a+b*c,@a@b@c@*@+)是算術(shù)表達(dá)式翻譯文法定義的一個(gè)翻譯。186.3自頂向下語(yǔ)法制導(dǎo)翻譯自頂向下的語(yǔ)法制導(dǎo)翻譯：遞歸下降翻譯LL(1)翻譯器196.3.1遞歸下降翻譯要求：不能有左遞歸，頭符號(hào)集不能相交在適當(dāng)?shù)奈恢貌迦雽?shí)現(xiàn)動(dòng)作符號(hào)的子程序。①E→E+T@＋②E→T ③T→T*F@*④T→F⑤F→(E)⑥F→i@i消除左遞歸①E→T｛+T@＋｝② ③T→F｛*F@*｝④⑤F→(E)⑥F→i@i20處理E的遞歸下降翻譯程序流程圖E→T｛+T@＋｝

TEINPUTSYM=下一個(gè)符號(hào)TOUT(“+”)INPUTSYM=‘+’出口YN21處理E的遞歸下降翻譯程序代碼E→T｛+T@＋｝

intE(){ intes=0;

es=T(); while(ch==‘+’){ ch=getchar();

es=T();

printf(“+”); } returnes;}TEINPUTSYM=下一個(gè)符號(hào)TOUT(“+”)INPUTSYM=‘+’出口YN22處理T的遞歸下降翻譯程序流程圖T→F｛*F@*｝FTINPUTSYM=下一個(gè)符號(hào)FOUT(“*”)INPUTSYM=‘*’出口YN23處理T的遞歸下降翻譯程序代碼T→F｛*F@*｝FTINPUTSYM=下一個(gè)符號(hào)FOUT(“*”)INPUTSYM=‘*’出口YNintT(){ intes=0;

es=F(); while(ch==‘*’){ ch=getchar();

es=F();

printf(“*”); } returnes;}24處理F的遞歸下降翻譯程序流程圖F→(E)F→i@iEFINPUTSYM=下一個(gè)符號(hào)

INPUTSYM=‘)’出口YNINPUTSYM=‘(’INPUTSYM=下一個(gè)符號(hào)

YNINPUTSYM=下一個(gè)符號(hào)

INPUTSYM=‘i’OUT(i)ERRORERRORN25處理F的遞歸下降翻譯程序代碼F→(E)F→i@iintF(){intes=0;

if(ch==‘(’){ ch=getchar();

es=E();

if(ch!=‘)’) return3; else{ ch=getchar(); returnes; }}else{…}｝else{

if(isalpha(ch)){ //判斷是否為字母

printf(“%c”,ch); ch=getchar(); returnes; } elsereturn4;}266.3.2LL(1)翻譯器考慮下面的輸入文法：①A→aBcD②A→b③B→c④B→aA⑤D→cD⑥D(zhuǎn)→b輸入文法的LL(1)分析表27如果我們?cè)谠撦斎胛姆ǖ倪m當(dāng)?shù)胤讲迦敕g所需要的動(dòng)作符號(hào)，那么，可得到如下的翻譯文法：①A→@va@wB@xc@yD@z②A→b③B→c@r④B→a@mA⑤D→cD@n⑥D(zhuǎn)→@sb輸入文法：①A→aBcD②A→b③B→c④B→aA⑤D→cD⑥D(zhuǎn)→b28翻譯文法：①A→@va@wB@xc@yD@z②A→b③B→c@r④B→a@mA⑤D→cD@n⑥D(zhuǎn)→@sb翻譯文法的LL(1)分析表29對(duì)于翻譯文法，動(dòng)作符號(hào)像其它符號(hào)一樣入棧。但當(dāng)動(dòng)作符號(hào)處于棧頂時(shí)，無(wú)論當(dāng)前的輸入符號(hào)是什么，都要執(zhí)行由該動(dòng)作符號(hào)所規(guī)定的操作，并將該動(dòng)作符號(hào)從棧頂彈出，且不移動(dòng)讀符號(hào)指針。a……棧頂A，當(dāng)前輸入符號(hào)a時(shí)，操作：A出棧；@zD@yc@xB@wa@v入棧；@v出棧并執(zhí)行；a出棧；@w出棧并執(zhí)行。

306.3.2LL(1)翻譯器將LL(1)分析擴(kuò)充為L(zhǎng)L(1)語(yǔ)言的翻譯器，只需擴(kuò)充相應(yīng)分析表的動(dòng)作部分并具體實(shí)現(xiàn)完成每個(gè)動(dòng)作符號(hào)的子程序，就可得到翻譯文法所確定語(yǔ)言的翻譯程序。316.4屬性翻譯文法在翻譯文法的基礎(chǔ)上，可以進(jìn)一步定義屬性文法，翻譯文法中的符號(hào)，包括終結(jié)符、非終結(jié)符和動(dòng)作符號(hào)均可帶有屬性，這樣能更好的描述和實(shí)現(xiàn)編譯過(guò)程。屬性可以分為兩種：綜合屬性繼承屬性326.4.1綜合屬性基本操作數(shù)帶有屬性的表達(dá)式文法G[E]：

1.

E→E+F 4.

T→F2.

E→T 5.

F→(E)3.

T→T*F 6.

F→iC

此文法能夠產(chǎn)生如下的輸入序列：（i3

＋i9)*i233根據(jù)給定的文法，可寫(xiě)出該輸入序列的語(yǔ)法樹(shù)自底向上的屬性計(jì)算ET*TFF(E)E+TTFi3i2

Fi9所以，用表示屬性計(jì)算是自底向上的，稱(chēng)為綜合屬性。ET*TFF(E)E+TTFi3i2

Fi9339391212122242434

產(chǎn)生式求值規(guī)則1.Ep4

→Eq5+Tr2 p4=q5+r2;2.Ep3

→Tq4p3=q4;3.Tp2

→Tq3*Fr1p2=q3*r1;4.Tp2

→Fq2p2=q2;5.Fp1

→(Eq1)p1=q1;6.Fp1

→iq1p1=q1;說(shuō)明：

p,q,r為屬性變量名。屬性變量名局部于每個(gè)產(chǎn)生式，也可使用不同的名字。

求值規(guī)則：綜合屬性是自底向上求值。為了形式地表示上述表達(dá)式的屬性求值過(guò)程，可以改寫(xiě)上述文法：356.4.2繼承屬性考慮下列文法：G[<說(shuō)明>]：1.<說(shuō)明>→Typeid<變量表>2.<變量表>→，id<變量表>3.<變量表>→ε符號(hào)表A整型BC整型其中

Type:類(lèi)型名（值：int,real,bool等）

id：變量名（值：指向該變量符號(hào)表項(xiàng)的指針）上述文法所產(chǎn)生的語(yǔ)句：intA，BC該文法的翻譯任務(wù)：將聲明的變量填入符號(hào)表完成該工作的動(dòng)作符號(hào)：@set_table36翻譯文法：1.<說(shuō)明>→Typeid@set_table<變量表>2.<變量表>→，id@set_table<變量表>3.<變量表>→ε填表時(shí)需要的信息：類(lèi)型，名字，以及填的位置如何得到？類(lèi)型和名字在詞法分析時(shí)得到，可設(shè)兩個(gè)綜合屬性。37Typett中放類(lèi)型值

idn

n中放變量名填表動(dòng)作符號(hào)也可帶有屬性：

@set_table↓t1，n1

↓t1，n1

可從前面得到，所以稱(chēng)為繼承屬性，繼承前面的值

<變量表>

↓t2↓t2

同上屬性翻譯文法：1.<說(shuō)明>→Typetidn@set_table↓t1,n1<變量表>↓t2

t2=t；t1=t；n1=n;

2.<變量表>↓t2

→，idn@set_table↓t1,n1<變量表>↓t3

t3＝t2；t1=t2；n1=n;3.<變量表>↓t2

→

ε38例：inta，bTypeint

idａ

,

idｂ

語(yǔ)法樹(shù)：

<說(shuō)明>Typeint

idａ

@set_table↓int,ａ

<變量表>↓int

,idｂ

@set_table↓intｂ

<變量表>↓int

ε繼承屬性求值：自頂向下綜合屬性求值：自底向上39

符號(hào)表aintbintpintａ，ｂ的分析翻譯過(guò)程：<說(shuō)明>Type

intid

a@set_table↓int,a<變量表>↓intType

intida@set_table↓int,a，id

b

@set_table↓int,b+翻譯文法：<說(shuō)明>→Typeid@set_table<變量表><變量表>→，id@set_table<變量表><變量表>→ε406.4.3屬性翻譯文法定義當(dāng)翻譯文法的符號(hào)具有屬性，并帶有屬性求值說(shuō)明時(shí)，就稱(chēng)為屬性翻譯文法。其具體定義如下：1)文法的每個(gè)終結(jié)符、非終結(jié)符和動(dòng)作符號(hào)都可以有一個(gè)有窮的屬性集。2)每個(gè)非終結(jié)符和動(dòng)作符號(hào)屬性可分為綜合屬性和繼承屬性。3)繼承屬性的求值規(guī)則：①～③4)綜合屬性的求值規(guī)則：①～④41繼承屬性的求值規(guī)則：①~③①開(kāi)始符號(hào)的繼承屬性具有初始值。②對(duì)產(chǎn)生式左部的非終結(jié)符，其繼承屬性則繼承前面產(chǎn)生式中該符號(hào)已有的繼承屬性值。③右部的符號(hào)，其繼承屬性由產(chǎn)生式中其它符號(hào)屬性值進(jìn)行計(jì)算。繼承屬性求值：自頂向下一個(gè)結(jié)點(diǎn)的繼承屬性值是由其父結(jié)點(diǎn)或兄弟結(jié)點(diǎn)的某些屬性決定的42綜合屬性的求值規(guī)則：①~④①對(duì)終結(jié)符號(hào)其綜合屬性具有指定的初始值。在具體實(shí)現(xiàn)中，該初始值將由詞法分析程序提供。②產(chǎn)生式右部的非終結(jié)符號(hào)的綜合屬性值，則取后面以該非終結(jié)符號(hào)為產(chǎn)生式左部時(shí)求得的綜合屬性值。③產(chǎn)生式的左部的非終結(jié)符號(hào)的綜合屬性值，由產(chǎn)生式中左部或右部的某些符號(hào)的屬性值進(jìn)行計(jì)算。④給定一動(dòng)作符號(hào)，其綜合屬性值將用該動(dòng)作符號(hào)的其它屬性值進(jìn)行計(jì)算。綜合屬性求值：自底向上一個(gè)結(jié)點(diǎn)的綜合屬性值是其子結(jié)點(diǎn)的某些屬性來(lái)決定的436.5屬性文法的自頂向下翻譯6.5.1L-屬性翻譯文法（L-ATG）這是屬性翻譯文法中較簡(jiǎn)單的一種。其輸入文法要求是LL(1)文法，可用自頂向下分析構(gòu)造分析器。在分析過(guò)程中可進(jìn)行屬性求值。一屬性翻譯文法稱(chēng)為是L-屬性的，對(duì)其中的每個(gè)產(chǎn)生式A→X1X2…Xn，下面的三個(gè)條件成立：①右部符號(hào)Xj(1jn)的繼承屬性之值，僅依賴(lài)于X1,X2,…,Xj-1的任意屬性或A的繼承屬性；②左部符號(hào)A的綜合屬性之值僅依賴(lài)于A的繼承屬性或（和）右部符號(hào)Xj(1jn)的任意屬性；③對(duì)一動(dòng)作符號(hào)而言，其綜合屬性之值是以該動(dòng)作符號(hào)的繼承屬性或產(chǎn)生式右部符號(hào)的任意屬性為變?cè)暮瘮?shù)。44①右部符號(hào)Xj(1jn)的繼承屬性之值，僅依賴(lài)于X1,X2,…,Xj-1的任意屬性或A的繼承屬性；繼承屬性求值規(guī)則：（1）產(chǎn)生式左部非終結(jié)符號(hào)的繼承屬性值，取前面產(chǎn)生式右部該符號(hào)已有的繼承屬性值。（2）產(chǎn)生式右部符號(hào)的繼承屬性值，用該產(chǎn)生式左部符號(hào)的繼承屬性或出現(xiàn)在該符號(hào)左部的符號(hào)的屬性值進(jìn)行計(jì)算。體現(xiàn)自頂向下，自左向右的求值特性。45②左部符號(hào)A的綜合屬性之值僅依賴(lài)于A的繼承屬性或（和）右部符號(hào)Xj(1jn)的任意屬性；③對(duì)一動(dòng)作符號(hào)而言，其綜合屬性之值是以該動(dòng)作符號(hào)的繼承屬性或產(chǎn)生式右部符號(hào)的任意屬性為變?cè)暮瘮?shù)。綜合屬性求值規(guī)則：（1）產(chǎn)生式右部非終結(jié)符號(hào)的綜合屬性值，取其下部產(chǎn)生式左部同名非終結(jié)符號(hào)的綜合屬性值。（2）產(chǎn)生式左部非終結(jié)符號(hào)的綜合屬性值，用該產(chǎn)生式左部符號(hào)的繼承屬性或某個(gè)右部符號(hào)的屬性進(jìn)行計(jì)算。（3）動(dòng)作符號(hào)的綜合屬性用該符號(hào)的繼承屬性或某個(gè)右部符號(hào)的屬性進(jìn)行計(jì)算。體現(xiàn)自底向上，自右向左的求值特性。46例：A→BC求值順序：1)A的繼承屬性（若A為開(kāi)始符號(hào)，則有指定值,否則由上面產(chǎn)生式右部符號(hào)的繼承屬性求得）2)B的繼承屬性（由A的繼承屬性求得）3)B的綜合屬性（由下面產(chǎn)生式中左部符號(hào)為B的綜合屬性求得）4)C的繼承屬性（由A的繼承屬性和B的屬性求得）5)C的綜合屬性（由下面產(chǎn)生式中左部符號(hào)為C的綜合屬性求得）6)A的綜合屬性（由A→BC計(jì)算）476.5.2L-屬性文法翻譯的實(shí)現(xiàn)——遞歸下降翻譯方法：對(duì)于每個(gè)非終結(jié)符號(hào)都編寫(xiě)一個(gè)翻譯子程序（過(guò)程）。根據(jù)該非終結(jié)符號(hào)具有的屬性數(shù)目，設(shè)置相應(yīng)的參數(shù)。繼承屬性：聲明為賦值形參綜合屬性：聲明為變量形參過(guò)程調(diào)用語(yǔ)句的實(shí)參：繼承屬性:繼承屬性值綜合屬性:屬性變量名（傳地址，返回時(shí)有值）U↓x,y→ProcedureU(x,y);x—賦值形參

y—變量形參‥48關(guān)于屬性名的約定：1）產(chǎn)生式左部的同名非終結(jié)符使用相同的屬性名。（遞歸下降分析法所必須）<L>↑a↓b→e↓I<R>↓J<L>↑x↓y→<H>↓z↑w<S>→I↑a<B>↓b<C>↓cb,c:=a

<S>→I↑x<B>↓x<C>↓x<L>↑x↓y→e↓I<R>↓J<L>↑x↓y→<H>↓z↑w2）具有相同值的屬性取相同的