第七章語義分析和中間代碼產(chǎn)生

1、國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室第七章第七章 語義分析和中間代碼產(chǎn)生語義分析和中間代碼產(chǎn)生n靜態(tài)語義檢查靜態(tài)語義檢查類型檢查類型檢查控制流檢查控制流檢查一致性檢查一致性檢查 相關(guān)名字檢查相關(guān)名字檢查名字的作用域分析名字的作用域分析 語法分語法分析器析器中間代碼中間代碼產(chǎn)生器產(chǎn)生器靜態(tài)檢靜態(tài)檢查器查器中間代碼中間代碼優(yōu)化器優(yōu)化器國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室n中間語言中間語言(復(fù)雜性界于源語言和目標(biāo)語言復(fù)雜性界于源語言和目標(biāo)語言之間之間)的好處：的好處：便于進(jìn)行與機器無關(guān)的代碼優(yōu)化工作便于進(jìn)行與機器無關(guān)的代碼優(yōu)化工作 易于移植易于移植使編譯程

2、序的結(jié)構(gòu)在邏輯上更為簡單明確使編譯程序的結(jié)構(gòu)在邏輯上更為簡單明確 源語言源語言程序程序目標(biāo)語目標(biāo)語言程序言程序中間語中間語言程序言程序compilerfront endcompilerback end國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室n常用的中間語言：常用的中間語言：后綴式，逆波蘭表示后綴式，逆波蘭表示圖表示：圖表示： dag、抽象語法樹、抽象語法樹三地址代碼三地址代碼n三元式三元式n四元式四元式n間接三元式間接三元式7.1 中間語言中間語言 國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室7.1.1 7.1.1 后綴式后綴式 n后綴式后綴式表示法：表示法：l

3、ukasiewicz發(fā)明的一種表示發(fā)明的一種表示表達(dá)式的方法，又稱表達(dá)式的方法，又稱逆波蘭逆波蘭表示法。表示法。n一個表達(dá)式一個表達(dá)式e的后綴形式可以如下定義：的后綴形式可以如下定義：1. 如果如果e是一個變量或常量，則是一個變量或常量，則e的后綴式是的后綴式是e自身。自身。2. 如果如果e是是e1 op e2形式的表達(dá)式，其中形式的表達(dá)式，其中op是任是任何二元操作符，則何二元操作符，則e的后綴式為的后綴式為e1 e2 op，其，其中中e1 和和e2 分別為分別為e1 和和e2的后綴式。的后綴式。3. 如果如果e是是(e1)形式的表達(dá)式，則形式的表達(dá)式，則e1 的后綴式就的后綴式就是是e的后

4、綴式。的后綴式。國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室n逆波蘭表示法不用括號。只要知道每個逆波蘭表示法不用括號。只要知道每個算符的目數(shù)，對于后綴式，不論從哪一算符的目數(shù)，對于后綴式，不論從哪一端進(jìn)行掃描，都能對它進(jìn)行唯一分解。端進(jìn)行掃描，都能對它進(jìn)行唯一分解。n后綴式的計算后綴式的計算用一個棧實現(xiàn)。用一個棧實現(xiàn)。一般的計算過程是：自左至右掃描后綴式，一般的計算過程是：自左至右掃描后綴式，每碰到運算量就把它推進(jìn)棧。每碰到每碰到運算量就把它推進(jìn)棧。每碰到k目運目運算符就把它作用于棧頂?shù)乃惴桶阉饔糜跅ｍ數(shù)膋個項，并用運算個項，并用運算結(jié)果代替這結(jié)果代替這k個項個項。國防科技大

