1、第七章 語(yǔ)義分析和 中間代碼產(chǎn)生,概述,靜態(tài)語(yǔ)義檢查 類型檢查 控制流檢查 一致性檢查 相關(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ǔ) 言程序,內(nèi)容線索,中間語(yǔ)言 說(shuō)明語(yǔ)句 賦值語(yǔ)句的翻譯 布爾表達(dá)式的翻譯 控制語(yǔ)句的翻譯 過(guò)程調(diào)用的處理,中間語(yǔ)言,常用的中間語(yǔ)言 后綴式，逆波蘭表示 圖表示 DAG 抽象語(yǔ)法樹(shù) 三地址代碼 三元式 四元式 間接三元式,后綴式,后綴式表示法：Lu

2、kasiewicz發(fā)明的一種表示表達(dá)式的方法，又稱逆波蘭表示法。 一個(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)算符就把它作用

3、于棧頂?shù)膋個(gè)項(xiàng)，并用運(yùn)算結(jié)果代替這k個(gè)項(xiàng)。,把表達(dá)式翻譯成后綴式的語(yǔ)義規(guī)則描述,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 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,

4、+,c,+,圖表示法,DAG 抽象語(yǔ)法樹(shù),DAG,有向無(wú)循環(huán)圖(Directed Acyclic Graph，簡(jiǎn)稱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+a*(b-c)+(b-c)*d的圖表示法,+,a,*,-,b,d,c,*,+,后綴表達(dá)式：aabc-*+bc- d *+,抽象語(yǔ)法樹(shù),在語(yǔ)法樹(shù)中去掉那些對(duì)翻譯不必要的信息，從而獲得更有效的源程序中間表示。這種經(jīng)變換后的語(yǔ)法樹(shù)稱之為抽象語(yǔ)法樹(shù)(Abstract Syntax Tree),Sif B then S1 else

5、S2,3*5+4,建立表達(dá)式的抽象語(yǔ)法樹(shù),mknode (op,left,right) 建立一個(gè)運(yùn)算符號(hào)結(jié)點(diǎn)，標(biāo)號(hào)是op，兩個(gè)域left和right分別指向左子樹(shù)和右子樹(shù)。 mkleaf (id,entry) 建立一個(gè)標(biāo)識(shí)符結(jié)點(diǎn)，標(biāo)號(hào)為id，一個(gè)域entry指向標(biāo)識(shí)符在符號(hào)表中的入口。 mkleaf (num,val) 建立一個(gè)數(shù)結(jié)點(diǎn)，標(biāo)號(hào)為num，一個(gè)域val用于存放數(shù)的值。,建立抽象語(yǔ)法樹(shù)的語(yǔ)義規(guī)則,產(chǎn) 生 式 語(yǔ) 義 規(guī) 則 EE1+TE.nptr := mknode ( +, E1.nptr, T.nptr ) EE1-TE.nptr := mknode ( -, E1.nptr, T

6、.nptr ) ETE.nptr := T.nptr T (E)T.nptr := E.nptr TidT.nptr := mkleaf ( id, id.entry ) Tnum T.nptr := mkleaf ( num, num.val ),a4c的抽象語(yǔ)法樹(shù),E nptr,T nptr,E nptr,To entry for a,E,T nptr,id,-,T nptr,id,To entry for c,num,a:=b*(-c)+b*(-c)的圖表示法,產(chǎn)生賦值語(yǔ)句抽象語(yǔ)法樹(shù)的屬性文法,產(chǎn) 生 式語(yǔ)義規(guī)則 Sid:=ES.nptr:=mknode(assign, mkleaf(i

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

8、T2:=b*T1 T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5,a:=b*(-c)+b*(-c)的圖表示法,三地址語(yǔ)句的種類,x:=y op z x:=op 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

9、 | 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= ,三地址語(yǔ)句,四元式之間的聯(lián)系通過(guò)臨時(shí)變量實(shí)現(xiàn)。 單目運(yùn)算只用arg1域，轉(zhuǎn)移語(yǔ)句將目標(biāo)標(biāo)號(hào)放入result域。 arg1,arg2,result通常為指針，指向有關(guān)名字的符號(hào)表入口，且臨時(shí)變量填入符號(hào)表。,op arg1arg2

10、result (0) uminuscT1 (1) *bT1T2 (2) uminuscT3 (3) *bT3T4 (4) +T2T4T5 (5) :=T5a,四元式 一個(gè)帶有四個(gè)域的記錄結(jié)構(gòu)，這四個(gè)域分別稱為op, arg1, arg2及result,a:=b*(-c)+b*(-c),三地址語(yǔ)句,oparg1arg2 (0)uminusc (1)*b(0) (2)uminusc (3)*b(2) (4)+(1)(3) (5)assigna(4),三元式 通過(guò)計(jì)算臨時(shí)變量值的語(yǔ)句的位置來(lái)引用這個(gè)臨時(shí)變量 三個(gè)域：op、arg1和arg2,a:=b*(-c)+b*(-c),三地址語(yǔ)句,多目運(yùn)算的三

11、元式 例. 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)算的先后次序列出有關(guān)三元式在三元式表中的位置。 優(yōu)點(diǎn): 方便優(yōu)化，節(jié)省空間,例如，語(yǔ)句 X:=(A+B)*C; Y:=D(A+B) 的間接三元式表示如下表所示。,四元式、三元式和間接三元式比較,三元式中使用了指向三元式的指針，優(yōu)化時(shí)修改較難。 間接三元式優(yōu)化只需要更改間接碼表，并節(jié)省三元式表

12、存儲(chǔ)空間。 修改四元式表也較容易，只是臨時(shí)變量要填入符號(hào)表，占據(jù)一定存儲(chǔ)空間。,內(nèi)容線索,中間語(yǔ)言 說(shuō)明語(yǔ)句的翻譯 賦值語(yǔ)句的翻譯 布爾表達(dá)式的翻譯 控制語(yǔ)句的翻譯 過(guò)程調(diào)用的處理,概述,說(shuō)明部分中把定義性出現(xiàn)的標(biāo)識(shí)符與類型等屬性相關(guān)聯(lián),從而確定它們?cè)谟?jì)算機(jī)內(nèi)部的表示法、取值范圍及可對(duì)其進(jìn)行的運(yùn)算。 為了產(chǎn)生有效地可執(zhí)行目標(biāo)代碼，對(duì)于說(shuō)明部分的翻譯，不僅僅把與標(biāo)識(shí)符相關(guān)聯(lián)的類型等屬性填入符號(hào)表中，還必須考慮到標(biāo)識(shí)符所標(biāo)記的對(duì)象的存儲(chǔ)分配問(wèn)題。,常量定義的翻譯,C+語(yǔ)言中有常量定義，以關(guān)鍵字const為標(biāo)志，如 const float pi=3.1416， one=1.0 對(duì)每個(gè)常量定義的處理應(yīng)

