編譯原理（全套課件下）

編譯原理下第五章語法制導(dǎo)翻譯333語法表述的是語言的形式，或者說是語言的樣子和結(jié)構(gòu)程序設(shè)計(jì)語言中更重要的一個方面，是附著在語言結(jié)構(gòu)上的語義語義揭示了程序本身的涵義、施加于語言結(jié)構(gòu)上的限制或者要執(zhí)行的動作―老鼠吃貓?問題 語法正確的句子，它的語義可能 存在問題334語義分析的任務(wù)：①檢查語言結(jié)構(gòu)的語義是否正確

②執(zhí)行所規(guī)定的語義動作 如表達(dá)式的求值、符號表的填寫、 中間代碼的生成335對于文法:EE1+TETTFFdigitdigitlexval為digit的屬性；F.val、T.val、E.val為文法符號F、T、E對應(yīng)的屬性值語法制導(dǎo)翻譯的基本思想： 將語言結(jié)構(gòu)的語義以屬性(attribute)的形 式賦予代表此結(jié)構(gòu)的文法符號，336

當(dāng)digit為常數(shù)時，digitlexval為digit在 常數(shù)表中的入口當(dāng)digit為標(biāo)識符時，digitlexval為digit在符號表中的入口；

F.val、T.val、E.val可以看作是中間變 量337FdigitTFETEE1+TFval:=digitlexvalTval:=FvalEval:=TvalEval:=E1val+Tval而屬性的計(jì)算以語義規(guī)則(semanticrules)的形式賦予由文法符號組成的產(chǎn)生式；在語法分析推導(dǎo)或歸約的每一步驟中，通過語義規(guī)則實(shí)現(xiàn)對屬性的計(jì)算，以達(dá)到對語義的處理338

換句話說是：為每一個產(chǎn)生式配上語義規(guī)則并且在適當(dāng)?shù)臅r候執(zhí)行這些規(guī)則。 即當(dāng)歸約（或推導(dǎo)）到某個產(chǎn)生式時， 除了按照產(chǎn)生式進(jìn)行相應(yīng)的代換之外(語法分析)，還要按照產(chǎn)生式所對應(yīng)的語義規(guī)則執(zhí)行相應(yīng)的語義動作，如計(jì)算表達(dá)式、查填符號表、產(chǎn)生中間代碼(語義分析)339

語法分析—建立語法分析樹

語義分析---遍歷語法分析樹

語法制導(dǎo)翻譯---建立與遍歷同時完成語法制導(dǎo)翻譯是目前最常用的語義分析技術(shù)340例1臺式計(jì)算器程序的語法制導(dǎo)定義

產(chǎn)生式LEnEE1+TETTT1*FTFF(E)Fdigit

語義規(guī)則

print(Eval) Eval:=E1val+Tval Eval:=TvalTval:=T1val*FvalTval:=Fval Fval:=Eval Fval:=digitlexval3*5+4的分析過程12341*FTF3E+T F4ET

53*5+4的語法分析過程342

Fval:=3digitlexval:=3Tval:=3Fval:=5*Eval:=15 Tval:=15+digitlexval:=4Tval:=4 Fval:=4Eval:=19Ln

digitlexval:=53*5+4的語義分析過程3435.1語法制導(dǎo)定義(Syntax-directeddefinitions)通

語法制導(dǎo)定義也叫屬性文法，它是在上下文無關(guān)文法的基礎(chǔ)上，通過每個文法 符號和一個屬性集合相關(guān)聯(lián)，過每一個產(chǎn)生式和一個語義規(guī)則集合相關(guān)聯(lián)。語義規(guī)則用來計(jì)算與產(chǎn)生式中出現(xiàn)的符號相關(guān)聯(lián)的屬性的值。9344

綜合屬性

◆屬性 繼承屬性 屬性可以代表任何對象：字符串、數(shù)字、類型、內(nèi)存單元或其它對象3455.1.1屬性

在一個語法制導(dǎo)定義中，A→P

都有與之相關(guān)聯(lián)的一套語義規(guī)則，規(guī)則可表示為：b=f（c1，c2，…,ck）其中：f是一個函數(shù)，且滿足下面兩種情況之一：1．b是A屬性，c1,c2,…,ck是中的文法符號的屬性，或者A的其它屬性，則 稱b是A的綜合屬性；3462．c1,c2,…,ck是A或中的任何文法 符號的屬性,則稱b是中的符號的 一個繼承屬性。在兩種情況下，都說屬性b依賴于屬性c1，c2，…，ck。347

5.1.2綜合屬性S-屬性定義:只使用綜合屬性的語法制導(dǎo)定義。 利用S-屬性定義進(jìn)行語義分析時,結(jié)點(diǎn)屬 性值的計(jì)算正好和自底向上分析建立分析 樹結(jié)點(diǎn)同步進(jìn)行。 綜合屬性從下到上包括自身，其屬性可 從后代和自身的其它屬性計(jì)算得到348例1臺式計(jì)算器程序的S-屬性定義

產(chǎn)生式LEnEE1+TETTT1*FTFF(E)Fdigit

語義規(guī)則

print(Eval) Eval:=E1val+Tval Eval:=TvalTval:=T1val*FvalTval:=Fval Fval:=Eval Fval:=digitlexval3*5+4的分析過程349*FTF3E+TF4ET

53*5+4的語法分析過程digitlexval:=3 Fval:=3Tval:=15Eval:=15lexval:=4lexval:=5val:=4val:=5val:=4val:=3val:=19\nL19350digitlexval:=3Tval:=3 Fval:=3

Fval:=5digitlexval:=5*Eval:=15 Tval:=15+digitlexval:=4Tval:=4 Fval:=4Eval:=19Ln351在建立每一個結(jié)點(diǎn)處

使用語義規(guī)則來計(jì)算綜合屬性值，即在用哪個產(chǎn)生式進(jìn)行歸約后，就執(zhí)行那個產(chǎn)生式的s-屬性定義計(jì)算屬性的值， 從葉結(jié)點(diǎn)到根結(jié)點(diǎn)進(jìn)行計(jì)算

