第6章語法制導翻譯技術分析

第6章語法制導翻譯技術2024/10/231內容提要引言翻譯文法語法制導翻譯自頂向下語法制導翻譯自底向上語法制導翻譯屬性翻譯文法屬性文法的自頂向下翻譯屬性文法的自底向上翻譯2024/10/232引言編譯程序的邏輯工作過程詞法分析和語法分析僅僅對源程序做形式變換和檢查。語義分析檢查程序語義是否正確。中間代碼生成將語義分析后的結果翻譯成代碼。上述工作過程采用串行處理方式實際應用中語法分析、語義分析、中間代碼生成采用并行處理方式詞法分析語法分析語義分析代碼優(yōu)化目標代碼生成目標代碼源程序中間代碼生成2024/10/233并行處理方式：

對文法中的每個產生式都附加一些動作(語義分析、操作符號表、代碼生成等),在語法分析過程中，每當需要使用一個產生式進行推導或歸約，語法分析程序除執(zhí)行相應的語法分析動作外，還要執(zhí)行相應的其它動作，完成語義分析和代碼生成等工作。（邊分析邊翻譯）并行處理方式涉及幾個概念翻譯文法語法制導翻譯屬性翻譯文法

2024/10/234翻譯文法：在描述語言規(guī)則的文法產生式右部的適當位置加入動作而得到的文法。翻譯文法@為動作符號標記，由符號@開始的符號串稱為一個動作符號。2024/10/235例：構造中綴表達式文法的翻譯文法，得到其后綴表達式。①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①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把中綴表達式文法叫做輸入文法；在輸入文法上添加動作后形成的文法叫做翻譯文法使用中綴表達式文法推導得到終結符號串叫做輸入序列；使用翻譯文法推導得到的符號串稱為活動序列。從活動序列中去掉所有動作符號得到輸入序列，而所有動作符號組成的符號串稱為動作序列。從動作序列中去掉動作符號標記得到輸出序列（翻譯結果）2024/10/236例：對于符號串(a+b)*c用輸入文法推導輸入序列(a+b)*c:E=>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)*c用翻譯文法推導活動序列(a@a+b@b@+)*c@c@*: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@+)*c@c@*將活動序列(a@a+b@b@+)*c@c@*中的動作符號去掉得到輸入序列：(a+b)*c所有動作符號組成的符號串即動作序列為：@a@b@+@c@*

去掉動作符號標記得到：ab+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@c2024/10/237由于翻譯文法是在輸入文法的產生式右部的適當位置插入動作符號形成的，因此，翻譯文法產生的動作序列受輸入語言的文法控制（語法制導）。語法制導翻譯：根據輸入文法，分析各條產生式的語義(要求計算機所完成的操作)，分別編出完成這些操作的子程序或程序段(稱為語義子程序或語義動作)，并把這些子程序或程序段的名字作為動作符號插入到輸入文法各產生式右部的適當位置上，從而實現翻譯文法。

①E→E+T@+ ⑤F→(E)②E→T⑥F→a@a③T→T*F@* ⑦F→b@b④T→F ⑧F→c@c①E→E+T⑤F→(E)②E→T ⑥F→a③T→T*F⑦F→b④T→F⑧F→c2024/10/238語法制導翻譯9語法制導翻譯的基本思想通俗地講，以語法分析為基礎，伴隨語法分析的各個步驟，執(zhí)行相應的語義動作。具體方法：

1．將文法符號所代表的語言成分的意思，用隸屬于該文法符號的屬性表示；