13、包括下列工作： （1）把等號(hào)右邊的常量值登錄入常量表中（若之前尚未登錄）并回送常量表序號(hào)； （2）然后為等號(hào)左邊的標(biāo)識(shí)符建立符號(hào)表新條目，在該條目中填入常量標(biāo)志、相應(yīng)類型及常量表序號(hào)。,假定常量定義中不指明類型，類型直接由常量值本身確定，且等號(hào)右邊僅整數(shù)或常量標(biāo)識(shí)符。 常量定義及相應(yīng)翻譯方案 CONSTEDFconst CDT CDT CDT，CD CDT CD CD id=num num.ord:=lookCT(num.lexval) id.ord:=num.ord; id.type:=integer; id.kind:=CONSTANT add(id.entry, id.kind, id.

14、type, id.ord) CD id=id1 id.kind:=CONSTANT; id.type:=id1.type; id.ord:=id1.ord add(id.entry, id.kind, id.type, id.ord),lookCT(c)將在常量表中查找常量c，若查不到，則把給常量值登錄入常量表。最終回送常量c值在常量表中的序號(hào),過(guò)程add是對(duì)過(guò)程addtype的擴(kuò)充，它把種類、類型與序號(hào)三者填入符號(hào)表相應(yīng)條目中,變量說(shuō)明的翻譯,變量說(shuō)明部分由一組變量說(shuō)明語(yǔ)句組成，這里假定每個(gè)變量說(shuō)明語(yǔ)句中僅包含一個(gè)標(biāo)識(shí)符。 變量說(shuō)明部分的語(yǔ)法定義 P D; D D; D D id: T T

