編譯原理：第七章語(yǔ)義分析和中間代碼產(chǎn)生.ppt

《編譯原理：第七章語(yǔ)義分析和中間代碼產(chǎn)生.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《編譯原理：第七章語(yǔ)義分析和中間代碼產(chǎn)生.ppt（104頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、編譯原理,第七章 語(yǔ)義分析和中間代碼產(chǎn)生,第七章 語(yǔ)義分析和中間代碼產(chǎn)生,靜態(tài)語(yǔ)義檢查 類(lèi)型檢查 控制流檢查 一致性檢查 相關(guān)名字檢查 名字的作用域分析,語(yǔ)法分 析器,中間代碼 產(chǎn)生器,靜態(tài)檢 查器,,中間代碼,優(yōu)化器,,,中間語(yǔ)言(復(fù)雜性界于源語(yǔ)言和目標(biāo)語(yǔ)言之間)的好處： 便于進(jìn)行與機(jī)器無(wú)關(guān)的代碼優(yōu)化工作 易于移植 使編譯程序的結(jié)構(gòu)在邏輯上更為簡(jiǎn)單明確,源語(yǔ)言 程序,目標(biāo)語(yǔ) 言程序,中間語(yǔ) 言程序,常用的中間語(yǔ)言： 后綴式，逆波蘭表示 圖表示： DAG、抽象語(yǔ)法樹(shù) 三地址代碼 三元式 四元式 間接三元式,7.1 中間語(yǔ)言,7.1.1 后綴式,后綴式表示法：Lukasiewicz發(fā)明的一種表示

2、表達(dá)式的方法，又稱(chēng)逆波蘭表示法。 一個(gè)表達(dá)式E的后綴形式可以如下定義： 1. 如果E是一個(gè)變量或常量，則E的后綴式是E自身。 2. 如果E是E1 op E2形式的表達(dá)式，其中op是任何二元操作符，則E的后綴式為E1 E2 op，其中E1 和E2 分別為E1 和E2的后綴式。 3. 如果E是(E1)形式的表達(dá)式，則E1 的后綴式就是E的后綴式。,逆波蘭表示法不用括號(hào)。只要知道每個(gè)算符的目數(shù)，對(duì)于后綴式，不論從哪一端進(jìn)行掃描，都能對(duì)它進(jìn)行唯一分解。 后綴式的計(jì)算 用一個(gè)棧實(shí)現(xiàn)。 一般的計(jì)算過(guò)程是：自左至右掃描后綴式，每碰到運(yùn)算量就把它推進(jìn)棧。每碰到k目運(yùn)算符就把它作用于棧頂?shù)膋個(gè)項(xiàng)，并用運(yùn)算結(jié)果代

3、替這k個(gè)項(xiàng)。,把表達(dá)式翻譯成后綴式的語(yǔ)義規(guī)則描述,產(chǎn)生式 EE(1)op E(2) E (E(1)) Eid,語(yǔ)義動(dòng)作 E.code:= E(1).code || E(2).code ||op E.code:= E(1).code E.code:=id,E.code表示E后綴形式 op表示任意二元操作符 “||”表示后綴形式的連接。,數(shù)組POST存放后綴式：k為下標(biāo)，初值為1 上述語(yǔ)義動(dòng)作可實(shí)現(xiàn)為： 產(chǎn)生式程序段 EE(1)op E(2)POSTk:=op;k:=k+1 E (E(1)) EiPOSTk:=i;k:=k+1 例：輸入串a(chǎn)+b+c的分析和翻譯 POST： 1 2 3 4

4、 5,EE(1)op E(2) E.code:= E(1).code || E(2).code ||op E (E(1))E.code:= E(1).code EidE.code:=id,a,b,+,c,+,,7.1.2 圖表示法,圖表示法 DAG 抽象語(yǔ)法樹(shù),7.1.2 圖表示法,無(wú)循環(huán)有向圖(Directed Acyclic Graph，簡(jiǎn)稱(chēng)DAG) 對(duì)表達(dá)式中的每個(gè)子表達(dá)式，DAG中都有一個(gè)結(jié)點(diǎn) 一個(gè)內(nèi)部結(jié)點(diǎn)代表一個(gè)操作符，它的孩子代表操作數(shù) 在一個(gè)DAG中代表公共子表達(dá)式的結(jié)點(diǎn)具有多個(gè)父結(jié)點(diǎn),a:=b*(-c)+b*(-c)的圖表示法,,抽象語(yǔ)法樹(shù)對(duì)應(yīng)的代碼： T1:=-c T2:=

