編譯原理課件章

第8章語法制導翻譯和中間代碼生成§8.1概述語法分析后的源程序語義處理中間代碼或目標代碼一、語義處理的任務：根據語義規(guī)則對識別出的各種語法成分析其含義，進行初步翻譯，生成相應的中間代碼或直接生成目標代碼。第一靜態(tài)語義分析或靜態(tài)審查。第二動態(tài)語義處理：

編譯中的語義處理是指兩個功能

①類型檢查。

②控制流檢查：確保控制語句有合法的轉向點。③一致性檢查。

④相關名字檢查。⑤名字的作用域分析第一:靜態(tài)語義分析通常包括：如果靜態(tài)語義正確，語義處理則要執(zhí)行真正的翻譯，即，或者將源程序翻譯成程序的一種中間表示形式（中間代碼），或者將源程序翻譯成目標代碼。

第二動態(tài)語義處理：實際應用中比較流行的語義分析方法：基于屬性文法的語法制導翻譯方法

8.2屬性文法屬性文法：屬性：

所謂屬性，用以描述事物或人的特征、性質，品質等等。比如，談到一個物體，可以用“顏色”描述它，談起某人，可以使用“有幽默感“來形容他。對一個文法,文法中的每個符號都有屬性，可以用"類型"、"值"或"存儲位置"來描述它。附加了一組屬性和運算（語義）規(guī)則的文法

屬性文法文法符號X的屬性t常用X.t來表示語義規(guī)則用花括號｛｝括起來，可被插入到產生式右部的任何合適的位置上。不同的產生式對應不同的語義規(guī)則不同的分析目標也對應不同的語義規(guī)則

1.屬性的表示2.語義規(guī)則的表示語義信息語義之間的關系一個屬性文法是一個三元組：

A＝（G，V，F），

G:是一個上下文無關文法

V:有窮的屬性集,每個屬性與文法的一終結符或非終結符相連。

F:關于屬性的屬性斷言或謂詞集.每個斷言與一個產生式相聯(lián)。一個斷言就是一個語義規(guī)則，描述各屬性的關系。用法：針對語義：為每個符號設置一個屬性，終結符號用單詞屬性。為每個產生式設置語義規(guī)則——描述各屬性的關系。屬性文法的定義：屬性分為兩種

繼承屬性和綜合屬性綜合屬性：在語法樹中，一個結點的綜合屬性由該結點的子結點的屬性值確定。它的計算規(guī)則由底向上.

繼承屬性:在語法樹中，一個結點的繼承屬性由該結點的父結點/兄弟結點的屬性確定。

例綜合屬性

L

EE

E1+TE

TT

T1*FT

FF

(E)F

iprint(E.val)E.val=E1.val+T.valE.val=T.valT.val=T1.val

F.valT.val=F.valF.val=E.valF.val=i.lexval語義規(guī)則產生式計算3*5+4的值3*5+4的分析樹只使用綜合屬性.LEETTFTFFi5i4i3+*3*5+4的分析樹一個結點的綜合屬性值是其子結點的某些屬性來決定的通常使用自底向上的分析方法在每個結點處使用語義規(guī)則來計算綜合屬性值當一個產生式獲得匹配時，就調用相應的語義子程序從葉結點到根結點進行計算

L

EE

E1+TE

TT

T1*FT

FF

(E)F

iprint(E.val)E.val=E1.val+T.valE.val=T.valT.val=T1.val

F.valT.val=F.valF.val=E.valF.val=i.lexval語義規(guī)則產生式繼承屬性一個結點的繼承屬性值是由此結點的父結點和/或兄弟結點的某些屬性來決定的。例，添加標識符類型的語義描述：繼承屬性

L1.in:=L.in產生式語義規(guī)則D

TL

T

int

T

real

L

L1,idL

idL.in:=T.typeT.type=integerT.type:=real

addtype(id.entry,L.in)

addtype(id.entry,L.in)與L產生式相聯(lián)的語義規(guī)則中有一個過程調用addtype，過程addtype的功能是把每個標識符的類型信息登錄在符號表的相關項中。句子intid1,id2的語法樹，使用