在分析樹中為每個文法符號上加上它們的屬性，則稱為帶注釋的分析樹，簡稱注釋分析樹綜合屬性值的計(jì)算方法

對于s-屬性定義，通常使用自底向上的分析方法，3525.1.3繼承屬性

繼承屬性值是由此結(jié)點(diǎn)的父結(jié)點(diǎn)和／或兄弟結(jié)點(diǎn)的某些屬性值來決定的。繼承屬性從上到下包括兄弟，也即繼承屬性從前輩和兄弟的屬性計(jì)算得到353表2帶有繼承屬性L.in的語法制導(dǎo)定義

產(chǎn)生式

DTL Tint Treal LL1,idLid

語義規(guī)則

Lin:=Ttype Ttype:=integer Ttype:=real L1in:=Lin addtype(identry,Lin)addtype(identry,Lin)354練習(xí)：設(shè)AS為文法的綜合屬性集，AI為繼承屬性集，則下列語法制導(dǎo)定義中

產(chǎn)生式P→xQRQ→u語義規(guī)則

Q.b=R.d R.c=1 R.e=Q.a Q.a=3355

P→yQRR→v

Q.b=R.f R.c=Q.a R.e=2R.d=R.c

R.f=R.e試求AS和AI356解：由1知：Q.b,R.e∈AI

由3知：R.c∈AI

由4知：R.d,R.f∈AS

由2知：Q.a=3∈AS

整理：AS={Q.a,R.d,R.f} AI={Q.b,R.c,R.e}3575.2語義規(guī)則語義規(guī)則也叫語義子程序或語義動作語義規(guī)則通常有兩種表現(xiàn)形式：語法制導(dǎo)定義和翻譯模式3585.2.1語法制導(dǎo)定義語法制導(dǎo)定義是關(guān)于語言翻譯高層次規(guī)格說明，它隱藏了具體實(shí)現(xiàn)細(xì)節(jié)，用使

戶不用顯式地說明翻譯發(fā)生的順序例：下面是將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式的文法和相應(yīng)的語法制導(dǎo)定義359產(chǎn)生式

L→E E→E1+E2 E→digit語法制導(dǎo)定義

print(E.val)

E.val=E1.val||E2.val||?+?

E.val=Digit.lexval語法制導(dǎo)定義只考慮?做什么?，用抽象的屬性表示文法符號所代表的語義3605.2.2翻譯模式翻譯模式也叫翻譯方案一個翻譯模式是一個上下文無關(guān)文法，

其中被稱為語義動作的程序段被嵌入 到產(chǎn)生式的右部。一個翻譯模式類似于語法制導(dǎo)定義，只是語義規(guī)則的計(jì)算順序是顯式給出的。361

這是一種語法分析和語義動作交錯的表示法，他表達(dá)在按深度優(yōu)先遍歷分 析樹的過程中何時執(zhí)行語義動作。 翻譯模式給出了使用語義規(guī)則進(jìn)行 計(jì)算的順序?？煽闯墒欠治鲞^程中翻譯 的注釋。362例2：一個簡單的翻譯模式（中綴變后綴）

E→TR R→addopT

{print(addop.lexeme)}R1|ε T→num{print(num.val)}3633+5的語義翻譯過程

ERTPr‘3‘3T+Pr‘+‘5RPr‘5‘

ε

結(jié)果：35+364翻譯方案不僅要考慮?做什么?，還要考慮?怎么做?某種意義上說，語法制導(dǎo)定義類似于算法，而翻譯方案更象程序365帶有繼承屬性L.in的翻譯方案DT｛Lin:=Ttype｝LTint｛Ttype:=integer｝Treal｛Ttype:=real｝

L{L1in:=Lin}

L1,id{addtype(identry,Lin)}

Lid{addtype(identry,Lin)}例5.3變量說明的類型定義inta,b,c

366DL.in=t.typeLrealL1.in=L.in,id 3L1.in=L.in,id2id1句子realid1,id2,id3的帶繼承屬性的分析樹TT.type=realLLAdd(L.in)Add(L.in)Add(L.in)367例：文法G的產(chǎn)生式如下：S→（L）S→aL→L,SL→S1.試寫出一個語法制導(dǎo)定義，輸出配對括號個數(shù)2.寫一個翻譯方案，打印每個a的嵌套深度368解：1.為S，L引入屬性h產(chǎn)生式S→（L）S→aL→L1,SL→SS‘→S語法制導(dǎo)定義

S.h=L.h+1 S.h=0 L.h=L1.h+S.h L.h=s.h print(S.h)369(SL,(L.h=0S.h=0LL.h=0)SS.h=1L)S S.h=0L.h=1S.h=2

a S(a,(a))的分析過程

a3702.為S，L引入屬性d,翻譯方案如下S‘→{S.d=0}SS→（{L.d=S.d+1}L）S→a{print(s.d)}L→{L1.d=L.d}L1,{S.d=L.d}SL→{S.d=L.d}SS‘S.h=0S(L.d=1L)L.d=1L,S.d=1S

S.d=1 Print(1)

Sa

(LS

L.d=2 S.d=2Print(2)

)a

371(a,(a))的分析過程ZZ.valYY.valZZ.val…………372stateval

5.3S-屬性定義及其自底向上的計(jì)算 在分析棧中使用一個附加的域來存 放綜合屬性值。 下圖為一個帶有綜合屬性值域的分析棧：

top373Ab:=f(c1,c2,…,ck)Ab

其中：b是A的綜合屬性，ci(1ik)是

中符號的屬性。綜合屬性的值在自底 向上的分析過程中，每步歸約時，計(jì)算相應(yīng)的屬性值。 例：AXYZAb:=f(Xx,Yy,Zz)XXxY

YyZZzAAA.b......374statevaltop歸約后,分析棧為：定義式A.b=f(X.x,Y.y,Z.z)(抽象)變成val[ntop]=f(val[top-2],val[top-1],val[top])（具體可執(zhí)行代碼）。在執(zhí)行代碼段之前執(zhí)行：ntop:=top-r+1

其中:r是句柄的長度,ntop為歸約后棧頂 執(zhí)行代碼段后執(zhí)行：top:=ntop;375例5.10用LR分析器實(shí)現(xiàn)臺式計(jì)算器

