編譯原理 5 語法制導(dǎo)翻譯學(xué)習(xí)課件

語法制導(dǎo)翻譯

哈爾濱工業(yè)大學(xué)陳鄞第五章編譯的階段詞法分析語法分析語義分析中間代碼生成代碼優(yōu)化目標代碼生成語義翻譯語法制導(dǎo)翻譯(Syntax-DirectedTranslation)語法制導(dǎo)翻譯使用CFG來引導(dǎo)對語言的翻譯，是一種面向文法的翻譯技術(shù)什么是語法制導(dǎo)翻譯如何表示語義信息？為CFG中的文法符號設(shè)置語義屬性，用來表示語法成分對應(yīng)的語義信息如何計算語義屬性？文法符號的語義屬性值是用與文法符號所在產(chǎn)生式（語法規(guī)則）相關(guān)聯(lián)的語義規(guī)則來計算的對于給定的輸入串x，構(gòu)建x的語法分析樹，并利用與產(chǎn)生式（語法規(guī)則）相關(guān)聯(lián)的語義規(guī)則來計算分析樹中各結(jié)點對應(yīng)的語義屬性值語法制導(dǎo)翻譯的基本思想將語義規(guī)則同語法規(guī)則（產(chǎn)生式）聯(lián)系起來涉及的兩個概念語法制導(dǎo)定義(Syntax-DirectedDefinitions,SDD)語法制導(dǎo)翻譯方案(SDT,Syntax-DirectedTranslationScheme)語法制導(dǎo)翻譯的基本思想SDD是對CFG的推廣將每個文法符號和一個語義屬性集合相關(guān)聯(lián)將每個產(chǎn)生式和一組語義規(guī)則相關(guān)聯(lián)，這些規(guī)則用于計算該產(chǎn)生式中各文法符號的屬性值如果X是一個文法符號，a是X的一個屬性，則用X.a表示屬性a在某個標號為X的分析樹結(jié)點上的值例語法制導(dǎo)定義(SDD)

產(chǎn)生式

語義規(guī)則D→T

L

L.inh=T.type

T→int T.type=integerT→real T.type=realL→L1,id L1.inh=L.inhSDT是在產(chǎn)生式右部嵌入了程序片段的CFG，這些程序片段稱為語義動作。按照慣例，語義動作放在花括號內(nèi)例D→T

{L.inh=T.type}LT→int{T.type=int}T→real{T.type=real}L→{L1.inh=L.inh}L1,id一個語義動作在產(chǎn)生式中的位置決定了這個動作的執(zhí)行時間語法制導(dǎo)翻譯方案(SDT)SDD是關(guān)于語言翻譯的高層次規(guī)格說明隱蔽了許多具體實現(xiàn)細節(jié)，使用戶不必顯式地說明翻譯發(fā)生的順序SDT可以看作是對SDD的一種補充，是SDD的具體實施方案顯式地指明了語義規(guī)則的計算順序，以便說明某些實現(xiàn)細節(jié)SDD與SDT5.1語法制導(dǎo)定義SDD5.2S-屬性定義與L-屬性定義5.3語法制導(dǎo)翻譯方案SDT5.4L-屬性定義的自頂向下翻譯5.5L-屬性定義的自底向上翻譯本章內(nèi)容語法制導(dǎo)定義SDD是對CFG的推廣將每個文法符號和一個語義屬性集合相關(guān)聯(lián)將每個產(chǎn)生式和一組語義規(guī)則相關(guān)聯(lián)，用來計算該產(chǎn)生式中各個文法符號的屬性值文法符號的屬性綜合屬性（synthesizedattribute）繼承屬性（inheritedattribute）5.1語法制導(dǎo)定義SDD綜合屬性（synthesizedattribute）在分析樹結(jié)點N上的非終結(jié)符A的綜合屬性只能通過N的子結(jié)點或N本身的屬性值來定義例

終結(jié)符可以具有綜合屬性。終結(jié)符的綜合屬性值是由詞法分析器提供的詞法值。因此在SDD中沒有計算終結(jié)符的屬性值的語義規(guī)則+TvalEvalE1val產(chǎn)生式語義規(guī)則E

E1+TEval=E1val+Tval繼承屬性(inheritedattribute)在分析樹結(jié)點N上的非終結(jié)符A的繼承屬性只能通過N的父結(jié)點、N的兄弟結(jié)點或N本身的屬性值來定義例終結(jié)符沒有繼承屬性。終結(jié)符從詞法分析器處獲得的屬性值被歸為綜合屬性值產(chǎn)生式語義規(guī)則D

TL