5、b*T1 T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5,,DAG對(duì)應(yīng)的代碼： T1:=-c T2:=b*T1 T5:=T2+T2 a:=T5,抽象語(yǔ)法樹(shù)對(duì)應(yīng)的代碼： T1:=-c T2:=b*T1 T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5,產(chǎn)生賦值語(yǔ)句抽象語(yǔ)法樹(shù)的屬性文法,產(chǎn) 生 式語(yǔ)義規(guī)則 Sid:=ES.nptr:=mknode(assign, mkleaf(id,id.place),E.nptr) EE1+E2E.nptr:=mknode(+,E1.nptr,E2.nptr) EE1*E2E.nptr:=mknode(*,E1.nptr,E2.

6、nptr) E-E1 E.nptr:=mknode(uminus,E1.nptr) E (E1)E.nptr:=E1.nptr Eid E.nptr:=mkleaf(id,id.place),7.1.3 三地址代碼,三地址代碼 x:=y op z 三地址代碼可以看成是抽象語(yǔ)法樹(shù)或DAG的一種線性表示,a:=b*(-c)+b*(-c)的圖表示法,DAG對(duì)應(yīng)的代碼： T1:=-c T2:=b*T1 T5:=T2+T2 a:=T5,抽象語(yǔ)法樹(shù)對(duì)應(yīng)的代碼： T1:=-c T2:=b*T1 T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5,三地址語(yǔ)句的種類(lèi),x:=y op z x:=op

7、 y x:=y goto L if x relop y goto L或if a goto L param x和call p,n，以及返回語(yǔ)句return y x:=yi及xi:=y的索引賦值 x:= E.code:=E1.code || E2.code || gen(E.place := E1.place + E2.place) EE1*E2E.place:=newtemp; E.code:=E1.code || E2.code || gen(E.place := E1.place * E2.place) E-E1 E.place:=newtemp; E.code:=E

8、1.code || gen(E.place := uminus E1.place) E (E1)E.place:=E1.place; E.code:=E1.code Eid E.place:=id.place; E.code= ,三地址語(yǔ)句,四元式 一個(gè)帶有四個(gè)域的記錄結(jié)構(gòu)，這四個(gè)域分別稱(chēng)為op, arg1, arg2及result oparg1arg2result (0)uminus cT1 (1)* bT1T2 (2)uminus cT3 (3)* bT3T4 (4)+ T2T4T5 (5):= T5a,三地址語(yǔ)句,三元式 通過(guò)計(jì)算臨時(shí)變量值的語(yǔ)句

9、的位置來(lái)引用這個(gè)臨時(shí)變量 三個(gè)域：op、arg1和arg2 oparg1arg2 (0)uminus c (1)* b(0) (2)uminus c (3)* b(2) (4)+ (1)(3) (5)assign a(4),三地址語(yǔ)句,xi:=y op arg1 arg2 (0) = x i (1) assign (0) y x:=yi op arg1 arg2 (0) = y i (1) assign x (0),三地址語(yǔ)句,間接三元式 為了便于優(yōu)化，用 三元式表+間接碼表 表示中間代碼 間接碼表:一張指示器表，按運(yùn)算的先后次

10、序列出有關(guān)三元式在三元式表中的位置。 優(yōu)點(diǎn): 方便優(yōu)化，節(jié)省空間,例如，語(yǔ)句 X:=(A+B)*C; Y:=D(A+B) 的間接三元式表示如下表所示。,7.2 說(shuō)明語(yǔ)句,7.3 賦值語(yǔ)句的翻譯,7.3.1 簡(jiǎn)單算術(shù)表達(dá)式及賦值語(yǔ)句,為賦值語(yǔ)句生成三地址代碼的S-屬性文法定義,產(chǎn)生式語(yǔ)義規(guī)則 Sid:=ES.code:=E.code || gen(id.place := E.place) EE1+E2E.place:=newtemp; E.code:=E1.code || E2.code || gen(E.place := E1.place + E2.place) EE1*E2E

