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

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

3、個項。,把表達式翻譯成后綴式的語義規(guī)則描述,產(chǎn)生式 EE(1)op E(2) E (E(1) Eid,語義動作 E.code:= E(1).code | E(2).code |op E.code:= E(1).code E.code:=id,E.code表示E后綴形式 op表示任意二元操作符 “|”表示后綴形式的連接。,數(shù)組POST存放后綴式：k為下標，初值為1 上述語義動作可實現(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 5,EE(1)op E(

4、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 抽象語法樹,7.1.2 圖表示法,無循環(huán)有向圖(Directed Acyclic Graph，簡稱DAG) 對表達式中的每個子表達式，DAG中都有一個結點 一個內(nèi)部結點代表一個操作符，它的孩子代表操作數(shù) 在一個DAG中代表公共子表達式的結點具有多個父結點,a:=b*(-c)+b*(-c)的圖表示法,抽象語法樹對應的代碼： T1:=-c T2:=b*T1 T3:=-c T4:=b*T

5、3 T5:=T2+T4 a:=T5,DAG對應的代碼： T1:=-c T2:=b*T1 T5:=T2+T2 a:=T5,抽象語法樹對應的代碼： T1:=-c T2:=b*T1 T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5,產(chǎn)生賦值語句抽象語法樹的屬性文法,產(chǎn) 生 式語義規(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.nptr) E-E1 E.nptr:=mkn

6、ode(uminus,E1.nptr) E (E1)E.nptr:=E1.nptr Eid E.nptr:=mkleaf(id,id.place),7.1.3 三地址代碼,三地址代碼 x:=y op z 三地址代碼可以看成是抽象語法樹或DAG的一種線性表示,a:=b*(-c)+b*(-c)的圖表示法,DAG對應的代碼： T1:=-c T2:=b*T1 T5:=T2+T2 a:=T5,抽象語法樹對應的代碼： T1:=-c T2:=b*T1 T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5,三地址語句的種類,x:=y op z x:=op y x:=y goto L if x rel

7、op y goto L或if a goto L param x和call p,n，以及返回語句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:=E1.code | gen(E.place := uminus E1.place

8、) E (E1)E.place:=E1.place; E.code:=E1.code Eid E.place:=id.place; E.code= ,三地址語句,四元式 一個帶有四個域的記錄結構，這四個域分別稱為op, arg1, arg2及result oparg1arg2result (0)uminus cT1 (1)* bT1T2 (2)uminus cT3 (3)* bT3T4 (4)+ T2T4T5 (5):= T5a,三地址語句,三元式 通過計算臨時變量值的語句的位置來引用這個臨時變量 三個域：op、arg1和arg2 oparg1arg2 (0)uminus c (1)* b(0

9、) (2)uminus c (3)* b(2) (4)+ (1)(3) (5)assign a(4),三地址語句,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ōu)化，用 三元式表+間接碼表 表示中間代碼 間接碼表:一張指示器表，按運算的先后次序列出有關三元式在三元式表中的位置。 優(yōu)點: 方便優(yōu)化，節(jié)省空間,例如，語句 X:=(A+B)*C; Y:=D(A+B) 的間接三元式表示如下表所示。,7.2 說明語句,7.3 賦值語句的

10、翻譯,7.3.1 簡單算術表達式及賦值語句,為賦值語句生成三地址代碼的S-屬性文法定義,產(chǎn)生式語義規(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.place:=newtemp; E.code:=E1.code | E2.code | gen(E.place := E1.place * E2.place) E-E1 E.place:=newtemp; E

11、.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)生賦值語句三地址代碼的翻譯模式,Sid:=E p:=lookup(); if pnil then emit(p := E.place) else error EE1+E2 E.place:=newtemp; emit(E.place := E1.place + E2.place) EE1*E2 E.place:=newtemp; emit

12、(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) EE1*E2 E.place:=newtemp; E.code:=E1.code | E2.code | gen(E.place := E1.place * E2.place),產(chǎn)生賦值語句三地址代碼的翻譯模式,E-E1 E.place:=newtemp;

13、 emit(E.place:= uminusE 1.place) E(E1) E.place:=E1.place Eid p:=lookup(); if pnil then E.place:=p else error ,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= ,計算數(shù)組元素的地址 數(shù)組元素存儲在一個連續(xù)的存儲塊中，根據(jù)數(shù)組元素的下標

14、可以快速地查找每個元素。 一維數(shù)組A,基址：base 域?qū)挘簑 元素個數(shù)：high-low+1,數(shù)組元素Ai的位置： base + ( i-low )w = iw + base - loww,7.3.2 數(shù)組元素的引用,二維數(shù)組A,存儲方式： 按行存放 按列存放,每維的下界：low1、low2 每維的上界：high1、high2 每維的長度：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、lo

15、w2、.、lowk 每維的長度：n1、n2、.、nk 存儲方式：按行存放 數(shù)組元素Ai1,i2,.,ik的位置： ( ( (i1n2+i2)n3+i3 )nk+ik )w + base - ( ( (low1n2+low2)n3+low3 )nk+lowk )w,K維數(shù)組A,遞歸計算： 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,語句 X:=A i, j 的分析樹,改寫文法： Lid | Elist ElistElist1 , E

16、 | idE,(1) SL:=E (2) EE+E (3) E(E) (4) EL (5) LElist (6) Lid (7) Elist Elist, E (8) Elistid E,屬性及函數(shù)設計,L 綜合屬性L.place和L.offset 簡單變量： L.offset=null L.place=符號表入口指針 數(shù)組元素（下標變量）： L.offset=計算公式第一項，指存放VARPART （可變項）的臨時變量的整數(shù)碼 L.place=計算公式第二項，指存放CONSPART（不變項）的 臨時變量的整數(shù)碼 E 綜合屬性E.place，保存E值的變量在符號表中的位置 Elist 綜合屬性E

17、list.array，ndim，place Elist.array：數(shù)組名在符號表中的位置 Elist.ndim：目前已經(jīng)識別出的下標表達式的個數(shù) Elist.place：保存遞推公式中em值的臨時變量在符號表中的位置 函數(shù) limit(array, j)：返回array指向的數(shù)組第j維的長度 invariant(array)：返回array指向的數(shù)組的地址計算公式中的不變項,S屬性定義翻譯方案,SL:=E, if (L.offset=null) /* L是簡單變量 */ emit(L.place := E.place ); else emit(L.place L.offset := E.pl

18、ace); ,EE1+E2, E.place=newtemp; emit(E.place := E1.place + E2.place) ,E(E1), E.place=E1.place ,EL, if (L.offset = null) /* L是簡單變量 */ 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; E

19、list.ndim=1; Elist.array=id.place , t=newtemp; m=Elist1.ndim+1; emit(t := Elist1.place limit(Elist1.array,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 E

20、list.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-(low1 n2+low2)n3+low3)nk+lowk)w,舉例,已知： 設A為一個1020的數(shù)組，即 n1=10，n2=20； 并設域?qū)?w=4； 數(shù)組的第一個元素為A1,1， 則有 low1=1，low2=1 所以： (low1n2+low2)w = (120+1)4 = 84 問題： 將賦值語句 x:=Ay,z 翻譯為三地址代碼。,賦值語句 x:=Ay,z的分析樹,A ,x,:=,y,z,.plac