5、學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室把表達(dá)式翻譯成后綴式的語義規(guī)則描述把表達(dá)式翻譯成后綴式的語義規(guī)則描述 產(chǎn)生式產(chǎn)生式ee(1)op e(2)e (e(1)eid語義動作語義動作e.code:= e(1).code | e(2).code |ope.code:= e(1).codee.code:=id e.code表示表示e后綴形式后綴形式 op表示任意二元操作符表示任意二元操作符 “|”表示后綴形式的連接表示后綴形式的連接。國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室n數(shù)組數(shù)組post存放后綴式：存放后綴式：k為下標(biāo)，初值為為下標(biāo)，初值為1n上述語義動作可實現(xiàn)為：上

6、述語義動作可實現(xiàn)為：產(chǎn)生式產(chǎn)生式程序段程序段ee(1)op e(2)postk:=op;k:=k+1e (e(1)eipostk:=i;k:=k+1n例：輸入串例：輸入串a(chǎn)+b+c的分析和翻譯的分析和翻譯post： 1 2 3 4 5ee(1)op e(2) e.code:= e(1).code | e(2).code |ope (e(1)e.code:= e(1).codeeide.code:=idab+c+國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室7.1.2 圖表示法圖表示法n圖表示法圖表示法dag抽象語法樹抽象語法樹 國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教

7、研室7.1.2 圖表示法圖表示法n無循環(huán)有向圖無循環(huán)有向圖(directed acyclic graph，簡稱簡稱dag)對表達(dá)式中的每個子表達(dá)式，對表達(dá)式中的每個子表達(dá)式，dag中都有一個中都有一個結(jié)點結(jié)點一個一個內(nèi)部結(jié)點內(nèi)部結(jié)點代表一個代表一個操作符操作符，它的孩子代表，它的孩子代表操作數(shù)操作數(shù)在一個在一個dag中代表公共子表達(dá)式的結(jié)點具有多中代表公共子表達(dá)式的結(jié)點具有多個父結(jié)點個父結(jié)點國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室 a:=b*(-c)+b*(-c)的圖表示法的圖表示法 assigna+*buminuscdagassigna+*buminusc抽象語法樹抽象語法

8、樹*buminusc國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室抽象語法樹抽象語法樹對應(yīng)的代碼：對應(yīng)的代碼： t1:=-c t2:=b*t1t3:=-c t4:=b*t3 t5:=t2+t4 a:=t5assigna+*buminusc抽象語法樹抽象語法樹*buminusc國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室dag對應(yīng)的代碼：對應(yīng)的代碼： t1:=-ct2:=b*t1t5:=t2+t2a:=t5assigna+*buminuscdag抽象語法樹抽象語法樹對應(yīng)的代碼：對應(yīng)的代碼： t1:=-c t2:=b*t1t3:=-c t4:=b*t3 t5:=t2+t4

9、 a:=t5國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室 產(chǎn)生賦值語句抽象語法樹的屬性文法產(chǎn)生賦值語句抽象語法樹的屬性文法 產(chǎn)產(chǎn) 生生 式式語義規(guī)則語義規(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:=mknode(uminus,e1.nptr)e (e1)e.nptr:=e1.nptreid e.nptr:=mkleaf(id,id.p

10、lace)國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室7.1.3 三地址代碼三地址代碼 n三地址代碼三地址代碼x:=y op z n三地址代碼可以看成是抽象語法樹或三地址代碼可以看成是抽象語法樹或dag的一種線性表示的一種線性表示 國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室 a:=b*(-c)+b*(-c)的圖表示法的圖表示法 assigna+*buminuscdagassigna+*buminusc抽象語法樹抽象語法樹*buminusc國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室 t1:=-c t1:=-c t2:=b*t1t2:=b*t1t3:=

11、-ct5:=t2+t2 t4:=b*t3a:=t5 t5:=t2+t4 a:=t5對于抽象語法樹的代碼對于抽象語法樹的代碼對于對于dag的代碼的代碼國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室三地址語句的種類三地址語句的種類 nx:=y op z nx:=op y nx:=y ngoto l nif x relop y goto l或或if a goto lnparam x和和call p,n，以及返回語句，以及返回語句return ynx:=yi及及xi:=y的索引賦值的索引賦值nx:=&y, x:=*y和和*x:=y的地址和指針賦值的地址和指針賦值國防科技大學(xué)計算機系

12、國防科技大學(xué)計算機系602教研室教研室n生成三地址代碼時，臨時變量的名字對應(yīng)生成三地址代碼時，臨時變量的名字對應(yīng)抽象語法樹的內(nèi)部結(jié)點抽象語法樹的內(nèi)部結(jié)點nid:=e對表達(dá)式對表達(dá)式e求值并置于變量求值并置于變量t中值中值id.place:=t國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室從賦值語句生成三地址代碼的從賦值語句生成三地址代碼的s-屬性文法屬性文法n非終結(jié)符號非終結(jié)符號s有綜合屬性有綜合屬性s.code，它代表，它代表賦值語句賦值語句s的三地址代碼。的三地址代碼。n非終結(jié)符號非終結(jié)符號e有如下兩個屬性：有如下兩個屬性：e.place表示存放表示存放e值的名字。值的名字。e

13、.code表示對表示對e求值的三地址語句序列。求值的三地址語句序列。函數(shù)函數(shù)newtemp的功能是，每次調(diào)用它時，將返的功能是，每次調(diào)用它時，將返回一個不同臨時變量名字回一個不同臨時變量名字,如如t1,t2,。國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室為賦值語句生成三地址代碼的為賦值語句生成三地址代碼的s-屬性文法定義屬性文法定義 產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(guī)則sid:=es.code:=e.code | gen(id.place := e.place)ee1+e2e.place:=newtemp; e.code:=e1.code | e2.code | gen(e.place

14、:= e1.place + e2.place)ee1*e2e.place:=newtemp; e.code:=e1.code | e2.code | gen(e.place := e1.place * e2.place)e-e1e.place:=newtemp; e.code:=e1.code | gen(e.place := uminus e1.place)e (e1)e.place:=e1.place; e.code:=e1.codeeid e.place:=id.place; e.code= 國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室三地址語句三地址語句n四元式四元式一個

15、帶有四個域的記錄結(jié)構(gòu)，這四個域分別一個帶有四個域的記錄結(jié)構(gòu)，這四個域分別稱為稱為op, arg1, arg2及及resultoparg1arg2result(0)uminusct1(1)*bt1t2(2)uminusct3(3)*bt3t4(4)+t2t4t5(5):=t5a 國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室三地址語句三地址語句n三元式三元式 通過計算臨時變量值的語句的位置來引用這通過計算臨時變量值的語句的位置來引用這個臨時變量個臨時變量三個域：三個域：op、arg1和和arg2oparg1arg2(0)uminusc(1)*b(0)(2)uminusc(3)*b(2

16、)(4)+(1)(3)(5)assigna(4)國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室三地址語句三地址語句nxi:=y op arg1 arg2 (0) = x i (1) ynx:=yiop arg1 arg2(0) = y i(1) assign x (0)國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室三地址語句三地址語句n間接三元式間接三元式 為了便于優(yōu)化，用為了便于優(yōu)化，用 三元式表三元式表+間接碼表間接碼表 表示表示中間代碼中間代碼間接碼表間接碼表:一張指示器表，按運算的先后次一張指示器表，按運算的先后次序列出有關(guān)三元式在三元式表中的位置。序列出有關(guān)三

17、元式在三元式表中的位置。優(yōu)點優(yōu)點: 方便優(yōu)化，節(jié)省空間方便優(yōu)化，節(jié)省空間國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室n例如，語句例如，語句x:=(a+b)*c;y:=d(a+b)的間接三元式表示如下表所示。的間接三元式表示如下表所示。間接代碼間接代碼 (1) (2) (3) (1) (4) (5)三元式表三元式表 oparg1 arg2(1)+ab(2)*(1) c(3):=x(2)(4)d(1)(5):=y(4)國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室7.2 說明語句說明語句國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室7.3 賦值語句的翻譯賦值語

18、句的翻譯 n7.3.1 簡單算術(shù)表達(dá)式及賦值語句簡單算術(shù)表達(dá)式及賦值語句 國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室為賦值語句生成三地址代碼的為賦值語句生成三地址代碼的s-屬性文法定義屬性文法定義 產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(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.

19、code | gen(e.place := e1.place * e2.place)e-e1e.place:=newtemp; e.code:=e1.code | gen(e.place := uminus e1.place)e (e1)e.place:=e1.place; e.code:=e1.codeeid e.place:=id.place; e.code= 國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室產(chǎn)生賦值語句三地址代碼的翻譯模式產(chǎn)生賦值語句三地址代碼的翻譯模式 sid:=e p:=lookup(); if p nil thenemit(p := e.pl

20、ace) 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)ee1*e2 e.place:=newtemp;

21、e.code:=e1.code | e2.code | gen(e.place := e1.place * e2.place)國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室產(chǎn)生賦值語句三地址代碼的翻譯模式產(chǎn)生賦值語句三地址代碼的翻譯模式 e-e1 e.place:=newtemp; emit(e.place:= uminuse 1.place)e(e1) e.place:=e1.placeeid p:=lookup(); if p nil then e.place:=p else error e-e1 e.place:=newtemp; e.code:=e1.code

22、 | gen(e.place := uminus e1.place)e (e1) e.place:=e1.place; e.code:=e1.codeeid e.place:=id.place; e.code= 國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室7.3.2 數(shù)組元素的引用數(shù)組元素的引用n數(shù)組元素地址的計算：數(shù)組元素地址的計算：國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室n設(shè)設(shè)a為為n維數(shù)組，每個元素寬度為維數(shù)組，每個元素寬度為w， lowi 為第為第i維維 的下界，的下界，ni 是為第是為第i維維 可取值的個可取值的個數(shù)數(shù), base為為a的第一個元素相對

23、地址的第一個元素相對地址 n元素元素ai1,i2,ik相對地址公式相對地址公式 (i1 n2+i2)n3+i3)nk+ik)w +base-(low1 n2+low2)n3+low3)nk+lowk)w nc= base-(low1 n2+low2)n3+low3)nk+lowk)w 國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室nid出現(xiàn)的地方也允許下面產(chǎn)生式中的出現(xiàn)的地方也允許下面產(chǎn)生式中的l出現(xiàn)出現(xiàn) l id elist | idelistelist,e | e 為了便于處理，文法改寫為為了便于處理，文法改寫為 lelist | id elistelist, e | id e

