程序設(shè)計語言編譯原理(第三版)第7章.ppt

1,第七章語義分析和中間代碼產(chǎn)生,一般情況下，在詞法分析程序和語法分析程序?qū)υ闯绦虻恼Z法結(jié)構(gòu)進(jìn)行分析之后，要么，由語法分析程序直接調(diào)用相應(yīng)的語義子程序進(jìn)行語義處理；要么，首先生成語法樹或該結(jié)構(gòu)的某種表示，再進(jìn)行語義處理。,2,語義處理分兩步：1.靜態(tài)語義分析，即驗證語法結(jié)構(gòu)合法的程序是否真正有意義。2.若靜態(tài)語義正確，語義處理則要執(zhí)行真正的翻譯。即要么生成程序的一種中間表示形式（中間代碼），要么生成實際的目標(biāo)代碼。,靜態(tài)語義檢查包括：（1）類型檢查；（2）控制流檢查；（3）一致性檢查；（4）相關(guān)名字檢查。,第七章語義分析和中間代碼產(chǎn)生,3,中間代碼：即中間語言，獨立于機器的，復(fù)雜性介于源語言和機器語言之間的一種表示形式。,采用中間語言的好處：,第七章語義分析和中間代碼產(chǎn)生,（1）便于進(jìn)行與機器無關(guān)的代碼優(yōu)化工作；,（2）使編譯程序改變目標(biāo)機更容易；,（3）使編譯程序的結(jié)構(gòu)在邏輯上更為簡單明確。,4,7.1中間語言7.2說明語句7.3賦值語句的翻譯7.4布爾表達(dá)式的翻譯7.5控制語句的翻譯7.6過程調(diào)用的處理（略）7.7類型檢查（略）,第七章語義分析和中間代碼產(chǎn)生,5,7.中間語言,中間語言形式：后綴式三地址代碼圖表示法,6,一、后綴式逆波蘭式：,規(guī)則：,7.中間語言,(1)E常量變量：后綴式為E本身,(2)EE1opE2：E1E2op,(3)E(E1)：(E1),(4)EopE1：E1op,7,7.中間語言,例子：,a*(b+c),(a+b)*(c+d),abc+*,x+yza>0(8+z)>3,ab+cd+*,xy+za0>8z+3>,8,二、圖表示法,1.DAG(無循環(huán)有向圖)與抽象語法樹對比相同點:對表達(dá)式中的每個子表達(dá)式，它們都有一個結(jié)點，一個內(nèi)部結(jié)點代表一個操作符，它的孩子代表操作數(shù)；不同點:在一個DAG中代表公共子表達(dá)式的結(jié)點具有多個父結(jié)點，而在一棵抽象語法樹中公共子表達(dá)式被表示為重復(fù)的子樹。,7.中間語言,9,例子：如圖所示，為a+a*(b-c)+(b-c)*d的DAG,7.中間語言,10,2.抽象語法樹,例子：(1)a:=b*-c+b*-c的圖表示法,7.中間語言,11,(2)a:=b*-c+b*-c的抽象語法樹的兩種表示法,012345678910,7.中間語言,12,三、三地址代碼,1.三地址代碼:下面一般形式的語句構(gòu)成的序列:x:=yopzT1:=y*z,T2:=x+T1,稱為三地址代碼的原因:每條語句通常包含三個地址,兩個用來表示操作數(shù),一個用來存放結(jié)果。,7.中間語言,具體實現(xiàn):用記錄表示,其中包含運算符和操作數(shù)的域。,x,y,z:名字,常數(shù),編譯時產(chǎn)生的臨時變量op:運算符號(如定點運算符,浮點運算符,邏輯運算符等),13,2.四元式：帶有四個域的記錄結(jié)構(gòu),7.中間語言,(op，arg1，arg2，result),14,7.中間語言,例子:三地址語句a:=b*-c+b*-c的四元式表示,四元式表示,15,3.三元式：為了避免把臨時變量填入符號表,可通過計算該臨時變量值的語句的位置來引用該臨時變量。,7.中間語言,（op，arg1，arg2）,16,7.中間語言,例子:三地址語句a:=b*-c+b*-c的三元式表示,17,4.間接三元式：便于代碼優(yōu)化處理方法：間接碼表+三元式表,例:語句X:=(A+B)*C;Y:=D(A+B)的間接三元式表示如下所示:,三元式表,7.中間語言,18,7.2說明語句,編譯過程中,對“說明語句”要做的工作:,對一個過程或分程序的一系列說明語句,考察時:,(1)需要為局部于該過程的名字分配存儲空間;,(2)對每個局部名字,都需在符號表中建立相應(yīng)的表項,并填入有關(guān)的信息如類型、在存儲器中的相對地址等。,19,一、過程中的說明語句,1.產(chǎn)生“說明語句”的文法：,PDDD;DDid:TTintegerTrealTarraynumofT1TT1,7.2說明語句,20,2.處理方式：處理第一條說明語句之前，先置offset為0，以后每次遇到一個新的名字，則:(1)將該名字填入符號表中,(2)置相對地址為當(dāng)前offset之值，(3)使offset加上該名字所表示的數(shù)據(jù)對象的域?qū)挕?7.2說明語句,21,3.相應(yīng)的翻譯模式：,7.2說明語句,PDDD;DDid:TTintegerTrealTarraynumofT1TT1,offset:=0,enter(id.name,T.type,offset);offset:=offset+t.width,T.type:=integer;T.width:=4,T.type:=real;T.width:=8,T.type:=array(num.val,T1.type);T.width:=num.valT1.width,T.type:=pointer(T1.type);T.width:=4,22,說明:(1)offset:全程變量,代表變量在過程數(shù)據(jù)區(qū)中的相對地址,用來跟蹤下一個可用的相對地址的位置.,7.2說明語句,(2)enter(name,type,offset):把名字name符號表,并給出此名字的類型type及在過程數(shù)據(jù)區(qū)中的相對地址offset.,(3)綜合屬性:T.type名字的類型;T.width名字的域?qū)?即該類型名字所占用的存儲單元個數(shù)),23,二、保留作用域信息,1.嵌套過程中的說明語句,7.2說明語句,(1)相應(yīng)的文法:PDDD;D|id:T|procid;D;S,(2)程序舉例:,24,7.2說明語句,2.含嵌套說明的翻譯模式：,PMDaddwidth(top(tblptr),top(offset);pop(tblptr);pop(offset),Mt:=mktable(nil);push(t,tblptr);push(0,offset),DD1;D2,Dprocid;ND1;St:=top(tblptr);addwidth(t,top(offset);pop(tblptr);pop(offset);enterproc(top(tblptr),id.name,t),Nt:=mktable(top(tblptr);push(t,tblptr);push(0,offset),Did:Tenter(top(tblptr),id.name,T.type,top(offset);top(offset):=top(offset)+T.width,25,(1)語義規(guī)則中的操作:,7.2說明語句,2.含嵌套說明的翻譯模式：,Mktable(previous):創(chuàng)建一張新符號表,并返回指向新表的一個指針;,Enter(table,name,type,offset):在指針table指示的符號表中為名字name建立一個新頂,并把類型type、相對地址offset填入到該項中;,26,7.2說明語句,(1)語義規(guī)則中的操作:,Enterproc(table,name,newtable):在指針table指示的符號表中為名字name的過程建立一個新頂。參數(shù)newtable指向過程name的符號表。,Addwidth(table,width):在指針table指示的符號表表頭中記錄下該表中所有名字占用的總寬度;,27,(2)棧:tblptr:存放指向符號表的指針,棧頂為指向當(dāng)前正在處理過程的符號表指針.offset:存放變量在數(shù)據(jù)區(qū)中的相對地址,棧頂為當(dāng)前正在處理過程的下一個變量的相對地址。,(3)top():取當(dāng)前棧頂元素push(a,B):將a推進(jìn)B棧棧頂pop(A):將A棧棧頂元素出棧,7.2說明語句,28,7.3賦值語句的翻譯,一、簡單算術(shù)表達(dá)式及賦值語句,1.產(chǎn)生“賦值語句”三地址代碼的翻譯模式:,Sid:=Ep:=lookup(id.name);ifpnilthenemit(p:=E.place)elseerror,EE1+E2E.place:=newtemp;emit(E.place:=E1.place+E2.place),EE1*E2E.place:=newtemp;emit(E.place:=E1.place*E2.place),E-E1E.place:=newtemp;emit(E.place:=uminusE1.place),E(E1)E.place:=E1.place,Eidp:=lookup(id.name);ifpnilthenE.place:=pelseerror,29,2.說明:id.nameid所代表的名字本身lookup(id.name)檢查符號表中是否存在相應(yīng)此名字的入口nil:返回一個該表項的指針=nil:未找到emit()將生成的三地址語句發(fā)送到輸出文件中E.place存放E值的名字newtemp產(chǎn)生“臨時變量”,7.3賦值語句的翻譯,30,3.例題：寫出下列代碼段中表達(dá)式的翻譯制導(dǎo)過程及其所產(chǎn)生的四元式beginInteger：B、C、D、X;X:=-B*(C+D);end,符號表,四元式,7.3賦值語句的翻譯,31,已歸約串PLACE輸入串語義動作#X:=-B*(C+D)#XX:=-B*(C+D)#X:=X_-B*(C+D)#X:=-X_B*(C+D)#X:=-BX_B*(C+D)#X:=-EX_B*(C+D)#E.place:=p=#X:=E1X_T1*(C+D)#E1.place:=newtemp=T1;生成四元式(1)#X:=E*(CX_T1_C+D)#X:=E*(E1X_T1_C+D)#E1.place:=p=,32,已歸約串PLACE輸入串語義動作#X:=E*(E1+DX_T1_C_D)#X:=E*(E1+E2X_T1_C_D)#E2.place:=p=#X:=E*(E3X_T1_T2)#E3.place:=newtemp=T2;生成四元式(2)#X:=E*(E3)X_T1_T2_#X:=E*E4X_T1_T2#E4.place=E3.place=T2#X:=E5X_T3#E5.place=T3;生成四元式(3)#S#p:=lookup(X.name);生成四元式(4),33,二、數(shù)組元素的引用,1.數(shù)組元素在存儲器中的存放:,7.3賦值語句的翻譯,一維數(shù)組地址:,二維數(shù)組地址:,Ai的地址=base+(i-low)*w=i*w+(base-low*w),Ai1,i2的地址=base+(i1low1)*n2+i1-low2)*w=(i1*n2)+i2)*w+(base(low1*n2)+low2)*w),34,7.3賦值語句的翻譯,1.數(shù)組元素在存儲器中的存放:,二、數(shù)組元素的引用,k維數(shù)組地址:,C=(low1n2+low2)n3+low3)nk+lowk)*w,變量部分：（(i1n2+i2）n3+i3）)nm+ime1=i1,em=em-1*nm+im,Ai1,i2,ik的地址=（i1n2+i2）n3+i3）)nk+ik)*w+base(low1n2+low2)n3+low3)nk+lowk)*w,35,改寫產(chǎn)生式的原因：使我們在整個下標(biāo)表達(dá)式串Elist的翻譯過程中隨時都能知道符號表中相應(yīng)于數(shù)組名字id的符號表入口,從而隨時能了解登記在符號表中的有關(guān)數(shù)組id的全部信息。,7.3賦值語句的翻譯,36,3.數(shù)組元素的翻譯模式：A.文法:(1)SL:=E(2)EE+E(3)E(E)(4)EL(5)LElist(6)Lid(7)ElistElist,E(8)ElistidE,7.3賦值語句的翻譯,37,B.說明:id.placeid的符號表入口.E.place存放E的名字/值.L.offset=null,L為簡單名字;null,L為數(shù)組元素引用,存放臨時變量的值.(變量部分的值)L.placeL簡單名字,則指向符號表中相應(yīng)此名字表項的指針,即此名字的符號表入口.L數(shù)組引用,則L.place存放臨時變量的值.(常量部分的值),7.3賦值語句的翻譯,38,7.3賦值語句的翻譯,B.說明:Elist.array用來記錄指向符號表中相應(yīng)數(shù)組名字表項的指針數(shù)組變量的符號表入口Elist.place表示臨時變量,用來臨時存放由Elist中的下標(biāo)表達(dá)式計算出的值。Elist.ndim記錄Elist中的下標(biāo)表達(dá)式的個數(shù),即維數(shù)。Limit(array,j)返回nj,即由array所指示的數(shù)組的第j維長度。,39,7.3賦值語句的翻譯,C.翻譯模式,SL:=EifL.offset=nullthenemit(L.place:=E.place)elseemit(L.placeL.offset:=E.place),(2)EE1+E2E.place:=newtemp;Emit(E.place:=E1.place+E2.place),(3)E(E1)E.place:=E1.place,40,7.3賦值語句的翻譯,(4)ELifL.offset=nullthenE.place:=L.placeelsebeginE.place:=newtemp;emit(E.place:=L.placeL.offset)end,(5)LElistL.place:=newtemp;emit(L.place:=Elist.array-C);L.offset:=newtemp;emit(L.offset:=w*Elist.place),(6)LidL.place:=id.place;L.offset:=null,41,7.3賦值語句的翻譯,(7)ElistElist1,Et:=newtemp;m:=Elist1.ndim+1;emit(t:=Elist1.place*limit(Elist1.array,m);emit(t:=t+t.place)Elist.array:=Elist1.array;Elist.place:=t;Elist.ndim:=m,(8)ElistidEElist.place:=E.place;Elist.ndim:=1;Elist.array:=id.place,42,4.舉例已知:A為1020的數(shù)組,即n1=10,n2=20,設(shè)w=4,x:=Ay,zx:=Ay,z其相應(yīng)的三地址語句序列如下:(1)T1:=y*20(2)T1:=T1+z(3)T2:=A-84(4)T3:=4*T1(5)T4:=T2T3(6)x:=T4,7.3賦值語句的翻譯,43,7.4布爾表達(dá)式的翻譯,前言:,2.布爾表達(dá)式的組成及形式組成:布爾運算符號、布爾變量、關(guān)系表達(dá)式and,or,not(,)形式:E1relopE2,1.布爾表達(dá)式的兩個基本作用(1)用來計算邏輯值(2)用作控制流語句的條件表達(dá)式,44,7.4布爾表達(dá)式的翻譯,3.產(chǎn)生布爾表達(dá)式的文法:EEorEEEandEEnotEE(E)EidrelopidEid,45,一、數(shù)值表示法,1.計算布爾表達(dá)式值的兩種方法：,7.4布爾表達(dá)式的翻譯,(1)逐步計算(與算術(shù)表達(dá)式計算類似)例：1or(not0and0)or0=1or(1and0)or0=1or0or0=1or0=1,(2)采取某種優(yōu)化措施AorBifAthenTelseBAandBifAthenBelseFnotAifAthenFelseT,46,2.采取“逐步計算法”計算布爾表達(dá)式,7.4布爾表達(dá)式的翻譯,(2)關(guān)系式a<bifa<bthen1else0,分析:(1)布爾式aorbandnotc,T1:=notcT2:=bandT1T3:=aorT2,100:ifa<bgoto103101:T:=0102:goto104103:T:=1104:,47,3.布爾表達(dá)式“逐步計算法”的翻譯模式：Emit():過程,將產(chǎn)生的三地址代碼送到輸出文件中.Nextstat:給出輸出序列中下一條三地址語句的地址索引,每產(chǎn)生一條三地址語句后,過程emit將nextstat加1.,7.4布爾表達(dá)式的翻譯,48,關(guān)于布爾表達(dá)式的數(shù)值表示法的翻譯模式:EE1orE2E.place:=newtemp;emit(E.place:=E1.placeorE2.place),EE1andE2E.place:=newtemp;emit(E.place:=E1.placeandE2.place),EnotE1E.place:=newtemp;emit(E.place:=notE1.place),E(E)E.place:=E1.place,Eid1relopid2E.place:=newtemp;emit(ifid1.placerelop.opid2.placegotonextstat+3);emit(E.place:=0);emit(gotonextstat+2);emit(E.place:=1);,EidE.place:=id.place,49,4.舉例：a<borc<dande<f,7.4布爾表達(dá)式的翻譯,100:ifa<bgoto103101:T1:=0102:goto104103:T1:=1,104:ifc<dgoto107105:T2:=0106:goto108107:T2:=1,108:ifecorbcgotoL2gotoL1L1:ifb<dgotoL2gotoL3L2:關(guān)于S1的三地址代碼gotoLnextL3:關(guān)于S2的三地址代碼Lnext:,7.4布爾表達(dá)式的翻譯,55,3.產(chǎn)生布爾表達(dá)式三地址代碼的語義規(guī)則課本188頁表7.7,注意：利用表7.7中的語義規(guī)則翻譯的最容易方法是經(jīng)過兩遍掃描。（1）為給定的輸入串構(gòu)造一顆語法樹；（2）對語法樹進(jìn)行深度優(yōu)先遍歷，進(jìn)行語義規(guī)則中規(guī)定的翻譯。,56,4.實現(xiàn)一遍掃描翻譯(1)三地址代碼表示四元式(jnz,a,p)ifagotop(jrop,x,y,p)ifxropygotop(j,p)gotop,(2)一遍掃描的主要問題：當(dāng)生成某些轉(zhuǎn)移語句時我們可能還不知道該語句將要轉(zhuǎn)移到的標(biāo)號究竟是什么？,問題的解決：在生成形式分支的跳轉(zhuǎn)指令時暫時不確定跳轉(zhuǎn)目標(biāo)，而建立一個鏈表，把轉(zhuǎn)向這個目標(biāo)的跳轉(zhuǎn)指令的標(biāo)號鍵入這個鏈表。一旦目標(biāo)確定之后再把它填入有關(guān)的跳轉(zhuǎn)指令中?；靥罴夹g(shù),E.truelist-E.falselist:分別記錄布爾表達(dá)式E所對應(yīng)的四元式中需回填“真”、“假”出口的四元式標(biāo)號所構(gòu)成的鏈表。,57,變量nextquad指向下一條將要產(chǎn)生但尚未形成的四元式的地址,初值為1,執(zhí)行一次emit后,自動加1.,函數(shù)makelist(i)將創(chuàng)建一個僅含i的新鏈表，其中i是四元式數(shù)組的一個下標(biāo)，函數(shù)返回指向這個鏈的指針。,函數(shù)merge(p1,p2)把鏈?zhǔn)诪閜1和p2的兩條鏈合并為一,作為函數(shù)值,回送合并后的鏈?zhǔn)?,過程backpatch(p,t)功能是完成“回填”,把p所鏈接的每個四元式的第四個區(qū)段都填為t.,（3）變量和過程,58,（4）翻譯模式:課本190頁,7.4布爾表達(dá)式的翻譯,(1)EE1orME2backpatch(E1.falselist,M.quad);E.truelist:=merge(E1.truelist,E2.truelist);E.falselist:=E2.falselist,(2)EE1andME2backpatch(E1.truelist,M.quad);E.truelist:=E2.truelist;E.falselist:=merge(E1.falselist,E2.falselist),(3)EnotE1E.truelist:=E1.falselist;E.falselist:=E1.truelist,(4)E(E1)E.truelist:=E1.truelist;E.falselist:=E1.falselist,59,(5)Eid1relopid2E.truelist:=makelist(nextquad);E.falselist:=makelist(nextquad+1);emit(jrelop.op,id1.place,id2.place,0);emit(j,-，-，0),7.4布爾表達(dá)式的翻譯,(6)EidE.truelist:=makelist(nextquad);E.falselist:=makelist(nextquad+1);emit(jnz,id.place,-,0);emit(j,-，-，0),(7)EM.quad:=nextquad;,60,5.例題：課本190頁例題7.4a<borc<dande<f,7.4布爾表達(dá)式的翻譯,翻譯結(jié)果：100(j<,a,b,0)101(j,-,-,102)102(j<,c,d,104)103(j,-,-,0)104(jL1:ifabgotoL2gotoLnextL2:ifcdgotoL3gotoL4L3:T1:=y+zX:=T1gotoL1L4:T2:=y-zX:=T2gotoL1Lnext,64,7.5控制語句的翻譯,2.一遍掃描產(chǎn)生中間代碼的翻譯模式課本195-196,SifEthenSifEthenSelseSwhileEdoSbeginLendALL;SS,分析：L.nextlist指向一個轉(zhuǎn)移指令鏈表S.nextlist指向一個轉(zhuǎn)移指令鏈表轉(zhuǎn)移指令鏈表：未填寫目標(biāo)標(biāo)號而在以后需要回填的轉(zhuǎn)移指令的鏈。,65,7.5控制語句的翻譯,（1）SifEthenM1S1NelseM2S2backpatch(E.truelist,M1.quad);backpatch(E.falselist,M2.quad);S.nextlist:=merge(S1.nextlist,N.nextlist,S2.nextlist)N：產(chǎn)生跳過S2的無條件跳轉(zhuǎn)指令。,（2）NN.nextlist:=makelist(nextquad);emit(j,)（3）MM.quad:=nextquad,(4)SifEthenMS1backpatch(E.truelist,M.quad);S.nextlist:=merge(E.falselist,S1.nextlist),66,7.5控制語句的翻譯,SwhileM1EdoM2S1backpatch(S1.nextlist,M1.quad);backpatch(E.truelist,M2.quad);S.nextlist:=E.falselistemit(j,，m1.quad),SbeginLendS.nextlist:=L.nextlist(7)SAS.nextlist:=makelist()(8)LL1;MSbackpatch(L1.nextlist,M.quad);L.nextlist:=S.nextlist(9)LSL.nextlist:=S.nextlist,67,7.5控制語句的翻譯,例7.6按照上述的語義動作，加上前述關(guān)于賦值句和布爾表達(dá)式的翻譯法，采用一遍掃描翻譯語句.課本196頁While(a<b)doif(c<d)thenx:=y+z；,翻譯結(jié)果：100(j<,a,b,102)101(j,-,-,0)False102(j<,c,d,104)103(j,-,-,100)(+,y,z,T)105(:=,T,-,x)106(j,-,-,100),