第4章靜態(tài)語義分析(4)計算機科學與技術學院國家示范性軟件學院1自學：學在西電-課程視頻本節(jié)內容：已討論：不考慮類型時的翻譯（4.3.2節(jié)）。4.6簡單算術表達式與賦值句考慮整數(shù)、實數(shù)混合運算時，必要的：(1)類型轉換規(guī)則；(2)類型轉換所需的三地址碼；(3)支持類型轉換的翻譯。24.7數(shù)組元素的引用數(shù)組空間的存儲分配：分配一個連續(xù)空間；第一個元素地址稱為首地址。a[0,2]a[0,3]a[0,4]a[1,2]a[1,3]a[1,4]a[2,2]a[2,3]a[2,4]以行為主：以列為主：確定元素地址的要素：首地址、相對首地址的偏移量。

不同的映射方式，使得同一個元素的偏移量不同。例如：a[1,2]，偏移量分別是3和1?？紤]二維數(shù)組

a[0..2,2..4]：數(shù)組到一維空間的映射方式：以行為主、以列為主、其他a[0,2]a[0,3]a[0,4]a[1,2]a[1,3]a[1,4]a[2,2]a[2,3]a[2,4]a[0,2]a[1,2]a[2,2]a[0,3]a[1,3]a[2,3]a[0,4]a[1,4]a[2,4]**僅討論一般意義的規(guī)則數(shù)組31．由定義數(shù)組類型時的語法確定映射方式：

a:array[d1]ofarray[d2]of...array[dn]ofinteger;

引用方式：a[i1,i2,...,in]或a[i1][i2]...[in]2．由編譯器(根據(jù)約定)確定映射方式：

a:array[d1,d2,...,dn]ofinteger;引用方式：a[i1,i2,...,in]引用數(shù)組元素時，如何確定對應元素的地址：1．確定元素地址的計算公式；

2．根據(jù)計算公式設計語義規(guī)則。C

程序示例：inta[d1][d2]…[dn];確定數(shù)組映射方式的兩種方法:

4.7數(shù)組元素的引用4（課堂討論中）三個假設條件：1.數(shù)組元素以行為主存放；2.數(shù)組每維下標的下界均為1；3.每個元素占w

個標準存貯單元。約定：數(shù)組的聲明：數(shù)組元素的引用：4.7.1數(shù)組元素的地址計算A[d1,d2,..,dn]A[i1,i2,..,in]5a+(i-1)*w二維數(shù)組A[d1,d2]元素的地址計算：addr(A[i1,i2])=a+(

)*w前面的元素個數(shù)前i1-1行的元素個數(shù)本行前面的元素個數(shù)1

2

3

…

i

…

a12…i2…1

2

3

…

i1

i1,i2

…

+(i2-1)(i1-1)*d2d2一維數(shù)組A[d1]元素的地址計算：4.7.1數(shù)組元素的地址計算首地址元素寬度addr(A[i])=6三維數(shù)組A[d1,d2,d3]

元素的地址計算：addr(A[i1,i2,i3])=a+(

)*w

(i1-1)*d2*d3d3d2d1a第1頁第2頁第i1頁+(i2-1)*d3+(i3-1)4.7.1數(shù)組元素的地址計算

第i1頁第i2行第i3列i1,i2,i34.7.1數(shù)組元素的地址計算7n維數(shù)組元素的地址計算:

A[d1,d2,…,dn]addr(A[i1，i2，...，in])=a+((i1-1)*d2*d3*...*dn+(i2-1)*d3*d4*...*dn+...+(in-1))*w

展開i-1、合并-，合并+addr(A[i1])=a+(i1-1)*waddr(A[i1,i2])=a+((i1-1)*d2+(i2-1))*waddr(A[i1,i2,i3])=a+((i1-1)*d2*d3+(i2-1)*d3+(i3-1))*w(i1-1)*d2*d3*...*dn+(i2-1)*d3*d4*...*dn+...+(in-1)1、2、3維數(shù)組元素的地址計算:+(i1*d2*d3*...*dn+i2

*d3*d4*...*dn+...+in-1*dn+in)*w=a-(d2*d3*...*dn+d3*d4*...*dn+...+dn+1)*wcvn維數(shù)組元素的地址計算:A[d1,d2,…,dn]8addr(A[i1，i2，...，in])=……c=d2*d3*d4...*dn+d3*d4*d5...*dn+*d4*d5*d6...*dn...+dn+1=(d2+1)*d3*d4*...*dn+d4*d5...*dn+...+dn+1=((d2+1)*d3+1)*d4*d5...*dn+...+dn+1......=(...((d2+1)*d3+1)*d4...+1)*dn+1同理：v=(...((i1*d2+i2)*d3+i3)*d4...+in-1)*dn+in