15、integer T real T arraynum of T1 T T1,變量說(shuō)明部分的翻譯 P D; offset:=0 D D; D D id: T enter(, T.type, offset); offset:=offset+T.width T integer T.type:=integer; T.width:=4 T real T.type:=real; T.width:=8 T arraynum of T1 T.type:=array(num.val, T1.type); T.width:=num.val*T1.width T T1 T.type=pointer(T1

16、.type); T.width:=4,文法轉(zhuǎn)換,P D; offset:=0 為了使得offset賦初值更明顯 變更為 P offset:=0 D; 也可采用增加非終結(jié)符號(hào)及產(chǎn)生式來(lái)實(shí)現(xiàn) P M D M offset:=0,保留作用域信息,過(guò)程（函數(shù)）定義的語(yǔ)法 P D; D D; D D id: T D proc id; D; S 過(guò)程及函數(shù)定義的翻譯必然涉及標(biāo)識(shí)符作用域問(wèn)題 基本思想：每個(gè)過(guò)程有一張獨(dú)立的符號(hào)表,T integer T real T arraynum of T1 T T1,過(guò)程示例 (1) Program sort(input, output) (2) var a: arr

17、ay0.10 of integer; (3) x: integer; (4) procedure readarray; (5) var i: integer; (6) begin a end readarray (7) procedure exchange(i, j:integer) (8) begin (9) x:=ai; ai:=aj; aj:=x (10) end exchange (11) procedure quicksort (m, n:integer); (12) var k, v: integer; (13) function partition (y,z: integer):

18、 integer; (14) var i,j: integer; (15) begin a (16) v (17) exchange(i, j); (18) end partition (19) begin end quicksort; (20) begin end sort.,語(yǔ)義規(guī)則中的操作 mktable(previous) ：創(chuàng)建一張新符號(hào)表，并返回指向新表的一個(gè)指針。 參數(shù)previous指向一張先前創(chuàng)建的符號(hào)表，其值放在新符號(hào)表表頭 enter(table, name, type, offset)：在指針table指示的符號(hào)表中為名字name建立一個(gè)新項(xiàng)，并把類型type、相對(duì)地址