11、.place:=newtemp; E.code:=E1.code || E2.code || gen(E.place := E1.place * E2.place) E-E1 E.place:=newtemp; E.code:=E1.code || gen(E.place := uminus E1.place) E (E1)E.place:=E1.place; E.code:=E1.code Eid E.place:=id.place; E.code= ,產(chǎn)生賦值語(yǔ)句三地址代碼的翻譯模式,Sid:=E p:=lookup(id.name); if pnil then em

12、it(p := E.place) else error EE1+E2 E.place:=newtemp; emit(E.place := E1.place + E2.place) EE1*E2 E.place:=newtemp; emit(E.place := E 1.place * E 2.place),Sid:=E S.code:=E.code || gen(id.place := E.place) EE1+E2 E.place:=newtemp; E.code:=E1.code || E2.code ||gen(E.place := E1.place + E2.place)

13、 EE1*E2 E.place:=newtemp; E.code:=E1.code || E2.code || gen(E.place := E1.place * E2.place),產(chǎn)生賦值語(yǔ)句三地址代碼的翻譯模式,E-E1 E.place:=newtemp; emit(E.place:= uminusE 1.place) E(E1) E.place:=E1.place Eid p:=lookup(id.name); if pnil then E.place:=p else error ,E-E1 E.place:=newtemp; E.code:=E1.c

14、ode || gen(E.place := uminus E1.place) E (E1) E.place:=E1.place; E.code:=E1.code Eid E.place:=id.place; E.code= ,,計(jì)算數(shù)組元素的地址 數(shù)組元素存儲(chǔ)在一個(gè)連續(xù)的存儲(chǔ)塊中，根據(jù)數(shù)組元素的下標(biāo)可以快速地查找每個(gè)元素。 一維數(shù)組A,基址：base 域?qū)挘簑 元素個(gè)數(shù)：high-low+1,數(shù)組元素Ai的位置： base + ( i-low )w = iw + base - loww,7.3.2 數(shù)組元素的引用,,,二維數(shù)組A,存儲(chǔ)方式： 按行存放 按列存放,每維的下界：l

15、ow1、low2 每維的上界：high1、high2 每維的長(zhǎng)度：n1=high1-low1+1 n2=high2-low2+1 域?qū)挘簑 基址：base,數(shù)組元素Ai,j的位置： base+((i-low1) n2+(j-low2))w =(in2+j)w+base-(low1n2+low2)w,,,,,,每維的下界：low1、low2、...、lowk 每維的長(zhǎng)度：n1、n2、...、nk 存儲(chǔ)方式：按行存放 數(shù)組元素Ai1,i2,...,ik的位置： ( (( (i1n2+i2)n3+i3 ))nk+ik )w + base - ( (( (low1n2+low2)n3+low3

16、 ))nk+lowk )w,K維數(shù)組A,遞歸計(jì)算： e1=i1,,e2=e1 n2+i2,e3=e2n3+i3,ek=ek-1nk+ik,,S屬性定義,SL:=E EE1+E2 E(E1) EL Lid | id Elist ElistElist1 , E | E,語(yǔ)句 X:=A i, j 的分析樹(shù),,改寫(xiě)文法： Lid | Elist ElistElist1 , E | idE,(1) SL:=E (2) EE+E (3) E(E) (4) EL (5) LElist (6) Lid (7) Elist Elist, E (8) Elistid E,屬性及函數(shù)設(shè)計(jì),L 綜合屬性L.place

17、和L.offset 簡(jiǎn)單變量： L.offset=null L.place=符號(hào)表入口指針 數(shù)組元素（下標(biāo)變量）： L.offset=計(jì)算公式第一項(xiàng)，指存放VARPART （可變項(xiàng)）的臨時(shí)變量的整數(shù)碼 L.place=計(jì)算公式第二項(xiàng)，指存放CONSPART（不變項(xiàng)）的 臨時(shí)變量的整數(shù)碼 E 綜合屬性E.place，保存E值的變量在符號(hào)表中的位置 Elist 綜合屬性Elist.array，ndim，place Elist.array：數(shù)組名在符號(hào)表中的位置 Elist.ndim：目前已經(jīng)識(shí)別出的下標(biāo)表達(dá)式的個(gè)數(shù) Elist.place：保存遞推公式中em值的臨時(shí)變量在符號(hào)表中的位置 函數(shù)