2．用語義規(guī)則(語義規(guī)則的執(zhí)行就是語義動作)規(guī)定產生式所代表的語言成分之間的關系（即屬性之間的關系），即用語義規(guī)則實現屬性計算。3.語義動作(語義規(guī)則的執(zhí)行)：在語法分析的適當時刻（如推導或歸約）執(zhí)行附在對應產生式上的語義規(guī)則，以實現對語言結構語義的處理，如計算、查填符號表、生成中間代碼、發(fā)布出錯信息等。2024/10/23自頂向下的語法制導翻譯：遞歸下降翻譯、LL(1)翻譯。遞歸下降翻譯(在適當位置插入實現動作符號的子程序）:例:算術表達式翻譯文法如下：(@為輸出其后的符號串)①E→E+T@+②E→T③T→T*F@*

④T→F ⑤F→(E)⑥F→a@a⑦F→b@b⑧F→c@c消除左遞歸得到：

E→TE’E’→+T@+E’|εT→FT’T’→*F@*T’|εF→(E)|a@a|b@b|c@c自頂向下語法制導翻譯

10FIRST(TE’)={(,a,b,c}FIRST(+T@+E’)={+}FOLLOW(E’)={#,)}FIRST(FT’)={(,a,b,c}FIRST(*F@*T’)={*}FOLLOW(T’)={#,+,)}FIRST((E))={(}FIRST(a@a)={a}FIRST(b@b)=FIRST(c@c)={c}求FIRST集和FOLLOW集不考慮動作符號11－對改寫后文法的每個非終結符號編寫一個函數。對于產生式E→TE’FIRST(TE’)={(,a,b,c}－用E1表示E’

E(){if(ch∈FIRST(TE’)) {T();E1();}elseerror();}2024/10/23E→TE’E’→+T@+E’|εT→FT’T’→*F@*T’|εF→(E)|a@a|b@b|c@c12對于產生式

E’→+T@+E’|ε-用E1表示E’FIRST(+T@+E’)={+}FOLLOW(E’)={#,)}E1(){ if(ch==‘+’) {ch=getnextsymbol();T();OUT(“+”);E1()；

} elseif(ch∈FOLLOW(E’))return;elseerror();}2024/10/23E→TE’E’→+T@+E’|εT→FT’T’→*F@*T’|εF→(E)|a@a|b@b|c@c對于產生式

T→FT’-用T1表示T’T(){if(ch∈FIRST(FT’)){F();T1();}else error();}2024/10/23E→TE’E’→+T@+E’|εT→FT’T’→*F@*T’|εF→(E)|a@a|b@b|c@c對于產生式T’→*F@*T’|εFIRST(*F@*T’)={*}FOLLOW(T’)={#,+,)}-用T1表示T’T1(){if(ch==‘*’){ch=getnextsymbol();F();OUT(“*”);T1()；}elseif(ch∈FOLLOW(E’))return;elseerror();}2024/10/2314E→TE’E’→+T@+E’|εT→FT’T’→*F@*T’|εF→(E)|a@a|b@b|c@c對于產生式F→(E)|a@a|b@b|c@c

F(){if(ch==‘a’){ch=getnextsymbol();OUT(“a”);}elseif(ch==‘b’){ch=getnextsymbol();OUT(“b”);}elseif(ch==‘c’){ch=getnextsymbol();OUT(“c”);}elseif(ch==‘(’）

{ch=getnextsymbol();E();if(ch==‘)’)ch=getnextsymbol();} elseerror（）;}2024/10/23152024/10/2316FIRST(TE’)={(,a,b,c}FIRST(+T@+E’)={+}FOLLOW(E’)={#,)}FIRST(FT’)={(,a,b,c}FIRST(*F@*T’)={*}FOLLOW(T’)={#,+,)}FIRST((E))={(}FIRST(a@a)={a}FIRST(b@b)=FIRST(c@c)={c}思考：句子a+b*c的翻譯輸出是什么？E→TE’E’→+T@+E’|εT→FT’T’→*F@*T’|εF→(E)|a@a|b@b|c@c輸出：abc*+LL(1)翻譯器

例：輸入文法：①A→aBcD②A→b③B→c④B→aA⑤D→cD⑥D→b

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

符號輸入符號

abc#ABDA→aBcDB→aA

A→b

D→b

B→cD→cD

翻譯文法：①A→@va@wB@xc@yD@z②A→b③B→c@r④B→a@mA⑤D→cD@n⑥D→@sb符號

輸入符號

abc#ABDA→@va@wB@xc@yD@zB→a@mAA→b

D→@sb

B→c@rD→cD@n

翻譯文法的LL(1)分析表

翻譯文法的動作符號同樣入棧，當其處于棧頂時，無條件出棧并執(zhí)行其規(guī)定的操作，不移動讀符號指針。

構造翻譯文法分析表不考慮動作符號2024/10/2317a……A..#@v

a

@w

B@x.#B..#@v出棧并執(zhí)行，a出棧，@w出棧并執(zhí)行

符號

輸入符號

abc#ABDA→@va@wB@xc@yD@zB→a@mA

A→b

D→@sb

B→c@rD→cD@n

2024/10/2318波蘭翻譯文法：對于一個文法,當且僅當文法中每個產生式右部的所有動作符號都只出現在所有輸入符號和非終結符號的右邊,則稱此類翻譯文法為波蘭翻譯文法。例：0)S→E1)E→E+T@ADD2)E→T3)T→T*F@MULT4)T→F5)F→(E)6)F→i

0)S→E1)E→E+T2)E→T3)T→T*F4)T→F5)F→(E)6)F→i

自底向上的語法制導翻譯2024/10/2319狀態(tài)

ACTION

GOTO

i+*()#ETF0S5

S4

1231

S6

A

2R2S7R2R2

3R4R4R4R4

4S5

S4

8235R6R6R6R6

6S5

S4

937S5

S4

108

S6

S11

9R1S7R1R1

10R3R3R3R3

11R5R5R5R5

算術表達式的LR分析表使用帶動作符號的產生式歸約要執(zhí)行動作符號規(guī)定的動作。波蘭翻譯0)S→E1)E→E+T@ADD2)E→T3)T→T*F@MULT4)T→F5)F→(E)6)F→i