代碼段(和表5.1對比）

printf(val[ntop]) val[ntop]:=val[top-2]+val[top]val[ntop]:=val[top-2]*val[top] val[ntop]:=val[top-1]產(chǎn)生式LEnEE+TETTT*FTFF(E)Fdigit376表5.5翻譯輸入3*5+4n所做的移動輸入3*5+4n *5+4n *5+4n *5+4n 5+4n +4n +4nstate

- 3 F T T* T*5 T*Fval

- 3 3 3 3- 3-5 3-5使用的產(chǎn)生式

Fdigit TF Fdigit377

L19

LEn輸入

+4n +4n 4n n n n nstate

T E E+ E+4 E+F E+T E Enval

15 15 15- 15-4 15-4 15-4 19 19-使用的產(chǎn)生式

TT*F ET Fdigit TF EE+T378，然總結(jié)： 采用自底向上分析，例如LR分析首先 給出S-屬性定義，后,把S-屬性定義變成可執(zhí)行的代碼段,這就構(gòu)成了翻譯程序。歸

象一座建筑,語法分析是構(gòu)架，約處有一個?掛鉤?,語義分析和翻譯的代碼段（語義子程序）就掛在這個鉤子上。這樣，隨著語法分析的進(jìn)行，約前調(diào)用歸相應(yīng)的語義子程序,

379

在這種分析模式中，語法分析是主動的，語義分析是從動的，語法分析制導(dǎo)著語義分析3805.4L-屬性定義 在語法分析過程中進(jìn)行語義分析和翻譯，屬性的計(jì)算順序受到語法分 析建立分析樹結(jié)點(diǎn)順序的限制。 一種自然的計(jì)算屬性的順序是按深 度優(yōu)先訪問分析樹結(jié)點(diǎn)的順序，它適應(yīng) 多種自底向上和自頂向下的翻譯方法。381◆深度優(yōu)先順序計(jì)算屬性PROCEDUREdfvisit(n:node); BEGIN FORn的每個子結(jié)點(diǎn)m,從左至右DO BEGIN

計(jì)算m的繼承屬性；

dfvisit(m) END;

計(jì)算n的綜合屬性

END;3825.4.1L-屬性定義 一個語法制導(dǎo)定義是L-屬性定義， 如果A→X1X2…XnP,其每一個語義規(guī)則中的每一個屬性都是一個綜合屬性，

或是Xj(1jn)的一個繼承屬性， 這個繼承屬性僅依賴于1、產(chǎn)生式中Xj的左邊符號X1,X2，…Xj-1

的屬性；2．A的繼承屬性。每一個S-屬性定義都是L-屬性定義。383例.一個簡單的翻譯模式

E→TR R→addopT

{print(addop.lexeme)}R1|ε T→num{print(num.val)}把語義動作看成終結(jié)符號，輸入9-5+2,其分析樹如圖，當(dāng)按深度優(yōu)先遍歷它，

執(zhí)行遍歷中訪問的語義動作，將輸出：

95–2+它是輸入表達(dá)式9-5+2的后綴式。384T9Pt(′+′)R

-Pt(′9′)

5

Pt(′-′)

TPt(′5′)+R T2Pt(′2′)R

9-5+2的帶語義動作的分析樹

E385設(shè)計(jì)翻譯模式（根據(jù)語法制導(dǎo)定義）條件：語法制導(dǎo)定義是L-屬性定義，保證語義動作不會引用還沒有計(jì)算的屬性值。1.只需要綜合屬性的情況： 為每一個語義規(guī)則建立一個包含賦值的動作，并把這個動作放在相應(yīng)的產(chǎn)生式右邊的末尾。例如：

TT1*FTval:=T1val*Fval TT1*F{Tval:=T1val*Fval}386以后才能計(jì)算。2.既有綜合屬性又有繼承屬性

?產(chǎn)生式右邊的符號的繼承屬性必須在 這個符號以前的動作中計(jì)算出來。

?一個動作不能引用這個動作右邊符號 的綜合屬性。

?產(chǎn)生式左邊非終結(jié)符號的綜合屬性只 有在它所引用的所有屬性都計(jì)算出來?計(jì)算這種屬性的動作通?？煞旁诋a(chǎn)生式右端的未尾。387下面的翻譯模式不滿足要求：SA1A2{A1in:=1;A2in:=2}Aa{print(Ain)}

S

A2

A1 a

Pr(A.in)A1.in=1,A2.in=2

end388

5.5自頂向下的翻譯--用翻譯模式構(gòu)造自頂向下翻譯。

5.5.1從翻譯模式中消除左遞歸對于一個翻譯模式，若采用自頂向下分析，必須消除左遞歸和提取左公因子，在改寫基本文法時考慮屬性值的計(jì)算。389EE1+T｛Eval:=E1val+Tval}EE1-T｛Eval:=E1val-Tval｝ET{E.val:=Tval}

T(E)｛Tval:=Eval｝

Tnum｛Tval:=numval}圖5.13帶左遞歸的文法的翻譯模式390E→T{Ri:=Tval} R｛Eval:=Rs｝

R→＋

T｛R1i:=R.i+T.val} R1｛R.s:=R1s} R→- T｛R1i:=Ri-Tval} R1｛Rs:=R1s} R→ε｛Rs:=Ri} T→（E）｛Tval:=E.val} T→num{Tval:=numval}經(jīng)過轉(zhuǎn)換的帶有右遞歸文法的翻譯模式6769391ETR.i=T.valRE.val=R.s9t.val=9-TR1.i=R.i-T.valR1R.s=R1.s5T.val=5+TR1.i=R.i+T.valR1R.s=R1.s

2T.val=2εR.s=R.i392關(guān)于左遞歸翻譯模式更一般化的討論左遞歸翻譯模式

A→A1Y｛A.a:=g(A1.a,Y.y)} A→X｛A.a:=f(X.x)}(5.2)每一個文法符號都有一個綜合屬性，用相應(yīng)的小寫字母表示，g和f是任意函數(shù)。消除左遞歸，文法轉(zhuǎn)換成