18、 limit(array, j)：返回array指向的數(shù)組第j維的長(zhǎng)度 invariant(array)：返回array指向的數(shù)組的地址計(jì)算公式中的不變項(xiàng),S屬性定義翻譯方案,SL:=E, if (L.offset==null) /* L是簡(jiǎn)單變量 */ emit(L.place := E.place ); else emit(L.place L.offset := E.place); ,EE1+E2, E.place=newtemp; emit(E.place := E1.place + E2.place) ,E(E1), E.place=E1.place ,EL, if (L.offset

19、 == null) /* L是簡(jiǎn)單變量 */ E.place=L.place; else E.place=newtemp; emit(E.place := L.place L.offset ); ,Lid, L.place=id.place; L.offset=null ,ElistidE,ElistElist1,E,LElist, Elist.place=E.place; Elist.ndim=1; Elist.array=id.place , t=newtemp; m=Elist1.ndim+1; emit(t := Elist1.place limit(Elist1.arra

20、y,m)); emit(t := t + E.place); Elist.array=Elist1.array; Elist.place=t; Elist.ndim=m , L.place=newtemp; emit( L.place := Elist.array - invariant(Elist.array)); L.offset=newtemp; emit(L.offset := w Elist.place) ,e2=e1n2+i2 e3=e2n3+i3 ek=ek-1nk+ik,e1=i1,Ai1,i2,,ik ((i1 n2+i2)n3+i3))nk+ik)w +base-((((l

21、ow1 n2+low2)n3+low3))nk+lowk)w,舉例,已知： 設(shè)A為一個(gè)1020的數(shù)組，即 n1=10，n2=20； 并設(shè)域?qū)?w=4； 數(shù)組的第一個(gè)元素為A1,1， 則有 low1=1，low2=1 所以： (low1n2+low2)w = (120+1)4 = 84 問(wèn)題： 將賦值語(yǔ)句 x:=Ay,z 翻譯為三地址代碼。,賦值語(yǔ)句 x:=Ay,z的分析樹(shù),A ,x,:=,,y,z,.place=x .offset=null,.place=y .offset=null,.place=y,.place=y .ndim=1 .array=A,，,.place=z .off

22、set=null,.place=z,.place=t1 .ndim=2 .array=A,.place=t2 .offset=t3,.place=t4,t4:=t2t3,t1:=y*20 t1:=t1+z,類(lèi)型轉(zhuǎn)換,用E.type表示非終結(jié)符E的類(lèi)型屬性 對(duì)應(yīng)產(chǎn)生式EE1 op E2的語(yǔ)義動(dòng)作中關(guān)于E.type的語(yǔ)義規(guī)則可定義為： if E1.type=integer andE2.type=integer E.type:=integer else E.type:=real 算符區(qū)分為整型算符int op和實(shí)型算符real op，,,x:=yi*j 其中x、y為實(shí)型；i、j為整型。這個(gè)賦值

23、句產(chǎn)生的三地址代碼為： T1:=i int* j T3:=inttoreal T1 T2:=y real+ T3 x:=T2,關(guān)于產(chǎn)生式EE1 E2 的語(yǔ)義動(dòng)作, E.place:=newtemp; if E1.type=integer and E2.type=integer then begin emit (E.place := E 1.place int+ E 2.place); E.type:=integer end else if E1.type=real and E2.type=real then begin emit (E.place := E 1.place r

24、eal+ E 2.place); E.type:=real end,else if E1.type=integer and E2.type=real then begin u:=newtemp; emit (u := inttoreal E 1.place); emit (E.place := u real+ E 2.palce); E.type:=real end else if E1.type=real and E1.type=integer then begin u:=newtemp; emit (u := inttoreal E 2.place); emit (E.place := E

25、 1.place real+ u); E.type:=real end else E.type:=type_error,7.3.3 記錄中域的引用,符號(hào)表表項(xiàng)之中保存記錄中的域的類(lèi)型和相對(duì)地址信息,7.4 布爾表達(dá)式的翻譯,布爾表達(dá)式的兩個(gè)基本作用: 用于邏輯演算,計(jì)算邏輯值; 用于控制語(yǔ)句的條件式. 產(chǎn)生布爾表達(dá)式的文法: EE or E | E andE | E | (E) | i rop i | i,計(jì)算布爾表達(dá)式通常采用兩種方法: 1. 如同計(jì)算算術(shù)表達(dá)式一樣,一步步算 1 or (not 0 and 0) or 0 =1 or (1 and 0) or 0 =1 or