表示屬性的傳遞情況。

L1.in:=L.in產生式語義規(guī)則D

TL

T

int

T

real

L

L1,idL

idL.in:=T.typeT.type=integerT.type:=real

addtype(id.entry,L.in)

addtype(id.entry,L.in)DTLLid1id2，int1、文法非終結符既可有綜合屬性，也可有繼承屬性；2、開始符號沒有繼承屬性；3、終結符只有綜合屬性，由詞法分析器提供。幾點說明：語法制導翻譯：將語義規(guī)則與語法規(guī)則相結合，在語法分析的過程中通過執(zhí)行語義動作，計算語義屬性值，從而完成預定的翻譯工作。8.3語法制導翻譯語法制導翻譯分為兩種處理方法：（1）自底向上的翻譯：（只有綜合屬性）對每個產生式編制一個語義子程序，在進行語法分析的過程中，當一個產生式獲得匹配時，就調用相應的語義子程序實現語義檢查與翻譯。這種實現方案隱藏了其中語義規(guī)則的計算次序等實現細節(jié)。（2）自頂向下翻譯（含有繼承屬性）：在產生式右部的適當位置，插入相應的語義動作，即語義規(guī)則或語義動作用花括號｛｝括起來，可被插入到產生式右部的任何合適的位置上。按照分析的進程，執(zhí)行遇到的語義動作。這是一種動作與分析交錯的實現方案。綜合屬性繼承屬性自底向上傳遞信息自頂向下（自左向右）傳遞信息僅包含綜合屬性的語法制導定義如：算術表達式求值的屬性文法S-屬性文法和自下而上的翻譯一個結點的綜合屬性值是其子結點的某些屬性來決定的２+3*4的注釋分析樹通常使用自底向上的分析方法在每個結點處使用語義規(guī)則來計算綜合屬性值當一個產生式獲得匹配時，就調用相應的語義子程序從葉結點到根結點進行計算只含有綜合屬性的語法制導定義稱為S屬性定義L-屬性文法在自上而下分析中的實現既包括綜合屬性，又包括繼承屬性，即對于所有Ａ→Ｘ1

Ｘ2

…

Ｘn，每一個屬性或者都是綜合屬性，或者Ｘi屬性計算僅使用ＡＸ1

Ｘ2

…

Ｘi-1

的屬性,這種叫L-屬性的文法法制導定義其屬性可用深度優(yōu)先的順序從左至右計算非L-屬性的文法制導定義產生式語義規(guī)則A

LMA

QRL.i:=l(A.i)M.i:=m(L.s)A.s:=f(M.s)R.i:=r(A.i)Q.i:=q(R.s)A.s:=f(Q.s)表中的語法制導定義不是L-屬性定義文法符號Q的繼承屬性依賴于它右邊文法符號R的屬性

L1.in:=L.in產生式語義規(guī)則D

TL

T

int

T

real

L

L1,idL

idL.in:=T.typeT.type=integerT.type:=real

addtype(id.entry,L.in)

addtype(id.entry,L.in)L-屬性文法的例子DTLLid1id2，int例一個簡單的翻譯模式

E→TRR→addopT{print(addop.lexeme)}R1|εT→num{print(num.val)}輸入9-5+2,其分析樹如下頁圖，當按深度優(yōu)先遍歷它，執(zhí)行遍歷中訪問的語義動作，將輸出結果是什么？它輸出結果是：95-2+它是輸出表達式9-5+2的后綴式。ET9TPt(′9′)RPt(′-′)Pt(′+′)R-5Pt(′5′)+T2Pt(′2′)R

9-5+2的帶語義動作的分析樹E→TRR→addopT{print(addop.lexeme)}R1|εT→num{print(num.val)}輸出：