L.

inh=T.

typedigit.lexval=3F.val=3T.val=3digit.lexval=5F.val=5T.val=15*+digit.lexval=4F.val=4T.val=4E.val=19LnE.val=15注釋分析樹(Annotated

parsetree)：每個節(jié)點都帶有屬性值的分析樹輸入：3*5+4n產(chǎn)生式

語義規(guī)則(1)L

En print(Eval)(2)E

E1+T Eval=E1val+Tval(3)E

T

Eval=Tval(4)T

T1*F

Tval=T1val×Fval(5)T

F

Tval=Fval(6)F(E) Fval=Eval(7)Fdigit Fval=digitlexval副作用(Sideeffect)SDD：例：帶有綜合屬性的SDD

id.lexeme=aid.lexeme=bid.lexeme=cDL.in=realT.type=realrealL.in=real,L.in=real,SDD：

產(chǎn)生式語義規(guī)則(1)

D

TL L.inh=T.

type(2)T

int T.type=int(3)T

real

T.type=real(4)L

L1,id L1.inh=L.inh

addtype(id.lexeme,L.inh)(5)

Lid addtype(id.lexeme,L.inh)輸入：reala

,b,c例：帶有繼承屬性L.in的SDD

一個沒有副作用的SDD有時也稱為屬性文法屬性文法的規(guī)則僅僅通過其它屬性值和常量來定義一個屬性值例產(chǎn)生式

語義規(guī)則(1)L

En

Lval=Eval(2)E

E1+T Eval=E1val+Tval(3)E

T

Eval=Tval(4)T

T1*F

Tval=T1val×Fval(5)T

F

Tval=Fval(6)F(E) Fval=Eval(7)F

digit

Fval=digit

lexval屬性文法(AttributeGrammar)SDD為CFG中的文法符號設(shè)置語義屬性。對于給定的輸入串x，應(yīng)用語義規(guī)則計算分析樹中各結(jié)點對應(yīng)的屬性值按照什么順序計算屬性值？語義規(guī)則建立了屬性之間的依賴關(guān)系，在對語法分析樹結(jié)點的一個屬性求值之前，必須首先求出這個屬性值所依賴的所有屬性值SDD的求值順序依賴圖是一個描述了分析樹中結(jié)點屬性間依賴關(guān)系的有向圖分析樹中每個標號為X的結(jié)點的每個屬性a都對應(yīng)著依賴圖中的一個結(jié)點如果屬性X.a的值依賴于屬性Y.b的值，則依賴圖中有一條從Y.b的結(jié)點指向X.a的結(jié)點的有向邊依賴圖(DependencyGraph)typeinininlexemelexemelexeme，idLDTL，idLidrealSDD：

產(chǎn)生式語義規(guī)則(1)

D

TL L.in=T.

type(2)T

int T.type=int(3)T

real

T.type=real(4)L

L1,id L1.in=L.in

addtype(id.lexeme,L.in)(5)

Lid addtype(id.lexeme,L.in)輸入：reala

,b,c例for分析樹中的每個結(jié)點ndofor與結(jié)點n對應(yīng)的文法符號的每個屬性ado在依賴圖中為a構(gòu)造一個結(jié)點；for

分析樹的每個結(jié)點n

do

for結(jié)點n所用產(chǎn)生式對應(yīng)的每條語義規(guī)則b:＝f(c1,c2,…,ck

)dofori:=1tok

do

從結(jié)點ci到結(jié)點b構(gòu)造一條有向邊；依賴圖的構(gòu)造方法typeinininlexemelexemelexeme，idLDTL，idLidrealSDD：

產(chǎn)生式語義規(guī)則(1)

D

TL L.in=T.

type(2)T

int T.type=int(3)T

real

T.type=real(4)L

L1,id L1.in=L.in

addtype(id.lexeme,L.in)(5)

Lid addtype(id.lexeme,L.in)輸入：reala

,b,c例可行的求值順序是滿足下列條件的結(jié)點序列N1,N2,…,Nk

：如果依賴圖中有一條從結(jié)點Ni到

Nj

的邊(Ni→Nj),那么i<j（即：在節(jié)點序列中，Ni排在Nj前面）這樣的排序?qū)⒁粋€有向圖變成了一個線性排序，這個排序稱為這個圖的拓撲排序(topologicalsort)屬性值的計算順序type4in5

6

in7

8in109lexeme

3lexeme

2

lexeme1，idLDTL，idLidrealSDD：

產(chǎn)生式語義規(guī)則(1)

D

TL L.in=T.

type(2)T

int T.type=int(3)T