24、 國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室n引入下列語義變量或語義過程引入下列語義變量或語義過程:elist.ndim ：下標(biāo)個數(shù)計數(shù)器：下標(biāo)個數(shù)計數(shù)器elist.place ：表示臨時變量，用來臨時存放：表示臨時變量，用來臨時存放已形成的已形成的elist中的下標(biāo)表達(dá)式計算出來的值中的下標(biāo)表達(dá)式計算出來的值 limit(array，j) ：函數(shù)過程，它給出數(shù)組函數(shù)過程，它給出數(shù)組array的第的第j維的長度維的長度國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室n每個代表變量的非終結(jié)符每個代表變量的非終結(jié)符l有兩項語義值有兩項語義值l.place：n若若l為為簡單

25、變量簡單變量i, 指變量指變量i的符號表入口的符號表入口 n若若l為為下標(biāo)變量下標(biāo)變量，指存放，指存放conspart的的 臨時臨時變量的整數(shù)碼變量的整數(shù)碼 l.offset ：n若若l為為簡單變量簡單變量，null，n若若l為為下標(biāo)變量下標(biāo)變量，指存放，指存放varpart的臨時變的臨時變量的整數(shù)碼量的整數(shù)碼 國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室(1) sl:=e(2) ee+e(3) e(e)(4) el(5) lelist (6) lid(7) elist elist, e(8) elistid e國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室(1) s

