第5章語法制導翻譯技術知識點：語法制導定義、翻譯方案

S屬性、L屬性

S-屬性定義翻譯L-屬性定義翻譯1/851語法制導翻譯技術語義分析包括到語言語義形式語義學研究開始于20世紀60年代初形式語義學能夠分為三類操作語義學：模擬數據加工過程中計算機系統操作指稱語義學：描述數據加工結果公理語義學：用公理化方法描述程序對數據加工語法制導翻譯技術多數編譯程序普遍采取一個技術比較靠近形式化2/852語法制導翻譯技術5.1語法制導定義及翻譯方案5.2S-屬性定義自底向上翻譯5.3L-屬性定義自頂向下翻譯5.4L-屬性定義自底向上翻譯5.5非L屬性定義翻譯小結3/8535.1語法制導定義及翻譯方案對上下文無關文法推廣每個文法符號都能夠有一個屬性集，能夠包含兩類屬性：綜合屬性和繼承屬性。分析樹中一個結點綜合屬性是從其子結點屬性值計算出來繼承屬性是從其弟兄結點和/或父結點屬性值計算出來分析樹中某個結點屬性值是由與在這個結點上所用產生式對應語義規則決定。和產生式相聯絡語義規則建立了屬性之間關系，這些關系可用有向圖（即：依賴圖）來表示。4/854內容安排一、語法制導定義二、依賴圖三、計算次序四、S屬性定義和L屬性定義五、翻譯方案5/855一、語法制導定義在一個語法制導定義中，對應于每一個文法產生式A

，都有與之相聯絡一組語義規則，其形式為：b=

(c1,c2,…,ck)這里，

是一個函數，而且或者(1)b是A一個綜合屬性，且c1、c2、…、ck是產生式右部文法符號屬性，或者(2)b是產生式右部某個文法符號一個繼承屬性，且c1、c2、…、ck是A或產生式右部文法符號屬性。屬性b依賴于屬性c1、c2、…、ck。語義規則函數都不含有副作用語法制導定義稱

為屬性文法6/856語義規則普通情況：語義規則函數可寫成表示式形式。一些情況下：一個語義規則唯一目標就是產生某個副作用，如打印一個值、向符號表中插入一條統計等；這么語義規則通常寫成過程調用或程序段。看成是對應產生式左部非終止符號虛擬綜合屬性。虛屬性和符號‘=’都沒有表示出來。7/857簡單算術表示式求值語法制導定義綜合屬性val與每一個非終止符號E、T、F相聯絡表示對應非終止符號所代表子表示式整數值L

n語義規則是一個過程，打印出由E產生算術表示式值，能夠認為是非終止符號L一個虛擬綜合屬性。產生式L

EnE

E1+TE

TT

T1*FT

FF

(E)F

digit語義規則 print(E.val) E.val=E1.val+T.valE.val=T.valT.val=T1.val*F.valT.val=F.valF.val=E.valF.val=digit.lexval8/858綜合屬性分析樹中，假如一個結點某一屬性由其子結點屬性確定，則這種屬性為該結點綜合屬性。假如一個語法制導定義僅僅使用綜合屬性，則稱這種語法制導定義為S-屬性定義。對于S-屬性定義，通常采取自底向上方法對其分析樹加注釋，即從樹葉到樹根，按照語義規則計算每個結點屬性值。簡單臺式計算機語法制導定義是S-屬性定義9/8593*5+4n分析樹加注釋過程屬性值計算能夠在語法分析過程中進行。LEnE+TTFT*FdigitFdigitdigit.lexval=3.val=3.val=3.lexval=5.val=5.val=15.val=15.lexval=4.val=4.val=4.val=19Print(19)10/8510繼承屬性分析樹中，一個結點繼承屬性值由該結點父結點和/或它弟兄結點屬性值決定。可用繼承屬性表示程序設計語言結構中上下文之間依賴關系能夠跟蹤一個標識符類型能夠跟蹤一個標識符，了解它是出現在賦值號右邊還是左邊，以確定是需要該標識符值還是地址。11/8511一個帶有繼承屬性L.in語法制導定義D產生申明包含了類型關鍵字int或real，后跟一個標識符表。T有綜合屬性type，其值由申明中關鍵字確定。L繼承屬性L.in，表示從父結點或弟兄結點繼承下來類型信息。產生式D

