哈工大編譯原理5-2.ppt

1、1,第六章 中間代碼,辛明影,2,中間代碼生成 6.1 中間語言 6.2 常用語句的翻譯 6.2.1 說明語句 6.2.2 賦值語句 6.2.3 布爾表達(dá)式 6.2.4 過程語句,辛明影,3,序 “中間代碼生成”程 序的任務(wù)是：,方法：語法制導(dǎo)翻譯。,采用獨(dú)立于機(jī)器的中間代 碼的好處：,把經(jīng)過語法分析和語義分析而獲得的源程序中間表 示翻譯為中間代碼表示。,1. 便于編譯系統(tǒng)建立和編譯系統(tǒng)的移植；,2. 便于進(jìn)行獨(dú)立于機(jī)器的代碼優(yōu)化工作。,辛明影,4,6.1 中間語言 語法樹 后綴式 三地址代碼表示,6.1.1 圖表示法 語法樹，有向非循環(huán)圖和后綴式表示源程序的自然層次結(jié)構(gòu)，例如： a:=b *

2、 - c+b * -c,辛明影,5,=,a,+,*,b,c,-,(a)語法樹,*,-,c,b,辛明影,6,賦值語句： 中 綴式： a:=b*-c+b*-c 后綴式： a b c - * b c - * + =,辛明影,7,=,a,+,*,b,c,-,(b)dag(Directed Acyclic Graph),辛明影,8,6.1.2 三地址代碼 一般形式 x：y op z,相應(yīng)于圖6.1的樹和dag的三地址代碼,t1：-c t2：b*t1 t5：t2+t2 a：= t5 對于dag的代碼,t1 ： -c t2 ： b* t1 t3 ： -c t4 ： b* t3 t5 ： t2+t4 a ：

3、t5 對于語法樹的代碼,辛明影,9,（3）無條件轉(zhuǎn)移語句goto L;,（4）條件轉(zhuǎn)移語句 if x relop y goto L，關(guān)系運(yùn)算符號relop( ，=，= 等等）;,（2）賦值語句 x：op y ，op為一目算符，如一目減uminus、邏輯非not、移位算符及轉(zhuǎn)換算符;,（1）賦值語句 x：y op z，op為二目算術(shù)算符或邏輯算符;,6.1.3 三地址語句的種類,辛明影,10,（5）復(fù)制語句 x：y;,（8）地址和指針賦值 xy，x* y 和 * xy。,（7）索引賦值 x:=yi 及 xi :=y ;,（6）過程調(diào)用語句 param x 和 call p, n ; 過程返回語句

4、 return y;,辛明影,11,6.1.4 三地址代碼的具體實(shí)現(xiàn),1四元式 op, arg1, arg2, result 2三元式 op, arg1, arg2 3間接三元式 間接碼表+三元式表,四元式需要利用較多的臨時(shí)單元,四元式之 間 的聯(lián)系通過臨時(shí)變量實(shí)現(xiàn)。,中間代碼優(yōu)化處理時(shí)，四元式比三元式方便的多,間接三元式與四元式同樣方便，兩種實(shí)現(xiàn)方式需要的存儲空間大體相同。,辛明影,12,1、 x=y op z,常用三地址碼的四元式表示：,2、 x=op y,3、goto L,4、if x rop y goto L,5、x=y,6、parm x call p,n,（op , y , z ,

5、x),（op , y , , x),（j , , , L),(jrop ,x ,y , L),(= , y , ,x),(param, , ,x),(= , yi , ,x),(= D Did ：T Tinteger Treal,x:integer;y:real,一個(gè)過程中的所有說明語句作為一個(gè)類集來處理。,用一個(gè)全程變量Offset來記錄下 一個(gè)數(shù)據(jù)在符號表中的相對地址。,Tarraynumof T1,T T1,辛明影,18,PD,DD; D,Did ：T,Tinteger,Treal,Tarraynumof T1,T T1,offset：0D,enter（，T.type，of

6、fset）; offset:=offsetT.width,T.type ：=integer; T.width：= 4,T.type：real; T.width ：8,T.type:array（num.val, T1.type); T.width： num.val *T1.width,T.type:pointer（T1type）； T.width ：= 4,辛明影,19,Name type kind addr X Y ,real 簡單變量 4,int 簡單變量 0,x:integer;y:real,P,Offset=0,D,D,D,;,x,:,T,Y,:,T,Enter;offset,Enter