其中：+(i1*d2*d3*...*dn+i2

*d3*d4*...*dn+...+in-1*dn+in)*w=a-(d2*d3*...*dn+d3*d4*...*dn+...+dn+1)*w=a–

c*w+v*w4.7.1數(shù)組元素的地址計算9c=(...((d2+1)*d3+1)*d4...+1)*dn+1v=(...((i1*d2+i2)*d3+i3)*d4...+in-1)*dn+in

令：v1=i1v2=i1*d2+i2v3=(i1*d2+i2)*d3+i3 ......vj=……..=vj-1*dj+ij ......vn=……..=vn-1*dn+in最終，得到數(shù)組元素的地址計算公式:addr(A[i1，i2，...，in])=a-cw+vw

=CONSPART

+VARPART同理：

c1=1

cj=cj-1*dj+1(j=2，3，...,n)(4.3)于是有：

v1=i1

vj=vj-1*dj+ij(j=2，3，...,n)(4.6)=v1*d2+i2=v2*d3+i3則：n維數(shù)組元素的地址計算:A[d1,d2,…,dn]4.7.1數(shù)組元素的地址計算10數(shù)組元素的地址：CONSPART[VARPART]，或簡寫：T1[T]三地址碼：(1)取值：

X=T1[T](2)賦值：T1[T]=X<1>引入數(shù)組元素后的賦值句文法引入了新的非終結符V，使得分析樹增高。**根據(jù)此文法進行翻譯存在困難,無法使用遞推公式(因為dj需要知道數(shù)組名a)。4.7.2數(shù)組元素引用的翻譯a[i,j]=x的分析樹A→V=EV→id|

id[EL]