TLT

intT

realL

L1,id

L

id語義規則L.in=T.typeT.type=integerT.type=realL1.in=L.inaddtype(id.entry,L.in)addtype(id.entry,L.in)12/8512語句realid1,id2,id3分析樹加注釋L產生式語義規則使用繼承屬性L.in把類型信息在分析樹中向下傳遞；并經過調用過程addtype，把類型信息填入標識符在符號表中對應表項中。

DTLL,id2L,id3id1real.type=real.in=real.in=real.in=realaddtype(id3.entry,L.in)addtype(id1.entry,L.in)addtype(id2.entry,L.in)13/8513二、依賴圖分析樹中，結點繼承屬性和綜合屬性之間相互依賴關系能夠由依賴圖表示。為每個包含過程調用語義規則引入一個虛擬綜合屬性b，方便把語義規則統一為b=

(c1,c2,…,ck)形式。依賴圖中：為每個屬性設置一個結點假如屬性b依賴于c，那么隸屬性c結點有一條有向邊連到屬性b結點。14/8514算法5.1結構依賴圖輸入：一棵分析樹輸出：一張依賴圖方法：for(分析樹中每一個結點n)for(結點n處文法符號每一個屬性a)為a在依賴圖中建立一個結點;for(分析樹中每一個結點n)for(結點n處所用產生式對應每一個語義規則b=

(c1,c2,…,ck))for(i=1;i<=k;i++)從ci結點到b結點結構一條有向邊;15/8515依賴圖結構舉例產生式依賴規則A

XYA.a=

(X.x,Y.y)X.i=g(A.a,Y.y)AXY.a.x.i.yDTLL,id2L,id3id1real4

type9

in10

addtype7

in8

addtype5

in6

addtype1

entry2

entry

3

entry16/8516三、計算次序有向非循環圖拓撲排序圖中結點一個排序m1,m2,…,mk有向邊只能從這個序列中前邊結點指向后面結點假如mi

mj是從mi指向mj一條邊，那么在序列中mi必須出現在mj之前。依賴圖任何拓撲排序給出了分析樹中結點語義規則計算有效次序在拓撲排序中，一個結點上語義規則b=

(c1,c2,…,ck)中屬性c1,c2,…,ck在計算b時都是可用。拓撲排序：1、2、3、4、5、6、7、8、9、104、5、3、6、7、2、8、9、1、1017/8517計算次序從拓撲排序中能夠得到下面程序，an代表依賴圖中與序號n結點相關屬性：a4=real；a5=a4；addtype(id3.entry,a5)；a7=a5；addtype(id2.entry,a7)；a9=a7；addtype(id1.entry,a9)；18/8518語法制導翻譯過程最基本文法用于建立輸入符號串分析樹；為分析樹結構依賴圖；對依賴圖進行拓撲排序；從這個序列得到語義規則計算次序；照此計算次序進行求值，得到對輸入符號串翻譯。輸入符號串分析樹依賴圖語義規則計算次序計算結果19/8519四、L屬性定義和L屬性定義

L屬性定義：一個語法制導定義是L屬性定義，假如與每個產生式A

X1X2…Xn對應每條語義規則計算屬性都是A綜合屬性，或是Xj（1

j

n）繼承屬性，而該繼承屬性僅依賴于：產生式中Xj左邊符號X1、X2、…、Xj-1屬性；A繼承屬性。每一個S屬性定義都是L屬性定義20/8520例：非L屬性定義

語法制導定義產生式語義規則A

LML.i=l(A.i)M.i=m(L.s)A.s=f(M.s)A

QRR.i=r(A.i)Q.i=q(R.s)A.s=f(Q.s)產生式D

TLT

intT

realL

L1,id

L

