第七章——語義分析和中間代碼生成

1、第七章 語義分析和中間代碼生成靜態(tài)語義檢查n類型檢查。驗證程序中執(zhí)行的每個操作是否遵守語言的類型系統(tǒng)的過程.，編譯程序必須報告不符合類型系統(tǒng)的信息。 n控制流檢查?？刂屏髡Z句必須使控制轉(zhuǎn)移到合法的地方。例如，在C語言中break語句使控制跳離包括該語句的最小while、for或switch語句。如果不存在包括它的這樣的語句，則報錯。 n一致性檢查。在很多場合要求對象只能被定義一次。例如Pascal語言規(guī)定同一標識符在一個分程序中只能被說明一次，同一case語句的標號不能相同，枚舉類型的元素不能重復(fù)出現(xiàn)等等。n相關(guān)名字檢查。有時，同一名字必須出現(xiàn)兩次或多次。例如，Ada 語言程序中，循環(huán)或程序塊

2、可以有一個名字，出現(xiàn)在這些結(jié)構(gòu)的開頭和結(jié)尾，編譯程序必須檢查這兩個地方用的名字是相同的。中間語言常見的中間語言的形式：n后綴式（逆波蘭式）n三地址代碼 三元式 四元式 間接三元式nDAG圖后綴式n又稱逆波蘭表示法，把運算量（操作數(shù)）寫在前面，把算符寫在后面（后綴）。 如：ab 寫成 ab ab*c 寫成 abc*+n定義：1.如果表達式E是一個變量或常量，則E的后綴式是E自身；2.如果E是E1 op E2形式的表達式 (op為二元操作符) ，則E的后綴式為E1E2op。E1 、E2分別為E1、E2的后綴式；3.如果E式(E1)形式的表達式，則E1的后綴式就是E的后綴式。這種表達式不需要括號這種

3、表達式不需要括號n如a*(b+c) 寫成 (a+b)*(c+d) 寫成 abc*abcd*+a*bc+*cdab將表達式翻譯為后綴式的語義規(guī)則nE.code表示E的后綴式，op為二元操作符，“|”表示后綴形式的連接。產(chǎn)生式語義規(guī)則EE1 op E2E(E)EidE.code:=E1.code|E2.code|opE.code:=E1.codeE.code:=id圖表示法 DAG 抽象語法樹nDAG: 無循環(huán)有向圖。對表達式的每個子表達式，DAG中都有一個結(jié)點。一個內(nèi)部結(jié)點代表一個操作符，它的孩子代表操作數(shù)。n在一個DAG圖中，代表公共子表達式的結(jié)點具有多個父結(jié)點。如表達式a+a*(b-c)+(

4、b-c)*d的DAG圖為：+*d*abc又如 a:=b*-c+b*-cassignuminus*abcassignuminus*abcuminus*bcDAG圖抽象語法樹一目“”運算符用uminus或表示，用以和二目“”運算符區(qū)分。a:=b*-c+b*-c的抽象語法樹可表示為：assign ida*idbidbuminus uminus idcidc或0idb1idc2uminus13*024idb5idc6uminus57*468379ida10assign9811三地址代碼n三地址代碼是由下面一般形式的語句構(gòu)成的序列：X :=Y op Z。其中，X,Y,Z為名字，常數(shù)或編譯時產(chǎn)生的臨時變量

5、，op代表運算符號。 每個語句右邊只能有一個運算符。n如：x+y*z 可翻譯為：T1 :y*zT2 :x+T1T1，T2為編譯時產(chǎn)生的臨時變量。a:=b*-c+b*-c的三地址代碼為：T1 : -cT2 :b*T1T3 : -cT4 :b*T3T5 :T2 +T4a : T5 assignuminus*abcuminus*bc對于抽象語法樹的代碼a:=b*-c+b*-c的三地址代碼為：T1 : -cT2 :b*T1T5 :T2 +T2a : T5 對于DGA的代碼assignuminus*abca:=b*-c+b*-c的三地址代碼為：T1 : -cT2 :b*T1T3 : -cT4 :b*T3