26、0 or 0 =1 or 0 =1 2. 采用某種優(yōu)化措施 把A or B解釋成 if A then true else B 把A and B解釋成 if A then B else false 把 A解釋成 if A then false else true,兩種不同的翻譯方法: 第一種翻譯法： A or B and C=D翻譯成 (1) (=, C, D, T1) (2) (and, B, T1, T2) (3) (or, A, T2, T3) 第二種翻譯法適合于作為條件表達(dá)式的布爾表達(dá)式使用.,7.4.1 數(shù)值表示法,a or b and not c 翻譯成 T1:=no

27、t c T2:=b and T1 T3:=a or T1 a

28、e or E2.place) EE1 and E2 E.place:=newtemp; emit(E.place := E 1.place and E2.place) Enot E1 E.place:=newtemp; emit(E.place := not E 1.place) E(E1) E.place:=E1.place,關(guān)于布爾表達(dá)式的數(shù)值表示法的翻譯模式,Eid1 relop id2 E.place:=newtemp; emit(if id1.place relop. op id2. place goto nextstat+3); emit(E.place := 0);

29、 emit(goto nextstat+2); emit(E.place:= 1) Eid E.place:=id.place ,a

30、: goto 112 111: T3:=1 112: T4:=T2 and T3 113: T5:=T1 or T4,,Eid1 relop id2 E.place:=newtemp; emit(if id1.place relop. op id2. place goto nextstat+3); emit(E.place := 0); emit(goto nextstat+2); emit(E.place:= 1) Eid E.place:=id.place EE1 or E2 E.place:=newtemp; emit(E.place := E 1.place or E2.p

31、lace) EE1 and E2 E.place:=newtemp; emit(E.place := E 1.place and E2.place) ,7.4.2 作為條件控制的布爾式翻譯,條件語(yǔ)句 if E then S1 else S2 賦予 E 兩種出口:一真一假,E.code,S1.code,S2.code,To E.true,To E.false,goto S.next,S.next,,E.true:,E.false:,,,,例：把語(yǔ)句: if ac or b c goto L2 “真”出口 goto L1 L1:if b

32、 “假”出口 L2:(關(guān)于S1的三地址代碼序列) goto Lnext L3:(關(guān)于S2的三地址代碼序列) Lnext:,,每次調(diào)用函數(shù)newlabel后都返回一個(gè)新的符號(hào)標(biāo)號(hào) 對(duì)于一個(gè)布爾表達(dá)式E，引用兩個(gè)標(biāo)號(hào) E.true是E為真時(shí)控制流轉(zhuǎn)向的標(biāo)號(hào) E.false是E為假時(shí)控制流轉(zhuǎn)向的標(biāo)號(hào),產(chǎn)生布爾表達(dá)式三地址代碼的語(yǔ)義規(guī)則,產(chǎn)生式語(yǔ)義規(guī)則 EE1 or E2 E1.true:=E.true; E1.false:=newlabel; E2.true:=E.true; E2.false:=E.false; E.code:=E1.code || gen(E1.f

33、alse :) || E2.code,產(chǎn)生布爾表達(dá)式三地址代碼的語(yǔ)義規(guī)則,產(chǎn)生式語(yǔ)義規(guī)則 EE1 and E2 E1.true:=newlabel; E1.false:=E.false; E2.true:=E.true; E2.false:=E.fasle; E.code:=E1.code || gen(E1.true :) || E2.code,產(chǎn)生布爾表達(dá)式三地址代碼的語(yǔ)義規(guī)則,產(chǎn)生式語(yǔ)義規(guī)則 Enot E1 E1.true:=E.false; E1.false:=E.true; E.code:=E1.code E (E1) E1.tru

34、e:=E.true; E1.false:=E.false; E.code:=E1.code,產(chǎn)生布爾表達(dá)式三地址代碼的語(yǔ)義規(guī)則,產(chǎn)生式語(yǔ)義規(guī)則 Eid1 relop id2 E.code:=gen(if id1.place relop.op id2.place goto E.true) || gen(goto E.false) Etrue E.code:=gen(goto E.true) Efalse E.code:=gen(goto E.false),考慮如下表達(dá)式： a