26、l:=e if l.offset=null then /*l是簡單變量是簡單變量*/emit(l.place := e.place) else emit( l.place l.offset := e.place) (2) ee1 +e2 e.place:=newtemp; emit(e.place := e 1.place + e 2.place)國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室(3) e(e1)e.place:=e1.place(4) el if l.offset=null then e.place:=l.place else begin e.place:=newt

27、emp; emit(e.place := l.place l.offset ) end 國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室ai1,i2,ik (i1 n2+i2)n3+i3)nk+ik)w +base-(low1 n2+low2)n3+low3)nk+lowk)w(8) elistid e elist.place:=e.place; elist.ndim:=1; elist.array:=id.place 國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室a i1,i2,ik ( (i1 n2+i2)n3+i3)nk+ik)w +base-(low1 n2+lo

28、w2)n3+low3)nk+lowk)w(7) 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:=m 國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室ai1,i2,ik (i1 n2+i2)n3+i3)nk+ik) w +base-(low1 n2+low2)n3+low3)nk+lowk)w(5

29、) lelist l.place:=newtemp; emit(l.place := elist.array c); l.offset:=newtemp; emit(l.offset := w * elist.place) (6) lid l.place:=id.place; l.offset:=null 國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室類型轉(zhuǎn)換類型轉(zhuǎn)換n用用e.type表示非終結(jié)符表示非終結(jié)符e的類型屬性的類型屬性 n對應(yīng)產(chǎn)生式對應(yīng)產(chǎn)生式ee1 op e2的語義動作中關(guān)于的語義動作中關(guān)于e.type的語義規(guī)則可定義為：的語義規(guī)則可定義為： if e1.type=in