real

T.type=real(4)L

L1,id L1.in=L.in

addtype(id.lexeme,L.in)(5)

Lid addtype(id.lexeme,L.in)輸入：reala

,b,c例拓撲排序：1,2,3,4,5,6,7,8,9,104,3,2,1,5,7,6,9,8,10例如果圖中沒有環(huán)，那么至少存在一個拓撲排序A.sB.iAB產(chǎn)生式語義規(guī)則A

B A.s

=B.iB.i

=A.s+1對于只具有綜合屬性的SDD

，可以按照任何自底向上的順序計算它們的值對于同時具有繼承屬性和綜合屬性的SDD，不能保證存在一個順序來對各個節(jié)點上的屬性進行求值從計算的角度看，給定一個SDD，很難確定是否存在某棵語法分析樹，使得SDD的屬性之間存在循環(huán)依賴關(guān)系幸運的是，存在一個SDD的有用子類，它們能夠保證對每棵語法分析樹都存在一個求值順序，因為它們不允許產(chǎn)生帶有環(huán)的依賴圖不僅如此，接下來介紹的兩類SDD可以和自頂向下及自底向上的語法分析過程一起高效地實現(xiàn)S-屬性定義

(S-AttributedDefinitions,S-SDD)L-屬性定義

(L-AttributedDefinitions,L-SDD)5.1語法制導(dǎo)定義SDD5.2S-屬性定義與L-屬性定義5.3語法制導(dǎo)翻譯方案SDT5.4L-屬性定義的自頂向下翻譯5.5L-屬性定義的自底向上翻譯提綱S-屬性定義僅僅使用綜合屬性的SDD稱為S屬性的SDD，或S-屬性定義、S-SDD例如果一個SDD是S屬性的，可以按照語法分析樹節(jié)點的任何自底向上順序來計算它的各個屬性值S-屬性定義可以在自底向上語法分析的過程中實現(xiàn)

產(chǎn)生式

語義規(guī)則(1)L

En Lval=Eval(2)E

E1+T Eval=E1val+Tval(3)E

T

Eval=Tval(4)T

T1*F

Tval=T1val×Fval(5)T

F

Tval=Fval(6)F(E) Fval=Eval(7)Fdigit Fval=digitlexval5.2S-屬性定義與L-屬性定義L-屬性定義（也稱為L屬性的SDD或L-SDD）的直觀含義：在一個產(chǎn)生式所關(guān)聯(lián)的各屬性之間，依賴圖的邊可以從左到右，但不能從右到左（因此稱為L屬性的，L是Left的首字母）L-屬性定義一個SDD是L-屬性定義，當且僅當它的每個屬性要么是一個綜合屬性，要么是滿足如下條件的繼承屬性：假設(shè)存在一個產(chǎn)生式A→X1X2…Xn，其右部符號Xi(1

i

n)的繼承屬性僅依賴于下列屬性：A的繼承屬性產(chǎn)生式中Xi左邊的符號

X1,X2,…,Xi-1

的屬性Xi本身的屬性，但Xi的全部屬性不能在依賴圖中形成環(huán)路每個S-屬性定義都是L-屬性定義L-SDD的正式定義一個SDD是L-屬性定義，當且僅當它的每個屬性要么是一個綜合屬性，要么是滿足如下條件的繼承屬性：假設(shè)存在一個產(chǎn)生式A→X1X2…Xn，其右部符號Xi(1

i

n)的繼承屬性僅依賴于下列屬性：A的繼承屬性產(chǎn)生式中Xi左邊的符號

X1,X2,…,Xi-1

的屬性Xi本身的屬性，但Xi的全部屬性不能在依賴圖中形成環(huán)路為什么不能是綜合屬性？L-SDD的正式定義一個SDD是L-屬性定義，當且僅當它的每個屬性要么是一個綜合屬性，要么是滿足如下條件的繼承屬性：假設(shè)存在一個產(chǎn)生式A→X1X2…Xn，其右部符號Xi(1

i

n)的繼承屬性僅依賴于下列屬性：A的繼承屬性產(chǎn)生式中Xi左邊的符號

X1,X2,…,Xi-1

的屬性Xi本身的屬性，但Xi的全部屬性不能在依賴圖中形成環(huán)路XjAisisL-SDD的正式定義

產(chǎn)生式語義規(guī)則(1)

T

FT′

T′.inh=F.val

T.val

=T′.syn(2)T′

*FT1′

T1′.inh=T′.inh×F.val

T′.syn=

T1′.syn

(3)T′

ε

T′.syn=T′.inh(4)