2024/10/2320步驟狀態(tài)棧符號棧輸入串ACTIONGOTO10#i+i#S5205#i+i#R63303#F+i#R42402#T+i#R21501#E+i#S66016#E+i#S570165#E+i#R6380163#E+F#R4990169#E+T#R111001#E#ACC輸入符號串i+i#的翻譯過程歸約之后執(zhí)行@ADD,輸出ADD0)S→E1)E→E+T@ADD2)E→T3)T→T*F@MULT4)T→F5)F→(E)6)F→i

2024/10/2321思考：若用棧計算后綴表達式，產生式6可添加什么動作？屬性：指與文法符號的類型和值等有關的一些語義信息，在編譯中用屬性描述被處理對象的語義特征。屬性代表與文法符號相關的語義信息。屬性的設置和語法結構的語義以及翻譯程序的需要有關。例如:文法符號X的類型屬性:X.type文法符號X的值屬性:X.val文法符號X的代碼序列:X.code文法符號X的內存：X.place文法符號X的符號表入口指針:X.entry等。屬性翻譯文法注：教材中用箭頭↑和↓代替.2024/10/232223屬性、語義規(guī)則屬性和變量一樣，可以在語法分析過程中進行計算和傳遞。語義規(guī)則：屬性的計算規(guī)則,屬性的加工和計算過程。由語義處理過程、語義動作、語義子程序來實現。屬性分為兩類：綜合屬性和繼承屬性。終結符只有綜合屬性,由詞法分析器提供例：i.lexval表示單詞符號“數”的詞法值id.entry表示單詞符號“標識符”的符號表入口非終結符既可以有綜合屬性也可以有繼承屬性注：教材中屬性前用↑表示綜合屬性，↓表示繼承屬性2024/10/2324兩種屬性：綜合屬性綜合屬性用于“自下而上”傳遞信息。綜合屬性：在語法樹中，一個結點的綜合屬性值由其子結點的屬性值確定。通常結合自下而上的語法分析在每一個結點處使用語義規(guī)則計算綜合屬性的值---由下層子結點的屬性值計算上層父結點的綜合屬性值，隨著自下而上語法分析的進行，最終可計算出開始符號的綜合屬性值。AX1X2…XnA.bX1.c1X2.c2…Xn.

ckAX1X2…Xn綜合屬性A.b=f(c1,c2,…,ck)帶屬性的語法樹2024/10/23例：設計一個語法分析程序接受算術表達式，并通過添加動作符號輸出表達式的值。已知符號串翻譯文法如下：①S→E@ANSWER②E→E+T③E→T④T→T*F⑤T→F⑥F→(E)⑦F→NUM@ANSWER的動作是輸出表達式的計算結果。表達式3+2*3的詞法分析結果如下：

NUM↑3+NUM↑2*NUM↑3其中NUM代表無符號整數,↑數字串表示該符號的屬性2024/10/2325改寫每一個產生式，添加符號屬性變量名，并定義符號屬性之間的關系即屬性求值規(guī)則(語義規(guī)則)，得到：

屬性文法求值規(guī)則

①S→E↑q@ANSWER↓rr=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↑qp=q通過自底向上進行求值的屬性，稱為綜合屬性，用↑來表示。終結符號的綜合屬性具有初始值，由詞法分析給出。2024/10/2326SET+E@ANSWERF*TTFNUM↑3

FNUM↑2

NUM↑3

NUM↑3+NUM↑2*NUM↑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

NUM↑3+NUM↑2*NUM↑3帶屬性計算的語法樹

屬性文法求值規(guī)則①S→E↑q@ANSWER↓rr=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在歸約過程中完成屬性值的計算⑦⑤③⑦⑤⑦④②2024/10/232728兩種屬性：繼承屬性繼承屬性用于“自上而下”傳遞信息。繼承屬性：在語法樹中，一個結點的繼承屬性由此結點的父結點和(或)兄弟結點的某些屬性確定?？梢杂美^承屬性來表示程序語言結構中的上下文依賴關系。繼承屬性的計算可以結合自上而下的語法分析進行A

X1…X

…XnA.

ck

X1.c1…X.b…Xn.ciAX1X2…X…Xn

繼承屬性X.b=f(c1,c2,…,ck)2024/10/23例：聲明語句文法 ①<聲明語句>→TYPEID<變量表>; ②<變量表>→，ID<變量表> ③<變量表>→ε

其中TYPE可為int，real，bool假設詞法分析程序輸出單詞符號時，對變量名輸出單詞記號ID和變量名；對TYPE輸出單詞記號TYPE和類型名。構造語法分析程序，能輸出變量名及其類型

2024/10/23291、添加語義動作@SET_TYPE輸出變量名及類型，因此@SET_TYPE帶有兩個屬性，即變量名和類型：