id語義規則L.in=T.typeT.type=integerT.type=realL1.in=L.inaddtype(id.entry,L.in)addtype(id.entry,L.in)例：是L屬性定義語法制導定義21/8521屬性計算次序——深度優先遍歷分析樹voiddeepfirst(n:node){for(n每一個子結點m，從左到右){計算m繼承屬性;deepfirst(m);};計算n綜合屬性;}.以分析樹根結點作為實參L屬性定義屬性都能夠用深度優先次序計算。進入結點前，計算它繼承屬性從結點返回時，計算它綜合屬性22/8522五、翻譯方案上下文無關文法一個便于翻譯書寫形式屬性與文法符號相對應語義動作括在花括號中，并插入到產生式右部某個適當位置上給出了使用語義規則進行屬性計算次序分析過程中翻譯注釋23/8523例：一個簡單翻譯方案

E

TR

R

addopT{print（addop.lexeme）}R1|

T

num{print(num.val)}9-5+2分析樹：ET

R9

-

T

R5+TR2

語義動作作為對應產生式左部符號對應結點子結點深度優先遍歷樹中結點，執行其中動作，打印出95-2+{print(

9

)}{print(

-

)}{print(

5

)}{print(

+

)}{print(

2

)}24/8524翻譯方案設計對于S屬性定義：為每一個語義規則建立一個包含賦值動作把這個動作放在對應產生式右邊末尾例：產生式語義規則

T

T1*FT.val=T1.val*F.val以下安排產生式和語義動作：

T

T1*F{T.val=T1.val*F.val}25/8525為L屬性定義設計翻譯方案標準產生式右部文法符號繼承屬性必須在這個符號以前動作中計算出來計算該繼承屬性動作必須出現在對應文法符號之前一個動作不能引用這個動作右邊文法符號綜合屬性產生式左邊非終止符號綜合屬性只有在它所引用全部屬性都計算出來之后才能計算這種屬性計算動作放在產生式右端末尾26/8526例：考慮以下翻譯方案

S

A1A2{A1.in=1；A2.in=2}

A

a{print(A.in)}SA1A2{A1.in=1;A2.in=2}a{print(A.in)}a{print(A.in)}a{print(A.in)}S{A1.in=1;A2.in=2}A1A2a{print(A.in)}

27/8527例：為以下L屬性定義設計翻譯方案產生式語義規則S

BB.ps=10S.ht=B.htB

B1B2B1.ps=B.psB2.ps=B.psB.ht=max(B1.ht,B2.ht)B

B1subB2B1.ps=B.psB2.ps=shrink(B.ps)B.ht=disp(B1.ht,B2.ht)B

textB.ht=text.h

B.ps28/8528把語義規則插入到產生式中適當位置S

{B.ps=10}B{S.ht=B.ht}S

{B.ps=10}

B{S.ht=B.ht}B

{B1.ps=B.ps}B1{B2.ps=B.ps}B2{B.ht=max(B1.ht,B2.ht)}B

{B1.ps=B.ps}B1sub{B2.ps=shrink(B.ps)}B2{B.ht=disp(B1.ht,B2.ht)}B

text{B.ht=text.h

B.ps}29/85295.2S-屬性定義自底向上翻譯S屬性定義：只用綜合屬性語法制導定義一、語法樹二、結構表示式語法樹三、結構表示式語法樹語法制導定義四、表示式有向非循環圖（dag）五、S屬性定義自底向上實現30/8530一、語法樹把語法規則中對語義無關緊要詳細要求去掉，剩下來本質性東西稱為抽象語法。如：賦值語句：x=y、x:=y、或y

x抽象形式：assignment(variable,expression)語法樹：分析樹抽象（或壓縮）形式。也稱為語法結構樹或結構樹。內部結點表示運算符號，其子結點表示它運算分量。31/8531語法樹示例S

