程序設計語言編譯原理(第三版)第7章.ppt
《程序設計語言編譯原理(第三版)第7章.ppt》由會員分享,可在線閱讀,更多相關《程序設計語言編譯原理(第三版)第7章.ppt(67頁珍藏版)》請在裝配圖網(wǎng)上搜索。
1,第七章語義分析和中間代碼產(chǎn)生,一般情況下,在詞法分析程序和語法分析程序對源程序的語法結構進行分析之后,要么,由語法分析程序直接調(diào)用相應的語義子程序進行語義處理;要么,首先生成語法樹或該結構的某種表示,再進行語義處理。,2,語義處理分兩步:1.靜態(tài)語義分析,即驗證語法結構合法的程序是否真正有意義。2.若靜態(tài)語義正確,語義處理則要執(zhí)行真正的翻譯。即要么生成程序的一種中間表示形式(中間代碼),要么生成實際的目標代碼。,靜態(tài)語義檢查包括:(1)類型檢查;(2)控制流檢查;(3)一致性檢查;(4)相關名字檢查。,第七章語義分析和中間代碼產(chǎn)生,3,中間代碼:即中間語言,獨立于機器的,復雜性介于源語言和機器語言之間的一種表示形式。,采用中間語言的好處:,第七章語義分析和中間代碼產(chǎn)生,(1)便于進行與機器無關的代碼優(yōu)化工作;,(2)使編譯程序改變目標機更容易;,(3)使編譯程序的結構在邏輯上更為簡單明確。,4,7.1中間語言7.2說明語句7.3賦值語句的翻譯7.4布爾表達式的翻譯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+yza0(8+z)3,ab+cd+*,xy+za08z+3,8,二、圖表示法,1.DAG(無循環(huán)有向圖)與抽象語法樹對比相同點:對表達式中的每個子表達式,它們都有一個結點,一個內(nèi)部結點代表一個操作符,它的孩子代表操作數(shù);不同點:在一個DAG中代表公共子表達式的結點具有多個父結點,而在一棵抽象語法樹中公共子表達式被表示為重復的子樹。,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.三地址代碼:下面一般形式的語句構成的序列:x:=yopzT1:=y*z,T2:=x+T1,稱為三地址代碼的原因:每條語句通常包含三個地址,兩個用來表示操作數(shù),一個用來存放結果。,7.中間語言,具體實現(xiàn):用記錄表示,其中包含運算符和操作數(shù)的域。,x,y,z:名字,常數(shù),編譯時產(chǎn)生的臨時變量op:運算符號(如定點運算符,浮點運算符,邏輯運算符等),13,2.四元式:帶有四個域的記錄結構,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)對每個局部名字,都需在符號表中建立相應的表項,并填入有關的信息如類型、在存儲器中的相對地址等。,19,一、過程中的說明語句,1.產(chǎn)生“說明語句”的文法:,PDDD;DDid:TTintegerTrealTarraynumofT1TT1,7.2說明語句,20,2.處理方式:處理第一條說明語句之前,先置offset為0,以后每次遇到一個新的名字,則:(1)將該名字填入符號表中,(2)置相對地址為當前offset之值,(3)使offset加上該名字所表示的數(shù)據(jù)對象的域寬。,7.2說明語句,21,3.相應的翻譯模式:,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名字的域寬(即該類型名字所占用的存儲單元個數(shù)),23,二、保留作用域信息,1.嵌套過程中的說明語句,7.2說明語句,(1)相應的文法: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:存放指向符號表的指針,棧頂為指向當前正在處理過程的符號表指針.offset:存放變量在數(shù)據(jù)區(qū)中的相對地址,棧頂為當前正在處理過程的下一個變量的相對地址。,(3)top():取當前棧頂元素push(a,B):將a推進B棧棧頂pop(A):將A棧棧頂元素出棧,7.2說明語句,28,7.3賦值語句的翻譯,一、簡單算術表達式及賦值語句,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)檢查符號表中是否存在相應此名字的入口nil:返回一個該表項的指針=nil:未找到emit()將生成的三地址語句發(fā)送到輸出文件中E.place存放E值的名字newtemp產(chǎn)生“臨時變量”,7.3賦值語句的翻譯,30,3.例題:寫出下列代碼段中表達式的翻譯制導過程及其所產(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)生式的原因:使我們在整個下標表達式串Elist的翻譯過程中隨時都能知道符號表中相應于數(shù)組名字id的符號表入口,從而隨時能了解登記在符號表中的有關數(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簡單名字,則指向符號表中相應此名字表項的指針,即此名字的符號表入口.L數(shù)組引用,則L.place存放臨時變量的值.(常量部分的值),7.3賦值語句的翻譯,38,7.3賦值語句的翻譯,B.說明:Elist.array用來記錄指向符號表中相應數(shù)組名字表項的指針數(shù)組變量的符號表入口Elist.place表示臨時變量,用來臨時存放由Elist中的下標表達式計算出的值。Elist.ndim記錄Elist中的下標表達式的個數(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,設w=4,x:=Ay,zx:=Ay,z其相應的三地址語句序列如下:(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布爾表達式的翻譯,前言:,2.布爾表達式的組成及形式組成:布爾運算符號、布爾變量、關系表達式and,or,not(,)形式:E1relopE2,1.布爾表達式的兩個基本作用(1)用來計算邏輯值(2)用作控制流語句的條件表達式,44,7.4布爾表達式的翻譯,3.產(chǎn)生布爾表達式的文法:EEorEEEandEEnotEE(E)EidrelopidEid,45,一、數(shù)值表示法,1.計算布爾表達式值的兩種方法:,7.4布爾表達式的翻譯,(1)逐步計算(與算術表達式計算類似)例:1or(not0and0)or0=1or(1and0)or0=1or0or0=1or0=1,(2)采取某種優(yōu)化措施AorBifAthenTelseBAandBifAthenBelseFnotAifAthenFelseT,46,2.采取“逐步計算法”計算布爾表達式,7.4布爾表達式的翻譯,(2)關系式abifabthen1else0,分析:(1)布爾式aorbandnotc,T1:=notcT2:=bandT1T3:=aorT2,100:ifabgoto103101:T:=0102:goto104103:T:=1104:,47,3.布爾表達式“逐步計算法”的翻譯模式:Emit():過程,將產(chǎn)生的三地址代碼送到輸出文件中.Nextstat:給出輸出序列中下一條三地址語句的地址索引,每產(chǎn)生一條三地址語句后,過程emit將nextstat加1.,7.4布爾表達式的翻譯,48,關于布爾表達式的數(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.舉例:aborcdandef,7.4布爾表達式的翻譯,100:ifabgoto103101:T1:=0102:goto104103:T1:=1,104:ifcdgoto107105:T2:=0106:goto108107:T2:=1,108:ifecorbcgotoL2gotoL1L1:ifbdgotoL2gotoL3L2:關于S1的三地址代碼gotoLnextL3:關于S2的三地址代碼Lnext:,7.4布爾表達式的翻譯,55,3.產(chǎn)生布爾表達式三地址代碼的語義規(guī)則課本188頁表7.7,注意:利用表7.7中的語義規(guī)則翻譯的最容易方法是經(jīng)過兩遍掃描。(1)為給定的輸入串構造一顆語法樹;(2)對語法樹進行深度優(yōu)先遍歷,進行語義規(guī)則中規(guī)定的翻譯。,56,4.實現(xiàn)一遍掃描翻譯(1)三地址代碼表示四元式(jnz,a,p)ifagotop(jrop,x,y,p)ifxropygotop(j,p)gotop,(2)一遍掃描的主要問題:當生成某些轉移語句時我們可能還不知道該語句將要轉移到的標號究竟是什么?,問題的解決:在生成形式分支的跳轉指令時暫時不確定跳轉目標,而建立一個鏈表,把轉向這個目標的跳轉指令的標號鍵入這個鏈表。一旦目標確定之后再把它填入有關的跳轉指令中?;靥罴夹g,E.truelist-E.falselist:分別記錄布爾表達式E所對應的四元式中需回填“真”、“假”出口的四元式標號所構成的鏈表。,57,變量nextquad指向下一條將要產(chǎn)生但尚未形成的四元式的地址,初值為1,執(zhí)行一次emit后,自動加1.,函數(shù)makelist(i)將創(chuàng)建一個僅含i的新鏈表,其中i是四元式數(shù)組的一個下標,函數(shù)返回指向這個鏈的指針。,函數(shù)merge(p1,p2)把鏈首為p1和p2的兩條鏈合并為一,作為函數(shù)值,回送合并后的鏈首.,過程backpatch(p,t)功能是完成“回填”,把p所鏈接的每個四元式的第四個區(qū)段都填為t.,(3)變量和過程,58,(4)翻譯模式:課本190頁,7.4布爾表達式的翻譯,(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布爾表達式的翻譯,(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.4aborcdandef,7.4布爾表達式的翻譯,翻譯結果: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指向一個轉移指令鏈表S.nextlist指向一個轉移指令鏈表轉移指令鏈表:未填寫目標標號而在以后需要回填的轉移指令的鏈。,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的無條件跳轉指令。,(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按照上述的語義動作,加上前述關于賦值句和布爾表達式的翻譯法,采用一遍掃描翻譯語句.課本196頁While(ab)doif(cd)thenx:=y+z;,翻譯結果: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),- 配套講稿:
如PPT文件的首頁顯示word圖標,表示該PPT已包含配套word講稿。雙擊word圖標可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設計者僅對作品中獨創(chuàng)性部分享有著作權。
- 關 鍵 詞:
- 程序設計語言 編譯 原理 第三
裝配圖網(wǎng)所有資源均是用戶自行上傳分享,僅供網(wǎng)友學習交流,未經(jīng)上傳用戶書面授權,請勿作他用。
鏈接地址:http://ioszen.com/p-11546702.html