@SET_TYPE↓n1，t1語法分析程序讀到一個變量后，調用SET_TYPE。因此文法改寫為：

(1)<聲明語句>→TYPEID@SET_TYPE<變量表>;(2)<變量表>→，ID@SET_TYPE<變量表>(3)<變量表>→ε2、確定需要的屬性TYPE需要一個屬性(類型名)，即TYPE↑tID需要一個屬性(變量名)，即ID↑n<變量表>需要一個屬性，即<變量表↓t2>2024/10/23303、確定語義規(guī)則（屬性求值規(guī)則）產生式(1)的TYPE↑t和ID↑n由詞法分析輸出得到。產生式(2)從詞法分析只能得到ID↑n，令產生式(2)左邊<變量表↓t2>=產生式(1)右邊<變量表↓t2>,得到翻譯文法：<聲明語句>→TYPE↑tID↑n@SET_TYPE↓n1,t1<變量表↓t2>

t2=t，t1=t，n1=n（屬性求值規(guī)則）2)<變量表↓t>→，ID↑n@SET_TYPE↓n1,t1<變量表↓t2>

t2=t，t1=t，n1=n（屬性求值規(guī)則）3)<變量表>→ε

(1)<聲明語句>→TYPEID@SET_TYPE<變量表>;(2)<變量表>→，ID@SET_TYPE<變量表>(3)<變量表>→ε2024/10/2331假設輸入符號串為inta,b；，詞法分析輸出為TYPE↑intID↑a,D↑b；，則帶有屬性的語法樹如圖所示按自頂向下或自左向右方式求得的屬性稱為繼承屬性,其前面冠以↓表示。

聲明語句

；@SET_TYPE↓a,int

ID↑a

TYPE↑int

變量表↓int

@SET_TYPE↓b,int

ID↑b

變量表↓int

，ε

TYPE↑intID↑a,D↑b；的語法樹<聲明語句>→TYPE↑tID↑n@SET_TYPE↓n1,t1<變量表↓t2>

(1)t2=t，(2)t1=t，(3)n1=n（屬性求值規(guī)則）2)<變量表↓t>→，ID↑n@SET_TYPE↓n1,t1<變量表↓t2>

(4)t2=t，(5)t1=t，(6)n1=n（屬性求值規(guī)則）3)<變量表

>→ε

2024/10/233233屬性文法：編譯技術中采用的一種語義描述工具，是一種適用于定義語言語義的特殊文法，即：在語言的文法中增加了屬性的文法。屬性翻譯文法：是以一個上下文無關文法為基礎,為每個文法符號引進一組屬性(語義值)，對文法的每個產生式都配備一組與之相關聯的屬性的計算規(guī)則(語義規(guī)則)而得到的文法?；蛘哒f：符號具有屬性并帶有屬性求值規(guī)則的翻譯文法稱為屬性翻譯文法其具體定義如下：2024/10/231)文法的每個終結符、非終結符和動作符號都可以有一個有窮的屬性集。2)每個非終結符和動作符號屬性可分為綜合屬性和繼承屬性。3)繼承屬性的求值規(guī)則：①開始符號的繼承屬性具有初始值。②對產生式左部的非終結符，其繼承屬性則繼承前面產生式中該符號已有的繼承屬性值。③右部的符號，其繼承屬性由產生式中其它符號屬性值進行計算。（語法樹上的父親和兄弟）2024/10/23344)綜合屬性的求值規(guī)則：①

終結符號的綜合屬性具有指定的初始值。在具體實現中，初始值由由詞法分析程序提供。②

產生式右部的非終結符號的綜合屬性值，則取后面以該非終結符號為產生式左部時求得的綜合屬性值。③

產生式的左部的非終結符號的綜合屬性值，由產生式中左部或右部的某些符號的屬性值進行計算。④給定一動作符號，其綜合屬性值用該動作符號的其它屬性值進行計算。2024/10/2335翻譯要求：翻譯輸出是四元式代碼

輸出符號串中的每個雙目運算都用一個四元式表示。四元式的順序與執(zhí)行時的運算順序相同。四元式有三個參數，從左到右為∶左操作數，右操作數，運算結果。

例：翻譯器將表達式a+b翻譯成如下四元式∶

ADDa,b,t1其中t1是臨時變量，保存表達式的結果。對于表達式：a+a*b，詞法分析得到ID↑a+ID↑a*ID↑b，屬性翻譯文法翻譯得到：

MULTab,t1ADDat1,t2例：算術表達式的翻譯文法：E→E+TE→TT→T*FT→FF→(E)F→ID

2024/10/23361、設計翻譯文法：E→E+T@ADDE→TT→T*F@MULTT→FF→(E)F→ID