19、offset填入到該項(xiàng)中。 addwidth(table, with)：指針table指示的符號(hào)表表頭中記錄下該表中所有名字占用的總寬度 enterproc(table, name, newtable)：在指針table指示的符號(hào)表中為名字為name的過(guò)程建立一個(gè)新項(xiàng)。 參數(shù)newtable指向過(guò)程name的符號(hào)表,翻譯 P M D; addwidth(top(tblptr), top(offset); pop(tblptr); pop(offset) M t:=mktable(nil); push(t, tblptr); push(0, offset) D D1; D2 D proc id;

20、 N D1; S t:=top(tblptr); addwidth(t,top(offset); pop(tblptr); pop(offset) enterproc(top(tblptr), , t) D id: T enter(top(tblptr), , T.type, top(offse); top(offset):=top(offset)+T.width N t:=mktable(top(tblptr); push(t, tblptr); push(0, offset),棧tblptr 保存各外層過(guò)程的符號(hào)表指針 棧offset 存放各嵌套過(guò)程的當(dāng)前相對(duì)地

21、址 棧頂元素為當(dāng)前被處理過(guò)程的下一個(gè)名字的相對(duì)地址,tblptr,offset,0,sort,nil,a,0,x,44,sort,44,48,readarray,sort,readarray,0,i,0,4,4,readarray,(1) Program sort(input, output) (2) var a: array0.10 of integer; (3) x: integer; (4) procedure readarray; (5) var i: integer; (6) begin a end readarray ,內(nèi)容線索,中間語(yǔ)言 說(shuō)明語(yǔ)句的翻譯 賦值語(yǔ)句的翻譯 布爾表達(dá)式

22、的翻譯 控制語(yǔ)句的翻譯 過(guò)程調(diào)用的處理,賦值語(yǔ)句的翻譯,簡(jiǎn)單算術(shù)表達(dá)式及賦值語(yǔ)句 簡(jiǎn)單算術(shù)表達(dá)式及賦值語(yǔ)句翻譯為三地址代碼的翻譯模式 屬性 表示id所代表的名字本身 過(guò)程lookup()檢查是否在符號(hào)表中存在相應(yīng)此名字的入口。如果有，則返回一個(gè)指向該表項(xiàng)的指針，否則，返回nil表示沒(méi)有找到 過(guò)程emit將生成的三地址語(yǔ)句發(fā)送到輸出文件中,產(chǎn)生賦值語(yǔ)句三地址代碼的翻譯模式,Sid:=E p:=lookup(); if pnil then emit(p := E.place) else error EE1+E2 E.place:=newtemp; emit

23、(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) EE1*E2 E.place:=newtemp; E.code:=E1.code | E2.code | gen(E.place :

24、= E1.place * E2.place),E-E1 E.place:=newtemp; 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

25、.code= ,類型轉(zhuǎn)換,用E.type表示非終結(jié)符E的類型屬性 對(duì)應(yīng)產(chǎn)生式EE1 op E2的語(yǔ)義動(dòng)作中關(guān)于E.type的語(yǔ)義規(guī)則可定義為： if E1.type=integer and E2.type=integer E.type:=integer else E.type:=real 進(jìn)行類型轉(zhuǎn)換的三地址代碼 x:= inttoreal y 算符區(qū)分為整型算符int op和實(shí)型算符real op， 例. x:=yi*j 其中x、y為實(shí)型；i、j為整型。這個(gè)賦值句產(chǎn)生的三地址代碼為： T1:=i int* j T3:=inttoreal T1 T2:=y real+ T3 x:=T2,關(guān)于產(chǎn)

26、生式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 real+ E 2.place); E.type:=real end,else if E1.type=integer and E2.type=real

27、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 1.place real+ u); E.type:=real end else E.type:=type_error,內(nèi)容線索,中間語(yǔ)言 說(shuō)明語(yǔ)句的

28、翻譯 賦值語(yǔ)句的翻譯 布爾表達(dá)式的翻譯 控制語(yǔ)句的翻譯 過(guò)程調(diào)用的處理,布爾表達(dá)式的翻譯,布爾表達(dá)式：用布爾運(yùn)算符把布爾量、關(guān)系表達(dá)式聯(lián)結(jié)起來(lái)的式子。 布爾運(yùn)算符：and, or, not ； 關(guān)系運(yùn)算符 , ， , 布爾表達(dá)式的兩個(gè)基本作用: 用于邏輯演算,計(jì)算邏輯值; 用于控制語(yǔ)句的條件式. 產(chǎn)生布爾表達(dá)式的文法: EE or E | E andE | E | (E) | id rop id | id 運(yùn)算符優(yōu)先級(jí)：布爾運(yùn)算由高到低:not and or，同級(jí)左結(jié)合 關(guān)系運(yùn)算符同級(jí)，且高于布爾運(yùn)算符,計(jì)算布爾表達(dá)式通常采用兩種方法: （1） 如同計(jì)算算術(shù)表達(dá)式一樣,一步步算 1 or (n

29、ot 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,對(duì)應(yīng)的，有兩種布爾表達(dá)式翻譯方法,數(shù)值表示法,a or b and not c 翻譯成 T1:=not c T2:=b and T1 T3:=a or T1 ab的關(guān)系表達(dá)式可等價(jià)地寫成 if ab then 1 else 0 ，翻譯成 100:if

30、ab goto 103 101:T:=0 102:goto 104 103:T:=1 104:,數(shù)值表示法的翻譯模式,過(guò)程emit將三地址代碼送到輸出文件中 nextstat：給出輸出序列中下一條三地址語(yǔ)句的地址索引 每產(chǎn)生一條三地址語(yǔ)句后，過(guò)程emit便把nextstat加1,數(shù)值表示法的翻譯模式,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.pla

31、ce:=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 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

32、 103:T:=1 104:,布爾表達(dá)式ab or cd and ef的翻譯結(jié)果,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: 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; emit(E.place := E 1.place or E2.place) EE1 and E2 E.place:=newtemp; emit(E.place := E 1.place and E2.place) ,作為條件控制的布爾式翻譯,條件語(yǔ)句 if E then