A→XR R→YR|ε393?再考慮語義動作，翻譯模式變?yōu)椋?/p>

A→X｛Ri:=f(Xx)} R｛Aa:=Rs} R→Y｛R1i:=g（Ri,Yy）} R1｛Rs:=R1s} R→ε｛Rs:=Ri}（5.4）經(jīng)過轉(zhuǎn)換的翻譯模式與圖5.14中一樣,使用R的繼承屬性i和綜合屬性s。（5.2）和（5.4）的結(jié)果是一樣的,

為什么？394Y2Y1Aa=g(f(Xx),Y1y) Aa=f(Xx) X(a)

輸入：XY1Y2Aa=g(g(f(Xx),Y1y),Y2y)395ARi=f(Xx) Ri=g(f(Xx),Y1y)Y1X

Y2

Ri=g(g(f(Xx),Y1y),Y2y)(b)

ε3965.5.2預(yù)測翻譯器的設(shè)計(jì)算法5.1預(yù)測語法制導(dǎo)翻譯器的建立輸入：一個帶有適合預(yù)測分析的文法的語法制導(dǎo)翻譯模式。 輸出：一個語法制導(dǎo)翻譯器的代碼。397方法：在預(yù)測分析器中加入語義動作代碼。1．AVN,建立一個可遞歸調(diào)用的函數(shù)過程A。為A的每一個繼承屬性都設(shè)臵一個形式參數(shù)，函數(shù)的返回值是A的綜合屬性值。2.函數(shù)過程A的代碼（指用符號形式表示的數(shù)據(jù)和程序）要根據(jù)當(dāng)前的輸入符號來決定使用哪一個產(chǎn)生式。3983．與每一個產(chǎn)生式有關(guān)的代碼，從左到右根椐產(chǎn)生式右部是單詞符號、非終結(jié)符號還是語義動作，分別是：（a）對于帶有綜合屬性x的單詞符號X，x存放在X.x中，Match(X)。 （b）對于BVN，編寫一個賦值語句

c：=B（b1,b2,…，bk),其中，

b1,b2,…，bk是繼承屬性，c是綜合屬性。 （c）對于每個動作，動作的代碼抄進(jìn)語法分 析器中，用代表屬性的變量來代替對屬性的 每一次引用。399ProcedureR;{

iflookahead=addopthen{ advance; T;R;}}非終結(jié)符R的遞歸過程400FunctionR(I:pointer):pointer;{varnptr,il,sl,s:pointer;

iflookahead=addopthen{

addop.lexeme=?+‘;

advance;nptr=T;

il=f(addop.lexeme,I,nptr); Sl=R(il);S=sl;}}

Elses=l;Returns;}嵌入語義的非終結(jié)符R的遞歸過程401

左遞歸翻譯模式

A→A1Y｛A.a:=g(A1.a,Y.y)} A→X｛A.a:=f(X.x)}(5.2)?再考慮語義動作，翻譯模式變?yōu)椋?/p>

A→X｛Ri:=f(Xx)} R｛A.a:=R.s} R→Y｛R1i:=g（Ri,Yy）} R1｛Rs:=R1s} R→ε｛Rs:=Ri}（5.4）第六章中間代碼403

中間代碼生成6.1中間語言6.2常用語句的翻譯6.2.1說明語句6.2.2賦值語句6.2.3布爾表達(dá)式6.2.4過程語句404：

序

?中間代碼生成?程序的任務(wù)是把經(jīng)過語法 分析和語義分析而獲得的源程序中間表示翻 譯為中間代碼表示。方法：語法制導(dǎo)翻譯。采用獨(dú)立于機(jī)器的中間代碼的好處：

1.便于編譯系統(tǒng)建立和編譯系統(tǒng)的移植；

2.便于進(jìn)行獨(dú)立于機(jī)器的代碼優(yōu)化工作。4056.1中間語言?語法樹?后綴式?三地址代碼表示6.1.1圖表示法 語法樹，有向非循環(huán)圖和后綴式表示源程序的自然層次結(jié)構(gòu)，例如：

a:=b*-c+b*-c406=a+*b-c

(a)語法樹*

-cb407賦值語句：中綴式：a:=b*-c+b*-c后綴式：

abc-*bc-*+=408=a+*b-

c(b)dag(DirectedAcyclicGraph)4096.1.2三地址代碼一般形式x：＝y(tǒng)opz相應(yīng)于圖6.1的樹和dag的三地址代碼t1：＝-ct2：＝b*t1t5：＝t2+t2a：=t5對于dag的代碼