2024/10/23372、確定屬性和求值規(guī)則，構造屬性翻譯文法1)令每個非終結符有一個綜合屬性：臨時變量，保存由它產生的表達式結果。2)輸入符號ID有一個綜合屬性：符號的變量名。3)動作符號有三個繼承屬性：左操作數、右操作數、運算結果。屬性翻譯文法如下：E↑x→E↑q+T↑r@ADD↓y,z,t，y=q,z=r,t=NEWT，x=tE↑x→T↑px=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返回一個新的臨時變量名，按產生順序分別為t1、t2、…。動作符號@ADD↓y,z,t

輸出ADDy,z,t動作符號@MULT↓y,z,t

輸出MULTy,z,t2024/10/2338ID↑a

E↑x

T↑r

+E↑q

F↑p

*T↑q

T↑p

F↑x

F↑x

ID↑a

ID↑b

@MULT↓y,z,t

@ADD↓y,z,t

表達式a+a*b的屬性語法樹E↑t2

T↑t1

E↑a

F↑b

T↑a

T↑a

F↑a

F↑a

@MULT↓a,z,t

@ADD↓a,z,t

產生新變量t2產生新變量t1E↑x→E↑q+T↑r@ADD↓y,z,t，y=q,z=r,t=NEWT，x=tE↑x→T↑px=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=p2024/10/2339@MULT↓a,b,t

@MULT↓a,b,t1

@ADD↓a,t1,t

@ADD↓a,t1,t2

屬性翻譯文法的語法樹需要保證完整性，即保證所有屬性能通過計算賦值。不同分析方法對文法有不同要求。L-屬性翻譯文法：自頂向下分析時保證語法樹的完整性屬性文法的自頂向下翻譯2024/10/23402024/10/2341

屬性翻譯文法是L-屬性翻譯文法，當且僅當對其中的每個產生式A→X1X2…Xn，下面三個條件成立：1．右部符號Xi(1≦i≦n)的繼承屬性之值，僅依賴于X1,X2,…,Xi-1的任意屬性或A的繼承屬性（P133繼承屬性規(guī)則③的限制）；

（L的含義：符號的繼承屬性只依賴于該符號左邊的屬性值）2．左部符號A的綜合屬性值僅依賴于A的繼承屬性或右部符號Xi(1≦i≦n)的任意屬性（P133綜合屬性規(guī)則③的限制）；3．對一動作符號而言，其綜合屬性值依賴于該動作符號的繼承屬性（P133繼承屬性規(guī)則④的限制）。條件2、3避免求值的循環(huán)依賴；給定文法后可通過構造依賴圖進行拓撲排序證明）例：文法中有產生式為：A↓I1↑S2,S3→B↓I4C↑S5D↑S6↓I7,I8E↓I9根據L-屬性的限制條件，I4=F(I1)、S2=G(I7,S6)合法，而I4=H(S2)不合法。

條件1條件2L-屬性文法翻譯的實現——遞歸下降翻譯

處理思路和處理不帶屬性的翻譯文法相同，由于屬性的存在需要改造對非終結符的處理方法：1)若非終結符具有屬性，則該非終結符的分析函數具有形參，形參數目等于其屬性個數。

2)對于繼承屬性，采用值傳遞方式，將繼承屬性值傳入被調函數，即在函數調用中所對應的實參是繼承屬性的值。

3)對于綜合屬性，采用引用（地址）傳遞方式，以便將值回傳給主調函數,即實參是一個變量引用（地址），在函數返回之前，把綜合屬性的值賦給該變量。

2024/10/2342為了進行屬性翻譯的程序設計，作下述約定：

1)將屬性名用作變量名和參數名。

2)所有出現在左部的同名非終結符，應具有相同的屬性名表。例:產生式L↑a↓b→E↓iR↓j，i,j=b,a=i+2L↑x↓y→H↑z↓w，w=y,z=2,x=z+y改成：L↑a↓b→E↓iR↓j，i,j=b,a=i+2L↑a↓b→H↑z↓w，w=b,z=2,a=z+b2024/10/23433)若兩個屬性值相同，則給它們相同的名字，但左部符號的屬性值相等時，不能改變成相同的名字。規(guī)則S→A↑aB↓bC↓c，當b=a，c=a時，可寫成S→A↑aB↓aC↓a規(guī)則L↑a→A↓b@f↓c

，當a=b,c=b時，可寫成L↑a→A↓a@f↓a規(guī)則L↓a↑b→xB↓cC↓d,當c=a,d=a時，