35、和Lfalse，則按定義將生成如下的代碼：,if a

36、(j, -, -, p) 表示 goto p,有時(shí),四元式轉(zhuǎn)移地址無(wú)法立即知道,我們只好把這個(gè)未完成的四元式地址作為E的語(yǔ)義值保存,待機(jī)回填。,為非終結(jié)符E賦予兩個(gè)綜合屬性E.truelist和E.falselist。它們分別記錄布爾表達(dá)式E所應(yīng)的四元式中需回填“真”、“假”出口的四元式的標(biāo)號(hào)所構(gòu)成的鏈表 例如:假定E的四元式中需要回填真出口的p，q，r三個(gè)四元式，則E.truelist為下列鏈: (p) (x， x，x，0) (q) (x，x，x，p) (r) (x，x，x，q),,,鏈尾,E. truelist =r,為了處理E.truelist和E.falselist ，引入下列語(yǔ)義變

37、量和過(guò)程: 變量nextquad，它指向下一條將要產(chǎn)生但尚未形成的四元式的地址(標(biāo)號(hào))。nextquad的初值為1，每當(dāng)執(zhí)行一次emit之后，nextquad將自動(dòng)增1。 函數(shù)makelist(i)，它將創(chuàng)建一個(gè)僅含i的新鏈表，其中i是四元式數(shù)組的一個(gè)下標(biāo)(標(biāo)號(hào))；函數(shù)返回指向這個(gè)鏈的指針。 函數(shù)merge(p1,p2)，把以p1和p2為鏈?zhǔn)椎膬蓷l鏈合并為一，作為函數(shù)值，回送合并后的鏈?zhǔn)住?過(guò)程backpatch(p, t)，其功能是完成“回填”，把p所鏈接的每個(gè)四元式的第四區(qū)段都填為t。,布爾表達(dá)式的文法,(1) EE1 or M E2 (2) | E1 and M E2 (3)

38、 | not E1 (4) | (E1) (5) | id1 relop id2 (6) | id (7)M,布爾表達(dá)式的翻譯模式,(7) M M.quad:=nextquad ,,布爾表達(dá)式的翻譯模式,(1) EE1 or M E2 backpatch(E1.falselist, M.quad); E.truelist:=merge(E1.truelist, E2.truelist); E.falselist:=E2.falselist (2) EE1 and M E2 backpatch(E1.truelist, M.quad); E.truelist:=E2.truel

39、ist; E.falselist:=merge(E1.falselist,E2.falselist) ,布爾表達(dá)式的翻譯模式,(3) Enot E1 E.truelist:=E1.falselist; E.falselist:=E1.truelist (4) E(E1) E.truelist:=E1.truelist; E.falselist:=E1. falselist,布爾表達(dá)式的翻譯模式,(5) Eid1 relop id2 E.truelist:=makelist(nextquad); E.falselist:=makelist(nextquad+1); emit(j relop

40、.op , id 1.place , id 2.place,0); emit(j, , , 0) (6) Eid E.truelist:=makelist(nextquad); E.falselist:=makelist(nextquad+1); emit(jnz , id .place , ,0)； emit( j, -, -, 0) ,布爾表達(dá)式的翻譯模式,作為整個(gè)布爾表達(dá)式的真假出口(轉(zhuǎn)移目標(biāo))仍待回填.,利用翻譯方案翻譯布爾表達(dá)式 a

41、=101,100：if a

42、 100) truelist 105(j, -, -, 103) falselist,,,7.5 控制語(yǔ)句的翻譯,考慮下列產(chǎn)生式所定義的語(yǔ)句 S if E then S1 | if E then S1 else S2 | while E do S1 其中E為布爾表達(dá)式。,,if-then語(yǔ)句 S if E then S1,E.code,S1.code,To E.true,To E.false,,E.true:,E.false:,if-then語(yǔ)句的屬性文法,產(chǎn)生式語(yǔ)義規(guī)則 Sif E then S1 E.true:=newlabel; E.flase:=S.next