21、e=x .offset=null,.place=y .offset=null,.place=y,.place=y .ndim=1 .array=A,，,.place=z .offset=null,.place=z,.place=t1 .ndim=2 .array=A,.place=t2 .offset=t3,.place=t4,t4:=t2t3,t1:=y*20 t1:=t1+z,類型轉(zhuǎn)換,用E.type表示非終結符E的類型屬性 對應產(chǎn)生式EE1 op E2的語義動作中關于E.type的語義規(guī)則可定義為： if E1.type=integer andE2.type=integer E.type

22、:=integer else E.type:=real 算符區(qū)分為整型算符int op和實型算符real op，,x:=yi*j 其中x、y為實型；i、j為整型。這個賦值句產(chǎn)生的三地址代碼為： T1:=i int* j T3:=inttoreal T1 T2:=y real+ T3 x:=T2,關于產(chǎn)生式EE1 E2 的語義動作, 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 e

23、lse if E1.type=real and E2.type=real then begin emit (E.place := E 1.place real+ 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=intege

24、r then begin u:=newtemp; emit (u := inttoreal E 2.place); emit (E.place := E 1.place real+ u); E.type:=real end else E.type:=type_error,7.3.3 記錄中域的引用,符號表表項之中保存記錄中的域的類型和相對地址信息,7.4 布爾表達式的翻譯,布爾表達式的兩個基本作用: 用于邏輯演算,計算邏輯值; 用于控制語句的條件式. 產(chǎn)生布爾表達式的文法: EE or E | E andE | E | (E) | i rop i | i,計算布爾表達式通常采用兩種方法: 1.

25、 如同計算算術表達式一樣,一步步算 1 or (not 0 and 0) or 0 =1 or (1 and 0) or 0 =1 or 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) 第二種翻