可寫成L↓a↑b→xB↓aC↓a但當b=a時，不能寫成L↓a↑a→aB↓aC↓a理由：左部非終結符號的屬性將作為該非終結符號分析函數的形參，而一個函數的形參不能重名。如函數L(inta,intb)不可寫成L(inta,inta)。2024/10/2344采用C語言編寫屬性翻譯程序時采用的方法：1)形式參數：產生式左部非終結符的屬性名表設計成相應的形參表；將繼承屬性的形參名說明為值形參(即簡單變量)，綜合屬性形參名說明為指針變量。2)局部變量：產生式中與在左部出現的屬性名不同的屬性名變成相應函數的局部變量。3)非終結符的代碼：對于右部出現的每個非終結符的函數調用，該非終結符的屬性作為實參。2024/10/23454)終結符的代碼：對文法中出現的每個終結符，將賦值語句插入到函數中它所對應的NEXTSYM之前，把保存在讀符號程序NEXTSYM中的終結符號屬性(某個全局變量中)賦給終結符屬性中的每個屬性變量（讀下一個符號前賦值）。5)動作符號的代碼：對出現在文法中的每個動作符號，插入代碼對動作符號的綜合屬性進行計算，并且把結果賦給對應于該綜合屬性的變量，然后執(zhí)行相應動作。2024/10/23466)屬性規(guī)則的代碼：與每個產生式有關的屬性求值規(guī)則，插入其代碼以便對屬性求值規(guī)則的右部求值，并把結果賦給該規(guī)則左部的每個變量?？梢园堰@些代碼放在屬性計算規(guī)則的所有自變量已知之后，且函數值被使用之前的任何地方。7)主程序：MAIN函數中，對文法開始符號的每一個綜合屬性的名字變成主程序的局部變量，然后調用開始符號對應的函數。2024/10/2347例：為算術表達式的L-屬性翻譯文法編寫遞歸下降翻譯器。E↑t→T↑pE'↓p↑tE'↓p↑t→+T↑r@ADD↓p,r,t0E'↓t0↑tt0=NEWT

E'↓p↑t→εt=pT↑t→F↑pT'↓p↑tT'↓p↑t→*F↑r@MULT↓p,r,t0T'↓t0↑tt0=NEWT

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

2024/10/2348如何得到該文法？1、消除左遞歸2、命名改造2024/10/2349E↑x→E↑q+T↑r@ADD↓y,z,t，y=q,z=r,t=NEWT，x=tE↑x→T↑px=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=pE↑x→T↑pE'↓q↑y

x=yq=pE'↓q↑y→+T↑r@ADD↓p,s,t0E'↓t1↑tt0=NEWTp=qs=rt1=t0t=t0y=tE'↓q↑y→εy=qT↑x→F↑pT'↓q↑yx=yq=pT'↓q↑y→*F↑r@MULT↓p,s,t0T'↓t0↑tt0=NEWTp=qs=rt1=t0t=t0y=tT'

↓q↑y→εy=qF↑q→(E↑p)|ID↑pq=p消除左遞歸ETF+TE’εIDE’T’εFIDT’ε2024/10/2350命名處理E↑t→T↑pE'↓p↑tE'↓p↑t→+T↑r@ADD↓p,r,t0E'↓t0↑tt0=NEWT

E'↓p↑t→εt=pT↑t→F↑pT'↓p↑tT'↓p↑t→*F↑r@MULT↓p,r,t0T'↓t0↑tt0=NEWT

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

E↑x→T↑pE'↓q↑y

x=yq=pE'↓q↑y→+T↑r@ADD↓p,s,t0E'↓t1↑tt0=NEWTp=qs=rt1=t0t=t0y=tE'↓q↑y→εy=qT↑x→F↑pT'↓q↑yx=yq=pT'↓q↑y→*F↑r@MULT↓p,s,t0T'↓t0↑tt0=NEWTp=qs=rt1=t0t=t0y=tT'

↓q↑y→εy=qF↑q→(E↑p)|ID↑pq=p對產生式E↑t→T↑pE'↓p↑t，t為綜合屬性,形參用指針變量intE(int*t){intes=0;intp;es=T(&p);

es=E1(p,t);

return(es);}E↑t→T↑pE'↓p↑tE'↓p↑t→+T↑r@ADD↓p,r,t0E'↓t0↑tt0=NEWT

E'↓p↑t→εt=pT↑t→F↑pT'↓p↑tT'↓p↑t→*F↑r@MULT↓p,r,t0T'↓t0↑tt0=NEWT

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

方法1方法2方法32024/10/2351對產生式E'↓p↑t→+T↑r@ADD↓p,r,t0E'↓t0↑t和

E'↓p↑t→εp為繼承屬性,形參用整型變量,t為綜合屬性,形參用指針變量intE1(intp,int*t){intr,es,t0;if(ch=='+'){ch=getword();es=T(&r);t0=NEWT();printf(“ADD%c,%c,%c\n",p,r,t0);es=E1(t0,t);return(es);}elseif(ch=='('||ch=='#') {*t=p; return(0);}elseerror();}......E'↓p↑t→+T↑r@ADD↓p,r,t0E'↓t0↑t

t0=NEWT

E'↓p↑t→εt=p......方法4，但+無屬性方法5，動作符號無綜合屬性方法62024/10/2352intNEWT(){staticinti=64;

i=i+1;

return(i);}對產生式T↑t→F↑pT'↓p↑tt為綜合屬性,形參用指針變量intT(int*t){intes=0,p;es=F(&p);