7、;offset,Offset=0,Offset=4,Offset=12,Int,real,T.type T.width,T.type T.width,T.type=int T.width=4,T.type=real T.width=8,辛明影,20,1 .問題的提出,二、 保留作用域信息,一般的語言中，標(biāo)識符的作用在程序正文中有一個(gè)確定的范圍。,因此，同一個(gè)標(biāo)識符在不同的程序正文中可能標(biāo)識不同的對象，,具有不同的性 質(zhì)，要求分配不同的存儲空間。,辛明影,21,于是提出下面的問題：,如何組織符號表，,使得同一個(gè)標(biāo)識符在不同的作用域中得到正確的引用而不產(chǎn)生混亂。,進(jìn)一步我們考慮一下具有嵌套定義的程

8、序結(jié)構(gòu),辛明影,22,2. 嵌套的程序結(jié)構(gòu),program sort（input，output）； var x, a ： array0.10 of integer； begin end.,procedure readarray； var i ： integer； begin end；,procedure quicksort（m，n ： integer）； var i ,k： integer； begin end；,procedure exchange； begin end；,procedure partition （y ，z ：integer ） var i，j ： integer； begi

9、n end;,辛明影,23,嵌套說明的文法：,PD DD; D Did ：T Dproc id;D;S .,此處的T用于產(chǎn)生類型； S用于產(chǎn)生語句,辛明影,24,嵌套說明的程序結(jié)構(gòu)首先要解決的問題是：非局部數(shù)據(jù)的訪問,綜合上述情況，對于程序結(jié)構(gòu)采用分程 序結(jié)構(gòu)的程序來說，要解決的問題是：,局部數(shù)據(jù)的訪問,2.非局部數(shù)據(jù)的訪問,解決方法:為每一個(gè)過程建立一個(gè)符號表,辛明影,25,具體翻譯時(shí)，每當(dāng)碰到過程說明Dproc id;D1;S時(shí),便創(chuàng)建一張符號表,并且把D1中的所有說明都填入此符號表中,新表中有一個(gè)指針，指向其直接外圍過程符號表,用于解決非局部數(shù)據(jù)的訪問,同時(shí)還要在直接外圍過程符號表中增加