26、譯法適合于作為條件表達式的布爾表達式使用.,7.4.1 數(shù)值表示法,a or b and not c 翻譯成 T1:=not c T2:=b and T1 T3:=a or T1 ab的關系表達式可等價地寫成 if ab then 1 else 0 ，翻譯成 100:if ab goto 103 101:T:=0 102:goto 104 103:T:=1 104:,關于布爾表達式的數(shù)值表示法的翻譯模式,過程emit將三地址代碼送到輸出文件中 nextstat給出輸出序列中下一條三地址語句的地址索引 每產(chǎn)生一條三地址語句后，過程emit便把nextstat加1,關于布爾表達式的數(shù)值表示法的翻譯

27、模式,EE1 or E2 E.place:=newtemp; emit(E.place := E 1.place 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,關于布爾表達式的數(shù)值表示法的翻譯模式,Eid1 relop id2 E.place:=newtemp; emit(if id1.place relop. op

28、id2. place goto nextstat+3); emit(E.place := 0); emit(goto nextstat+2); emit(E.place:= 1) Eid E.place:=id.place ,ab 翻譯成 100:if ab goto 103 101:T:=0 102:goto 104 103:T:=1 104:,布爾表達式ab or cd and ef的翻譯結果,100:if ab goto 103 101:T1:=0 102:goto 104 103:T1:=1 104:if cd goto 107 105:T2:=0 106:goto 108 107:

29、T2:=1 108: if ef goto 111 109: T3:=0 110: 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;

30、emit(E.place := E 1.place or E2.place) EE1 and E2 E.place:=newtemp; emit(E.place := E 1.place and E2.place) ,7.4.2 作為條件控制的布爾式翻譯,條件語句 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:,例：把語句: if ac or b c goto L2 “真”出口 goto L1 L1:if bd

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

32、1.false :) | E2.code,產(chǎn)生布爾表達式三地址代碼的語義規(guī)則,產(chǎn)生式語義規(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)生布爾表達式三地址代碼的語義規(guī)則,產(chǎn)生式語義規(guī)則 Enot E1 E1.true:=E.false; E1.false:=E.true; E.code:=E1.code E (E1) E1.true:=E.true; E1.false:=E.fal

33、se; E.code:=E1.code,產(chǎn)生布爾表達式三地址代碼的語義規(guī)則,產(chǎn)生式語義規(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),考慮如下表達式： ab or cd and ef假定整個表達式的真假出口已分別置為Ltrue和Lfalse，則按定義將生成如下的代碼：,if ab goto Ltrue goto L1 L1:if