95-2+設計翻譯模式分兩種情況:1、只需要綜合屬性的情況2.既有綜合屬性又有繼承屬性為每一個語義規(guī)則建立一個包含賦值的動作，并把這個動作放在相應的產生式右邊的末尾。例如：TT1*F{Tval:=T1val*Fval}TT1*F{Tval:=T1val*Fval}1.只需要綜合屬性的情況：產生式右邊的符號的繼承屬性必須在這個符號以前的動作中計算出來。一個動作不能引用這個動作右邊符號的屬性。產生式左邊非終結符號的綜合屬性只有在它所引用的所有屬性都計算出來以后才能計算。計算這種屬性的動作通?？煞旁诋a生式右端的未尾。2.既有綜合屬性又有繼承屬性下面的翻譯模式不滿足要求,不滿足第1)個條件：

SA1A2{A1in:=1;A2in:=2}Aa{print(Ain)}可以看出,按深度優(yōu)先遍歷輸入串aa的語法樹，當要打印屬性A.in時，該屬性還沒有定義。也就是說，從S開始按深度優(yōu)先遍歷A1和A2子樹之前，A1.in和A2.in的值還未賦值。SA1A2aaA1.in:=1;A2.in:=2Print(A.in)Print(A.in)如果計算A1.in和A2.in的值的動作分別被嵌入在產生式SA1A2的右部A1和A2之前，而不是后面，那么A.in在執(zhí)行Print（A.in）時已有定義。S{A1in:=1}A1{A2in:=2}

A2Aa{print(Ain)}SA1A2aaA1.in:=1;Print(A.in)Print(A.in)A2.in:=2;常見的中間代碼形式：后綴式三地址代碼（四元式、三元式和間接三元式）圖形（抽象語法樹等）

中間代碼：一種介于源語言和目標語言之間的中間語言形式中間代碼逆波蘭記號

逆波蘭記號是最簡單的一種中間代碼表示形式。這種表示法將運算對象寫在前面，把運算符號寫在后面，比如把a+b寫成ab+，把a*b寫成ab*，用這種表示法表示的表達式也稱做后綴式。中綴表示后綴表示

a+bab+

a+b*cabc*+

(a+b)*cab+c*a:=b*c+b*dabc*bd*+:=特點1、運算對象出現的順序和原有順序（從左到右）相同2、運算符按實際計算順序（從左到右）出現3、運算符緊跟在運算對象的后面出現，且沒有括號優(yōu)點：簡明、便于計值后綴表示法表示表達式，其最大的優(yōu)點是易于計算機處理表達式。常用的算法是使用一個棧，自左至右掃描算術表達式（后綴表示），每掃描到運算對象，就把它推進棧；掃描到運算符，若該運算符是二目的，則對棧頂部的兩個運算對象實施該運算，并將運算結果代替這兩個運算對象而進棧；若是一目運算符，則對棧頂元素執(zhí)行該運算，并以運算結果代替該元素進棧，最后的結果留在棧頂。

例如B@CD*+（它的中綴表示為－B+C*D，使用@表示一目減）的計值過程為：B進棧；對棧頂元素施行一目減運算，并將結果代替棧頂，即－B置于棧頂；C進棧；

D進棧；棧頂兩元素相乘，兩元素退棧，相乘結果置棧頂；棧頂兩元素相加，兩元素退棧，相加結果進棧，現在棧頂存放的是整個表達式的值。

逆波蘭表示很容易擴充到表達式以外的范圍。只要遵守運算對象后直接緊跟它們的運算符的規(guī)則即可。比如把轉語句GOTOL寫為“Ljump"，

運算對象L為語句標號，運算符jump表示轉到某個標號L。再比如條件語句ifEthenS1elseS2

可表示為：ES1S2￥，把ifthenelse看成三目運算符，用￥來表示。例:給出下列表達式的逆波蘭式:(1)a*(-b+c)(2)a+b*(c+d/e)解(1)ab@c+*(2)abcde/+*+練習:P2021

另一類中間代碼形式是三元式。把表達式及各種語句表示成一組三元式(op,ARG1,ARG2)。分別是算符op，第一運算對象ARG1和第二運算對象ARG2。運算對象可能是源程序中的變量，也可能是某個三元式的結果，用三元式的編號表示。例如a:=b*c+b*d的表示為：

（1）（*，b，c）

（2）（*，b，d）

（3）（+（1），（2））