es=T1(p,t);

return(es);}E↑t→T↑pE'↓p↑tE'↓p↑t→+T↑r@ADD↓p,r,t0E'↓t0↑tt0=NEWT

E'↓p↑t→εt=pT↑t→F↑pT'↓p↑tT'↓p↑t→*F↑r@MULT↓p,r,t0T'↓t0↑tt0=NEWT

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

2024/10/2353intT1(intp,int*t){intr,es,t0;if(ch=='*'){ch=getword();es=F(&r);t0=NEWT();

printf(“MULT%c,%c,%c\n",p,r,t0);es=T1(t0,t);return(es);}elseif(ch=='+'||ch=='#'||ch==')'){*t=p;return(0);}elseerror();}......T'↓p↑t→*F↑r@MULT↓p,r,t0T'↓t0↑tt0=NEWT

T'↓p↑t→εt=p......2024/10/2354對產生式T’↓p↑t→*F↑r@MULT↓p,r,t0T’↓t0↑t和T’

↓p↑t→ε，p為繼承屬性,形參用整型變量；t為綜合屬性,形參用指針變量intF(int*p){intes=0;if(ch=='('){ch=getword();es=E(p);

if(ch!=')')return(3);else{ch=getword();return(es);}}else{ if(isalpha(ch))

{*p=ch; ch=getword(); return(es); }elsereturn(4);}}對產生式F↑p→(E↑p)|ID↑pp為綜合屬性,形參用指針變量方法42024/10/2355主程序：1、MAIN函數中對開始符號的每一個綜合屬性作為其局部變量；2、調用開始符號對應的函數，如果實參對應開始符號的繼承屬性，則以值參方式傳入該屬性的初始值；如果對應開始符號的綜合屬性，則傳入該屬性局部變量的地址。E↑t→T↑pE'↓p↑tmain(){intes=0,t;printf("請輸入算術表達式(操作數只能是單個字母)：");ch=getword();printf("輸出四元式為：\n");es=E(&t);

if(es==0)printf("\n翻譯成功!\n");elseprintf("\n表達式有語法錯誤!\n");}方法7（1）方法7（2）2024/10/2356運行程序輸入：a*(b+c)+b*d輸出四元式序列為：其中A、B、C、D都是臨時變量。ADDb,c,AMULTa,A,BMULTb,d,CADDB,C,D2024/10/235758輸入：NUM↑2*NUM↑4+NUM↑6#E'↓t0↑tNUM↑2*E↑tT↑pF↑pT'↓p↑t+F↑rE'↓p↑t

T↑rNUM↑6F↑p

2024/10/23T'↓p↑t

NUM↑4F↑2T'↓2↑tF↑4MULT↓p,r,t0MULT↓2,r,t0MULT↓2,4,t0MULT↓2,4,8T'↓t0↑tT'↓8↑tADD↓p,r,t0F↑6T'↓6↑tT'↓8↑8T'↓2↑8T↑8E'↓8↑tT↑6T'↓6↑6E'↓8↑14ADD↓8,6,t0ADD↓8,6,14E'↓14↑tE'↓14↑14E↑14調用進入返回遞歸下降翻譯程序的運行（將文法中ID改為NUMt0=p+rt0=p*r）L-屬性文法翻譯的實現—LL(1)法擴充翻譯文法的LL(1)翻譯器：對所有符號，符號本身和屬性同時進棧。將棧符號設計為兩部分(符號名、屬性域)例：對符號串ABC，假定A有屬性A1和A2，B有屬性B1，C無屬性。入棧后如圖所示。

A屬性

A1屬性

A2B屬性B1C…#2024/10/2359例：文法S→E↑p@ANSWER↓r

r=pE↑p→+E↑qE↑r@ADD↓A1,A2↑R

A1=q,A2=r,R=A1+A2,p=RE↑p→*E↑qE↑r@MULT↓A1,A2↑R

A1=q,A2=r,R=A1*A2,p=RE↑p→NUM↑q

p=q

構造其翻譯器

步驟：1、棧符號設計2、構造LL(1)分析表3、設計語義動作2024/10/23601、棧符號設計根據屬性類型確定屬性域的存放內容，可存放屬性值和指向屬性值的指針。對于綜合屬性，其屬性域存放一個指針，指向存貯該屬性值的單元。對于繼承屬性，其屬性域直接保存其屬性值。繼承屬性的屬性域剛入棧時為空，但在該棧符號變成棧頂符號之前的某一時刻，必須通過計算賦值，即在成為棧頂時，繼承屬性的屬性域必須有值。2024/10/2361@MULT

繼承屬性1

繼承屬性2

綜合屬性指針

@ADD繼承屬性1

繼承屬性2

綜合屬性指針

@ANSWER

繼承屬性NUM

綜合屬性指針E綜合屬性指針SS的棧符號

E的棧符號

NUM的棧符號

@ANSWER的棧符號

@ADD的棧符號

@MULT的棧符號

S→E↑p@ANSWER↓r

r=pE↑p→+E↑qE↑r@ADD↓A1,A2↑R

A1=q,A2=r,R=A1+A2,p=RE↑p→*E↑qE↑r@MULT↓A1,A2↑R

A1=q,A2=r,R=A1*A2,p=RE↑p→NUM↑q

p=q

2024/10/23622、構造屬性翻譯文法LL(1)分析表。符號輸入符號

+*NUM#SE121314

LL(1)析表(1)S→E↑p@ANSWER↓r

r=p(2)E↑p→+E↑qE↑r@ADD↓A1,A2↑R

A1=q,A2=r,R=1+A2,p=R(3)E↑p→*E↑qE↑r@MULT↓A1,A2↑R

A1=q,A2=r,R=A1*A2,p=R(4)E↑p→NUM↑q

p=q

2024/10/23633、語義動作設計假定要求翻譯器計算輸出由文法定義的表達式值,三個動作符號的翻譯動作為：1)@ADD：把頭兩個域的內容相加并將結果存貯在第三個域所指的單元中，然后出棧。2)@MULT：把頭兩個域的內容相乘并將結果存貯在第三個域所指的單元中，然后出棧。3)@ANSWER：輸出屬性域的內容結果，然后出棧。