(G4.10)EL→E|EL，EE→E+E|(E)|V4.7.2數(shù)組元素引用的翻譯11修改文法以適應遞推公式的同步計算：A→V=E (1)G4.11V→id (2)|EL] (3)EL→id[E (4)|EL,E (5)E→E+E (6)|(E) (7)|V (8)//得到數(shù)組名,第一維下標,即v1//計算第i維的vi//完成元素引用的分析、對v的計算根據(jù)修改后的文法，a[i,j]=x的分析樹變?yōu)椋簐1=i1

vj=vj-1*dj+ij121.

屬性.array：數(shù)組名在符號表中的入口(或數(shù)組首地址)。2.

屬性.dim：數(shù)組維數(shù)計數(shù)器，記錄當前分析到的維數(shù)。3.

屬性.place：下標列表EL：表示vj=vj-1*dj+ij

(j=2,...,n)的存儲地址，vj是臨時變量；簡單變量id，E：仍然表示相應數(shù)據(jù)的地址；數(shù)組元素id[EL]：存放不變部分，一般可以是一個臨時變量。4.屬性.offset：保存數(shù)組元素地址中的可變部分。簡單變量的offset為空，可記為null。5.

函數(shù)limit(array,k)：查詢數(shù)組array中第k維長度dk。語義規(guī)則<2>屬性和函數(shù)4.7.2數(shù)組元素引用的翻譯

{V.place=newtemp();emit(V.place'='EL.array'-'C);V.offset=newtemp();emit(V.offset'='EL.place'*'w);}{k=EL1.dim+1;dk=limit(EL1.array,k);T=newtemp();emit(T'='EL1.place'*'dk);emit(T'='T'+'E.place);EL.place=T;EL.dim=k;EL.array=EL1.array;}13(4)EL→id[E{EL.place=E.place;EL.dim=1;EL.array=entry();}(5)EL→EL1,E(3)V→EL](2)V→id{V.place=entry();V.offset=null;}(1)A→V=E {if（V.offset==null） emit(V.place'='E.place); elseemit(V.place'['V.offset']''='E.place); }

Vk-1*dk

Vk=Vk-1*dk+ik屬性CONSPART[VARPART]=XCONSPART=a-c*wVARPART=v*wV1=i1<3>語義規(guī)則v1=i1

vj=vj-1*dj+ij14(6)E→E1+E2 {T=newtemp();E.place=T; emit(T'='E1.place'+'E2.place); }(7)E→(E1){E.place=E1.place;}(8)E→V{if（V.offset==null）E.place=V.place; else{T=newtemp();E.place=T; emit(T'='V.place'['V.offset']')； }}T=CONSPART[VARPART]<3>語義規(guī)則15例4.38設數(shù)組聲明：arr:array[10,20]ofint，w=4，

對賦值句arr[i+x,j+y]=m+n的翻譯過程和結果如下。A→V=E(1)V→id (2)|EL](3)EL→id[E(4)|EL,E(5)E→E+E(6)|(E)(7)|V (8)<4>分析舉例注釋分析樹:AV5E9EL2]EL1E6,E7E8+arrE3[E4E5+E1E2+V1iV2XV3jV4yV6mV7n=16產(chǎn)生式 屬性計算結果 中間代碼V1→i V1.place=i,V1.offset=nullE1→V1 E1.place=V1.place=iV2→x V2.place=x,V2.offset=nullE2→V2 E2.place=V2.place=xE3→E1+E2 E3.place=t1 t1=i+xEL1→arr[E3 EL1.place=t1,EL1.dim=1 EL1.array=arrE6→E4+E5 E6.place=t2 t2=j+yEL2→EL1,E6 EL2.array=arr,EL2.dim=2 t3=t1*20 EL2.place=t3,d2=20 t3=t3+t2V5→EL2] V5.place=t4,V5.offset=t5 t4=arr-84 t5=t3*4E9→E7+E8 E9.place=t6 t6=m+nA→V5=E9 t4[t5]=t6<4>分析舉例主要分析步驟17布爾表達式的應用：①

邏輯運算，如：x=aorb②

控制語句的控制條件，如:

if(C){...}，while（C）{...}等三種表達式的關系(文法約定優(yōu)先級與結合性)：4.8.1布爾表達式的作用與結構4.8布爾表達式RE→RErelopRE|(RE)|EE→EopE|-E|(E)|id|numBE→BEorBE|BEandBE|notBE|(BE)|RE|true|false(and)18abcxyz

例如：

a*b<candx>yornotz等價于：思考：后綴式？簡化的布爾表達式文法：or(*)(<)(>)(not)布爾運算的優(yōu)先級與結合性：4.8布爾表達式E→EorE|EandE|notE|(E)|idrelopid|id|true|falseG4.12優(yōu)先級：not>and>or結合性：and,or為左結合，not為右結合19可以用1表示true，用0表示false。not、and、or與-(一元)、*、+

對應看。例2：

a<b

的三地址碼序列：(101)ifa<b

goto104(102)t5=0(103)goto105(104)t5=1例1：

AorBandnotC

的三地址碼序列：t1=notCt2=Bandt1t3=Aort2<1>數(shù)值表示的直接計算4.8.2布爾表達式的計算方法對于關系運算表達式的計算，如a<b，按模板翻譯成三地址碼序列。(i)ifa

relop

bgotoi+3(i+1)t1=0(i+2)gotoi+2+2(i+3)t1=120

短路計算以if-then-else的形式解釋布爾表達式，具體控制邏輯如下：例：對布爾表達式AorBandnotC采用短路計算，則等價于下述解釋：ifA then trueelse 對比直接計算：t1=notCt2=Bandt1t3=Aort2or出口and出口if Bthenelse falseifCthenfalseelsetrue(4.8)XorYXandYnotX4.8.2布爾表達式的計算方法<2>邏輯表示的短路計算ifXthentrueelseYifXthenYelsefalseifXthenfalseelsetrue21有必要短路計算嗎？考慮C語句：

while(ptr&&ptr->data==x)...4.8.2布爾表達式的計算方法直接計算：(9)t3=t1andt2(1)ifptr!=0goto4(2)t1=0(3)goto5(4)t1=1(5)ifptr->data==xgoto8(6)t2=0(7)goto9(8)t2=1(i)ifarelopb

gotoi+3(i+1)t1=0(i+2)gotoi+2+2(i+3)t1=122有必要短路計算嗎？考慮C語句：

while(ptr&&ptr->data==x)...(9)t3=t1andt2ifptr!=0thenifptr->data==xthentrueelsefalseelsefalse4.8.2布爾表達式的計算方法(1)ifptr!=0goto4(2)t1=0(3)goto5(4)t1=1直接計算：(5)ifptr->data==xgoto8(6)t2=0(7)goto9(8)t2=1短路計算：XandYifXthenYelsefalse采用短路計算：回避了指針為空時對ptr->data的訪問，

從而避免了程序運行時錯誤。23是否短路計算，可以在語法or語義方面規(guī)定。如Ada語言提供兩組運算：非短路計算： and， or短路計算：andthen，

orelse4.8.2布爾表達式的計算方法有必要短路計算嗎？考慮C語句：

while(ptr&&ptr->data==x)...于是上述語句可以改寫為：

whileptr/=nullandthenptr^.data=xloop...若程序設計語言沒有規(guī)定，則由編譯器決定

采用短路計算：回避了指針為空時對ptr->data的訪問，

從而避免了程序運行時錯誤。24全局量nextstat：下一可用的三地址碼序號，調用emit后遞增１。語義規(guī)則：(1)E→E1orE2{E.place=newtemp(); emit(E.place'='E1.place'or'E2.place);}(2)|E1andE2{E.place=newtemp(); emit(E.place'='E1.place'and'E2.place);}(3)|notE1{E.place=newtemp(); emit(E.place'=''not'E1.place);}(4)|(E1){E.place=E1.place;}(5)|id1relopid2<下頁>(6)|id{E.place=entry();}(7)|true{E.place=newtemp;emit(E.place'=''1');}(8)|false{E.place=newtemp;emit(E.place'=''0');}4.8.3直接計算的語法制導翻譯25(5)E→id1relopid2{E.place=newtemp();emit('if'id1.placerelop.opid2.place'goto'nextstat+3);emit(E.place'=''0');emit('goto'nextstat+2);emit(E.place'=''1');}4.8.3直接計算的語法制導翻譯(i)ifarelopb

gotoi+3(i+1)t1=0(i+2)gotoi+2+2(i+3)t1=14.8.3直接計算的語法制導翻譯26例4.39布爾表達式a<borc<dande<f的直接計算的翻譯序號產(chǎn)生式(1)E1→a<b(2)E2→c<d

(3)E3→e<f

三地址碼(1)ifa<bgoto4(2)t1=0(3)goto5(4)t1=1(5)ifc<dgoto8(6)t2=0(7)goto9(8)t2=1(9)ife<fgoto12(10)t3=0(11)goto13(12)t3=1E→id1relopid2{E.place=newtemp();emit('if'id1.placerelop.opid2.place'goto'nextstat+3);emit(E.place'=''0');emit('goto'nextstat+2);emit(E.place'=''1');}nextstat=5nextstat=9nextstat=13nextstat:初值１4.8.3直接計算的語法制導翻譯E→E1andE2{E.place=newtemp();emit(E.place'='E1.place'and'E2.place);}27序號產(chǎn)生式(1)E1→a<b(2)E2→c<d

(3)E3→e<f

(4)E4→E2andE3三地址碼(1)ifa<bgoto4(2)t1=0(3)goto5(4)t1=1(5)ifc<dgoto8(6)t2=0(7)goto9(8)t2=1(9)ife<fgoto12(10)t3=0(11)goto13(12)t3=1(13)t4=t2andt3nextstat=13nextstat=14例4.39布爾表達式a<borc<dande<f的直接計算的翻譯nextstat:初值１4.8.3直接計算的語法制導翻譯nextstat=15E→E1orE2{E.place=newtemp();emit(E.place'='E1.place'or'E2.place);}28序號產(chǎn)生式(1)E1→a<b(2)E2→c<d

(3)E3→e<f

(4)E4→E2andE3(5)E5→E1orE4三地址碼(1)ifa<bgoto4(2)t1=0(3)goto5(4)t1=1(5)ifc<dgoto8(6)t2=0(7)goto9(8)t2=1(9)ife<fgoto12(10)t3=0(11)goto13(12)t3=1(13)t4=t2andt3(14)t5=t1ort4nextstat=14例4.39布爾表達式a<borc<dande<f的直接計算的翻譯nextstat:初值１29①.true：表達式的真出口，表達式為真時的轉向。②.false：表達式的假出口，表達式為假時的轉向。③newlable()：產(chǎn)生并返回一個新的標號。ifAthengotoLTgotoLFLT:…LF:…A.trueA.false布爾表達式A翻譯4.8.4短路計算的語法制導定義短路計算的中間代碼(實質)：

①布爾運算：用跳轉指令實現(xiàn)(控制邏輯);②表達式的值：用跳轉到的目標位置表示。屬性與函數(shù)：簡單的例子（此處忽略A自身的計算）30考慮布爾表達式E→E1opE2，應該有下述代碼序列：根據(jù)短路計算的邏輯（4.8），表達式真/假出口存在關系：[注1]計算表達式E1和E2的中間代碼；

計算E2之前的標號

E1.false，表示

當E1為假時，計算表達式E2。4.8.4短路計算的語法制導定義若op是

or

運算:

E1.codeE1.false: E2.code若op

是or

運算:E1.true=E2.true=E.true

E2.false=E.false314.8.4短路計算的語法制導定義考慮布爾表達式E→E1opE2，應該有下述代碼序列：根據(jù)短路計算的邏輯（4.8），表達式真/假出口存在關系：[注2]計算表達式E1和E2的中間代碼；

計算E2之前的標號

E1.true，表示

當E1為真時，計算表達式E2。若op是

or

運算:

E1.codeE1.false: E2.code若op

是and

運算:

E1.codeE1.true: E2.code若op

是or

運算:E1.true=E2.true=E.true

E2.false=E.false若op

是and

運算:E1.false=E2.false=E.falseE2.true=E.true語義制導定義：32(1)E→E1orE2 {E1.true=E.true;E1.false=newlabel(); E2.true=E.true;E2.false=E.false; E.code=E1.code||emit(E1.false':')||E2.code;}(2)|E1andE2 {E1.false=E.false;E1.true=newlabel();E2.false=E.false;E2.true=E.true;E.code=E1.code||emit(E1.true':')||E2.code;}函數(shù)

newlable：產(chǎn)生一個新

標號，如L1,L2,…。E1.true=E2.true=E.true

E2.false=E.falseE1.false=E2.false=E.falseE2.true=E.true若op是

or

運算:

E1.codeE1.false: E2.code若op

是and

運算:

E1.codeE1.true: E2.code語義制導定義：33(1)E→E1orE2 {E1.true=E.true;E1.false=newlabel(); E2.true=E.true;E2.false=E.false; E.code=E1.code||emit(E1.false':')||E2.code;}(2)|E1andE2 {E1.false=E.false;E1.true=newlabel();E2.false=E.false;E2.true=E.true;E.code=E1.code||emit(E1.true':')||E2.code;}函數(shù)

newlable：產(chǎn)生一個新

標號，如L1,L2,…。(3)|notE1{E1.false=E.true;E1.true=E.false;E.code=E1.code;}(4)|(E1){E1.false=E.false;E1.true=E.true;E.code=E1.code;}語義制導定義：34函數(shù)

newlable：產(chǎn)生一個新

標號，如L1,L2,…。|id1relopid2

{E.code=emit ('if'id1.placerelop.opid2.place'goto'E.true)||emit('goto'E.false);}翻譯arelopb的模板：ifarepopbgotoE.truegotoE.falseE→…語義制導定義：35函數(shù)

newlable：產(chǎn)生一個新

標號，如L1,L2,…。(6)|id{E.code=emit('if'id.place'goto'E.true)||emit('goto'E.false);}(7)|true{E.code=emit('goto'E.true);}(8)|false{E.code=emit('goto'E.false);}|id1relopid2

{E.code=emit ('if'id1.placerelop.opid2.place'goto'E.true)||emit('goto'E.false);}E→…36ifa<bgotoE1.tgotoE1.fifc<dgotoE2.tgotoE2.fife<fgotoE3.tgotoE3.fE→id1relopid2

{E.code=emit('if'id1.placerelop.opid2.place'goto'E.true)||emit('goto'E.false);}例4.40再考慮布爾表達式

a<borc<dande<f的短路計算：注釋分析樹：三地址碼序列：4.8.4短路計算的語法制導定義.t=LT.f=LF37ifa<bgotoE1.tgotoE1.fifc<dgotoE2.tgotoE2.fife<fgotoE3.tgotoE3.f例4.40再考慮布爾表達式

a<borc<dande<f的短路計算：注釋分析樹：三地址碼序列：4.8.4短路計算的語法制導定義E4→E2andE3{E2.false=E4.false;E2.true=newlabel();E3.false=E4.false;E3.true=E4.true;E4.code=E2.code||emit(E2.true':')||E3.code;}.t=LT.f=LF.t=L1L1L1:38ifa<bgotoE1.tgotoE1.fifc<dgotoE2.tgotoE2.fife<fgotoE3.tgotoE3.f例4.40再考慮布爾表達式

a<borc<dande<f的短路計算：注釋分析樹：三地址碼序列：4.8.4短路計算的語法制導定義.t=LT.f=LF.t=L1L1L1:E5→E1orE4{E1.true=E5.true;E1.false=newlabel();E4.true=E5.true;E4.false=E5.false;E5.code=E1.code||emit(E1.false':')||E4.code;}.f=L2.t=LT.t=LT.f=LFLTL2L2:39ifa<bgotoE1.tgotoE1.fifc<dgotoE2.tgotoE2.fife<fgotoE3.tgotoE3.f例4.40再考慮布爾表達式

a<borc<dande<f的短路計算：注釋分析樹：三地址碼序列：4.8.4短路計算的語法制導定義.t=LT.f=LF.t=L1L1L1:.f=L2.t=LT.t=LT.f=LFLTL2L2:E4→E2andE3{E2.false=E4.false;E2.true=newlabel;E3.false=E4.false;E3.true=E4.true;E4.code=E2.code||emit(E2.true':')||E3.code;}.f=LF.t=LT.f=LFLFLFLT4.8.5拉鏈與回填40①如何實現(xiàn)表達式的真、假出口；②如何在語法分析的同時正確生成(所有轉向均確定的)三地址碼序列?；舅枷耄寒斎刂反a中的轉向不確定時，將所有轉向同一目標位置的三地址碼拉成一個鏈；一旦所轉向的目標位置被確定，則沿此鏈對所有三地址碼回填此位置。語法制導定義未解決的問題（需要翻譯方案解決）：解決方法：拉鏈與回填即：設計一種可行的翻譯方案，僅對分析樹進行一次遍歷

即可生成所需的中間代碼序列。4.8.5拉鏈與回填411.屬性.tc：真出口鏈，鏈接所有轉向同一真出口的三地址碼。2.屬性.fc：假出口鏈，鏈接所有轉向同一假出口的三地址碼。<1>短路計算的翻譯方案——3.函數(shù)mkchain(i)：為序號為i的三地址碼構造一個新鏈，并返回指向該鏈的指針。4.函數(shù)merge(P1，P2)：合并鏈P1和P2，令P2為合并后

的鏈頭，并返回鏈頭指針。5.過程backpatch(P，i)：將

P鏈中所有三地址碼的轉向目標位置用i回填。新增屬性與過程：4.8.5拉鏈與回填42例4.41

設有三地址碼序列：①P1=mkchain(i)：③P2=merge(P1,P2)：④backpatch(P2,k):(i)gotok...(j)gotok

...(k)②P2=mkchain(j)：(i)goto-...(j)goto-...(k)<1>短路計算的翻譯方案——新增屬性與過程：4.8.5拉鏈與回填43E→EorE|EandE|notE|(E)|idrelopid|id|true|false文法G4.12E→Eor

M

E|Eand

M

E|notE|(E)|idrelopid|id|true|falseM→ε文法G4.13E1.codeE1.false:E2.code思考E1orE2

的翻譯：在LR分析過程中：(1)何時得知E1.false

的具體值？(2)何時回填E1.fc？<2>短路計算的翻譯方案——修改文法（Why?）44M的屬性.stat：記錄當前第一個可用的三地址碼序號。(1)M→ε(2)E→E1orME2{M.stat=nextstat;}{backpatch(E1.fc,M.stat);E.tc=merge(E1.tc,E2.tc);E.fc=E2.fc;}or運算的真假出口關系:E1.true=E2.true=E.true

E2.false=E.false4.8.5拉鏈與回填E1.codeE1.false:E2.code思考E1orE2

的翻譯：<3>短路計算翻譯的語義規(guī)則45M的屬性.stat：記錄當前第一個可用的三地址碼序號。(1)M→ε(2)E→E1orME2{M.stat=nextstat;}{backpatch(E1.fc,M.stat);E.tc=merge(E1.tc,E2.tc);E.fc=E2.fc;}4.8.5拉鏈與回填<3>短路計算翻譯的語義規(guī)則(3)E→E1andME2(4)E→notE1(5)E→（E1）

{E.tc=E1.fc;E.fc=E1.tc;}{E.tc=E1.tc;E.fc=E1.fc;}(將or產(chǎn)生式中的.tc與.fc交換即得)464.8.5拉鏈與回填<3>短路計算翻譯的語義規(guī)則(7)E→id{E.tc=mkchain(nextstat); E.fc=mkchain(nextstat+1); emit('if'id.place'goto-'); emit('goto-');}(8)E→true{E.tc=mkchain(nextstat);emit('goto-');}(9)E→false{E.fc=mkchain(nextstat);emit('goto-');}(6)E→id1relopid2{ emit('if'id1.placerelop.opid2.place'goto-'); emit('goto-');}E.tc=mkchain(nextstat);E.fc=mkchain(nextstat+1);47再考慮布爾表達式a<borc<dande<f(6)E→id1relopid2{E.tc=mkchain(nextstat);E.fc=mkchain(nextstat+1);emit('if'id1.placerelop.opid2.place'goto-');emit('goto-');}設nextstat初始為1(1)ifa<bgoto-(2)goto-(1)ifa<bgoto-(2)goto-48再考慮布爾表達式a<borc<dande<f設nextstat初始為1(1)M→ε{M.stat=nextstat;}49再考慮布爾表達式a<borc<dande<f設nextstat初始為1(6)E→id1relopid2{E.tc=mkchain(nextstat);E.fc=mkchain(nextstat+1);emit('if'id1.placerelop.opid2.place'goto-');emit('goto-');}(3)ifc<dgoto-(4)goto-(1)ifa<bgoto-(2)goto-50再考慮布爾表達式a<borc<dande<f設nextstat初始為1(1)M→ε{M.stat=nextstat;}(3)ifc<dgoto-(4)goto-(1)ifa<bgoto-(2)goto-51再考慮布爾表達式a<borc<dande<f設nextstat初始為1(6)E→id1relopid2{E.tc=mkchain(nextstat);E.fc=mkchain(nextstat+1);emit('if'id1.placerelop.opid2.place'goto-');emit('goto-');}(5)ife<fgoto-(6)goto-(3)ifc<dgoto-(4)goto-(1)ifa<bgoto-(2)goto-(5)ife<fgoto-(6)goto-(3)ifc<dgoto-(4)goto-(1)ifa<bgoto-(2)goto-52再考慮布爾表達式a<borc<dande<f設nextstat初始為1E4→E2andM2E3

{backpatch(E2.tc,M2.stat);E4.fc=merge(E2.fc,E3.fc);E4.tc=E3.tc;}5(5)ife<fgoto-(6)goto-(3)ifc<dgoto-(4)goto-(1)ifa<bgoto-(2)goto-53再考慮布爾表達式a<borc<dande<f設nextstat初始為15E5→E1orM1E4

{backpatch(E1.fc,M1.stat);E5.tc=merge(E1.tc,E4.tc);E5.fc=E4.fc;}354序號產(chǎn)生式 三地址碼(1)E1→a<b(1)

ifa<bgoto- (2)goto

3

(2)M1→ε(3)E2→c<d(3)ifc<dgoto

5

(4)goto-(4)M2→ε(5)E3→e<f

(5)

ife<fgoto-

(6)goto-(6)E4→E2andM2E3(7)E5→E1orM1E4最終：E5.tc=(5,1)

E5.fc=(6,4)4.8.5拉鏈與回填再考慮布爾表達式a<borc<dande<f設nextstat初始為1對照:

ifa<bgoto

LTgoto

L2L2:ifc<dgoto

L1goto

LFL1:ife<fgotoLTgoto

LF

55①無條件轉移：gotoL（轉向標號L指示的位置）

exit、break（退出某個范圍）②條件轉移：

if

布爾表達式then

…

else

…

while

布爾表達式do{…}(本節(jié)僅討論前兩種語句的翻譯)4.9控制語句四類控制語句：③循環(huán)：

for_loop：有下界/上界/循環(huán)步長，或指定一個范圍(range-basedloop)④分支：

switch/case：根據(jù)不同的取值執(zhí)行不同的分支56S→id:S (1)//帶標號的語句

|gotoid (2)//goto語句

|if(E)thenS (3)//條件轉移語句|if(E)thenSelseS(4)|while(E)doS (5)|A (6)//賦值句

|{L} (7)//語句塊L→L;S (8)//語句序列

|S (9)條件轉移/無條件轉移語句基于的文法:4.9控制語句G4.1457作用域的規(guī)定：遇到標號定義，則將有關信息填寫進符號表；遇到標號引用，則查詢符號表中的標號信息，并據(jù)之生成正確轉向的三地址碼。但若標號引用先于標號定義，則要借助符號表進行拉鏈與回填。4.9.1標號與無條件轉移S→id:S|gotoid定義出現(xiàn)引用出現(xiàn)在一定的作用域內，一個標號僅允許定義一次，但可以引用多次。符號表條目(記錄標號信息)：標記的位置轉向的標號稱謂無條件轉移的構成要素58在符號表中，為標號條目設置以下信息域：type：標識符的種類:如'標號'、'變量'、'未知'…def：id代表的實體是否已定義:'未定義'、'已定義'。addr：遇到標號定義時，保存此標號對應三地址碼的序號；

遇到標號定義前，保存鏈頭。定義過程：fill(entry(),t,d,n)，將t、d、n分別

填寫到符號表中標識符id的.type、.def、.addr域中。第1次entry(a)引用在先標號定義4.9.1標號與無條件轉移4.9.1標號與無條件轉移59(1)S→gotoid{if(entry().type=='未知')//id第一次出現(xiàn)，是標號

{

}elseif(entry().type=='標號')//已出現(xiàn)過,且是標號{

}elseerror；

//

id已出現(xiàn)過，但不是標號，出錯}第1次entry(a)引用在先標號定義fill(entry(),'標號','未定義',

nextstat);emit('goto–');//尚未定義，