ifEthenS1elseS2語法樹if--then--elseES1S2+*435表示式3*5+4語法樹LEnE+TTFT*FdigitFdigitdigit32/8532二、結構表示式語法樹表示式語法樹形式每一個運算符號或運算分量都對應樹中一個結點運算符號結點子結點分別是與該運算符各個運算分量對應子樹根。每一個結點可包含若干個域：標識域、指針域、屬性值域等在運算符結點中一個域標識運算符號其它各域包含指向與各運算分量對應結點指針稱運算符號為該結點標號33/8533結構函數makenode(op,left,right)建立一個運算符號結點，標號是op；域left和right是指向其左右運算分量結點指針。makeleaf(id,entry)建立一個標識符結點，標號是id；域entry是指向該標識符在符號表中對應條目標指針。makeleaf(num,val)建立一個數結點，標號為num；域val用于保留該數值。34/8534建立表示式a-4+c語法樹p1=makeleaf(id,entrya);p2=makeleaf(num,4);p3=makenode(‘-’,p1,p2);p4=makeleaf(id,entryc);p5=makenode(‘+’,p3,p4);

id符號表中a入口P1num4P2

-

P3

id符號表中c入口P4

+

P5+-ca435/8535三、結構表示式語法樹語法制導定義目標：為表示式創建語法樹產生式語義：創建與產生式左部符號代表子表示式對應子樹，即創建子樹根結點。文法符號屬性：統計所建結點，E.nptr、T.nptr指向對應子樹根結點指針產生式語義動作：E

E1+TE.nptr=makenode(

+

,E1.nptr,T.nptr)

T

idT.nptr=makeleaf(id,id.entry)

T

numT.nptr=makeleaf(num,num.val)36/8536結構表示式語法樹語法制導定義產生式E

E1+TE

E1-TE

TT

(E)T

idT

numE.nptr=makenode(

+

,E1.nptr,T.nptr)E.nptr=makenode(

-

,E1.nptr,T.nptr)E.nptr=T.nptrT.nptr=E.nptrT.nptr=makeleaf(id,id.entry)T.nptr=makeleaf(num,num.val)語義規則37/8537表示式a-4+c語法樹結構num4

id符號表中a入口aEEETc4.nptr.nptr.nptr.nptr.nptr.nptr

-

id符號表中c入口+

-T+T38/8538四、表示式有向非循環圖(dag)dag與語法樹相同地方：表示式每一個子表示式都有一個結點一個內部結點表示一個運算符號，且它子結點表示它運算分量。dag與語法樹不一樣地方：dag中，對應一個公共子表示式結點含有多個父結點語法樹中，公共子表示式被表示為重復子樹為表示式創建dag函數makenode和makeleaf建立新結點之前先檢驗是否已經存在一個相同結點若已存在，返回一個指向先前已結構好結點指針；不然，創建一個新結點，返回指向新結點指針。39/8539為表示式a+a*(b-c)+(b-c)*d結構dag函數調用p1=makeleaf(id,a)；p2=makeleaf(id,a)；p3=makeleaf(id,b)；p4=makeleaf(id,c)；p5=makenode(

-

,p3,p4)；p6=makenode(

*

,p2,p5)；p7=makenode(

+

,p1,p6)；p8=makeleaf(id,b)；p9=makeleaf(id,c)；p10=makenode(

-

,p8,p9)；p11=makeleaf(id,d)；p12=makenode(

*

,p10,p11)；p13=makenode(

+

,p7,p12)；abc

-*+d*+

p1

p2

p3

p4

p5

p6

p7

p8

p9

p10

p11

p12

p1340/8540五、S-屬性定義自底向上實現已知自底向上分析方法中，分析程序使用一個棧來存放已經分析過子樹信息。分析樹中某結點綜合屬性由其子結點屬性值計算得到自底向上分析程序在分析輸入符號串同時能夠計算綜合屬性考慮怎樣保留文法符號綜合屬性值？保留屬性值數據結構怎樣與分析棧相聯絡？怎樣確保：每當進行歸約時，由棧中正在歸約產生式右部符號屬性值計算其左部符號綜合屬性值。41/8541擴充分析棧目標：使之能夠保留綜合屬性做法：在分析棧中增加一個域，來存放綜合屬性值例：帶有綜合屬性域分析棧棧由一對數組state和val實現state元素是指向LR(1)分析表中狀態指針（或索引）假如state[i]對應符號為A，val[i]中就存放分析樹中與結點A對應屬性值。假設綜合屬性剛好在每次歸約前計算A