Fdigit F.val=digit.lexval綜合屬性繼承屬性例：L-SDD非L屬性的SDD例

產(chǎn)生式

語義規(guī)則(1)A

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

QR R.i=r(A.i) Q.i=q(R.s)

A.s=f(Q.s)綜合屬性繼承屬性×5.1語法制導(dǎo)定義SDD5.2S-屬性定義與L-屬性定義5.3語法制導(dǎo)翻譯方案SDT5.4L-屬性定義的自頂向下翻譯5.5L-屬性定義的自底向上翻譯提綱

語法制導(dǎo)翻譯方案(SDT)是在產(chǎn)生式右部中嵌入了程序片段(稱為語義動作)的CFG例D→T

{L.inh=T.type}LT→int{T.type=integer}T→real{T.type=real}L→{L1.inh=L.inh}L1,id5.3語法制導(dǎo)翻譯方案SDT

語法制導(dǎo)翻譯方案(SDT)是在產(chǎn)生式右部中嵌入了程序片段(稱為語義動作)的CFG語法制導(dǎo)翻譯方案SDTSDT可以看作是SDD的具體實施方案本節(jié)主要關(guān)注如何使用SDT來實現(xiàn)兩類重要的SDD，因為在這兩種情況下，SDT可以在語法分析過程中實現(xiàn)基本文法可以使用LR分析技術(shù)，且SDD是S屬性的基本文法可以使用LL分析技術(shù)，且SDD是L屬性的

將一個S-SDD轉(zhuǎn)換為SDT的方法：將每個語義動作都放在產(chǎn)生式的最后例SDT產(chǎn)生式

語義規(guī)則(1)L

En

Lval=Eval(2)E

E1+T Eval=E1val+Tval(3)E

T

Eval=Tval(4)T

T1*F

Tval=T1val×Fval(5)T

F

Tval=Fval(6)F(E) Fval=Eval(7)F

digit

Fval=digit

lexval(1)L

En

{Lval=Eval}(2)E

E1+T{Eval=E1val+Tval}(3)E

T

{Eval=Tval}(4)T

T1*F

{Tval=T1val×Fval}(5)T

F

{Tval=Fval}(6)F(E){Fval=Eval}(7)F

digit

{Fval=digit

lexval}S-SDD將S-SDD轉(zhuǎn)換為SDT如果一個S-SDD的基本文法可以使用LR分析技術(shù)，那么它的SDT可以在LR語法分析過程中實現(xiàn)例

產(chǎn)生式

語義規(guī)則(1)L

En

Lval=Eval(2)E

E1+TEval=E1val+Tval(3)E

T

Eval=Tval(4)T

T1*F

Tval=T1val×Fval(5)T

F

Tval=Fval(6)F(E)Fval=Eval(7)F

digit

Fval=digit

lexvalS-SDDSLR自動機當歸約發(fā)生時執(zhí)行相應(yīng)的語義動作S-屬性定義的SDT實現(xiàn)狀態(tài)文法符號綜合屬性S0$.........Sm-2XX.xSm-1YY.ySmZZ.z.........top若支持多個屬性使棧記錄變得足夠大在棧記錄中存放指針擴展的LR語法分析棧在分析棧中使用一個附加的域來存放綜合屬性值A(chǔ)

XYZ{A.a=f(X.x,Y.y,Z.z)}A.aX.X

Y.y

Z.zstack[top-2].symb=A

stack[top-2].val=f(stack[top-2].val,stack[top-1].val,stack[top].val)top=top-2;重寫語義動作使其顯示地操作語法分析棧

產(chǎn)生式語義動作(1)E′→E print(Eval) {print

(stack[top].val);}(2)E→E1+TEval=E1val+Tval {stack[top-2].val=stack[top-2].val+stack[top].val; top=top-2;}(3)E→T Eval=Tval(4)T→T1*

FTval=T1val×Fval {stack[top-2].val=stack[top-2].val×stack[top].val; top=top-2;}(5)T→F Tval=Fval(6)F→(E)Fval=Eval {stack[top-2].val=stack[top-1].val; top=top-2;}(7)F→digitFval=digitlexval

例：在自底向上語法分析棧中實現(xiàn)桌面計算器例狀態(tài)

符號

屬性輸入：3*5+40$_5d3SLR自動機

產(chǎn)生式語義動作(1)E′→E{print(stack[top].val);}(2)E→E1+T{stack[top-2].val=stack[top-2].val+stack[top].val;top=top-2;}(3)E→T(4)T→T1*