10、一個(gè)指向該過程D1符號表的指針,過程名id 作為直接外圍過程的局部名字記錄在直接外圍過程符號表中；,辛明影,26,Nil header x a readarray exchange quicksort,sort,header i,header,readarray,exchange,Header I k patition,Header I j,quicksort,patition,嵌套過程的符號表,辛明影,27,翻譯時(shí)常用操作：,4. enterproc（table,name, newtable） 在外圍過程符號表中建立內(nèi)嵌過程的新表項(xiàng),1. mktable( previous）創(chuàng)建一張新符號表

11、,2. Enter(table，name，type，offset)插入表項(xiàng),3. addwidth（table，width）記錄總域?qū)?指向直接外層符號表,指向當(dāng)前過程符號表,指向直接外層符號表,指向內(nèi)層過程的符號表,指向當(dāng)前外層符號表,內(nèi)嵌過程名字,辛明影,28,Tblptr是一個(gè)棧，用于存放指向嵌套外層過程的符號表指針,Offset是一個(gè)棧，用于存放變量的相對地址，當(dāng)過程結(jié)束時(shí)，offset里記錄的是過程占用的所有字節(jié)數(shù)。,翻譯時(shí)用到的數(shù)據(jù)結(jié)構(gòu)：,辛明影,29,處理嵌套過程中的說明語句翻譯方案,PMDaddwidth(top(tblptr),top(offset); pop();pop(o

12、ffset),M t:=mktable（nil）； push(t,tblptr);push(0,offset),DD1；D2,Dproc id; N D1；S t:top（tblptr); addwidth(t,top(offset); pop（tblptr）；pop（offset); enterproc(top（tblptr），，t),辛明影,30,D id: T enter(top(tblptr),,T.type, top(offset); top(offset）：= top(offset) T.width,例：,procedure quicksort（m，n

13、： integer）； var i ： integer； begin end；,procedure partition （y ，z ：integer ） var i，j ，x，v： integer； begin end;,N t ：mktable(top（tblptr)； push(t，tblptr）；push（0，offset),辛明影,31,P,M,D,proc,Q,;,N,D,;,S,proc,P,;,N,D,;,S,j,:,T,int,辛明影,32,上述語法樹對應(yīng)的語句： Proc Q;proc R;j:int;S;S,遍歷語法樹所得到的翻譯序列： ,執(zhí)行上面翻譯序列符號表及棧的變化,

14、辛明影,33,tabptr offset,t,主,0,主,T=Q,Q,0,Q,T=p,P,0,*,t.type=int t.width=4,J int 0,4,t,4,R,t,0,Q,0,M t:=mktable（nil）； push(t,tblptr);push(0,offset),N t ：mktable(top（tblptr)； push(t，tblptr）；push（0，offset),N t ：mktable(top（tblptr)； push(t，tblptr）；push（0，offset),TintegerT.type ：=integer; T.width：= 4,D id: T

15、 enter(top(tblptr),,T.type, top(offset); top(offset）：= top(offset) T.width,Dproc id; N D1；S t:top（tblptr); addwidth(t,top(offset); pop（tblptr）；pop（offset); enterproc(top（tblptr），，t),Dproc id; N D1；S t:top（tblptr); addwidth(t,top(offset); pop（tblptr）；pop（offset); enterproc(top（tblptr），i

16、，t),PMDaddwidth(top(tblptr),top(offset); pop(tblptr);pop(offset),辛明影,34,一組嵌套過程，每個(gè)過程說明為局部名字建立一個(gè)符號表，所有正在翻譯過程的符號表組成整個(gè)源程序的符號表。,翻譯語句部分時(shí)查找符號表，查找過程的符號表的路線相當(dāng)于當(dāng)前被 翻譯過程的靜態(tài)鏈。,辛明影,35,三、 記錄中的域名 T record LD end T.type:=record（top（tblptr)； T.width:top(offset)； pop（tblptr);pop(offset) L t:=mktable(nil); push(

17、t,tblptr);push(0,offset) 為個(gè)記錄中的域名建立一張符號表 該翻譯模式強(qiáng)調(diào)了作為一個(gè)語言結(jié)構(gòu)的記錄的設(shè)計(jì)與活動(dòng)記錄之間的相似處.,辛明影,36,一、 符號表中的名字,6.2.2 賦值語句,賦值語句的翻譯：,如何根據(jù)名字查找符號表的表項(xiàng)？,表達(dá)式的成分可以是整型量、實(shí)型量、數(shù)組 元素和記錄,名字可以理解為指向符號表中相應(yīng)該名字表項(xiàng)的指針,過程lookup()檢查是否在符號表中存在相應(yīng)此名字的表項(xiàng)。,辛明影,37,用最近嵌套作用域規(guī)則查找非局部名字,若找到，返回有關(guān)信息。,lookup過程先通過top(tblptr）指針在當(dāng)前符號表中查找名字為name的表項(xiàng)。,

18、若未找到，lookup就利用當(dāng)前符號表表頭的指針找到該符號表的外圍符號表，,然后在那里查找名字為name的表項(xiàng)，,直到所有外圍過程的符號表中均無此name表項(xiàng)，,則lookup返回nil,表明查找失敗。,辛明影,38,lookup()= id.entry nil,emit 它將生成的三地址代碼送到輸出文件上。例： emit(E.place:=E1.place+E2.place) 或 emit(= , E1.place，E2.place， E.place),二、簡單算術(shù)表達(dá)式及賦值語句,辛明影,39,Sid:=E,產(chǎn)生賦值語句三地址代碼的翻譯模式,EE1+E2,EE1*E2,p:=

19、lookup(); if pnil then emit(p:= E.place) else error ,E.place=newtemp; emit(E.place:=E1.place+E2.place),E.place=newtemp; emit(E.place:=E1.place+E2.place),辛明影,40,E(E1),Eid,E -E, E.place:=newtemp;emit(E.place := uminusE1.place,E.place:=E1.place,p:=lookup(); if pnil then E.place:=p else er

20、ror,辛明影,41,語義動(dòng)作應(yīng)包括類型分析，文法符號應(yīng)有類型屬性，在類型分析的基礎(chǔ)上，進(jìn)行相容和賦值相容檢查，生成類型轉(zhuǎn)換的三地址代碼。,辛明影,42,數(shù)組元素的目標(biāo)代碼是什么？,三、 數(shù)組元素地址分配（復(fù)雜賦值語句）,如何生成數(shù)組元素的三地址代碼?,數(shù)組元素的三地址代碼是什么？,回顧一下，數(shù)組元素的地址計(jì)算公式：,辛明影,43,任一數(shù)組元素Ai1,i2, in的地址為： D=a+(i1-l1) d2d3 dn +(i2-l2) d2 d2 dn + (in-1-ln-1) dn + (in-ln),整理后C= ( (l1 d2 +l2) d3+ l3) d4+ + ln-1) dn+ ln

21、,C是數(shù)組計(jì)算中不變的部分,辛明影,44,變量部分：v= ( (i1 d2 +i2) d3+ i3) d4+ + in-1) dn+ in,i1地址：v= i1 i1,i2地址：v= i1 d2 +i2=ai1 d2 +i2 i1,i2，i3地址：v= (i1 d2 +i2) d3+ i3 =i1,i2 d3+ i3 i1,i2,i3,.,in地址: v= ( (i1 d2 +i2) d3+ i3) d4+ + in-1) dn+ in =i1,i2,i3,.,in-1 dn+ in,辛明影,45,1、數(shù)組元素地址的計(jì)算公式,每個(gè)數(shù)組元素的寬度,數(shù)組首地址,=bace-low*w + i*w,