43、; S1.next:=S.next S.code:=E.code || gen(E.true :) || S1.code,,if-then-else語(yǔ)句 S if E then S1 else S2,E.code,S1.code,S2.code,To E.true,To E.false,goto S.next,S.next,,E.true:,E.false:,if-then-else語(yǔ)句的屬性文法,產(chǎn)生式 語(yǔ)義規(guī)則 Sif E then S1 else S2 E.true:=newlabel; E.false:=newlabel; S1.next:=S

44、.next S2.next:=S.next; S.code:=E.code || gen(E.true :) || S1.code || gen(goto S.next) || gen(E.false :) || S2.code,,while-do語(yǔ)句 S while E do S1,E.code,S1.code,To E.true,To E.false,goto S.begin,S.begin:,,E.true:,E.false:,while-do語(yǔ)句的屬性文法,產(chǎn)生式語(yǔ)義規(guī)則 Swhile E do S1S.begin:=newlabel; E.true:=ne

45、wlabel; E.false:=S.next; S1.next:=S.begin; S.code:=gen(S.begin :) || E.code || gen(E.true :) || S1.code || gen(goto S.begin),考慮如下語(yǔ)句 :while a

46、Lnext:,一遍掃描翻譯控制流語(yǔ)句,考慮下列產(chǎn)生式所定義的語(yǔ)句: (1) Sif E then S (2) | if E then S else S (3) | while E do S (4) | begin L end (5) | A (6) LL;S (7) | S S表示語(yǔ)句， L表示語(yǔ)句表， A為賦值語(yǔ)句，E為一個(gè)布爾表達(dá)式,if 語(yǔ)句的翻譯 相關(guān)產(chǎn)生式 S if E then S(1) | if E then S(1) else S(2) 改寫(xiě)后產(chǎn)生式 S if E then M S1 S if E then M1 S1 N else M2 S2 M N,翻譯模式: 1. S

47、if E then M S1 backpatch(E.truelist, M.quad); S.nextlist:=merge(E.falselist, S1.nextlist) 2. Sif E then M1 S1 N else M2 S2 backpatch(E.truelist, M1.quad); backpatch(E.falselist, M2.quad); S.nextlist:=merge(S1.nextlist, N.nextlist, S2.nextlist) 3. M M.quad:=nextquad 4. N N.nextlist:=makelist(nextquad

48、); emit(j,,,) ,while 語(yǔ)句的翻譯 相關(guān)產(chǎn)生式 S while E do S(1) 翻譯為：,E的代碼,S (1)的代碼,“真”出口,“假”出口,為了便于回填，改寫(xiě)產(chǎn)生式為: Swhile M1 E do M2 S1 M,翻譯模式: 1. Swhile M1 E do M2 S1 backpatch(S1.nextlist, M1.quad); backpatch(E.truelist, M2.quad); S.nextlist:=E.falselist emit(j,,, M1.quad) 2. M M.quad:=nextquad ,產(chǎn)生式 LL;S 改寫(xiě)為： LL1;

49、 M S M,翻譯模式: 1. LL1; M S backpatch(L1.nextlist, M.quad); L.nextlist:=S.nextlist 2. M M.quad:=nextquad ,其它幾個(gè)語(yǔ)句的翻譯 1. Sbegin L end S.nextlist:=L.nextlist 2. SA S.nextlist:=makelist( ) 3. LS L.nextlist:=S.nextlist ,A1的代碼,例：,if a

50、的代碼,A1的代碼,A2的代碼,,E的代碼,A3的代碼,100：if a

51、id1 relop id2 E.truelist:=makelist(nextquad); E.falselist:=makelist(nextquad+1); emit(j relop.op , id 1.place , id 2.place,0); emit(j, , , 0) ,P179 Sid:=E p:=lookup(id.name); if pnil then emit(p := E.place) else error EE1+E2 E.place:=newtemp; emit(E.place := E1.place + E2.place),P195 Sif E the