F{stack[top-2].val=stack[top-2].val×stack[top].val;top=top-2;}(5)T→F(6)F→(E){stack[top-2].val=stack[top-1].val;top=top-2;}(7)F→digit

例輸入：3*5+40$_3F3SLR自動機

產(chǎn)生式語義動作(1)E′→E{print(stack[top].val);}(2)E→E1+T{stack[top-2].val=stack[top-2].val+stack[top].val;top=top-2;}(3)E→T(4)T→T1*

F{stack[top-2].val=stack[top-2].val×stack[top].val;top=top-2;}(5)T→F(6)F→(E){stack[top-2].val=stack[top-1].val;top=top-2;}(7)F→digit

狀態(tài)

符號

屬性例輸入：3*5+40$_2T37*_5d5SLR自動機

產(chǎn)生式語義動作(1)E′→E{print(stack[top].val);}(2)E→E1+T{stack[top-2].val=stack[top-2].val+stack[top].val;top=top-2;}(3)E→T(4)T→T1*

F{stack[top-2].val=stack[top-2].val×stack[top].val;top=top-2;}(5)T→F(6)F→(E){stack[top-2].val=stack[top-1].val;top=top-2;}(7)F→digit

狀態(tài)

符號

屬性例輸入：3*5+40$_2T37*_10F155SLR自動機

產(chǎn)生式語義動作(1)E′→E{print(stack[top].val);}(2)E→E1+T{stack[top-2].val=stack[top-2].val+stack[top].val;top=top-2;}(3)E→T(4)T→T1*

F{stack[top-2].val=stack[top-2].val×stack[top].val;top=top-2;}(5)T→F(6)F→(E){stack[top-2].val=stack[top-1].val;top=top-2;}(7)F→digit

狀態(tài)

符號

屬性例輸入：3*5+40$_2T315SLR自動機

產(chǎn)生式語義動作(1)E′→E{print(stack[top].val);}(2)E→E1+T{stack[top-2].val=stack[top-2].val+stack[top].val;top=top-2;}(3)E→T(4)T→T1*

F{stack[top-2].val=stack[top-2].val×stack[top].val;top=top-2;}(5)T→F(6)F→(E){stack[top-2].val=stack[top-1].val;top=top-2;}(7)F→digit

狀態(tài)

符號

屬性例輸入：3*5+40$_1E3156+_5d4SLR自動機

產(chǎn)生式語義動作(1)E′→E{print(stack[top].val);}(2)E→E1+T{stack[top-2].val=stack[top-2].val+stack[top].val;top=top-2;}(3)E→T(4)T→T1*

F{stack[top-2].val=stack[top-2].val×stack[top].val;top=top-2;}(5)T→F(6)F→(E){stack[top-2].val=stack[top-1].val;top=top-2;}(7)F→digit

狀態(tài)

符號

屬性例輸入：3*5+40$_1E3156+_3F4SLR自動機

產(chǎn)生式語義動作(1)E′→E{print(stack[top].val);}(2)E→E1+T{stack[top-2].val=stack[top-2].val+stack[top].val;top=top-2;}(3)E→T(4)T→T1*

F{stack[top-2].val=stack[top-2].val×stack[top].val;top=top-2;}(5)T→F(6)F→(E){stack[top-2].val=stack[top-1].val;top=top-2;}(7)F→digit

狀態(tài)

符號

屬性例輸入：3*5+40$_1E3156+_9T419SLR自動機

產(chǎn)生式語義動作(1)E′→E{print(stack[top].val);}(2)E→E1+T{stack[top-2].val=stack[top-2].val+stack[top].val;top=top-2;}(3)E→T(4)T→T1*

F{stack[top-2].val=stack[top-2].val×stack[top].val;top=top-2;}(5)T→F(6)F→(E){stack[top-2].val=stack[top-1].val;top=top-2;}(7)F→digit

狀態(tài)

符號

屬性例輸入：3*5+40$_1E31519SLR自動機

產(chǎn)生式語義動作(1)E′→E{print(stack[top].val);}(2)E→E1+T{stack[top-2].val=stack[top-2].val+stack[top].val;top=top-2;}(3)E→T(4)T→T1*

F{stack[top-2].val=stack[top-2].val×stack[top].val;top=top-2;}(5)T→F(6)F→(E){stack[top-2].val=stack[top-1].val;top=top-2;}(7)F→digit

狀態(tài)

符號

屬性把計算某個非終結(jié)符號A的繼承屬性的動作插入到產(chǎn)生式右部中緊靠在A的本次出現(xiàn)之前的位置上將計算一個產(chǎn)生式左部的綜合屬性的動作放置在這個產(chǎn)生式右部的最右端將一個L-SDD轉(zhuǎn)換為SDT的規(guī)則