22、一維數(shù)組的數(shù)組元素計(jì)算公式,VAR a:ARRAY low.high OF int;,求 ai的地址：,base（ilow ）* w,任一數(shù)組元素Ai1,i2, in的地址: addr=a-c+v,辛明影,46,對于一個(gè)二維數(shù)組，可以按行或按列存放。,若按行存放，則可用如下公式計(jì)算：,數(shù)組地址計(jì)算：,可在編譯時(shí)計(jì)算出來,常量部分+變量部分：,bace-l1*w + i*w,辛明影,47,base（i1 一l1）* d2i2 一l2）*w）,令c= （l1 *d22）l2）*w 則常量部分=al1,l2-c,A1,1 A1,2 A1,3 A2,1 A2,2 A2,3,A2,3按行存放,Ai1,i

23、2 的地址：,A1,2=,base-(1*3+1)+(1*3+2),= base+1,= base（low1 *d2）low2）*w, （i1*d2）i2)* w,辛明影,48,整理后：常量部分： c=(.(l1*d2+l2)*d3+l3).)*dk +lk) * w 變量部分v= (.(i1*n2+i2)*n3+i3.)*nk+ik)*w,多維數(shù)組Ai1,i2,.,ik 的地址的計(jì)算,(.(i1*d2+i2)*d3+i3.)*dk+ik)*w+base-(.(l1*d2+l2)*d3+l3.)*dk+lk)*w,ai1,i2,in的地址 =base-c+v,辛明影,49,x:=ai1,.,i

24、n的目標(biāo)代碼結(jié)構(gòu)：,t1: =v,t2:=base-c,t3:=t2t1,x:=t3,辛明影,50,2、數(shù)組的類型信息：,a 嵌套深度 偏移量 類型,名字表,內(nèi)情向量,C=84 l1=1 u1=10 d1=10 l2=1 u2=20 d2=20 基類型,int 標(biāo)準(zhǔn)類型 ,VAR a:ARRAY 1.10,1.20 OF int;,符號表中的信息可組織如下：,辛明影,51,地址計(jì)算變量部分： (i1*d2+i2)*d3+i3)*d4+ 可利用遞歸公式計(jì)算： e1= i 1,3、引用數(shù)組元素的文法 L id Elist | id ElistElist,E|E,為了便于語義處理，上述方法改寫為：