拉鏈if(entry().def=='未定義')//尚未定義，

拉鏈{

}else{}fill(entry(),'標號','未定義',nextstat);emit('goto–');emit('goto'entry(id).addr);

//轉向明確，不拉鏈--翻譯方案4.9.1標號與無條件轉移60--翻譯方案(2)S→LABS1{

略（根據(jù)S1語句的種類，進行相應的翻譯）}(3)LAB→id':'{見下頁}(1)S→gotoid{if(entry().type=='未知')//id第一次出現(xiàn)，是標號

{

}elseif(entry().type=='標號')//已出現(xiàn)過,且是標號{

}elseerror；

//

id已出現(xiàn)過，但不是標號，出錯}fill(entry(),'標號','未定義',

nextstat);emit('goto–');//尚未定義，

拉鏈if(entry().def=='未定義')//尚未定義，

拉鏈{

}else{}fill(entry(),'標號','未定義',nextstat);emit('goto–');emit('goto'entry(id).addr);

//轉向明確，不拉鏈4.9.1標號與無條件轉移61(3)LAB→id':'{if(entry().type=='未知')//id第一次出現(xiàn)，是標號

{}

elseelseerror;//其它情況均出錯}第1次entry(a)引用在先標號定義if(

entry().type=='標號'andentry().def=='未定義')//定義前有引用{}q=entry().addr;