2024/10/23641)#入棧，文法開始符號S入棧，輸入指針指向符號++NUM↑2NUM↑3#

S#符號棧：輸入串+NUM↑2NUM↑3#

E↑p@ANSWER↓r#符號棧：2)查分析表S行+列，入棧，因為r=p，所以E↑p為指向@ANSWER↓r的指針。

符號輸入符號

+*NUM#SE121314

輸入符號串+NUM↑2NUM↑3#的分析過程：2024/10/2365(1)S→E↑p@ANSWER↓r

r=p(2)E↑p→+E↑qE↑r@ADD↓A1,A2↑R

A1=q,A2=r,R=A1+A2,p=R(3)E↑p→*E↑qE↑r@MULT↓A1,A2↑R

A1=q,A2=r,R=A1*A2,p=R(4)E↑p→NUM↑q

p=q

NUM↑2NUM↑3#

E↑qE↑r@ADD↓A1↓A2↑R@ANSWER↓r#符號棧：

3)查分析表E行+列,E出棧前,E↑p指向@ANSWER↓r,因為E↑p=@ADD↑R,所以@ADD↑R指向@ANSWER↓r;新入棧的E↑qE↑r,分別指向@ADD↑A1↑A2;因棧頂為+,+出棧,讀下一個符號。

符號輸入符號

+*NUM#SE121314

2024/10/2366E↑p@ANSWER↓r#(1)S→E↑p@ANSWER↓r

r=p(2)E↑p→+E↑qE↑r@ADD↓A1,A2↑R

A1=q,A2=r,R=A1+A2,p=R......+NUM↑2NUM↑3#

NUM↑3#

E↑r@ADD2↓A2↑R@ANSWER↓r#符號棧：

4)查分析表E行NUM列，E出棧前,E↑q指向@ADD↑A1,而E↑q=NUM↑q,所以NUM↑q入棧,把NUM

↑2放入E出棧前E↑q指向的單元@ADD↑A1。然后，NUM出棧,讀下一個符號。

2024/10/2367......(4)E↑p→NUM↑qp=q

符號輸入符號

+*NUM#SE1213

14

符號棧：E↑qE↑r@ADD↓A1↓A2↑R@ANSWER↓r#NUM↑2NUM↑3#

符號輸入符號

+*NUM#SE1213

14

5)查分析表E行NUM列，E出棧前,E↑r指向@ADD↑A2,而E↑r=NUM↑q,所以NUM↑q入棧,把NUM↑3放入E↑r指向的單元@ADD↑A2。然后NUM出棧，讀下一個符號。

#

@ADD23↑R@ANSWER↓r#符號棧：2024/10/2368.......(4)E↑p→NUM↑q

p=q

NUM↑3#

E↑r@ADD2↓A2↑R@ANSWER↓r#符號棧：

6)棧頂為動作符號@ADD：把頭兩個域內容2和3相加，并把計算結果5存貯在第三個域@ADD↑R所指的@ANSWER↓r中，出棧。#

@ANSWER5#符號棧：2024/10/2369符號輸入符號

+*NUM#SE1213

14

......(2)E↑p→+E↑qE↑r@ADD↓A1,A2↑R

A1=q,A2=r,R=A1+A2,p=R#

@ADD23↑R@ANSWER↓r#符號棧：7)棧頂為動作符號@ANSWER,輸出屬性域的內容5，出棧。棧內為#，輸入指針指向#，成