XYZ對應語義規則是A.a=

(X.x,Y.y,Z.z)ZZ.zYY.yXX.x┅┅topstateval42/8542修改分析程序對于終止符號其綜合屬性值由詞法分析程序產生當分析程序執行移進操作時，其屬性值隨終止符號（或狀態符號）一起入棧。為每個語義規則編寫一段代碼，以計算屬性值對每一個產生式A

XYZ把屬性值計算與歸約動作聯絡起來歸約前，執行與產生式相關代碼段歸約：右部符號及其屬性出棧左部符號及其屬性入棧LR分析程序中應增加計算屬性值

代碼段ZZ.zYY.yXX.xtop?

......statevalAA.a43/8543例：用LR分析程序實現表示式求值產生式L

EnE

E1+TE

TT

T1*FT

FF

(E)F

digit語義規則 print(E.val) E.val=E1.val+T.valE.val=T.valT.val=T1.val*F.valT.val=F.valF.val=E.valF.val=digit.lexval代碼段print(val[top])val[ntop]=val[top-2]+val[top]val[ntop]=val[top-2]*val[top]val[ntop]=val[top-1]44/8544對3*5+4n進行分析動作序列步驟輸入分析棧分析動作(1)3*5+4nstate:0

val:-移進(2)*5+4nstate:05

val:-3歸約，用F

digit(3)*5+4nstate:03val:-3歸約，用T

F(4)*5+4nstate:02val:-3移進(5)5+4nstate:027val:-3-移進(6)+4nstate:0275val:-3-5歸約，用F

digit(7)+4nstate:02710val:-3-5歸約，用T

T*F45/8545步驟輸入分析棧分析動作(8)+4nstate:02val:-15歸約，用E

T(9)+4nstate:01val:-15移進(10)4nstate:016val:-15-移進(11)nstate:0165val:-15-4歸約，用F

digit(12)nstate:0163val:-15-4歸約，用T

F(13)nstate:0169val:-15-4歸約，用E

E+T(14)nstate:01val:-19接收46/85465.3L-屬性定義自頂向下翻譯在自頂向下分析過程中實現L屬性定義翻譯預測分析方法對文法要求不含左遞歸A

FIRST()FIRST()=一、消除翻譯方案中左遞歸二、預測翻譯程序設計47/8547一、消除翻譯方案中左遞歸例：考慮關于表示式語法制導定義產生式語義規則E

E1+TE.val=E1.val+T.valE

E1-TE.val=E1.val-T.valE

T

E.val=T.valT

(E)

T.val=E.valT

num

T.val=num.val翻譯方案：(1)E

E1+T{E.val=E1.val+T.val}(2)E

E1-T{E.val=E1.val-T.val}(3)E

T{E.val=T.val}(4)T

(E){T.val=E.val}(5)T

num{T.val=num.val}由(1)和(3)有：(1

)E

T{E.val=T.val}R(3

)R