//取出鏈頭，下面回填fill(entry(),

'標號','已定義',nextstat);backpatch(q,nextstat);--翻譯方案前1頁fill(entry(),'標號','已定義',

nextstat);4.9.1標號與無條件轉移(3)LAB→id':'{if(entry().type=='未知')//id第一次出現(xiàn)，是標號

{}

elseelseerror;//其它情況均出錯}fill(entry(),'標號','已定義',

nextstat);62L1:x=a+b;gotoL1;---和-------

gotoL2;L2:x=a+b;gotoL2;結果：(1)t1=a+b(2)x=t1(3)goto1(1)goto-(2)t1=a+b(3)x=t1(4)goto22前2頁研習教材中的例4.43、例4.44if(

entry().type=='標號'andentry().def=='未定義')//定義前有引用{}q=entry().addr;

//取出鏈頭，下面回填fill(entry(),

'標號','已定義',nextstat);backpatch(q,nextstat);--翻譯方案鏈表頭63

E.codeE.true:S1.codeE.false:...(3)S→if(E)thenS1{}已有屬性：

.true.false.codeS.code=E.code||emit(E.true':')||S1.code;S→if(E)thenS (3)|if(E)thenSelseS(4)|while(E)doS (5)三地址碼序列結構4.9.2條件轉移屬性.begin(入口)：語句S

開始的三地址碼序號.屬性.next(出口)：語句S

結束后的三地址碼序號.E.true=newlabel();E.false=S.next;S1.next=S.next;<1>語法制導定義64E.codeE.true:S1.code

gotoS.nextE.false:S2.codeS.next:...(4)S→if(E)thenS1elseS2{ }S.code=E.code