34、 cd goto L2 goto Lfalse L2:if ef goto Ltrue goto Lfalse,布爾表達式的翻譯,兩遍掃描 為給定的輸入串構造一棵語法樹； 對語法樹進行深度優(yōu)先遍歷，進行語義規(guī)則中規(guī)定的翻譯。 一遍掃描,一遍掃描實現(xiàn)布爾表達式的翻譯,采用四元式形式 把四元式存入一個數(shù)組中，數(shù)組下標就代表四元式的標號 約定 四元式(jnz, a, -, p) 表示 if a goto p 四元式(jrop, x, y, p)表示 if x rop y goto p 四元式(j, -, -, p) 表示 goto p,有時,四元式轉(zhuǎn)移地址無法立即知道,我們只好把這個未完成的四元式地

35、址作為E的語義值保存,待機回填。,為非終結符E賦予兩個綜合屬性E.truelist和E.falselist。它們分別記錄布爾表達式E所應的四元式中需回填“真”、“假”出口的四元式的標號所構成的鏈表 例如:假定E的四元式中需要回填真出口的p，q，r三個四元式，則E.truelist為下列鏈: (p) (x， x，x，0) (q) (x，x，x，p) (r) (x，x，x，q),鏈尾,E. truelist =r,為了處理E.truelist和E.falselist ，引入下列語義變量和過程: 變量nextquad，它指向下一條將要產(chǎn)生但尚未形成的四元式的地址(標號)。nextquad的初值為1，

36、每當執(zhí)行一次emit之后，nextquad將自動增1。 函數(shù)makelist(i)，它將創(chuàng)建一個僅含i的新鏈表，其中i是四元式數(shù)組的一個下標(標號)；函數(shù)返回指向這個鏈的指針。 函數(shù)merge(p1,p2)，把以p1和p2為鏈首的兩條鏈合并為一，作為函數(shù)值，回送合并后的鏈首。 過程backpatch(p, t)，其功能是完成“回填”，把p所鏈接的每個四元式的第四區(qū)段都填為t。,布爾表達式的文法,(1) EE1 or M E2 (2) | E1 and M E2 (3) | not E1 (4) | (E1) (5) | id1 relop id2 (6) | id (7)M,布爾表達式的翻譯模

37、式,(7) M M.quad:=nextquad ,布爾表達式的翻譯模式,(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.truelist; E.falselist:=merge(E1.falselist,E2.falselist) ,布爾表達式的翻譯模式,(3) Enot E1

38、 E.truelist:=E1.falselist; E.falselist:=E1.truelist (4) E(E1) E.truelist:=E1.truelist; E.falselist:=E1. falselist,布爾表達式的翻譯模式,(5) Eid1 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) (6) Eid E.truelist:=makelist

39、(nextquad); E.falselist:=makelist(nextquad+1); emit(jnz , id .place , ,0)； emit( j, -, -, 0) ,布爾表達式的翻譯模式,作為整個布爾表達式的真假出口(轉(zhuǎn)移目標)仍待回填.,利用翻譯方案翻譯布爾表達式 ab or cd and ef,E,E,E,a b,c d,e f,or,M,E,and,M,E,.t=100 .f=101,100：if ab goto 101：goto ,.q=102,.t=102 .f=103,102：if cd goto 103：goto ,.q=104,.t=104 .f=105,

40、104：if ef goto 105：goto ,104,.t=104 .f=103, 105,102,.t=100, 104 .f=103, 105,假定變量nextquad的初值為100,ab or cd and ef,100(j, a, b, 0) 101(j, -, -, 102) 102(j, c, d, 104) 103(j, -, -, 0) 104(j, e, f, 100) truelist 105(j, -, -, 103) falselist,7.5 控制語句的翻譯,考慮下列產(chǎn)生式所定義的語句 S if E then S1 | if E then S1 else S2 |