30、teger and e2.type=integer e.type:=integer else e.type:=real n算符區(qū)分為整型算符算符區(qū)分為整型算符int op和實型算符和實型算符real op，國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室nx:=yi*j 其中其中x、y為實型；為實型；i、j為整型。這個賦值句為整型。這個賦值句產(chǎn)生的三地址代碼為：產(chǎn)生的三地址代碼為： t1:=i int* j t3:=inttoreal t1 t2:=y real+ t3 x:=t2 國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室關(guān)于產(chǎn)生式關(guān)于產(chǎn)生式ee1 e2 的語義動作

31、的語義動作 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國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室else if e1.type=integer

32、 and e2.type=real then beginu:=newtemp;emit (u := inttoreal e 1.place);emit (e.place := u real+ e 2.palce);e.type:=realendelse if e1.type=real and e1.type=integer then beginu:=newtemp;emit (u := inttoreal e 2.place);emit (e.place := e 1.place real+ u);e.type:=realend else e.type:=type_error國防科技大學(xué)計算機

33、系國防科技大學(xué)計算機系602教研室教研室7.3.3 記錄中域的引用記錄中域的引用 n符號表表項之中保存記錄中的域的類型和符號表表項之中保存記錄中的域的類型和相對地址信息相對地址信息國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室7.4 布爾表達(dá)式的翻譯布爾表達(dá)式的翻譯n布爾表達(dá)式的兩個基本作用布爾表達(dá)式的兩個基本作用:用于邏輯演算用于邏輯演算,計算邏輯值計算邏輯值;用于控制語句的條件式用于控制語句的條件式.n產(chǎn)生布爾表達(dá)式的文法產(chǎn)生布爾表達(dá)式的文法: ee or e | e ande | e | (e) | i rop i | i國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教