6、T5 :T2 +T4a : T5 對于抽象語法樹的代碼T1 : -cT2 :b*T1T5 :T2 +T2a : T5 對于DGA的代碼三地址語句的種類nX :=Y op ZnX := op YnX :=Yngoto Lnif x relop y goto L 或if a goto Ln用于過程調(diào)用的param x 和call p，n及return ynx :=yi 及 xi :=ynx :=&y， x :=*y， *x :=y四元式n帶有四個記錄域：op，arg1，arg2，result。n一元運算符不用arg2n條件或無條件轉(zhuǎn)移語句將目標標號置于resultnparam類運算符僅使用

7、arg1域如a:=b*-c+b*-coparg1 arg2result(0)(1)(2)(3)(4)(5)T1 : -cT2 :b*T1T3 : -cT4 :b*T3T5 :T2 *T4 a : T5uminus C T1 * b T1 T2uminus C T3 * b T3 T4 + T2 T4 T5:= T5a三元式n帶有三個記錄域：op，arg1，arg2。n對一目運算符arg1，arg2只用其一，多目運算符可用若干相繼三元式表示。n如：xi :=y x := yi (0) (= ，x，i)(1) (:=，(0)，y)(0) ( =，y，i)(1) (:=，x，(0)( =，y，xi)

8、 /變址存數(shù)四元式(= ，yi ，x) /變址取數(shù)四元式n如a:=b*-c+b*-coparg1arg2result(0)(1)(2)(3)(4)(5)uminus C T1 * b T1 T2uminus C T3 * b T3 T4 + T2 T4 T5:= T5aoparg1arg2(0)(1)(2)(3)(4)(5)四元式三元式uminus C * b (0)uminus C * b (2) + (1) (3) := a (4) 間接三元式n不直接使用三元式，而是另設(shè)一張指示器（稱為間接碼表），它將按運算的先后順序列出有關(guān)三元式在三元式表中的位置。n如： X:=(A+B)*C Y:=D

9、*(A+B) 表示為：oparg1arg2(1)(2)(3)(4)(5)三元式表 A B * (1) C * D (1) := X (2) := Y (4) 間接代碼（1）（2）（3）（1）（4）（5）當要調(diào)整運算順序時，只需要重新安排間接碼表。說明語句n說明語句的翻譯模式 PD offset:=0 DD;D Did:T enter(,T.type,offset); offset:=offset+T.width Tinteger T.type:=integer T.width:=4 Treal T.type:=real T.width:=8 Tarraynum of T1 T.t

10、ype:=array(num.val,T1.type); T.width:=num.valT1.width TT1 T.type:=pointer(T1.type); T.width:=4賦值語句的翻譯1.簡單算術(shù)表達式和賦值語句S id := 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(E.place“:=” E1.

11、place“*”E2.place)E - E1 E.place:=newtemp; emit(E.place“:=”“uminus” E1.place)E( E1) E.place:= E1.placeEid E.place:=newtemp; P:=lookup(); if Pnil then E.place:=P else error數(shù)組元素的引用n數(shù)組在存儲器中的存放方式?jīng)Q定了數(shù)組元素的地址計算法。若數(shù)組存放在一片連續(xù)單元。假設(shè)A每個元素寬度為w，則Ai的起始地址為： base(i-low)wiw(base-loww)多維數(shù)組：按列存放 按行存放A1,1A2,1A1,2A2