產(chǎn)生式語義規(guī)則(1)

T

FT′

T′.inh=F.val

T.val

=T′.syn(2)T′

*FT1′

T1′.inh=T′.inh×F.val

T′.syn=

T1′.syn

(3)T′

ε

T′.syn=T′.inh(4)

FdigitF.val=digit.lexvalL-SDDSDT1)

T→F

{T?.inh=F.val}T?

{T.val=T?.syn}2)T?→*F

{T1?.inh=T?.inh×F.val}T1?

{T?.syn=T1?.syn}3)T?→ε

{T?.syn=

T?.inh}4)F→digit{F.val=digit.lexval}例如果一個L-SDD的基本文法可以使用LL分析技術(shù)，那么它的SDT可以在LL或LR語法分析過程中實現(xiàn)例1)

T→F

{T?.inh=F.val}T?

{T.val=T?.syn}2)T?→*F

{T1?.inh=T?.inh×F.val}T1?

{T?.syn=T1?.syn}3)T?→ε

{T?.syn=

T?.inh}4)F→digit

{F.val=digit.lexval}SELECT(1)={digit}SELECT(2)={*}SELECT(3)={$}SELECT(4)={digit}L-屬性定義的SDT實現(xiàn)如果一個L-SDD的基本文法可以使用LL分析技術(shù)，那么它的SDT可以在LL或LR語法分析過程中實現(xiàn)在非遞歸的預(yù)測分析過程中進行語義翻譯在遞歸的預(yù)測分析過程中進行語義翻譯在LR分析過程中進行語義翻譯L-屬性定義的SDT實現(xiàn)5.1語法制導(dǎo)定義SDD5.2S-屬性定義與L-屬性定義5.3語法制導(dǎo)翻譯方案SDT5.4L-屬性定義的自頂向下翻譯5.5L-屬性定義的自底向上翻譯提綱5.4.1在非遞歸的預(yù)測分析過程中進行翻譯5.4.2在遞歸的預(yù)測分析過程中進行翻譯5.4L-屬性定義的自頂向下翻譯擴展的LL(1)語法分析棧A

actionAsyn指向?qū)⒈粓?zhí)行的語義動作代碼的指針A的繼承屬性A的綜合屬性SymbolValue

5.4.1在非遞歸的預(yù)測分析過程中進行翻譯1)

T→F

{T′.inh=F.val}T′{T.val=T′.syn}2)T′

→*F

{T1′.inh=T′.inh×F.val}T1′

{T′.syn=

T1′.syn}3)T′

→ε

{T′.syn=

T′.inh}4)F→digit{F.val=digit.lexval}a1：T′.inh=F.val

a2：

T.val=T′.syn

a3：

T1′.inh=T′.inh×F.val

a4

：

T′.syn=

T1′.syn

a5

：

T′.syn=

T′.inh

a6

：

F.val=digit.lexval

1)

T→F{a1}T′

{a2

}2)T?→*F{a3}T1′{a4

}3)T?→ε

{a5

}4)F→digit{a6

}例TTsyn$val輸入:3*5a1：T?.inh=F.val

a2：

T.val=T?.syn

a3：

T1?.inh=T?.inh×F.val

a4

：

T?.syn=

T1?.syn

a5

：

T?.syn=

T?.inh

a6

：

F.val=digit.lexval

1)

T→F

{a1}T?{a2}2)T?→*F

{a3}T1?

{a4}3)T?→ε

{a5}4)F→digit

{a6}例Tsyn$val輸入:3*5{a2}T’synFsyn{a1}FsynvalT’inha1：T?.inh=F.val

a2：

T.val=T?.syn

a3：

T1?.inh=T?.inh×F.val

a4

：

T?.syn=

T1?.syn

a5

：

T?.syn=

T?.inh

a6

：

F.val=digit.lexval

1)

T→F

{a1}T?{a2}2)T?→*F

{a3}T1?

{a4}3)T?→ε

{a5}4)F→digit

{a6}例a1：T?.inh=F.val

a2：

T.val=T?.syn

a3：

T1?.inh=T?.inh×F.val

a4

：

T?.syn=

T1?.syn

a5

：

T?.syn=

T?.inh

a6

：

F.val=digit.lexval

1)

T→F

{a1}T?{a2}2)T?→*F

{a3}T1?

{a4}3)T?→ε

{a5}4)F→digit