34、研室n計算布爾表達(dá)式通常采用兩種方法計算布爾表達(dá)式通常采用兩種方法:1. 如同計算算術(shù)表達(dá)式一樣如同計算算術(shù)表達(dá)式一樣,一步步算一步步算 1 or (not 0 and 0) or 0 =1 or (1 and 0) or 0 =1 or 0 or 0 =1 or 0 =12. 采用某種優(yōu)化措施采用某種優(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國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室兩種

35、不同的翻譯方法兩種不同的翻譯方法:n第一種翻譯法：第一種翻譯法： a or b and c=d翻譯成翻譯成(1) (=, c, d, t1)(2) (and, b, t1, t2)(3) (or, a, t2, t3)n第二種翻譯法適合于作為條件表達(dá)式的第二種翻譯法適合于作為條件表達(dá)式的布爾表達(dá)式使用布爾表達(dá)式使用.國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室7.4.1 數(shù)值表示法數(shù)值表示法 na or b and not c 翻譯成翻譯成t1:=not ct2:=b and t1t3:=a or t1nab的關(guān)系表達(dá)式可等價地寫成的關(guān)系表達(dá)式可等價地寫成if ab then 1

36、 else 0 ，翻譯成，翻譯成 100:if ab goto 103101:t:=0102:goto 104103:t:=1104:國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室 關(guān)于布爾表達(dá)式的數(shù)值表示法的翻譯模關(guān)于布爾表達(dá)式的數(shù)值表示法的翻譯模式式 n過程過程emit將三地址代碼送到輸出文件中將三地址代碼送到輸出文件中nnextstat給出輸出序列中下一條三地址語句的給出輸出序列中下一條三地址語句的地址索引地址索引n每產(chǎn)生一條三地址語句后，過程每產(chǎn)生一條三地址語句后，過程emit便把便把nextstat加加1 國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室 關(guān)于布

37、爾表達(dá)式的數(shù)值表示法的翻譯模式關(guān)于布爾表達(dá)式的數(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.place:=newtemp; emit(e.place := not e 1.place)e(e1) e.place:=e1.place國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室關(guān)于布爾表達(dá)式的數(shù)值表示法的翻譯模式關(guān)于布爾表達(dá)

38、式的數(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 103101:t:=0102:goto 104103:t:=1104:國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室布爾表達(dá)式布爾表達(dá)式ab or cd and ef的翻譯結(jié)果的

39、翻譯結(jié)果 100:if ab goto 103101:t1:=0102:goto 104103:t1:=1104:if cd goto 107105:t2:=0106:goto 108107: t2:=1108: if ec or b c goto l2 “真真”出口出口 goto l1l1:if bd goto l2 “真真”出口出口 goto l3 “假假”出口出口 l2:(關(guān)于關(guān)于s1的三地址代碼序列的三地址代碼序列)goto lnextl3:(關(guān)于關(guān)于s2的三地址代碼序列的三地址代碼序列)lnext:國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室n每次調(diào)用函數(shù)每次調(diào)用函數(shù)n

40、ewlabel后都返回一個新的后都返回一個新的符號標(biāo)號符號標(biāo)號n對于一個布爾表達(dá)式對于一個布爾表達(dá)式e，引用兩個標(biāo)號，引用兩個標(biāo)號e.true是是e為為真真時控制流轉(zhuǎn)向的標(biāo)號時控制流轉(zhuǎn)向的標(biāo)號e.false是是e為為假假時控制流轉(zhuǎn)向的標(biāo)號時控制流轉(zhuǎn)向的標(biāo)號 國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室產(chǎn)生布爾表達(dá)式三地址代碼的語義規(guī)則產(chǎn)生布爾表達(dá)式三地址代碼的語義規(guī)則 產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(guī)則 ee1 or e2 e1.true:=e.true; e1.false:=newlabel; e2.true:=e.true; e2.false:=e.false; e.code:=e

41、1.code | gen(e1.false :) | e2.code e1.codeto e.trueto e1.falsee2.codeto e.trueto e.false國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室產(chǎn)生布爾表達(dá)式三地址代碼的語義規(guī)則產(chǎn)生布爾表達(dá)式三地址代碼的語義規(guī)則 產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(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.codee1.code

42、to e. falseto e1. truee2.codeto e.trueto e.false國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室產(chǎn)生布爾表達(dá)式三地址代碼的語義規(guī)則產(chǎn)生布爾表達(dá)式三地址代碼的語義規(guī)則 產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(guī)則enot e1 e1.true:=e.false; e1.false:=e.true; e.code:=e1.code e (e1) e1.true:=e.true; e1.false:=e.false; e.code:=e1.code國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室產(chǎn)生布爾表達(dá)式三地址代碼的語義規(guī)則產(chǎn)生布爾表達(dá)式三地址

43、代碼的語義規(guī)則 產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(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)國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室考慮如下表達(dá)式：考慮如下表達(dá)式： ab or cd and ef假定整個表達(dá)式的真假出口已分別置為假定整個表達(dá)式的真假出口已分別置為ltrue和和lfalse，則按定義將生成如下的代碼：

44、，則按定義將生成如下的代碼：if ab goto ltruegoto l1l1:if cd goto l2goto lfalsel2:if ef goto ltruegoto lfalse國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室布爾表達(dá)式的翻譯布爾表達(dá)式的翻譯n兩遍掃描兩遍掃描為給定的輸入串構(gòu)造一棵語法樹；為給定的輸入串構(gòu)造一棵語法樹；對語法樹進(jìn)行深度優(yōu)先遍歷，進(jìn)行語義規(guī)則中對語法樹進(jìn)行深度優(yōu)先遍歷，進(jìn)行語義規(guī)則中規(guī)定的翻譯。規(guī)定的翻譯。n一遍掃描一遍掃描國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室一遍掃描實現(xiàn)布爾表達(dá)式的翻譯一遍掃描實現(xiàn)布爾表達(dá)式的翻譯n采用四

45、元式形式采用四元式形式n把四元式存入一個數(shù)組中，數(shù)組下標(biāo)就代表四元把四元式存入一個數(shù)組中，數(shù)組下標(biāo)就代表四元式的標(biāo)號式的標(biāo)號n約定約定 四元式四元式(jnz, a, -, p) 表示表示 if a goto p 四元式四元式(jrop, x, y, p)表示表示 if x rop y goto p四元式四元式(j, -, -, p) 表示表示 goto p國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室n有時有時,四元式轉(zhuǎn)移地址無法立即知道四元式轉(zhuǎn)移地址無法立即知道,我們我們只好把這個未完成的四元式地址作為只好把這個未完成的四元式地址作為e的的語義值保存語義值保存,待機待機回填回填。

46、國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室n為非終結(jié)符為非終結(jié)符e賦予兩個綜合屬性賦予兩個綜合屬性e.truelist和和e.falselist。它們分別記錄布爾表達(dá)式。它們分別記錄布爾表達(dá)式e所應(yīng)的所應(yīng)的四元式中需回填四元式中需回填“真真”、“假假”出口的四元式的出口的四元式的標(biāo)號所構(gòu)成的鏈表標(biāo)號所構(gòu)成的鏈表 n例如例如:假定假定e的四元式中需要回填的四元式中需要回填真真出口的出口的p，q，r三個四元式，則三個四元式，則e.truelist為下列鏈為下列鏈:(p) (x， x，x，0)(q) (x，x，x，p)(r) (x，x，x，q)鏈尾鏈尾e. truelist =r國防

47、科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室n為了處理為了處理e.truelist和和e.falselist ，引入下列，引入下列語義變量和過程語義變量和過程:變量變量nextquad，它指向下一條將要產(chǎn)生但尚未形，它指向下一條將要產(chǎn)生但尚未形成的四元式的地址成的四元式的地址(標(biāo)號標(biāo)號)。nextquad的初值為的初值為1，每當(dāng)執(zhí)行一次每當(dāng)執(zhí)行一次emit之后，之后，nextquad將自動增將自動增1。函數(shù)函數(shù)makelist(i)，它將創(chuàng)建一個僅含，它將創(chuàng)建一個僅含i的新鏈表，的新鏈表，其中其中i是四元式數(shù)組的一個下標(biāo)是四元式數(shù)組的一個下標(biāo)(標(biāo)號標(biāo)號)；函數(shù)返回；函數(shù)返回指向這個鏈

48、的指針。指向這個鏈的指針。函數(shù)函數(shù)merge(p1,p2)，把以，把以p1和和p2為鏈?zhǔn)椎膬蓷l鏈為鏈?zhǔn)椎膬蓷l鏈合并為一，作為函數(shù)值，回送合并后的鏈?zhǔn)住：喜橐?，作為函?shù)值，回送合并后的鏈?zhǔn)住＿^程過程backpatch(p, t)，其功能是完成，其功能是完成“回填回填”，把把p所鏈接的每個四元式的第四區(qū)段都填為所鏈接的每個四元式的第四區(qū)段都填為t。國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室布爾表達(dá)式的文法布爾表達(dá)式的文法(1) e e1 or m e2(2) | e1 and m e2(3)| not e1(4)| (e1)(5)| id1 relop id2(6)| id(7)