12、,2記為C，可在數(shù)組說明時計算出來A1,1A1,2A2,1A2,2多維數(shù)組的地址計算n二維數(shù)組若按行存放：Ai1,i2的相對地址為： (i1n2)+i2)w+(base-(low1n2)+low2)wn將數(shù)組元素加入賦值語句后的翻譯模式n在算術(shù)表達式中，當有兩種不同類型的量進行運算時，如整型量和實型量，規(guī)定首先必須把整型轉(zhuǎn)換成實型。在編譯時可確定S L:= E if L.offset=null then emit( L.place“:=”E.place) else emit( L.place L.offset :=E.place)EE1+E2 E.place := newtemp; emit(

13、E.place := E1.place + E2.place)E( E1) E.place:= E1.placeEL if L.offset=null then E.place:=L.place; else begin E.place := newtemp; emit(E.place := L.place L.offset ) endLElist L.place := newtemp; emit(L.place := Elist.arrayC L.offset := newtemp; emit(L.offset := w *Elist.place) Lid L.place:= id.place

14、; L.offset := null Elist Elist1,E 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 := mElist idE Elist.place := E.place; Elist.ndim := 1; Elist.array := id.place x:=Ay,z設(shè)A為1020的數(shù)組，w4，則x

15、:=Ay,z的三地址語句序列為：T1:=y*20T1:=T1+zT2:=A-84T3:=4*T1T4:=T2T3X:=T484=C=(1201)4設(shè)A為1020的數(shù)組，w4，則 Ay,z := x 的三地址語句序列為：T1:=y*20T1:=T1+zT2:=A-84T3:=4*T1T2T3:= X布爾表達式的翻譯n布爾表達式的兩個基本作用： 用于計算邏輯值 用于控制流語句中的條件表達式n布爾表達式是用布爾運算符號(and,or,not)作用到布爾變量或關(guān)系表達式上組成的。n關(guān)系表達式：E1 relop E2 relop為關(guān)系運算符n規(guī)定優(yōu)先級not，and，or依次降低。布爾表達式的翻譯n如同

16、計算算術(shù)表達式，一步步計算 如：1 and (0 or 1) and not 0 =1 and 1 and 1 =1 and 1 =1n采取某種優(yōu)化措施如：A or B 若A為1，則不用計算B,可知結(jié)果為1可以if-then-else來解釋 A or B if A then true else B A and B if A then B else true not A if A then false else true 數(shù)值表示法na or b and not c 翻譯為三地址序列： T1:= not c T2:= b and T1 T3:= a or T2n關(guān)系表達式ab，可理解為 if a

17、b then 1 else 0，翻譯為三地址序列： (1) if ab goto (4) (2) t:=0 (3) goto (5) (4) t:=1 (5) 后繼語句布爾表達式的翻譯模式EE1 or E2 E.place:= newtemp; emit(E.place“:=” E1.place “or” E2.place)EE1 and E2 E.place:= newtemp; emit(E.place“:=” E1.place “and” E2.place)E not E1 E.place:=newtemp; emit(E.place “:=” “not” E1.place)E( E1)

18、 E.place:= E1.placeEid1 relop id2 E.place:=newtemp; emit(ifid1.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例：布爾表達式ab or cd and ef (1) if ab goto (4) (2) T1:=0 (3) goto (5) (4) T1:=1 (5) if cd goto (8) (6) T2:=0 (7) goto (9

19、) (8) T2:=1 (9) if ab goto (12) (10) T3:=0 (11) goto (13) (12) T3:=1 (13) T4:=T2 and T3 (14) T5:=T1 or T4作為條件控制的布爾表達式n條件語句 if E then S1 else S2，作為轉(zhuǎn)移條件的布爾表達式E，可賦予它兩個出口，一個為“真”出口，出向S1；一個為“假”出口，出向S2。 如： if (ab) then x:=x+1 if ab goto E.true goto E.false (+,x,1,T1) (:=,T1,-,x)(1) ( jc or bc goto L2 goto

20、L1 L1: if bd goto L2 goto L3 L2: S1產(chǎn)生的三地址代碼序列 goto Lnext L3: S2產(chǎn)生的三地址代碼序列 Lnext: 后繼語句產(chǎn)生布爾表達式三地址代碼的語義規(guī)則產(chǎn)生式語義規(guī)則EE1 or E2E1.true:= E.true;E1.false:=newlable;E2.true:= E.true;E2.false:= E.false;E.code:=E1.code|gen(E1.false”:”)|E2.codeEE1 and E2E1.true:= newlable;E1.false:= E.false;E2.true:= E.true;E2.fa

21、lse:= E.false;E.code:=E1.code|gen(E1.true”:”)|E2.codeEnot E1E1.true:= E.false;E1.false:= E.true;E.code:= E1.code;n例：ab or cd and ef if ab goto Ltrue goto L1 L1: if cd goto L2 goto Lfalse L2: if ef goto Ltrue goto Lfalse用四元式實現(xiàn)三地址代碼n(jnz，a，p)表示if a goto pn(jrop，x，y，p)表示if x rop y goto pn(j，p)表示 goto p

22、n記錄需回填地址的四元式，把需回填E.true的四元式拉成一鏈，把需回填E.false的四元式拉成一鏈，分別稱做“真”鏈和“假”鏈。（10）goto E.true （20） goto E.true （30） goto E.true則鏈成（10） goto （0） （20） goto （10） （30） goto （20）把地址（30）稱作“真”鏈鏈首，0為鏈尾標志，即地址（10）為“真”鏈鏈尾。語義描述使用的變量和過程：語義描述使用的變量和過程： E.truelist ： “真真”鏈，鏈， E.falselist ： “假假”鏈鏈 。 Nextquad： makelist(i)：下一條將要產(chǎn)生

23、但尚未形成的四元式的地址下一條將要產(chǎn)生但尚未形成的四元式的地址 emit( )： 輸出一條四元式輸出一條四元式 merge(p1, p2)： 把把 p1的鏈首填在的鏈首填在p2 的鏈尾的鏈尾例：例： merge(p1, p2)(p10) goto ( 0) p1 鏈鏈 (p100) goto (p10)(p1) goto (p100)(p20) goto( 0) p2 鏈鏈 (p200) goto (p20)(p2) goto (p200) backpatch(p,t)把把鏈首鏈首p所鏈接的每個四元式的第四區(qū)段都填為所鏈接的每個四元式的第四區(qū)段都填為t創(chuàng)建一個僅含創(chuàng)建一個僅含i i的新鏈表，的

24、新鏈表，i i是四元式的標號是四元式的標號語句語句 if ab or cd and ef then S1 else S2的四元式的四元式(1) if ab goto (7) (E.true ) (1)和和(5）(2) goto (3) 拉鏈拉鏈（真）（真）(3) if cd goto (5)(4) goto (p+1)(E.false)(4) 和和(6)(5) if ef goto (7)拉鏈拉鏈（假）（假）(6) goto (p+1)(7)( S1的四元式的四元式 (p-1) ）(p) goto (q)(p+1) (S2的四元式的四元式(q-1) ）(q)自下而上分析中的一種翻譯方案：自下而

25、上分析中的一種翻譯方案：(1) EE1 or ME2 backpatch(E1.falselist, M.quad); E.truelist:=merge(E1.truelist, E2.truelist) E.falselist:= E2.falselist(2) EE1 and ME2 backpatch(E1.truelist, M.quad); E.truelist:= E2.truelist; E.falselist:= merge(E1.falselist,E2.falselist);(3) Enot E1 E.truelist:= E1.falselist; E.falselis

26、t:= E1.truelist(4) E(E1) E.truelist:= E1.truelist; E.falselist:= E1.falselist (5) Eid1 rop id2 E.truelist:=makelist(nextquad); E.false:= makelist(nextquad+1); emit(j rop , id1.place , id2.place , 0 ); emit(j,-,-,0 ) (6) Eid E.truelist:= makelist(nextquad); E.false:= makelist(nextquad+1); emit (jnz ,

27、 id.place , , 0 ); emit(j,-,-,0 ) (7) M M.quad:= nextquad例： ab or cd and efab: (1) ( j,a,b,_ ) (2) ( j,-,-,_)cd: (3) ( j,c,d,_ ) (4) ( j,-,-,_ )ef: (5) ( j,e,f,_ ) (6) ( j,-,-,_ ) (3) ( j,c,d,(5) ) (4) ( j,-,-,_ )E.true (5) ( j,e,f,_ ) (6) ( j,-,-,(4) )相同出口(1) ( j,a,b,_ )(2) ( j,-,-,(3) ) (3) ( j,c,

28、d,(5) ) (4) ( j,-,-,_ ) (5) ( j,e,f,_ ) (6) ( j,-,-,(4) )E.trueE.falseE.true控制流語句nIf-then,if-then-else,while-don文法：Sif E then S1 | if E then S1 else S2 | while E do S1E.codeS1.codeE.trueE.falseE.trueE.falseifthenE.codeS1.codegoto S.nextS2.codeE.trueE.falseE.trueE.falseS.nextifthenelseE.codeS1.codego

29、to S. beginE.trueE.falseE.trueE.falseS. beginwhiledon如while ab do if cd then x:=yz else x:=y-z翻譯為：L1: if ab goto L2 goto LnextL2: if cd goto L3 goto L4L3: T1:=y+z x:=T1 goto L1L4: T2:=y-z x:=T2 goto L1Lnext: 后繼語句翻譯模式為：用四元式實現(xiàn)三地址代碼例：nwhile (ab) do if (cd) then x:=y+z nbegin while (ab) do x:=x+y x:=x+z end用四元式實現(xiàn)三地址代碼標號與goto語句n帶標號的語句形式：L:S 當該語句被處理之后，標號L