t1：＝-c t2：＝b*t1 t3：＝-c t4：＝b*t3 t5：＝t2+t4 a：＝t5對于語法樹的代碼410運(yùn)算符號relop(<，=，＞=等等）;

6.1.3三地址語句的種類（1）賦值語句x：＝y(tǒng)opz，op為二目算術(shù)算符或邏輯算符;（2）賦值語句x：＝opy，op為一目算符，如一目減uminus、邏輯非not、移位算符及轉(zhuǎn)換算符;（3）無條件轉(zhuǎn)移語句gotoL;（4）條件轉(zhuǎn)移語句ifxrelopygotoL，關(guān)系411（5）復(fù)制語句x：＝y(tǒng);（6）過程調(diào)用語句paramx和callp,n;

過程返回語句returny;（7）索引賦值x:=y[i]及x[i]:=y;（8）地址和指針賦值x＝＆y，x＝*y

和*x＝y(tǒng)。在設(shè)計(jì)中間代碼形式時，選擇多少種算 符需要tradeoff.4126.1.4語法制導(dǎo)翻譯生成三地址代碼幾個用到的量：(1)E.place表示存放E值的名字。(2)E.code表示對E求值的三地址語句序列。(3)newtemp是個函數(shù)，對它的調(diào)用將產(chǎn)生一個新的臨時變量。產(chǎn)生式語義規(guī)則S→id:=ES.code:=E.code║gen(id.place':='E.place)E→E1+E2E.place:=newtemp;E.code:=E1.code║E2.code║gen(E.place':=? E1.place'+'E2.place)413產(chǎn)生式語義規(guī)則E→E1*E2E.place:=newtemp;E.code:=E1.code║E2.code ║gen(E.place':=? E1.place'*'E2.place)E.place:=newtemp;E.code:=E1.code‖gen( E.place′:=′uminus′E1.place)E→-E1414415

語義規(guī)則E.place:=E1.place;E.code:=E1.code

產(chǎn)生式E→(E1)產(chǎn)生賦值語句三地址代碼的語法制導(dǎo)定義E→idE.place:=id.place;E.code:=?‘416三地址語句序列是語法樹的線性表示，用臨時變量代替語法樹中的結(jié)點(diǎn)。

實(shí)際實(shí)現(xiàn)中，三地址語句序列往往是被存放 到一個輸出文件中，而不是將三地址語句序 列臵入code屬性之中4176.1.5三地址代碼的具體實(shí)現(xiàn)

1．四元式op,arg1,arg2,result 2．三元式op,arg1,arg2 3．間接三元式間接碼表+三元式表四元式需要利用較多的臨時單元,四元式之間的聯(lián)系通過臨時變量實(shí)現(xiàn)。中間代碼優(yōu)化處理時，四元式比三元式方便的多,間接三元式與四元式同樣方便，兩種實(shí)現(xiàn)方式需要的存儲空間大體相同。418常用三地址碼的四元式表示：1、x=yopz2、x=opy3、gotoL4、ifxropygotoL5、x=y6、parmxcallp,n7、x=y[i]x[i]=y8、x=&yx=*y（op,y,z,x)（op,y,,x)（j,,,L)(jrop,x,y,L)(=,y,,x)419對于語句a:=b*-c+b*-c的三種表示方法 三地址語句的四元式表示

(-,c,,t1) (*,b,t1,t2) (-,c,,t3) (*,b,t1,t4) (+,t2,t4,t5)

(=,t5,,a)oparg1arg2(0)(1)(2)(3)(4)(5)uminus *uminus * + assign

c b c b（1）

a(0)(2)(3)(4)420

三地址語句的三元式表示三元式中使用指向三元式語句的指針。oparg1arg2(14)(15)(16)(17)(18)(19)uminus *uminus * + assign

c b c b15 a(14)(16)(17)(18)statement(0)(1)(2)(3)(4)(5)(14)(15)(16)(17)(18)(19)421三地址語句的間接三元式表示 語句的移動僅改變左邊的語句表422

6.2常用語句的翻譯6.2.1說明語句說明語句的翻譯：對每個局部名字在，符號表中建立相應(yīng)的表項(xiàng)，填寫有關(guān)的信息.如類型、嵌套深度、相對地址,內(nèi)情向量等。相對地址：相對靜態(tài)數(shù)據(jù)區(qū)基址或活動記錄中局部數(shù)據(jù)區(qū)基址的一個偏移值423下面是類型說明和數(shù)組說明的文法和翻譯方案P→DD→D;DD→id：TT→integerT→realx:integer;y:real

一、過程中的說明語句 一個過程中的所有說明語句作為一個類 集來處理。用一個全程變量Offset來記錄下 一個數(shù)據(jù)在符號表中的相對地址。T→array[num]ofT1T→↑T1

424D→id：TT→integerT→realT→↑T1P→D｛offset：＝0}DD→D;D｛enter（，T.type，offset）; offset:=offset＋T.width｝｛T.type：=integer;T.width：=4｝｛T.type：＝real;T.width：＝8}T→array[num]ofT1 {T.type:＝array（num.val,T1.type); T.width：＝num.val*T1.width}｛T.type:＝pointer（T1．type）；

T.width：=4}425Nametypekind……addrXY…………

intreal

簡單變量簡單變量

04x:integer;y:realPOffset=0DD;x:TY:TEnter;offsetEnter;offsetOffset=4Offset=0Offset=12

DIntrealT.typeT.widthT.typeT.widthT.type=intT.width=4T.type=realT.width=8426

二、保留作用域信息

1.問題的提出 一般的語言中，標(biāo)識符的作用在程序正文中有一個確定的范圍。因此，同一個標(biāo)識符在不同的程序正文中可能標(biāo)識不同的對象，具有不同的性質(zhì)，要求分配不同的存儲空間。427于是提出下面的問題：如何組織符號表，使得同一個標(biāo)識符在不同的作用域中得到正確的引用而不產(chǎn)生混亂。進(jìn)一步我們考慮一下具有嵌套定義的程序結(jié)構(gòu)4282.嵌套sort（input2012/12/14…program的程序結(jié)構(gòu)，output）；

varx,a：array［0..10]ofinteger；

procedurereadarray；

vari：integer；begin…end；

begin…begin計(jì)算機(jī)學(xué)院end.end；

procedureexchange；

begin…end；procedurequicksort（m，n：integer）；

vari,k：integer；

procedurepartition（y，z：integer）

vari，j：integer；

begin…end;429嵌套說明的文法：P→DD→D;DD→id：TD→procid;D;S……..此處的T用于產(chǎn)生類型；S用于產(chǎn)生語句430

嵌套說明的程序結(jié)構(gòu)首先要解決的問題是：非局部數(shù)據(jù)的訪問綜合上述情況，對于程序結(jié)構(gòu)采用分程序結(jié)構(gòu)的程序來說，要解決的問題是：

1.局部數(shù)據(jù)的訪問

2.非局部數(shù)據(jù)的訪問解決方法:為每一個過程建立一個符號表431

具體翻譯時，每當(dāng)碰到過程說明

D→procid;D1;S時,便創(chuàng)建一張符號表,并且把

D1中的所有說明都填入此符號表中 新表中有一個指針，指向其直接外圍過程 符號表,用于解決非局部數(shù)據(jù)的訪問 過程名id作為直接外圍過程的局部名字記 錄在直接外圍過程符號表中；同時還要在直接外圍過程符號表中增加一個指向該過程D1符號表的指針NilheaderxareadarrayexchangequicksortHeaderIkpatitionHeaderIjheaderi432sort

readarray exchange

header

quicksortpatition嵌套過程的符號表433指）創(chuàng)建一張指向，外層