25、LElist| id ElistElist,E|id E,e2=e1*d2+i2；,e3=e2*d3+i3,em=em-1*dm+im,辛明影,52,Elist 引進(jìn)綜合屬性array，指向數(shù)組名a在符號表中的入口地址.,Elist.place：臨時(shí)變量，用來臨時(shí)存放由 Elist 中的下標(biāo)表達(dá)式計(jì)算出來的值;,函數(shù)limit（array，j）：返回nj ，即由 array所指示的數(shù)組的第j維長度;,4、 有關(guān)變量與函數(shù)的說明 Elist.ndim：記錄Elist中的下標(biāo)表達(dá)式的 個(gè)數(shù)，即維數(shù),對于A1.10,1.20， Limit(A,2)=20 Limit(A,1)=10,辛明影,53,L

26、有兩個(gè)屬性值： L.Place和L.offset,L.offset=null:表示L為一個(gè)簡單名字 L.offset不為空，表示數(shù)組元素引用,L.Place:如果L為一個(gè)簡單名字，則L.Place為指向該名字在符號表中的入口的指針；,如果L不為一個(gè)簡單名字，則L.Place為數(shù)組計(jì)算中的常數(shù)部分，base-c,辛明影,54,5、訪問數(shù)組元素的翻譯模式 給定文法G(S)： (0) M （1）SL： M E （2）EEE （3）E（E） （4）EL （5) LElist （6）Lid （7）ElistElist，E （8）Elistid E,辛明影,55,6、相應(yīng)語義動(dòng)作 若L是一個(gè)簡單的名字，將

27、生成一般的賦值；,若L為數(shù)組元素引用，則生成對L所指示地址的索引賦值,0M S.place：L.place; S.offset=L.offset,辛明影,56,2EE1E2 E.place：newtemp; emit（E.place： E1placeE2.place）,3E（E1） E.place ：E1.place,1SL ： ME if S. offsetnull then emit(S.place ： E.place) else emit（S.placeS.offset：= E. Place）,辛明影,57,使用索引來獲得地址L.placeL.offset 的內(nèi)容： 4 EL if L.

28、offsetnull then E.place:L.place * L is a simple id */ else begin emit(E.place:=L.placeL.offset) end,辛明影,58,一個(gè)空的offset表示一個(gè)簡單的名字： 6 Lld （L.place:=id.place;L.offset:=null,5 LElist L.place:=newtemp; emit（L.place:=Elist.array c) L.offset:=newtemp; emit（L.offset:=w*Elist.place),辛明影,59,應(yīng)用遞歸公式掃描下一個(gè)下標(biāo)表達(dá)式 7El

29、istElist1,E t：newtemp; m： Elist1ndim1； emit（t = Elist1.place * limit （Elist1.array,m）； emit（t = t E.place）； Elist.array：Elist1array; Elist.place：=t; Elist.ndim：m,em-1*dm,em-1*dm+im,辛明影,60,8 ElistidE Elist.place:=E.place; Elist.ndim:=1： Elist.array：id.place,例:設(shè)A為一個(gè)10*20的數(shù)組，,C=（l1*n2）l2）*w =(1*20 1）*4

30、84。,設(shè)w4，,若數(shù)組第一個(gè)元素為 A1，1 。則有，,即n1=10, n2= 20;,辛明影,61,S,L,X,=,E,L,E,EList,E,A,E,L,y,L,z,act61,act62,act41,act63,act7,act5,act43,act42,act1,act8,acc0,M,對賦值語句x：= Ay,z的帶注釋的分析樹如圖所示。,辛明影,62,Act61 act0 Act62 act41 Act8 Act63 Act42 Act7 Act5 Act43 act1,遍歷后得屬性計(jì)算順序：,act61,L.place L.offset E.place Elist.place E

31、list.ndim Elist.array,非終結(jié)符的屬性值,x,null,四元式表,act62,y,null,act41,y,act8,y,1,A,act63,z,null,act42,z,act7,2,t1=y*20,t1=t1+z,A,t1,2,act5,t2=A-84,t3=4*t1,t3,act43,t4=t2t3,t2,act1,act0,t4,s.place x,s.offset null,X=t4,m,6 Lld （L.place:=id.place;L.offset:=null,0 M s.place=L.place S.offset=L.offset,6 Lld （L.place:=id.place;L.offset:=null,4if L.offsetnull (EL ) then E.place:L.place else E.place:=newtemp; emit(E.place:=L.placeL.offset) ,8 ElistidE Elist.place:=E.place; Elist.ndim:=1： E