（4）（∶＝（3），a）三元式和樹形表示例：A=B+C*D/EF=C*D三元式(1)*,C,D(2)/,(1),E(3)+,B,(2)(4)=,A,(3)(5)*,C,D(6)=,F,(1)

不便于代碼優(yōu)化：刪除某些三元式后可能需作一系列的修改

三元式(1)*,C,D(2)/,(1),E(3)+,B,(2)(4)=,A,(3)(5)=,F,(1)間接三元式執(zhí)行順序（間接碼表）(1)(2)(3)(4)(1)(5)三元式的執(zhí)行次序用另一張表表示,優(yōu)化時三元式可以不變，僅僅改變其執(zhí)行順序表例:A+B*(C-D)+E/(C-D)^N三元式：

（1）（－C

D）

（2）（*B（1））

（3）（+

A（2））

（4）（－C

D）

（5）（^（4）N）

（6）（/

E（5））

（7）（+（3）（6））

間接三元式：

（1）(－C

D)

（2）(*

B

(1))

（3）(+

A(2))

（4）(^(1)

N）

（5）(/

E

(4))（6）(+

(3)

(5))

間接碼表

（1）

（2）

（3）

（1）

（4）

（5）

（6）每生成一條指令，先檢查已生成的間接三元式序列，若已有,不再生成,只把序號列入間接碼表。間接碼表明了間接三元式執(zhí)行的順序樹形表示是三元式表示的翻版。例:a∶=b*c+b*d可表示成下面的樹表示：

例表達式(A-12)*B+6的語法結構樹將賦值語句變換為語法結構樹基本函數——結點構造Mknode(op,left,right)建標記為op的算符結點,結點有兩個域，分別為left和right.Mkleaf(id,entry)建標記為id的葉結點，有一個entry域，它是指向符號表的入口。Mkleaf(num,val)建標記為id的葉結點,有一個val域，是表示該數的值。構造a-4+c的語法樹：

＋－id指向c的入口id指向a的入口num4(1)p1:=mkleaf(id,entrya);(2)p2:=mkleaf(num,4);(3)p3:=mknode(‘-’，p1,p2)(4)p4:=mkleaf(id,entryc)(5)p5:=mknode(‘+’,p3,p4)語法制導定義(屬性文法)E.p是語法結構樹指針四元式和三元式的主要不同在于，四元式對中間結果的引用必須通過給定的名字，而三元式是通過產生中間結果的三元式編號。也就是說，四元式之間的聯(lián)系是通過臨時變量實現的。(OP,ARG1,ARG2,T)有時，為了更直觀，也把四元式的形式寫成簡單賦值形式或更易理解的形式。比如把a∶=b*c+b*d四元式序列寫成：

（1）t1∶=b*c

（2）t2∶=b*d

（3）t3∶=t1+t2

（4）a∶=t3

把（jump，－，－，L）寫成gotoL

把（jrop，B，C，L）寫成ifBropCgotoL2．具體實現四元式操作符操作數1操作數2結果結果：通常是由編譯引進的臨時變量例:X=(A+B)*(C+D)-E+,A,B,T1+,C,D,T2*,T1,T2,T3-,T3,E,T4=,T4,一,XT1,T2,T3,T4為臨時變量，由四元式優(yōu)化比較方便T1=A+BT2=C+DT3=T1+T2T4=T3-EX=T4請將表達式-(a+b)*(c+d)-(a+b)分別表示成三元式、間接三元式和四元式序列。

三元式

(1)(+a,b)

(2)(+c,d)

(3)(*(1),(2))

(4)(-(3),/)

(5)(+a,b)

(6)(-(4),(5))

間接三元式

間接三元式序列間接碼表

(1)(+a,b)

(1)

(2)(+c,d)

(2)

(3)(*(1),(2))

(3)

(4)(-(3),/)

(4)

(5)(-(4),(1))

(1)

(5)四元式

(1)(+,a,b,t1)

(2)(+,c,d,t2)

(3)(*,t1,t2,t3)

(4)(-,t3,/,t4)

(5)(+,a,b,t5)

(6)(-,t4,t5,t6)簡單的賦值語句的（四元式）翻譯四元式形式：t:=arg1oparg2語義屬性：,E.place

函數：lookup()

過程：emit(t:=arg1oparg2)（生成一條指令）

newtemp;(分配一個臨時工作單元）(1)S→id∶=E{p∶=lookup（id．name）；

ifp≠nil

then

Emit（p‘∶=’E．place）

else

error}

(2)E→E1+E2{E．place∶=newtemp；

Emit（E.place‘∶=’E1.place‘+’E2．place）}

(3)E→E1*E2{E.placeE∶=newtemp；

Emit（E.place‘∶=’E1.place‘*’E2.place）}

(4)E→－E1{E.Place‘∶=’newtemp；

Emit（E．Place‘:=’‘uminus’E1．place）}

(5)E→（E1）{E．Place’∶=’E1．place}

(6)E→id{p:=lookup（id．name）}；

if

p≠nilthen

E．placeE’∶=’p

else

error}賦值語句的四元式翻譯實際上，在一個表達式中可能出現各種不同類型的變量，而不象前面假定為同一類型。因此，上例應改為P181圖8.13的形式。8.3布爾表達式的翻譯程序設計語言中的布爾表達式有兩個作用。一是計算邏輯值更多的情況是二:用做改變控制流語句中的條件表達式，如在if-then，if-then-else，或是while-do語句中那樣。布爾表達式是由布爾算符and，or和not或表示為（∧，∨和┓）施于布爾變量或關系表達式而成。約定優(yōu)先順序為┓,∧,∨,遵循左結合。布爾表達式有兩個作用：是計算邏輯值用來改變控制流語句中的條件表達式。布爾表達式的翻譯方法通常，計算布爾表達式的值有兩種辦法:第一種辦法，如同計算算術表達式一樣，步步計算出各部分的真假值，最后計算出整個表達式的值。那么布爾表達式1or（not0and0）or0的計算過程是：

1or（not0and0）or0

＝1or（1and0）or0

＝1or0or0

＝1or0

＝1

用數值1表示true，用0表示false。另一種計算方法是采取某種優(yōu)化措施，只計算部分表達式.例如要計算AorB，若計算出A的值為1，那么B的值就無需再計算了，因為不管B的值為何結果，AorB的值都為1。如計算AandB若A為假值0，則無需計算B，結果為0。這種計算方法，意味著可以用if–then-else來解釋∧，∨和┓即：把A∨B解釋成：ifAthentrueelseB把A∧B解釋成：ifAthenBelsefals.把┓A解釋成：ifAthenfalseelsetrue控制語句中布爾表達式的翻譯

現在討論出現在ifthen；ifthenelse和whiledo等語句中的布爾表達式E的翻譯。

這三種語句的語法為：

S→ifEthenS1|ifEthenS1elseS2|whileEdoS1

控制語句的代碼結構

(a)ifEthenS1E的代碼.

。S1的代碼JumpoutS2的代碼out(b)|ifEthenS1elseS2E的代碼.

。

S1的代碼真假beginE的代碼.

。S1的代碼Jumpbegin(c)whileEdoS1對于E為E1orE2的形式：1、E1為真，則E為真，即E的真出口為E1的真出口。2、E1為假，計算E2，即E1的假出口應為E2的第一個四元式標號，E2的真、假出口與E的真、假出口一樣。翻譯的基本思路：對于E為aropb,形成代碼為：IfaropbgotoE.truegotoE.false把條件轉移的布爾表達式E翻譯成僅含條件轉移和無條件轉移的四元式E：aropbifaropbgotoE.truegotoE.false如：a<borc<dande<f可以翻成如下四元式：（1)ifa<bgoto(2)goto