+T{E.val=E1.val+T.val}R1(3")

R

繼承屬性R.i：表示在R之前已經推導出子表示式值綜合屬性R.s：表示在R完全展開之后得到表示式值消除左遞歸方法：A

A

|

替換為：A

RR

R|

48/8548R1.i語義規則為：R1.i=R.i+T.valR.s語義規則為：R.s=R1.s于是得到：(3

)R

+T{R1.i=R.i+T.val}R1{R.s=R1.s}一樣可得到：(2

)R

-T{R1.i=R.i-T.val}R1{R.s=R1.s}為(3")設置把R.i傳遞給R.s語義動作，得到：

(3")R

{R.s=R.i}對于(1

)，E

T{E.val=T.val}R經過R屬性R.s和R.i完成E和T綜合屬性傳遞E.val=T.val，得到：(1

)E

T{R.i=T.val}

R{E.val=R.s}對于(3

)R

+T{E.val=E1.val+T.val}R149/8549翻譯方案ETRnum+TRnum-TRnum

.val=8.val=8.i=8.val=5.val=5.i=13.val=7.val=7.i=6.s=6.s=6.s=6.val=6E

T{R.i=T.val}R{E.val=R.s}R

+T{R1.i=R.i+T.val}R1{R.s=R1.s}R

-T{R1.i=R.i-T.val}R1{R.s=R1.s}R

{R.s=R.i}T

(E){T.val=E.val}T

num{T.val=num.val}表示式8+5-7翻譯過程50/8550消除翻譯方案中左遞歸普通方法翻譯方案：A

A1Y{A.a=g(A1.a,Y.y)}A

X{A.a=f(X.x)}為R設置繼承屬性R.i和綜合屬性R.sR.i：表示在R之前已經掃描過符號串屬性值R.s：表示在R完全展開為終止符號之后得到符號串屬性值。消除基本文法中左遞歸：A

XRR

YR|

翻譯方案轉換為：A

X{R.i=f(X.x)}R{A.a=R.s}R

Y{R1.i=g(R.i,Y,y)}R1{R.s=R1.s}R

{R.s=R.i}

AXR

.x.i.s.aAXR

.x.i.s.aYR.y.i.s51/8551例：考慮建立表示式語法樹語法制導定義翻譯方案(1)E

E1+T{E.nptr=makenode(

+

,E1.nptr,T.nptr)}(2)E

E1-T{E.nptr=makenode(

-

,E1.nptr,T.nptr)}(3)E

T{E.nptr=T.nptr}(4)T

(E){T.nptr=E.nptr}(5)T

id{T.nptr=makelead(id,id.entry)}(6)T

num{T.nptr=makeleaf(num,num.val)}消除左遞歸：E

TRR

+TR|-TR|

非終止符號R，含有繼承屬性R.i和綜合屬性R.sR.i：保留指向在R之前建立子樹根結點指針R.s：保留指向R完全展開之后建立子樹根結點指針52/8552結構表示式語法樹翻譯方案E

T{R.i=T.nptr}R{E.nptr=R.s}R

+T{R1.i=makenode(

+

,R.i,T.nptr)}R1{R.s=R1.s}R

-T{R1.i=makenode(

-

,R.i,T.nptr)}R1{R.s=R1.s}R

{R.s=R.i}T

(E){T.nptr=E.nptr}T

id{T.nptr=makelead(id,id.entry)}T

num{T.nptr=makeleaf(num,num.val)}53/8553使用繼承屬性結構a-4+c語法樹num4id符號表中a入口.nptr-

id符號表中c入口ETRid-TRnum+TRid

.

nptr.

nptr.

i.

i.

i+

.

s.

s.

s.

nptr54/8554二、預測翻譯程序設計從翻譯方案出發結構自頂向下語法制導翻譯程序算法5.2：結構語法制導預測翻譯程序輸入：基礎文法適合于預測分析語法制導翻譯方案輸出：語法制導翻譯程序方法：（修改預測分析程序結構技術）(1)為每個非終止符號A建立一個函數(能夠是遞歸函數)A每一個繼承屬性對應函數一個形參A綜合屬性作為函數返回值A產生式中每個文法符號每個屬性都對應一個局部變量(2)A函數代碼由多個分支組成55/8555按照從左到右次序考慮產生式右部記號、非終止符號和語義動作對帶有綜合屬性x記號X把屬性x值保留于為X.x申明變量中產生一個匹配記號X調用推進掃描指針對非終止符號B產生一個函數調用語句c=B(b1,b2,…,bk)bi(i=1,2,…,k)是對應于B繼承屬性變量c是對應于B綜合屬性變量對每一個語義動作把動作代碼復制到分析程序中用代表屬性變量代替翻譯方案中引用屬性(3)與每個產生式相關程序代碼56/8556例：為結構表示式語法樹翻譯方案

結構翻譯程序為每個非終止符號結構一個函數functionE:

syntax_tree_node；function(in:

syntax_tree_node):

syntax_tree_node；functionT:

syntax_tree_node；兩個R產生式結合起來，用符號addop代表

+

和

-

R

addopT{R1.i=makenode(addop.lexeme,R.i,T.nptr)}R1{R.s=R1.s}R

{R.s=R.i}57/8557與R

addopTR|

對應分析過程voidproc_R(void){if(lookahead==addop){match(addop);proc_T();proc_R();}};58/8558實現翻譯方案函數syntax_tree_nodefun_R(syntax_tree_nodein){syntax_tree_nodetnptr,i1,s1,s;charaddoplexeme;if(lookahead==addop){/*產生式R

addopTR*/addoplexeme=lexval;match(addop);tnptr=fun_T();i1=makenode(addoplexeme,in,tnptr);s1=R(i1);s=s1;};else/*產生式R

*/s=in;returns;};59/85595.4L屬性定義自底向上翻譯在自底向上分析過程中實現L屬性定義翻譯能夠實現任何基于LL(1)文法L屬性定義能夠實現許多（不是全部）基于LR(1)文法L屬性定義一、從翻譯方案中去掉嵌入動作二、分析棧中繼承屬性三、模擬繼承屬性計算四、用綜合屬性代替繼承屬性60/8560一、從翻譯方案中去掉嵌入動作自底向上地處理繼承屬性等價變換：使全部嵌入動作都出現在產生式右端末尾方法：在基礎文法中引入新產生式，形如：M

M：標識非終止符號，用來代替嵌入在產生式中動作把被M替換動作放在產生式M

末尾61/8561例：去掉以下翻譯方案中嵌入動作：

E

TR

R

+T{print(

+

)}R|-T{print(

-

)}R|

T

num{print(num.val)}標識非終止符號M和N，及產生式M

和N

用M和N替換出現在R產生式中動作新翻譯方案E

TRR

+TMR|-TNR|

T

num{print(num.val)}M

{print(

+

)}N

{print(

-

)}62/8562變換前、后翻譯方案是等價numprint(num.val)-Tprint(

-

)R4numprint(num.val)

5numprint(num.val)+Tprint(

+

)R3ETR深度優先次序進行遍歷print(num1.val)print(num2.val)print(

+

)print(num3.val)print(

-

)動作執行結果是：34+5-變換前，表示式3+4-5分析樹：63/8563變換后，表示式3+4-5分析樹：深度優先次序進行遍歷print(num1.val)print(num2.val)print(

+

)print(num3.val)print(

-

)動作執行結果是：34+5-Numprint(num.val)

print(

+

)-TNR4Numprint(num.val)

print(

-

)

5Numprint(num.val)+TMR3ETR64/8564二、分析棧中繼承屬性LR分析程序對產生式A

XY歸約考慮分析過程中屬性計算65/8565復制規則主要作用翻譯方案：D

T{L.in=T.type}LT

int{T.type=integer}T

real{T.type=real}L

{L1.in=L.in}L1,id{addtype(id.entry,L.in)}L

id{addtype(id.entry,L.in)}DTLrealL,rL,qp.type.in.in.in.s.entry.s.entry.s.entry輸入符號串：realp,q,r66/8566例：應用繼承屬性，用復制規則傳遞標識符類型輸入棧分析動作realp,q,r$state:val:移進p,q,r$state:realval:real歸約，用T

realp,q,r$state:Tval:real移進,q,r$state:Tpval:realpentry歸約，用L

id,q,r$state:TLval:real-移進q,r$state:TL,val:real-,移進,r$state:TL,qval:real-,qentry歸約，用L

L,id,r$state:TLval:real-移進r$state:TL,val:real-,移進$state:TL,rval:real-,rentry歸約，用L

L,id$state:TLval:real-歸約，用D

TL$state:Dval:-接收67/8567計算屬性值代碼段產生式代碼段D

TLT

intval[ntop]=integerT

realval[ntop]=realL

L,idaddtype(val[top],val[top-3])L

idaddtype(val[top],val[top-1])68/8568三、模擬繼承屬性計算要想從棧中取得繼承屬性，當且僅當文法允許屬性值在棧中存放位置能夠預測。例：屬性值在棧中位置不可預測語法制導定義產生式語義規則(1)S

aACC.i=A.s(2)S

bABCC.i=A.s(3)C

cC.s=g(C.i)引入標識非終止符號，對原語法制導定義進行等價變換產生式語義規則(1’)

S

aACC.i=A.s(2’)

S

bABMCM.i=A.s；C.i=M.s(3’)C

cC.s=g(C.i)

(4’)M

M.s=M.i SbA.sB.iM.s.iC

69/8569用標識非終止符號模擬

非復制規則語義規則例：考慮以下產生式及語義規則：S

aACC.i=f(A.s)C

cC.s=g(C.i)┉aANc┉A.sN.stop┉aAc┉A.stop引入標識非終止符號NS

aANCN.i=A.s；C.i=N.sN

N.s=f(N.i)全部繼承屬性均由復制規則實現繼承屬性在棧中位置能夠預測70/8570例：用復制規則設置全部繼承屬性產生式語義規則S

LBB.ps=L.sS.ht=B.htL

L.s=10B

B1MB2B1.ps=B.psM.i=B.psB2.ps=M.sB.ht=max(B1.ht,B2.ht)B

B1subNB2B1.ps=B.psN.i=B.psB2.ps=N.sB.ht=disp(B1.ht,B2.ht)B

textB.ht=text.h

B.psM

M.s=M.iN

N.s=shrink(N.i)71/8571實現語法制導定義代碼段產生式語義規則S

LBval[ntop]=val[top]L

val[ntop]=10B

B1MB2val[ntop]=max(val[top-2],val[top])B

B1subNB2val[ntop]=disp(val[top-3],val[top])B

textval[ntop]=val[top]

val[top-1]M

val[ntop]=val[top-1]N

val[ntop]=shrink(val[top-2]) 72/8572算法5.3：L屬性定義自底向上分析和翻譯輸入：基礎文法是LL(1)文法L屬性定義輸出：在分析過程中計算全部屬性值分析程序方法：假設：每個非終止符號A都有一個繼承屬性A.i每一個文法符號X都有一個綜合屬性X.s(1)對每個產生式A

X1X2…Xn引入n個新標識非終止符號M1、M2、…、Mn用產生式A

M1X1M2X2…MnXn代替原來產生式Xj繼承屬性與標識非終止符號Mj相聯絡屬性Xj.i(也就是Mj.s)總是在Mj處計算，且發生在開始做歸約到Xj動作之前。73/8573(2)在自底向上分析過程中，各個屬性值都能夠

被計算出來第一個情況：用Mj

進行歸約已知：每個標識非終止符號在文法中是唯一Mj屬于哪個形式為A

M1X1M2X2…MnXn產生式計算屬性Xj.i需要哪些屬性、以及它們位置

M1X1M2X2

…Mj-1Xj-1

A.iX1.iX1.sX2.iX2.s…Xj-1.iXj-1.sstatevaltop-2(j-1)top-2(j-1)+2top-2(j-2)+2toptop-2(j-1)+1top-2(j-2)+1top-1MjMj.sntop74/8574第二種情況：用A

M1X1M2X2…MnXn進行歸約已知：A.i值、及其位置計算A.s所需要屬性值均已在棧中已知位置 即各相關Xj位置上stateval…M1X1M2X2

…MnXn…A.iX1.iX1.sX2.iX2.s…Xn.iXn.stoptop-2ntop-2n+2top-2n+4stateval…A…A.iA.stoptop-175/8575四、用綜合屬性代替繼承屬性例：PASCAL變量申明語句可由以下文法產生：D

L:TT

integer|charL

L,id|id問題：標識符由L產生，而類型不在L子樹中歸約從左向右進行，類型信息從右向左傳遞只用綜合屬性不能使類型和標識符聯絡在一起DL:TL,rL,qpchar.type.in.in.in...76/8576處理方法改寫文法，使類型作為標識符表最終一個元素D

idLL

,idL|:TT

integer|char