49、m 國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室布爾表達(dá)式的翻譯模式布爾表達(dá)式的翻譯模式 (7) m m.quad:=nextquad 國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室布爾表達(dá)式的翻譯模式布爾表達(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.true

50、list:=e2.truelist; e.falselist:=merge(e1.falselist,e2.falselist) e1.codeto e.trueto e1.falsee2.codeto e.trueto e.falsee1.codeto e. falseto e1. truee2.codeto e.trueto e.false國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室布爾表達(dá)式的翻譯模式布爾表達(dá)式的翻譯模式 (3) enot e1 e.truelist:=e1.falselist; e.falselist:=e1.truelist(4) e(e1) e.tru

51、elist:=e1.truelist; e.falselist:=e1. falselist國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室布爾表達(dá)式的翻譯模式布爾表達(dá)式的翻譯模式 (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(nextquad); e.falselist:=make

52、list(nextquad+1); emit(jnz , id .place , ,0)； emit( j, -, -, 0) 國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室布爾表達(dá)式的翻譯模式布爾表達(dá)式的翻譯模式 n作為整個布爾表達(dá)式的作為整個布爾表達(dá)式的真真假假出口出口(轉(zhuǎn)移轉(zhuǎn)移目標(biāo)目標(biāo))仍待回填仍待回填.國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室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) trueli

53、st105 (j, -, -, 103) falselist 國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室n計算布爾表達(dá)式通常采用兩種方法計算布爾表達(dá)式通常采用兩種方法:1. 如同計算算術(shù)表達(dá)式一樣如同計算算術(shù)表達(dá)式一樣,一步步算一步步算 1 or (not 0 and 0) or 0 =1 or (1 and 0) or 0 =1 or 0 or 0 =1 or 0 =12. 采用某種優(yōu)化措施采用某種優(yōu)化措施 把把a or b解釋成解釋成 if a then true else b 把把a and b解釋成解釋成 if a then b else false 把把 a解釋成解釋

54、成 if a then false else true回顧：布爾表達(dá)式的翻譯回顧：布爾表達(dá)式的翻譯國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室 關(guān)于布爾表達(dá)式的數(shù)值表示法的翻譯模式關(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);emit(goto nextstat+2);emit(e.place:= 1) eid e.place:=id.place ee1 or e2 e.pla

55、ce:=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) 國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室回顧：布爾表達(dá)式的翻譯回顧：布爾表達(dá)式的翻譯n作為條件控制的布爾式翻譯作為條件控制的布爾式翻譯n一遍掃描實現(xiàn)布爾表達(dá)式的翻譯一遍掃描實現(xiàn)布爾表達(dá)式的翻譯國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室7.4.2 作為條件控制的布爾式翻譯作為條件控制的布爾式翻譯 n條件語句條件語句 if e