{a6}Tsyn$val輸入:3*5{a2}T’synsyn{a1}FsynvalT’inh{a6}digitlexval=3digit_lexval=3stack[top-1].val=stack[top].digit_lexvalFval=3val=3例Tsyn$val輸入:3*5{a2}T’synsyn{a1}T’inhFval=3stack[top-1].inh=stack[top].Fvalinh=3a1：T?.inh=F.val

a2：

T.val=T?.syn

a3：

T1?.inh=T?.inh×F.val

a4

：

T?.syn=

T1?.syn

a5

：

T?.syn=

T?.inh

a6

：

F.val=digit.lexval

1)

T→F

{a1}T?{a2}2)T?→*F

{a3}T1?

{a4}3)T?→ε

{a5}4)F→digit

{a6}例Tsyn$val輸入:3*5{a2}T’synsyn{a4}T1’T1’syn{a3}Fsyn*FT’inh=3syninhvala1：T?.inh=F.val

a2：

T.val=T?.syn

a3：

T1?.inh=T?.inh×F.val

a4

：

T?.syn=

T1?.syn

a5

：

T?.syn=

T?.inh

a6

：

F.val=digit.lexval

1)

T→F

{a1}T?{a2}2)T?→*F

{a3}T1?

{a4}3)T?→ε

{a5}4)F→digit

{a6}例Tsyn$val輸入:3*5{a2}T’synsyn{a4}T1’T1’syn{a3}FsynT’inh=3syninhval{a6}digitlexval=5digit_lexval=5stack[top-1].val=stack[top].digit_lexvalval=5Fval=5a1：T?.inh=F.val

a2：

T.val=T?.syn

a3：

T1?.inh=T?.inh×F.val

a4

：

T?.syn=

T1?.syn

a5

：

T?.syn=

T?.inh

a6

：

F.val=digit.lexval

1)

T→F

{a1}T?{a2}2)T?→*F

{a3}T1?

{a4}3)T?→ε

{a5}4)F→digit

{a6}例Tsyn$val輸入:3*5{a2}T’synsyn{a4}T1’T1’syn{a3}T’inh=3syninhFval=5stack[top-1].inh=stack[top].T’inh

×stack[top].Fval

inh=15a1：T?.inh=F.val

a2：

T.val=T?.syn

a3：

T1?.inh=T?.inh×F.val

a4

：

T?.syn=

T1?.syn

a5

：

T?.syn=

T?.inh

a6

：

F.val=digit.lexval

1)

T→F

{a1}T?{a2}2)T?→*F

{a3}T1?

{a4}3)T?→ε

{a5}4)F→digit

{a6}例Tsyn$val輸入:3*5{a2}T’synsyn{a4}T1’synsynT1’inh=15{a5}stack[top-1].syn=stack[top].T1’inhsyn=15T1’syn=15a1：T?.inh=F.val

a2：

T.val=T?.syn

a3：

T1?.inh=T?.inh×F.val

a4

：

T?.syn=

T1?.syn

a5

：

T?.syn=

T?.inh

a6

：

F.val=digit.lexval

1)

T→F

{a1}T?{a2}2)T?→*F

{a3}T1?

{a4}3)T?→ε

{a5}4)F→digit

{a6}例Tsyn$val輸入:3*5{a2}T’synsyn{a4}T1’syn=15stack[top-1].syn=stack[top].T1’synsyn=15T’syn=15a1：T?.inh=F.val

a2：

T.val=T?.syn

a3：

T1?.inh=T?.inh×F.val

a4

：

T?.syn=

T1?.syn

a5

：

T?.syn=

T?.inh

a6

：

F.val=digit.lexval

1)

T→F

{a1}T?{a2}2)T?→*F

{a3}T1?

{a4}3)T?→ε

{a5}4)F→digit

{a6}例Tsyn$val輸入:3*5{a2}T’syn=15stack[top-1].val=stack[top].T’synval=15a1：T?.inh=F.val

a2：

T.val=T?.syn

a3：

T1?.inh=T?.inh×F.val

a4

：

T?.syn=

T1?.syn

a5

：

T?.syn=

T?.inh

a6

：

F.val=digit.lexval

1)

T→F

{a1}T?{a2}2)T?→*F

{a3}T1?

{a4}3)T?→ε

{a5}4)F→digit

{a6}例①在變量A的記錄下面加一個綜合記錄，用來將計算得到的A的綜合屬性值回填②綜合記錄出棧時，要將綜合屬性值復(fù)制給后面特定的語義子程序③變量展開時（即普通記錄出棧時），如果其含有繼承屬性，則要將繼承屬性值復(fù)制給后面特定的語義子程序分析棧中的每一個記錄都對應(yīng)著一段執(zhí)行代碼1)T→F{a1:T′.inh=F.val}T′

