第06章 語法制導翻譯技術

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

@+,@*,@a為動作符號。@為動作符號標記，后面為字符串。在本例中，其對應語義子程序的功能是要輸出打印動作符號標記后面的字符串。所以：產(chǎn)生式1：E→E+T@+的語義是分析E,+和T，輸出+產(chǎn)生式6：F→a@a的語義是分析a，輸出a11例：符號串(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用輸入文法推導：ETTF*F(E)E+TTFaFbb12用翻譯文法推導得到活動序列(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下面給出輸入文法和翻譯文法的概念：輸入文法：未插入動作符號時的文法。由輸入文法可以通過推導產(chǎn)生輸入序列。翻譯文法：插入動作符號的文法。由翻譯文法可以通過推導產(chǎn)生活動序列。 輸入序列 動作序列

14定義

翻譯文法是上下文無關文法，其終結符號集由輸入符號和動作符號組成。由翻譯文法所產(chǎn)生的終結符號串稱為活動序列?；顒有蛄校河煞g文法推導出的符號串，由終結符和動作符號組成?！駨幕顒有蛄兄?，抽去動作符號，則得輸入序列(a+b)*b●從活動序列中，抽去輸入序列，則得動作序列，執(zhí)行動作序列，則完成翻譯任務：

@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}在高級程序設計語言的翻譯中有各種各樣的翻譯文法，其中的動作符號代表不同的語義動作。符號串翻譯文法：若插入文法中的動作符號對應的語義子程序是輸出動作符號標記@后的字符串的文法。166.2語法制導翻譯例：輸入序列：a+b*c活動序列：a@a+b@b*c@c@*@+動作序列：@a@b@c@*@+翻譯結果：abc*+語法制導翻譯：按翻譯文法進行的翻譯。給定一輸入符號串，根據(jù)翻譯文法獲得翻譯該符號串的動作序列，并執(zhí)行該序列所規(guī)定的動作的過程。176.2語法制導翻譯語法制導翻譯的主要思想：在文法的適當位置插入語義動作符號，當按文法分析到動作符號時就調(diào)用相應的語義子程序，完成翻譯任務。翻譯文法所定義的翻譯是由輸入序列和動作序列組成的對偶集。對偶：（輸入序列，動作序列）如：(a+b*c,@a@b@c@*@+)是算術表達式翻譯文法定義的一個翻譯。186.3自頂向下語法制導翻譯自頂向下的語法制導翻譯：遞歸下降翻譯LL(1)翻譯器196.3.1遞歸下降翻譯要求：不能有左遞歸，頭符號集不能相交在適當?shù)奈恢貌迦雽崿F(xiàn)動作符號的子程序。①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=下一個符號TOUT(“+”)INPUTSYM=‘+’出口YN21處理E的遞歸下降翻譯程序代碼E→T｛+T@＋｝

intE(){ intes=0;

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

es=T();

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

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

es=F();

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

INPUTSYM=‘)’出口YNINPUTSYM=‘(’INPUTSYM=下一個符號

YNINPUTSYM=下一個符號

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如果我們在該輸入文法的適當?shù)胤讲迦敕g所需要的動作符號，那么，可得到如下的翻譯文法：①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對于翻譯文法，動作符號像其它符號一樣入棧。但當動作符號處于棧頂時，無論當前的輸入符號是什么，都要執(zhí)行由該動作符號所規(guī)定的操作，并將該動作符號從棧頂彈出，且不移動讀符號指針。a……棧頂A，當前輸入符號a時，操作：A出棧；@zD@yc@xB@wa@v入棧；@v出棧并執(zhí)行；a出棧；@w出棧并執(zhí)行。

306.3.2LL(1)翻譯器將LL(1)分析擴充為LL(1)語言的翻譯器，只需擴充相應分析表的動作部分并具體實現(xiàn)完成每個動作符號的子程序，就可得到翻譯文法所確定語言的翻譯程序。316.4屬性翻譯文法在翻譯文法的基礎上，可以進一步定義屬性文法，翻譯文法中的符號，包括終結符、非終結符和動作符號均可帶有屬性，這樣能更好的描述和實現(xiàn)編譯過程。屬性可以分為兩種：綜合屬性繼承屬性326.4.1綜合屬性基本操作數(shù)帶有屬性的表達式文法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ù)給定的文法，可寫出該輸入序列的語法樹自底向上的屬性計算ET*TFF(E)E+TTFi3i2

Fi9所以，用表示屬性計算是自底向上的，稱為綜合屬性。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;說明：

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

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

Type:類型名（值：int,real,bool等）

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

idn

n中放變量名填表動作符號也可帶有屬性：

@set_table↓t1，n1

↓t1，n1

可從前面得到，所以稱為繼承屬性，繼承前面的值

<變量表>

↓t2↓t2

同上屬性翻譯文法：1.<說明>→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ｂ

語法樹：

<說明>Typeint

idａ

@set_table↓int,ａ

<變量表>↓int

,idｂ

@set_table↓intｂ

<變量表>↓int

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

符號表aintbintpintａ，ｂ的分析翻譯過程：<說明>Type

intid

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

intida@set_table↓int,a，id

b

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

y—變量形參‥48關于屬性名的約定：1）產(chǎn)生式左部的同名非終結符使用相同的屬性名。（遞歸下降分析法所必須）<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）具有相同值的屬性取相同的