56、then s1 else s2 賦予賦予 e 兩種出口兩種出口:一真一假一真一假 e.codes1.codes2.codeto e.trueto e.falsegoto s.nexts.nexte.true:e.false:國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室產(chǎn)生布爾表達(dá)式三地址代碼的語義規(guī)則產(chǎn)生布爾表達(dá)式三地址代碼的語義規(guī)則 產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(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

57、alse :) | e2.code e1.codeto e.trueto e1.falsee2.codeto e.trueto e.false國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室產(chǎn)生布爾表達(dá)式三地址代碼的語義規(guī)則產(chǎn)生布爾表達(dá)式三地址代碼的語義規(guī)則 產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(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.codee1.codeto e. falseto e1.

58、 truee2.codeto e.trueto e.false國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室產(chǎn)生布爾表達(dá)式三地址代碼的語義規(guī)則產(chǎn)生布爾表達(dá)式三地址代碼的語義規(guī)則 產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(guī)則enot e1 e1.true:=e.false; e1.false:=e.true; e.code:=e1.code e (e1) e1.true:=e.true; e1.false:=e.false; e.code:=e1.code國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室產(chǎn)生布爾表達(dá)式三地址代碼的語義規(guī)則產(chǎn)生布爾表達(dá)式三地址代碼的語義規(guī)則 產(chǎn)生式產(chǎn)生式語義規(guī)

59、則語義規(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)國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室回顧：布爾表達(dá)式的翻譯回顧：布爾表達(dá)式的翻譯n作為條件控制的布爾式翻譯作為條件控制的布爾式翻譯n一遍掃描實現(xiàn)布爾表達(dá)式的翻譯一遍掃描實現(xiàn)布爾表達(dá)式的翻譯國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室布爾表達(dá)式

60、的文法布爾表達(dá)式的文法(1) e e1 or m e2(2) | e1 and m e2(3)| not e1(4)| (e1)(5)| id1 relop id2(6)| id(7)m 國防科技大學(xué)計算機系國防科技大學(xué)計算機系602教研室教研室布爾表達(dá)式的翻譯模式布爾表達(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,