{a2:T.val=T′.syn}符號屬性代碼段F根據(jù)當前輸入符號選擇產(chǎn)生式進行推導(dǎo)F_synvalstack[top-1].Fval=stack[top].val；top=top-1;a1Fvalstack[top-1].inh=stack[top].Fval；top=top-1;T′inh根據(jù)當前輸入符號選擇產(chǎn)生式進行推導(dǎo)若選2):stack[top+3].T′inh

=stack[top].inh;top=top+6;若選3):stack[top].T′inh

=stack[top].inh;

T′_synsynstack[top-1].T′syn=stack[top].syn；top=top-1;a2T′synstack[top-1].val=stack[top].T′syn；top=top-1;1)

T→F

{a1}T?{a2}2)T?→*F

{a3}T1?

{a4}3)T?→ε

{a5}4)F→digit

{a6}a1：T?.inh=F.val

a2：

T.val=T?.syn

a3：

T1?.inh=T?.inh×F.val

a4

：

T?.syn=

T1?.syn

a5

：

T?.syn=

T?.inh

a6

：

F.val=digit.lexval

例2)T′

→*F{a3:T1′.inh=T′.inh×F.val}T1′{a4:T′.syn=T1′.syn}符號屬性代碼段*輸入指針后移F根據(jù)當前輸入符號選擇產(chǎn)生式進行推導(dǎo)F_synvalstack[top-1].Fval=stack[top].val；top=top-1;a3T?inh;Fvalstack[top-1].inh=stack[top].T′inh×

stack[top].Fval；top=top-1;T1′inh根據(jù)當前輸入符號選擇產(chǎn)生式進行推導(dǎo)若選2):stack[top+3].T′inh=stack[top].inh;top=top+6;若選3):stack[top].T′inh=stack[top].inh;

T1′_synsynstack[top-1].T1′syn=stack[top].syn；top=top-1;a4T1′synstack[top-1].syn=stack[top].T1′syn；top=top-1;1)

T→F

{a1}T?{a2}2)T?→*F

{a3}T1?

{a4}3)T?→ε

{a5}4)F→digit

{a6}a1：T?.inh=F.val

a2：

T.val=T?.syn

a3：

T1?.inh=T?.inh×F.val

a4

：

T?.syn=

T1?.syn

a5

：

T?.syn=

T?.inh

a6

：

F.val=digit.lexval

例3)T′

→

ε

{a5:T′.syn=

T′.inh}符號屬性代碼段a5T′inhstack[top-1].syn=stack[top].T′inh；top=top-1;1)

T→F

{a1}T?{a2}2)T?→*F

{a3}T1?

{a4}3)T?→ε

{a5}4)F→digit

{a6}a1：T?.inh=F.val

a2：

T.val=T?.syn

a3：

T1?.inh=T?.inh×F.val

a4

：

T?.syn=

T1?.syn

a5

：

T?.syn=

T?.inh

a6

：

F.val=digit.lexval

例4)F→digit{a6:F.val=digit.lexval}符號屬性代碼段digit輸入指針后移digit_synlexvalstack[top-1].digitlexval=stack[top].lexval；top=top-1;a6digitlexvalstack[top-1].val=stack[top].digitlexval；top=top-1;1)

T→F

{a1}T?{a2}2)T?→*F

{a3}T1?

{a4}3)T?→ε

{a5}4)F→digit

{a6}a1：T?.inh=F.val

a2：

T.val=T?.syn

a3：

T1?.inh=T?.inh×F.val

a4

：

T?.syn=

T1?.syn

a5

：

T?.syn=

T?.inh

a6

：

F.val=digit.lexval

例T′syn

T′

(token,T′inh){

D:Fval,T1′inh,T1′syn；

iftoken=“*”then

{Getnext(token)；

Fval=F(token)；

T1′inh=T′inh×Fval；

Getnext(token)；

T1′syn=T1′(token,T1′inh)；

T?syn=T1′syn； returnT′syn；

}

elseiftoken=

“$”

then

{

T′syn=T′inh； returnT′syn；}

elseError；}例SDT

1)

T→F{T′.inh=F.val}T′

{T.val=T′.syn}2)T′→*F{T1′.inh=T′.inh×F.val}T1′

{T′.syn=T1′.syn}3)T′

→ε

{T′.syn=

T′.inh}4)F→

digit

{F.val=digit.lexval}5.4.2在遞歸的預(yù)測分析過程中進行翻譯對于每個動作，將其代碼復(fù)制到語法分析器