（3）ifc<dgoto(4)goto(5)ife<fgoto(6)gotoE.tue(3)(5)E.falseE.trueE.false我們使用E．true和E．false分別表示整個表達式a＜borc＜dande<f的真、假出口，而E．true和E．false的值并不能在產生四元式的同時就知道。為了看清這一點，我們把該表達式放在條件語句中考慮，如語句If(a＜borc＜dande<f)thenS1elseS2的四元式序列見下頁：（1）if

a＜b

goto

（2）goto

（3）if

c＜d

goto

（4）goto

（5）if

e<f

goto

（6）goto

（7）（關于S1的四元式）

…

（p）goto

（p+1）（關于S2的四元式）

…

（q）If(a＜borc＜dande<f)thenS1elseS2的四元式序列為（7）（3）（5）(p+1)（q）（7）（p+1）使用拉鏈回填翻譯控制語句中的布爾表達式拉鏈：

……….L1:gotoL;

……….L2:gotoL;

……….L3:gotoL;

……….L:……….

L2L10語義描述使用的量：E.true“真”鏈，E.false“假”鏈E.codebeginE的第一個四元式

nextstat下一四元式地址

過程：

emit()

輸出一條四元式

merge(p1,p2)

例：

merge(p1,p2)(p100)goto0

……