指向直接外層1.mktable(previous向當(dāng)前過程符新符號表

號表

2.Enter(table，name，type直接offset)插入表項(xiàng)

符號表 內(nèi)嵌過程

符號表 程的符號表

4.enterproc（table,name,newtable）

在外圍過程符號表中建立內(nèi)嵌過程的新表項(xiàng)434

翻譯時用到的數(shù)據(jù)結(jié)構(gòu)：Tblptr是一個棧，用于存放指向嵌套外層過程的符號表指針Offset是一個棧，用于存放變量的相對地址，當(dāng)過程結(jié)束時，offset里記錄的是過程占用的所有字節(jié)數(shù)。435處理嵌套過程中的說明語句翻譯方案P→MD{addwidth(top(tblptr),top(offset));①pop();pop(offset)}M→ε{t:=mktable（nil）；②push(t,tblptr);push(0,offset)｝D→D1；D2D→procid;ND1；S {t:＝top（tblptr); addwidth(t,top(offset));③

pop（tblptr）；pop（offset);enterproc(top（tblptr），，t)}436D→id:T {enter(top(tblptr),,T.type,top(offset));④top(offset）：=top(offset)＋T.width}例：procedurequicksort（m，n：integer）；begin…end；vari：integer；

procedurepartition（y，z：integer）

vari，j，x，v：integer；begin…end;N→ε{t：＝mktable(top（tblptr))；⑤push(t，tblptr）；push（0，offset)}437PMDprocQ;ND;S③①εε⑤procP;Nε⑤D;S③j:Tint＊④②438

上述語法樹對應(yīng)的語句：

ProcQ;procR;j:int;S;S遍歷語法樹所得到的翻譯序列：②⑤⑤＊④③③①

執(zhí)行上面翻譯序列符號表及棧的變化0R4Jint00QQ計(jì)算機(jī)學(xué)院439tabptroffset

主tT=QPQ

主t.type=intt.width=4 40 0 0T=pt②⑤⑤*④③③①{t:＝（2012/12/14enterproc(top（tblptr），，t)}

pop(tblptr);pop(offset)}{enter(top(tblptr),,T.type,top(offset)); addwidth(t,top(offset)); pop（tblptr）；pop（offset);440

編譯過程：用先根次序遍歷上一頁中的樹，用棧來存儲編譯過程中使用的量，象table和offset。使用兩個棧，分別保存剛編譯過的符號表箭頭table和offset的值。進(jìn)入過程partition，quicksort過程的編譯并未結(jié)束，活動記錄的設(shè)計(jì)和符號表的建立尚未完成，因此，要把quicksort過程使用的table和offset保存于棧中。441

一組嵌套過程，每個過程說明為局部名字建立一個符號表，所有正在翻譯過程的符號表組成整個源程序的符號表。 翻譯語句部分時查找符號表，查找過程的 符號表的路線相當(dāng)于當(dāng)前被翻譯過程的靜 態(tài)鏈。442三、記錄中的域名T→recordLDend {T.type:=record（top（tblptr))；

T.width:＝top(offset)；

pop（tblptr);pop(offset)}L→ε{t:=mktable(nil);

push(t,tblptr);push(0,offset))}

為－個記錄中的域名建立一張符號表

該翻譯模式強(qiáng)調(diào)了作為一個語言結(jié)構(gòu)的記錄的設(shè)計(jì)與活動記錄之間的相似處.443

6.2.2賦值語句 賦值語句的翻譯：表達(dá)式的成分可以是整型量、實(shí)型量、數(shù)組元素和記錄 一、符號表中的名字 名字可以理解為指向符號表中相應(yīng)該名字表 項(xiàng)的指針

如何根據(jù)名字查找符號表的表項(xiàng)？

◆過程lookup()檢查是否在符號表中 存在相應(yīng)此名字的表項(xiàng)。444若找到，返回有關(guān)信息。用最近嵌套作用域規(guī)則查找非局部名字