41、 while E do S1 其中E為布爾表達式。,if-then語句 S if E then S1,E.code,S1.code,To E.true,To E.false,E.true:,E.false:,if-then語句的屬性文法,產(chǎn)生式語義規(guī)則 Sif E then S1 E.true:=newlabel; E.flase:=S.next; S1.next:=S.next S.code:=E.code | gen(E.true :) | S1.code,if-then-else語句 S if E then S1 else S2,E.code,S1.code,S2.code,To E.t

42、rue,To E.false,goto S.next,S.next,E.true:,E.false:,if-then-else語句的屬性文法,產(chǎn)生式 語義規(guī)則 Sif E then S1 else S2 E.true:=newlabel; E.false:=newlabel; S1.next:=S.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語句 S while E do S1,E.code,S1.code

43、,To E.true,To E.false,goto S.begin,S.begin:,E.true:,E.false:,while-do語句的屬性文法,產(chǎn)生式語義規(guī)則 Swhile E do S1S.begin:=newlabel; E.true:=newlabel; E.false:=S.next; S1.next:=S.begin; S.code:=gen(S.begin :) | E.code | gen(E.true :) | S1.code | gen(goto S.begin),考慮如下語句 :while ab doif cd thenx:=y+z else x:=y-z,生成下

44、列代碼： L1:if ab goto L2 goto Lnext L2:if cd goto L3 goto L4 L3:T1:=y+z x:=T1 goto L1 L4:T2:=y-z x:=T2 goto L1 Lnext:,一遍掃描翻譯控制流語句,考慮下列產(chǎn)生式所定義的語句: (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表示語句， L表示語句表， A為賦值語句，E為一個布爾表達式,if 語句的翻譯 相關產(chǎn)生式 S if E

45、then S(1) | if E then S(1) else S(2) 改寫后產(chǎn)生式 S if E then M S1 S if E then M1 S1 N else M2 S2 M N,翻譯模式: 1. Sif 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.next

46、list:=merge(S1.nextlist, N.nextlist, S2.nextlist) 3. M M.quad:=nextquad 4. N N.nextlist:=makelist(nextquad); emit(j,) ,while 語句的翻譯 相關產(chǎn)生式 S while E do S(1) 翻譯為：,E的代碼,S (1)的代碼,“真”出口,“假”出口,為了便于回填，改寫產(chǎn)生式為: Swhile M1 E do M2 S1 M,翻譯模式: 1. Swhile M1 E do M2 S1 backpatch(S1.nextlist, M1.quad); backpatch(E.t

47、ruelist, M2.quad); S.nextlist:=E.falselist emit(j, M1.quad) 2. M M.quad:=nextquad ,產(chǎn)生式 LL;S 改寫為： LL1; M S M,翻譯模式: 1. LL1; M S backpatch(L1.nextlist, M.quad); L.nextlist:=S.nextlist 2. M M.quad:=nextquad ,其它幾個語句的翻譯 1. Sbegin L end S.nextlist:=L.nextlist 2. SA S.nextlist:=makelist( ) 3. LS L.nextlist:

48、=S.nextlist ,A1的代碼,例：,if ab or cd and ef then A1 else A2; while ab do A3,if 語句的代碼,while 語句的代碼,E的代碼,A1的代碼,A2的代碼,E的代碼,A3的代碼,100：if ab goto 101：goto 102 102：if cd goto 104 103：goto 104：if ef goto 105：goto ,127：if ab goto 128：goto ,106： . 115：,116：goto ,117： . 126：,A2的代碼,106,106,117,117,129： . 138：,A3的代

49、碼,129,139：goto 127,127,.n=116,翻譯語句while (ab) doif (cd) then x:=y+z;,P190 (5) Eid1 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(); if pnil then emit(p := E.place) else error EE1+

50、E2 E.place:=newtemp; emit(E.place := E1.place + E2.place),P195 Sif E then 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 ,翻譯語句while (ab) doif (cd) then x:=y+z;,100(j, a, b, 102) 101(j, -, -,