p1鏈(p10)gotop100……`(p1)gotop10(p200)goto0……

p2鏈(p20)gotop200……(p2)gotop20

backpatch(p,t)

把p所鏈接的每個四元式的第四區(qū)段都填為t。如：E1orE2E1有一個真出口，E2也有一個真出口，將兩個鏈合并為一條鏈。p1（7）E→true{E.true:=nextstat;E.codebegin:=nextstat;emit(‘goto’__)}(8)E→false{E.false:=nextstat;E.codebegin:=nextstat;emit(‘goto’__)}以表達式a<borc<dande>f為例，它的四元式序列：100：ifa<bgoto

101:goto

102：ifc<dgoto

103：goto104:ife>fgoto105:goto將分析產生語法樹時的語義動作結果“真”“假”鏈情況注釋在相應結點處，見P185圖8.17E.true102104E.falseE.trueE.false控制語句的翻譯條件轉移

考慮ifthen，ifthenelse和whiledo語句，在圖8.12中已給出了它們的代碼結構。這里我們使用下面文法G[S]定義這些語句：

G[S]

（1）S→ifEthenS

（2）|

ifEthenSelseS

（3）|

whileEdoS

（4）|

beginLend

（5）|

A

（6）L→L；S

（7）|S

其中各非終結符號的意義是：

S--語句

L--語句串

A--賦值句

E--布爾表達式為了能使語義在程序置于每個產生式的最后，需對原文法的產生式拆分，對G(S)進行拆分修改為G(S’):(1)S→CS1(8)C→ifEthen(2)S→TpS2(9)Tp→CSelse(3)S→WdS3(10)Wd→WEdo(4)S→beginLend(11)W→while(5)

S→A(6)S→LsS1(12)Ls→L;(7)L→S(1)S→CS1{S.Chain:=merge(C.Chain,S1.Chain)(8)C→ifEthen{backpatch(E.true,nextstat)C.chain:=E.false}(9)Tp→CS1else{q:=nextstatemit(‘goto’___)backpatch(C.Chain,nextstat)Tp.Chain:=merge(S1.chain,q)}(2)S→TpS2{S.chain:=merge(Tp.Chain,S2.Chain)}(11)W→while{W.codebegin:=nextstat}(10)Wd→WEdo{backpatch(E.true,nextstat)Wd.chain:=E.false

Wd.codebegin:=W.codebegin}S→WdS3{backpatch(S3.chain,Wd.codebegin)emit(‘goto’Wd.codebegin)S.chain:=Wd.chain}(4)S→beginLend{S.chain:=L.chain}(5)

S→A{S.chain:=0/*空鏈*/}L→S{L.chain:=S.chain}(12)Ls→L;{backpatch(L.chain,nextstat)}(6)L→LsS1{L.chain:=S1.chain}按照上述文法產生式相應的語義動作，加上前述關于賦值句和布爾表達式的翻譯法，語句

while（A＜B）doif（C＜D）thenX∶=Y+Z

將被翻譯成如下的一串四元式：

100

ifA<B

goto

101

goto

102

if

C＜Dgoto

103

goto100

104

T∶=Y+Z

105

X∶=T

106

goto100

107while（A＜B）doif（C＜D）thenX∶=Y+Z102107104for循環(huán)語句fori∶=E1stepE2untilE3doS1

為了簡單起見，假定E2總是正的。在這種假定下，上述循環(huán)句的意義等價于：

i∶=E1；

gotoOVER；

AGAIN：i∶=i+E2；

OVER：ifi≤E3then

beginS1；gotoAGAINend；

翻譯見P191-P192開關語句開關語句（case語句或switch語句）switchEof

caseV1：S1

caseV2：S2

…

caseVn-1：Sn-1

default：Sn

end如果分叉不太多，case語句翻譯成如下的一連串條件轉移語句。

t∶=E；

L1：ift≠V1gotoL2；

S1；

gotonext；

L2：ift≠V2gotoL3；

S2

gotonext；

…

Ln-1：ift≠Vn-1gotoLn；

Sn-1；

gotonext；

Ln：Sn；

next：另一種方法:P190圖8.18

計算E值，并把結果放到臨時變量t中

gototestL1:S1的中間代碼

gotonextL2:S2的中間代碼

gotonext

……Ln:Sn的中間代碼

gotonexttest:ift=v1gotoL1;ift=v2gotoL2;

…….ift=vn-1gotoLn-1;gotoLnnext:goto語句多數程序語言中的轉移是通過標號和goto語句實現的。帶標號語句的形式是L∶S；goto語句的形式是gotoL。

當L∶S；語句被處理之后，標號L是"定義了"的。即在符號表中，將登記L的項的"地址"欄中登上語句S的第一個四元式的地址。如果gotoL是一個向上轉移的語句，那么，當編譯程序碰到這個語句時，L必是已定義了的。通過對L查找符號表獲得它的定義地址p，編譯程序可立即產生出相應于這個gotoL的四元式如（j，－，－，p）。

如果gotoL是一個向下轉移的語句，也就是說，標號L尚未定義，那么，若L是第一次出現，則把它填進符號表中并標志上“未定義”。由于L尚未定義，對gotoL只能產生一個不完全的四元式（goto－），它的轉移目標須待L定義時再回填進去。

在這種情況下，必須把所有那些以L為轉移目標的四元式的地址全都記錄下來，以便一旦L定義時就可對這些四元式進行回填。我們將采用如圖8.20所示的拉鏈辦法，把所有以L為轉移目標的四元式串在一起。鏈的首地址放在符號表中L的"地址"欄中建鏈的方法是：若gotoL中的標號L尚未在符號表中出現，則把L填入表中，置L的“定義否”標志為“未”，把nextstat填進L的地址欄中作為新鏈首，然后，產生四元式(p)（goto0），其中0為鏈尾標志。若L已在符號表中出現（但“定義否”標志為“未”），則把它的地址欄中的編號（記為p）取出，把nextstat填進該欄作新鏈首，然后，產生四元式(q)（gotop）。一旦標號L定義時，我們將根據這條鏈回填那些待填轉移目標的四元式。一般而言，假定用下面的產生式來定義標號語句S→labelS

label→i：1.若i所指的標識符（假定為L）不在符號表中，則把它填入，置“類型”為“標號”，“定義否”為“已”，“地址”為nextstat。

2.若L已在符號表中但“類型”不為“標號”或“定義否”為“已”，則報告出錯。

3.若L已在符號表中，則把標志“未”改為“已”，然后，把地址欄中的鏈首（記為q）取出，同時把nextstat填在其中，最后，執(zhí)行backpatch(q,nextstat)。過程調用的四元式產生過程調用的實質是把程序控制轉移到子程序,在轉子之前,必須用某種辦法把實參的信息傳給調用的子程序。傳遞實參信息方面有種種不同的方法,我們這里只討論一種,即傳實參地址的方式。若實參是一個變量或數組，則直接傳遞地址。若實參是表達式，如：A+B或2，則把它們的值計算出來，并存放在一個臨時變量T中，然后傳遞T的地址。傳遞實參地址的一個簡單辦法是：把實參地址逐一放在轉指令的前面；例：過程調用：CallS(A+B,Z)譯為：計算A＋B的值置于T中/*T:=A+B*/ParT/*第一個實參的地址*/ParZ/*第二個實參的地址*/CallS/*轉指令*/為了處理在實參時記住每個實參的地址，以便最后把它們排在Call指令之前，我們需要把這些地址存放起來，我們可用隊列來存放。例：一個描述過程調用語句的文法如下：

(1)S→calli(<arglist>)(2)<arglist>→<arglist>1,E(3)<arglist>→E它的語法制導翻譯見P196例：寫一個翻譯過程調用語句的語義子程序。要求生成的四元式序列在轉指令之前的參數四元式par按反序出現（與實在參數的順序相反）。過程調用語句的文法如下：

(1)S→calli(<arglist>)(2)<arglist>→<arglist>1,E(3)<arglist>→E(1)<arglist>→E{建一個arglist.Stack棧，它僅包含一項E.Place}(2)<arglist>→<arglist>1,E{將E.Palce壓入<arglist>1.Stack棧，

arglist.Stack:=arglist1.Stack}(3)S→calli(<arglist>){Whilearglist.Stack≠nulldobegin

將arglist.Stack棧頂彈出生成

Gen(par,_,_,p)end;Gen(call,_,_,Entry(i))}簡單說明語句的翻譯程序設計語言中的說明語句旨在定義各種形式的有名實體，如常量、變量、數組、記錄(結構)、過程、子程序等等，說明語句的種類也多，對象說明、變量說明、類型說明、過程說明等等。編譯程序把說明語句中定義的名字和性質登記在符號表中，用以檢查名字的引用和說明是否一致。簡單說明句的翻譯

程序設計語言中最簡單的說明句的語法描述為：

D→integer〈namelist〉|real〈namelist〉

〈namelise〉→〈namelist〉，id|id

即使用關鍵字integer和real定義一串名字的性質。對這種說明句的翻譯是指在符號表中登錄該名和性質。

用上述文法來制導翻譯(自下而上)存在著這樣一個問題，我們只能在把所有的名字都歸約成namelist后才能把它們的性質登記進符號表我們可以把上述的文法改寫成：

D→D1,id

|integerid

|realid

這樣,就能把所說明的性質及時地告訴每個名字id，或者說，每當讀進一個標識符時，就可以把它的性質登記在符號表中，不用把它們集中起來最后再成批登記了。

現在來定義這些產生式所對應的語義動作，給非終結符D一個語義變量D.ATT，用以記錄說明句所引入的名字的性質(int還是real)，使用過程enter(id,A)把名字id和性質A登錄在名表中。

(1)D→integerid{enter(id,int);

D.ATT∶=int}

(2)D→realid{enter(id,real);

D.ATT∶=real}

(3)D→D1,id{enter(id,D1.ATT);

D.ATT∶=D1.ATT}過程中的說明現在主要討論過程中的局部變量的說明。我們要為過程的局部名字安排存儲，對這些名字建符號表時，要記錄名字，類型和相對地址。為了記錄相對地址，可以使用一個變量offset。記錄當前可用的空間的開始地址，每次分配一個變量，將offset增加相應的值，offset增加的值由名字的類型決定，即由數據對象的寬度決定，寬度用Width來表示。例：產生式語義動作

D→realid{enter(id,real,offset);D.ATT:=real;D.Width:=8;offset:=offset+D.Width;}

數組的翻譯：一般編譯程序對數組的處理是把數組的相關信息匯集在一個叫做“內情向量”的表格中，“內情向量”，包括數組的類型，維數，各維的上、下界，每維的長度以及數組的首地址。

A[l1:u1,l2:u2,,ln

:un]

l1

u1

l2

u2::type

a（首地址）

nCd1d2其中：li表示每維的下界，ui表示每維的上界,di為每維的長度,di=ui-li+1C為Conspart=a-C的第二項,a為數組的首地址，n為數組的維數,type為數組的類型X:=a[i,j]翻譯成四元式的結構：

T1:=VARPART;T2:=CONSPART;T3:=T2[T1];