lookup過程先通過top(tblptr）指針在當(dāng)前符號表中查找名字為name的表項(xiàng)。若未找到，lookup就利用當(dāng)前符號表表頭的指針找到該符號表的外圍符號表， 名字為name的表項(xiàng)，

然后在那里查找直到所有外圍過程則的符號表中均無此name表項(xiàng)，lookup返回nil,表明查找失敗。445

二、簡單算術(shù)表達(dá)式及賦值語句

lookup()=id.entry nilemit它將生成的三地址代碼送到輸出文件上。例：emit(E.place?:=‘E1.place?+‘E2.place)或emit(=,E1.place，E2.place，E.place)446

產(chǎn)生賦值語句三地址代碼的翻譯模式

S→id:=E{p:=lookup(); ifp<>nilthenemit(p':='E.place) elseerror} E→E1+E2{E.place=newtemp; emit(E.place':='E1.place'+'E2.place')}E→E1*E2{E.place=newtemp; emit(E.place':='E1.place'+'E2.place')}447E→(E1)E→idE→-E{E.place:=newtemp; emit(E.place′:=′′uminus′E1.place}{E.place:=E1.place}{p:=lookup();ifp<>nilthenE.place:=pelseerror}448語義動作應(yīng)包括類型分析，文法符號應(yīng)有類型屬性，在類型分析的基礎(chǔ)上，進(jìn)行相容和賦值相容檢查，生成類型轉(zhuǎn)換的三地址代碼。449數(shù)組首

地址

三、數(shù)組元素地址分配（復(fù)雜賦值語句） 數(shù)組元素的三地址代碼是什么？ 如何生成數(shù)組元素的三地址代碼?1、數(shù)組元素地址的計(jì)算公式

①一維數(shù)組的數(shù)組元素計(jì)算公式

VARa:ARRAY[low..high]OFreal;

每個數(shù)組元 素的寬度base＋（i－low）*w =bace-low*w+i*w450數(shù)組地址計(jì)算：

常量部分+變量部分：

bace-low*w+i*w

可在編譯時計(jì)算出來

②對于一個二維數(shù)組，可以按行或按列存放。 若按行存放，則可用如下公式計(jì)算：A[1,1]A[1,2]A[1,3]A[2,1]A[2,2]A[2,3]A[2,3]按行存放451

A[1,2]=base-(1*3+1)+(1*3+2) =base+1令c=（（low1*n2）＋low2）*w

則常量部分=a[low1,low2]-cA[i1,i2]的地址：

base＋（（i1一low1）*n2＋i2一low2）*w）

=base－（（low1*n2）＋low2）*w

＋（（i1*n2）＋i2)*w452

③多維數(shù)組A[i1,i2,...,ik]的地址的計(jì)算

((...((i1*n2+i2)*n3+i3...)*nk+ik)*w+base- ((...((low1*n2+low2)*n3+low3...)*nk+lowk)*w整理后：常量部分：c=((...((low1*n2+low2)*n3+low3)...)*nk

+lowk)*w變量部分v=((...((i1*n2+i2)*n3+i3...)*nk+ik)*wa[i1,i2,…in]的地址

=base-c+v453x:=a[i1,….,in]的三地址代碼結(jié)構(gòu)：

t1:=v t2:=base-c t3:=t2[t1] x:=t3454a嵌套深度偏移量類型名字表內(nèi)情向量

C=84 low1=1high1=10 n1=10 low2=1high2=20 n2=20

基類型

int標(biāo)準(zhǔn)類型

82、數(shù)組的類型信息：

VARa:ARRAY[1..10,1..20]OFint;

符號表中的信息可組織如下：4553、引用數(shù)組元素的文法

L→id[Elist]|id Elist→Elist,E|E為了便于語義處理，上述方法改寫為：

L→Elist]|id Elist→Elist,E|id[E

地址計(jì)算變量部分：

((i1*n2+i2)*n3+i3)*n4+……

可利用遞歸公式計(jì)算：e1=i1,e2=e1*n2+i2；e3=e2*n3+i3…em=em-1*nm+im

456指示的數(shù)組，所4、有關(guān)變量與函數(shù)的說明Elist.ndim：記錄Elist中的下標(biāo)表達(dá)式的個數(shù)，即維數(shù)函數(shù)limit（array，j）：返回nj，即由

array對于A[1..10,1..20]的第j維長度;

Limit(A,2)=20 Limit(A,1)=10

Elist中的下標(biāo)表達(dá)式計(jì)算出來的值;Elist引進(jìn)綜合屬性array，指向數(shù)組名a在符號表中的入口地址.457

L有兩個屬性值：L.Place和L.offsetL.Place:如果L為一個簡單名字，則L.Place為指向該名字在符號表中的入口的指針；如果L不為一個簡單名字，則L.Place為數(shù)組計(jì)算中的常數(shù)部分，base-cL.offset=null:表示L為一個簡單名字L.offset不為空，表示數(shù)組元素引用458

5、訪問數(shù)組元素的翻譯模式給定文法G(S)：

(0)M→ε

（1）S→L：＝ME

（2）E→E＋E

（3）E→（E）

（4）E→L

（5)L→Elist]

（6）L→id

（7）Elist→Elist，E

（8）Elist→id[E4596、相應(yīng)語義動作?若L是一個簡單的名字，將生成一般的賦值； 若L為數(shù)組元素引用，則生成對L所指示地 址的索引賦值

1．S→L：＝

ME

｛ifS.offset＝null thenemit(S.place'：＝'E.place)else emit（S.place'[?S.offset']'：='E.Place）}4600．M→ε

｛S.place：＝L.place; S.offset=L.offset｝2．E→E1＋E2

｛E.place：＝newtemp; emit（E.place'：＝'E1．place'＋'E2.place）｝

3．E→（E1）

{E.place：＝E1.place}461使用索引來獲得地址L.place[L.offset]的內(nèi)容：

4．E→L

｛ifL.offset＝null thenE.place:＝L.place／*Lisasimpleid*/ elsebegin E.place:=newtemp; emit(E.place':='L.place'[L.offset']') end}462

5．L→Elist]

｛L.place:=newtemp; emit（L.place':='Elist.array'－'c) L.offset:=newtemp; emit（L.offset':='w'*'Elist.place)}一個空的offset表示一個簡單的名字：

6．L→ld

（L.place:=id.place;L.offset:=null}463應(yīng)用遞歸公式掃描下一個下標(biāo)表達(dá)式