52、n M S1 backpatch(E.truelist, M.quad); S.nextlist:=merge(E.falselist, S1.nextlist) M M.quad:=nextquad SA S.nextlist:=makelist( ) ,P195 Swhile M1 E do M2 S1 backpatch(S1.nextlist, M1.quad); backpatch(E.truelist, M2.quad); S.nextlist:=E.falselist emit(j,,, M1.quad) M M.quad:=nextquad ,翻譯語(yǔ)句while (a

53、oif (c

54、,未,產(chǎn)生式Sgoto L的語(yǔ)義動(dòng)作: 查找符號(hào)表； IF L在符號(hào)表中且定義否欄為已 THEN GEN(J，-，-，P) ELSE IF L不在符號(hào)表中 THEN BEGIN 把L填入表中； 置定義否為未，地址欄為NXQ； GEN(J，-，-，0) END ELSE BEGIN Q:=L的地址欄中的編號(hào)； 置地址欄編號(hào)為NXQ； GEN(J，-，-，Q) END ,帶標(biāo)號(hào)語(yǔ)句的產(chǎn)生式: Slabel S label i: label i: 對(duì)應(yīng)的語(yǔ)義動(dòng)作: 1. 若i所指的標(biāo)識(shí)符(假定為L(zhǎng))不在符號(hào)表中，則把它填入，置類(lèi)型為標(biāo)號(hào)，定義否為已，地址為nextqua

55、d ； 2. 若L已在符號(hào)表中但類(lèi)型不為標(biāo)號(hào)或定義否為已，則報(bào)告出錯(cuò)； 3. 若L已在符號(hào)表中，則把標(biāo)號(hào)未改為已，然后，把地址欄中的鏈頭(記為q)取出，同時(shí)把nextquad填在其中，最后，執(zhí)行BACKPATCH(q，nextquad )。,7.5.3 CASE語(yǔ)句的翻譯,語(yǔ)句結(jié)構(gòu) case E of C1:S1; C2:S2; Cn-1:Sn-1; otherwise:Sn end,翻譯法(一): T:=E L1:if TC1 goto L2 S1的代碼 goto next L2:if TC2 goto L3 S2的代碼 goto next L3: Ln-1:if TCn-1

56、 goto Ln Sn-1的代碼 goto next Ln:Sn的代碼 next:,改進(jìn):,翻譯法(二): 計(jì)算E并放入T中 goto test L1:關(guān)于S1的中間碼 goto next Ln-1:關(guān)于Sn-1的中間碼 goto next Ln:關(guān)于Sn的中間碼 goto next test:if T=C1 goto L1 if T=C2 goto L2 if T=Cn-1 goto Ln-1 goto Ln next:,(case, C1, P1) (case, C2, P2) (case, Cn-1, Pn-1) (case, T, Pn) (label, NEXT, -, -),

57、Pi是Li在 符號(hào)表中 的位置,7.6 過(guò)程調(diào)用的處理,過(guò)程調(diào)用主要對(duì)應(yīng)兩種事: 傳遞參數(shù) 轉(zhuǎn)子,傳地址:把實(shí)在參數(shù)的地址傳遞給相應(yīng)的形式參數(shù) 調(diào)用段預(yù)先把實(shí)在參數(shù)的地址傳遞到被調(diào)用段可以拿到的地方； 程序控制轉(zhuǎn)入被調(diào)用段之后，被調(diào)用段首先把實(shí)在參數(shù)的地址抄進(jìn)自己相應(yīng)的形式單元中； 過(guò)程體對(duì)形式參數(shù)的引用域賦值被處理成對(duì)形式單元的間接訪問(wèn)。,翻譯方法：把實(shí)參的地址逐一放在轉(zhuǎn)子指令的前面. 例如， CALL S(A，X+Y) 翻譯為: 計(jì)算X+Y置于T中的代碼 par A /*第一個(gè)參數(shù)的地址*/ par T /*第二個(gè)參數(shù)的地址*/ call S /*轉(zhuǎn)子*/,過(guò)程調(diào)用的翻譯,過(guò)程調(diào)用文法: (1) S call id (Elist) (2) Elist Elist, E (3) Elist E 參數(shù)的地址存放在一個(gè)隊(duì)列中 最后對(duì)隊(duì)列隊(duì)列中的每一項(xiàng)生成一條par語(yǔ)句,翻譯模式 3. ElistE 初始化queue僅包含E.place 2. ElistElist, E 將E.place加入到queue的隊(duì)尾 1. Scall id (Elist) for 隊(duì)列queue中的每一項(xiàng)p do emit(param p); emit(call id.place) ,作業(yè),P217-1，3 ，4 ，5 ，6 ，7 ，12,