7．Elist→Elist1,E {t：＝newtemp;m：＝Elist1．ndim＋1；

emit（t'：='Elist1.place'*'‘ limit（Elist1.array,m））；emit（t'：=‘t'＋’E.place）；Elist.array：＝Elist1．a(chǎn)rray;Elist.place：=t; Elist.ndim：＝m｝em-1*nmem-1*nm+im464設(shè)w＝4，若數(shù)組第一個元素為A[1，1]。則有，C=（（low1*n2）＋low2）*w=(1*20＋1）*4＝84。

8．Elist→id[E

｛Elist.place:=E.place; Elist.ndim:=1：

Elist.array：＝id.place}例:設(shè)A為一個10*20的數(shù)組，即n1=10,n2=20;act8465LX=ELE,EA[ELyact61 EListact62

Lact41z

]act7act5act43

act42act63Mεacc0對賦值語句x：=A[y,z]的帶注釋的分析樹如圖所示。

S act1L.placext2zyL.offsetnullnullnullt3E.placezt4yElist.placet1yElist.ndim21Elist.array

mAA2Elist.place:=E.place;＝'1E.place)Elist.ndim:=1else（E.place:=newtemp；'*'‘elset'：=t;'Elist1.placeElist.place：E.place:=newtemp;Act5L.place:=id.place;L.offset:=null;}s.place=L.place：：s.place四元式表Act424140864675｛．{t｛L：if→ldL.offsetnullnull(Elist(E→Elist1,E)))emit｛（if→ld'→id[E‘null'null’→L→L→Elist]6．．Elist＝L.offset＝＋(SE.place＝）E的屬性值MifL→→ldnewtemp;LS.L.place:=newtemp;非終結(jié)符）；tεoffset=＝t(E(L→L))act7｛mthenemit(S.place'ndimarray;；－'c)else（then＝：L.place':='Elist.array'E.place:．．＋act43elseE.place:=newtemp;=Act43Elist.ndim：＝：＝id.place}='E.Place}）}}emitemits.place'['L.offset']'：Elist.arraym｝（（L.offset':='w'*'Elist.place)}limit（act1emit(E.place':='L.place'[L.offset']')}466act62

act41Act8Act63act8act63t1=y*20Act61遍歷后得屬性計(jì)算順序：act0

t1=t1+zAct62

t2=A-84t3=4*t1t4=t2[t3] X=t4｛：

xs.offsetnullAct7L.offset＝＝：

then：Elist1 L.offset:=newtemp; emitact1467

該賦值語句在由底向上的分析中被翻譯成如下三地址語句序列：

t1：=y*20 t1：=t1＋z t2：=A-84 t3:=4*t1 t4：=t2[t3] x:=t4注意：20、84、4都是編譯中引入的常量。所指

表中查找。明影辛468向的符號四、訪問記錄中的域編譯器將記錄的域的類型和相對地址保存在相應(yīng)域名的符號表表項(xiàng)之中，可以把用在符號表中查找名字的程序同樣用來查找域名。例如：表達(dá)式：p↑．info＋1

變量P是一個指向某個記錄類型的指針，info為其中一個算術(shù)型類型的域名。 編譯程序內(nèi)部把p表示為：pointer（record（t）），域名info將可以在t469pinfonextTYPE link=node; node=RECORD info:integer; next:link END;VARp:link;取 取L L(level,offsetp) 0(L)470

7.2.3布爾表達(dá)式 布爾表達(dá)式:用布爾運(yùn)算符號(and,or,not)作用到布爾變量或關(guān)系表達(dá)式上而組成 布爾表達(dá)式的作用：

1.用作計(jì)算邏輯值

2.用作控制流語句如if-then，if-then-else

和while-do等之中的條件表達(dá)式 本節(jié)考慮由如下文法生成的布爾表達(dá)式：

E→EorE|EandE|notE|(E）|

idrelopid|true|false

471And、or左結(jié)合

not右結(jié)合一、翻譯布爾表達(dá)式的方法1、表示一個布爾表達(dá)式的值

?方法一：用數(shù)值表示真和假，從而對布 爾表達(dá)式的求值可以象對算術(shù)表達(dá)式的求 值那樣一步一步地來計(jì)算例1or(not0and0)or0 =1or(1and0)or先級：not、and、or優(yōu)0=1or0or0=1or0=1472方法二：另一種方法是根據(jù)布爾表達(dá)式的特點(diǎn)，采用了某種優(yōu)化措施。 例：AorB如果A為真，那么B的值就不必計(jì)算，此時AorB的值已定，為真。 同理，AandB如果A為假，那么B的值就不必計(jì)算，此時AandB的值已定，為假。方法二用于翻譯控制流語句中的布爾表達(dá)式尤其方便。473二、數(shù)值表示法 用1表示真，0表示假來實(shí)現(xiàn)布爾表達(dá)式的翻 譯布爾表達(dá)式：aorbandnotc

翻譯成三地址代碼序列：

100：t1:=notc 101：t2:=bandt1 102：t3:=aort1474100：ifa＜bgotol03101：t：=0102：gotol04。103:t:=1104：

關(guān)系表達(dá)式：a<b

等價(jià)于ifa<bthen1else0翻譯成三地址代碼序列：四元式序列：100:(j<,a,b,103)101:(=,0,,t)102:(j,,,104)103:(=,1,,t)104:475每執(zhí)行一次emit后，nextquat自動加1

也就是即100:(j<,a,b,103)101:(=,0,,t)102:(j,,,104)103:(=,1,,t)104

nextquat三、布爾表達(dá)式的數(shù)值表示法的翻譯模式emit用于將一個三地址語句輸送到文件中Nextquat是一個計(jì)數(shù)器，指向下一個三地址語

句在輸出序列中的索引序號,將生成的三地址語句序號。476E→E1orE2｛E.place:=newtemp;E→notE1｛E.place:=newtemp;②emit(E.place':=''not'E1.place)}

emit(E.place':='E1.place'orE2.place)}E→E1andE2｛E.place:=newtemp;①emit(E.place':='E1.place'andE2.place)}477E→id1relopid2{E.place:=newtemp; emit('if'id1.placerelop.op id2.place'goto'nextstart+3); emit(E.place':=''0');③E→ture④E→false⑤emit('goto'nextstat+2); emit(E.place':=''1')}

｛E.place:=newtemp; emit(E.place':=''1')}

｛E.place:=newtemp; emit(E.place':=''0')}478EEEE例：布爾表達(dá)式a<bandc<dande<f對應(yīng)的語法樹

E①

③a<bandc<dande<f③③①動計(jì)執(zhí)

③語義2012/12/14作算機(jī)學(xué)院行順序：③

①③①110:t4=0id1.placeE1.place113:t5=t3and‘?0t4emit(E.place?=‘E1.place?1‘)}emit(E.place?=‘‘E2.place)}4792012/12/14例：布爾表達(dá)式a<bandc<dande<f可以生成如下的三地址碼100:ifa<bgoto103101:t1=0102:goto104103:t1=1104:ifc<dgoto107105:t2=0106:goto104107:t2=1計(jì)算機(jī)學(xué)院emit(E.place?=?andrelop.op111:goto113id2.place=‘112:t4=1108:t3=t1andt2109:ife<fgoto112{E.place=newtemp; emit(?if‘ {E.place=newtemp; emit(E.place?goto‘ nextstart+3){E.place=newtemp;‘E2.place)}emit(?goto‘nextstart+2) ?and

480四、控制流語句中的布爾表達(dá)式的翻譯 對于出現(xiàn)在條件語句ifEthens1elses2中的布 爾表達(dá)式E，其作用就是控制對S1和S2的選擇 因此，作為條件的布爾表達(dá)式，把它設(shè)計(jì)成 兩個出口：E.true和E.false

考慮E的上下文，對于IF語句，E.true指向S1，

E.false指向S2； 對于while語句E.true指向循環(huán)的開始，

E.false指向while的下一語句481E.true:ifa＜bgotoE.true（真出口）E.false:gotoE.false（假出口）