編譯原理-劉善梅-第7章 語義分析和中間代碼產(chǎn)生6ppt課件

1、編譯原理第七章第七章 語義分析和中間代碼產(chǎn)生語義分析和中間代碼產(chǎn)生第七章第七章 語義分析和中間代碼產(chǎn)生語義分析和中間代碼產(chǎn)生n中間語言中間語言n賦值語句的翻譯賦值語句的翻譯n布爾表達式的翻譯布爾表達式的翻譯n控制語句的翻譯控制語句的翻譯n過程調(diào)用的處理過程調(diào)用的處理 第七章第七章 語義分析和中間代碼產(chǎn)生語義分析和中間代碼產(chǎn)生n靜態(tài)語義檢查靜態(tài)語義檢查n類型檢查類型檢查n控制流檢查控制流檢查n一致性檢查一致性檢查 n相關(guān)名字檢查相關(guān)名字檢查n名字的作用域分析名字的作用域分析 第七章第七章 語義分析和中間代碼產(chǎn)生語義分析和中間代碼產(chǎn)生n靜態(tài)語義檢查和中間代碼產(chǎn)生在編譯程靜態(tài)語義檢查和中間代碼產(chǎn)生在

2、編譯程序中的地位：序中的地位：語法分語法分析器析器中間代碼中間代碼產(chǎn)生器產(chǎn)生器靜態(tài)檢靜態(tài)檢查器查器中間代碼中間代碼優(yōu)化器優(yōu)化器n中間語言中間語言n獨立于機器獨立于機器n復(fù)雜性界于源語言和目標(biāo)語言之間復(fù)雜性界于源語言和目標(biāo)語言之間n引入中間語言的好處：引入中間語言的好處：n便于進行與機器無關(guān)的代碼優(yōu)化工作便于進行與機器無關(guān)的代碼優(yōu)化工作 n易于移植易于移植n使編譯程序的結(jié)構(gòu)在邏輯上更為簡單明確使編譯程序的結(jié)構(gòu)在邏輯上更為簡單明確 源語言源語言程序程序目標(biāo)語目標(biāo)語言程序言程序中間語中間語言程序言程序CompilerFront EndCompilerBack Endn常用的中間語言：常用的中間語言：

3、n后綴式，又叫逆波蘭表示后綴式，又叫逆波蘭表示n圖表示：圖表示： DAG圖、抽象語法樹圖、抽象語法樹n三地址代碼三地址代碼n三元式三元式n四元式四元式n間接三元式間接三元式7.1 中間語言中間語言 7.1.1 7.1.1 后綴式后綴式 n后綴式表示法：后綴式表示法：Lukasiewicz發(fā)明的一種表示發(fā)明的一種表示表達式的方法，又稱逆波蘭表示法。表達式的方法，又稱逆波蘭表示法。n一個表達式一個表達式E的后綴形式可以如下定義：的后綴形式可以如下定義：n1. 如果如果E是一個變量或常量，則是一個變量或常量，則E的后綴式是的后綴式是E自身。自身。n2. 如果如果E是是E1 op E2形式的表達式，其

4、中形式的表達式，其中op是任何二元操作符，則是任何二元操作符，則E的后綴式為的后綴式為E1 E2 op，其中，其中E1 和和E2 分別為分別為E1 和和E2的后綴式。的后綴式。n3. 如果如果E是是(E1)形式的表達式，則形式的表達式，則E1 的后綴的后綴式就是式就是E的后綴式。的后綴式。n逆波蘭表示法不用括號。只要知道每個逆波蘭表示法不用括號。只要知道每個算符的目數(shù)，對于后綴式，不論從哪一算符的目數(shù)，對于后綴式，不論從哪一端進行掃描，都能對它進行唯一分解。端進行掃描，都能對它進行唯一分解。n后綴式的計算后綴式的計算n用一個棧實現(xiàn)。用一個棧實現(xiàn)。n一般的計算過程是：自左至右掃描后綴一般的計算過

5、程是：自左至右掃描后綴式，每碰到運算量就把它推進棧。每碰式，每碰到運算量就把它推進棧。每碰到到k目運算符就把它作用于棧頂?shù)哪窟\算符就把它作用于棧頂?shù)膋個項，個項，并用運算結(jié)果代替這并用運算結(jié)果代替這k個項。個項。把表達式翻譯成后綴式的語義規(guī)則描述把表達式翻譯成后綴式的語義規(guī)則描述 產(chǎn)生式產(chǎn)生式EE(1)op E(2)E (E(1)Eid語義規(guī)則語義規(guī)則E.code:= E(1).code | E(2).code |opE.code:= E(1).codeE.code:=id E.code表示表示E后綴形式后綴形式 op表示任意二元操作符表示任意二元操作符 “|”表示后綴形式的連接。表示后綴形式

6、的連接。7.1.2 圖表示法圖表示法n圖表示法圖表示法nDAGn抽象語法樹抽象語法樹 7.1.2 圖表示法圖表示法 a+a*(b-c)+(b-c)*d的的DAG+*abd*-ca有兩個父結(jié)點（有兩個父結(jié)點（+，*）；）；表達式表達式b-c也有兩個父結(jié)點；也有兩個父結(jié)點； a:=b*(-c)+b*(-c)的圖表示法的圖表示法 assigna+*buminuscDAGassigna+*buminusc抽象語法樹抽象語法樹*buminusc抽象語法樹對應(yīng)的代碼：抽象語法樹對應(yīng)的代碼： T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5assigna+*bum

7、inusc抽象語法樹抽象語法樹*buminusc a:=b*(-c)+b*(-c)的抽象語法樹對應(yīng)的代碼的抽象語法樹對應(yīng)的代碼DAG對應(yīng)的代碼：對應(yīng)的代碼： T1:=-cT2:=b*T1T5:=T2+T2a:=T5assigna+*buminuscDAG a:=b*(-c)+b*(-c)的的DAG對應(yīng)的代碼對應(yīng)的代碼抽象語法樹對應(yīng)的代碼：抽象語法樹對應(yīng)的代碼： T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T57.1.3 三地址代碼三地址代碼 n三地址代碼三地址代碼nx:=y op z /*每個語句的右邊只能有一個運每個語句的右邊只能有一個運算符算符*

8、/n三地址代碼可以看成是抽象語法樹或三地址代碼可以看成是抽象語法樹或DAG的的一種線性表示一種線性表示 a:=b*(-c)+b*(-c)的圖表示法的圖表示法 assigna+*buminuscDAGassigna+*buminusc抽象語法樹抽象語法樹*buminusc相應(yīng)于相應(yīng)于 a:=b*(-c)+b*(-c)抽象語法樹與抽象語法樹與DAG的三地址碼的三地址碼 T1:=-c T1:=-c T2:=b*T1T2:=b*T1T3:=-cT5:=T2+T2 T4:=b*T3a:=T5 T5:=T2+T4 a:=T5對于抽象語法樹的代碼對于抽象語法樹的代碼對于對于DAG的代碼的代碼三地址語句的種類

9、三地址語句的種類 nx:=y op z nx:=op y nx:=y ngoto L nif x relop y goto L或或if a goto Ln傳參傳參param x和轉(zhuǎn)子和轉(zhuǎn)子call p,n，以及返回語句，以及返回語句return ynx:=yi及及xi:=y的索引賦值的索引賦值nx:=&y, x:=*y和和*x:=y的地址和指針賦值的地址和指針賦值n編譯程序中，三地址語句的具體實現(xiàn)可以用記編譯程序中，三地址語句的具體實現(xiàn)可以用記錄來表示，記錄中包含運算符和操作數(shù)的域。錄來表示，記錄中包含運算符和操作數(shù)的域。n通常有三種表示方法：通常有三種表示方法：n四元式四元式 op,

10、 arg1, arg2, resultn三元式三元式 op, arg1, arg2n間接三元式間接三元式 間接碼表間接碼表+三元式表三元式表四元式需要利用較多的臨時單元四元式需要利用較多的臨時單元, ,四元式之四元式之 間間 的聯(lián)系通的聯(lián)系通過臨時變量實現(xiàn)。過臨時變量實現(xiàn)。中間代碼優(yōu)化處理時，四元式比三元式方便的多中間代碼優(yōu)化處理時，四元式比三元式方便的多, ,間接三間接三元式與四元式同樣方便，兩種實現(xiàn)方式需要的存儲空間元式與四元式同樣方便，兩種實現(xiàn)方式需要的存儲空間大體相同。大體相同。三地址語句的具體實現(xiàn)三地址語句的具體實現(xiàn)n四元式四元式n一個帶有四個域的記錄結(jié)構(gòu)，這四個域一個帶有四個域的記

11、錄結(jié)構(gòu)，這四個域分別稱為分別稱為op, arg1, arg2及及resultnoparg1arg2resultn(0)uminuscT1n(1)*bT1T2n(2)uminuscT3n(3)*bT3T4n(4)+T2T4T5n(5):=T5a 23 對于語句a:=b*-c+b*-c 的四元式表示 三地址語句的四元式表示 (- , c , , t1) (* , b , t1 , t2) (- , c , , t3) (* , b , t1 , t4) (+ ,t2 , t4 , t5) (= , t5 , ,a)1、 x=y op z2、 x=op y3、goto L4、if x rop y g

12、oto L5、x=y6、parm x call p,n 7、x=yi xi=y8、x=&y x=*y（op , y , z , x)（op , y , , x)（j , , , L)(jrop ,x ,y , L)(= , y , ,x)三地址語句的具體實現(xiàn)三地址語句的具體實現(xiàn)n三元式三元式 n通過計算臨時變量值的語句的位置來引通過計算臨時變量值的語句的位置來引用這個臨時變量用這個臨時變量n三個域：三個域：op、arg1和和arg2noparg1arg2n(0)uminuscn(1)*b(0)n(2)uminuscn(3)*b(2)n(4)+(1)(3)n(5)assigna(4)三地

13、址語句的具體實現(xiàn)三地址語句的具體實現(xiàn)nxi:=y nop arg1 arg2 n(0) = x i n(1) assign (0) ynx:=yinop arg1 arg2n(0) = y in(1) assign x (0)三地址語句的具體實現(xiàn)三地址語句的具體實現(xiàn)n間接三元式間接三元式 n為了便于優(yōu)化，用為了便于優(yōu)化，用 三元式表三元式表+間接碼表間接碼表 表示中間代碼表示中間代碼n間接碼表間接碼表:一張指示器表，按運算的先后一張指示器表，按運算的先后次序列出有關(guān)三元式在三元式表中的位次序列出有關(guān)三元式在三元式表中的位置。置。n優(yōu)點優(yōu)點: 方便優(yōu)化，節(jié)省空間方便優(yōu)化，節(jié)省空間n例如，語句例如

14、，語句nX:=(A+B)*C;nY:=D(A+B)n的間接三元式表示如下表所示。的間接三元式表示如下表所示。間接代碼間接代碼 (1) (2) (3) (1) (4) (5)三元式表三元式表 OPARG1 ARG2(1)+AB(2)*(1) C(3):=X(2)(4)D(1)(5):=Y(4)小結(jié)小結(jié)n常用的中間語言常用的中間語言n 后綴式，逆波蘭表示后綴式，逆波蘭表示n 圖表示：圖表示：DAG，抽象語法樹，抽象語法樹n 三地址代碼：三元式、四元式、間接三元三地址代碼：三元式、四元式、間接三元式式第七章第七章 語義分析和中間代碼產(chǎn)生語義分析和中間代碼產(chǎn)生n中間語言中間語言n賦值語句的翻譯賦值語句

15、的翻譯n布爾表達式的翻譯布爾表達式的翻譯n控制語句的翻譯控制語句的翻譯n過程調(diào)用的處理過程調(diào)用的處理 賦值語句的翻譯賦值語句的翻譯 1.簡單算術(shù)表達式及賦值語句簡單算術(shù)表達式及賦值語句 id:=E對表達式對表達式E求值并置于變量求值并置于變量T中中id.place=Tn非終結(jié)符號非終結(jié)符號S有綜合屬性有綜合屬性S.code，它代表，它代表賦值語句賦值語句S的三地址代碼。的三地址代碼。n非終結(jié)符號非終結(jié)符號E有如下兩個屬性：有如下兩個屬性：nE.place表示存放表示存放E值的單元的名字。值的單元的名字。nE.code表示對表示對E求值的三地址語句序列。求值的三地址語句序列。n函數(shù)函數(shù)newte

16、mp的功能是，每次調(diào)用它時，的功能是，每次調(diào)用它時，將返回一個不同臨時變量名字將返回一個不同臨時變量名字,如如T1,T2,。為賦值語句生成三地址代碼的為賦值語句生成三地址代碼的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.code

17、 | 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= 產(chǎn)生賦值語句三地址代碼的翻譯模式產(chǎn)生賦值語句三地址代碼的翻譯模式 Sid:=E p:=lookup(); if pnil thenemit(p := E.place) else error EE1+E2 E.place:=ne

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

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

20、code:=E1.codeEid E.place:=id.place; E.code= 2. 數(shù)組元素的引用數(shù)組元素的引用n數(shù)組元素地址的計算：數(shù)組元素地址的計算：nX:=Ai1,i2， ,ik+YnAi1,i2， ,ik=X+Y 賦值語句的翻譯賦值語句的翻譯 n設(shè)設(shè)A為為1維數(shù)組，每個元素寬度為維數(shù)組，每個元素寬度為w， low為下界，為下界，base為為A的第一個元素的第一個元素;n則則A(i)這個元素的相對地址為：這個元素的相對地址為：base+（i-low）wn上式可整理為：上式可整理為：iw+（base-loww）可變部分可變部分不變部分不變部分n設(shè)設(shè)A為為2維數(shù)組，按行存放，每個元

21、素寬度為維數(shù)組，按行存放，每個元素寬度為w， lowi 為第為第i維維 的下界，的下界， ni 為第為第i維維 可取值的個數(shù)；可取值的個數(shù)；base為為A的第一個元素的相對地址；的第一個元素的相對地址；n則則A(i1,i2)這個元素的相對地址為：這個元素的相對地址為：nbase+（i1-low1）n2 +i2-low2）wn上式可整理為：上式可整理為： n（i1 n2+i2) w+base-( (low1 n2）+low2)w ）可變部分可變部分不變部分不變部分A1,1A1,2A1,3A2,1A2,2A2,3n設(shè)設(shè)A為為n維數(shù)組，按行存放，每個元素寬度為維數(shù)組，按行存放，每個元素寬度為w，nl

22、owi 為第為第i維維 的下界，的下界，upi 為第為第i維維 的上界的上界nni 為第為第i維維 可取值的個數(shù)（可取值的個數(shù)（ ni = upi - lowi +1）nbase為為A的第一個元素相對地址的第一個元素相對地址 n元素元素Ai1,i2,ik相對地址公式相對地址公式 n(i1 n2+i2)n3+i3)nk+ik)w +nbase-(low1 n2+low2)n3+low3)nk+lowk)w nC= base-(low1 n2+low2)n3+low3)nk+lowk)w 可變部分可變部分不變部分不變部分nid出現(xiàn)的地方也允許下面產(chǎn)生式中的出現(xiàn)的地方也允許下面產(chǎn)生式中的L出現(xiàn)出現(xiàn)

23、nL id Elist | idnElistElist,E | E n為了便于處理，文法改寫為為了便于處理，文法改寫為n LElist | id nElistElist, E | id E (i1 n2+i2)n3+i3)nk+ik)w +base-(low1 n2+low2)n3+low3)nk+lowk)w產(chǎn)生帶數(shù)組元素引用的賦值語句基礎(chǔ)文法產(chǎn)生帶數(shù)組元素引用的賦值語句基礎(chǔ)文法(1) SL:=E(2) EE+E(3) E(E)(4) EL(5) LElist (6) Lid(7) Elist Elist, E(8) Elistid En引入下列語義變量或語義過程屬性）引入下列語義變量或語義

24、過程屬性）:nElist.ndim ：下標(biāo)個數(shù)計數(shù)器，即維數(shù)：下標(biāo)個數(shù)計數(shù)器，即維數(shù)nElist.place ：表示臨時變量，用來臨時：表示臨時變量，用來臨時存放已形成的存放已形成的Elist中的下標(biāo)表達式計算出中的下標(biāo)表達式計算出來的值來的值.n Elist. array：記錄數(shù)組名：記錄數(shù)組名 nlimit(array，j) ：函數(shù)過程，它給出數(shù)組：函數(shù)過程，它給出數(shù)組array的第的第j維的長度維的長度(i1 n2+i2)n3+i3)nk+ik)w +base-(low1 n2+low2)n3+low3)nk+lowk)wn每個代表變量的非終結(jié)符每個代表變量的非終結(jié)符L有兩個屬性：有兩個

25、屬性：nL.place：n若若L為簡單變量為簡單變量i, 指變量指變量i的符號表入口的符號表入口 n若若L為下標(biāo)變量，指存放不變部分的為下標(biāo)變量，指存放不變部分的 臨時變臨時變量的整數(shù)碼量的整數(shù)碼 nL.offset ：n若若L為簡單變量，為簡單變量，null，n若若L為下標(biāo)變量，指存放可變部分的臨時變?yōu)橄聵?biāo)變量，指存放可變部分的臨時變量的整數(shù)碼量的整數(shù)碼 (i1 n2+i2)n3+i3)nk+ik)w +base-(low1 n2+low2)n3+low3)nk+lowk)w帶數(shù)組元素引用的賦值語句翻譯模式帶數(shù)組元素引用的賦值語句翻譯模式(1) SL:=E if L.offset=null

26、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)(i1 n2+i2)n3+i3)nk+ik)w +base-(low1 n2+low2)n3+low3)nk+lowk)w(3) E(E1)E.place:=E1.place(4) EL if L.offset=null then E.place:=L.place else begin E.p

27、lace:=newtemp; emit(E.place := L.place L.offset ) end 帶數(shù)組元素引用的賦值語句翻譯模式帶數(shù)組元素引用的賦值語句翻譯模式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 A i1,i2,ik ( (i1 n2+i2)n3+i3)nk+ik)w +base-(low1 n2+low2)n3+low3)nk+lo

28、wk)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 Ai1,i2,ik (i1 n2+i2)n3+i3)nk+ik) w +base-(low1 n2+low2)n3+low3)nk+lowk)w(5) LElist L.place:=newtemp; emit(L.place := El

29、ist.array C); L.offset:=newtemp; emit(L.offset := w * Elist.place) (6) Lid L.place:=id.place; L.offset:=null 類型轉(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ī)則可定義為：n if E1.type=integer andE2.type=integern E.type:=integern else E.type:=real n算符區(qū)分為整型算符算符

30、區(qū)分為整型算符int op和實型算符和實型算符real op，nx:=yi*jn 其中其中x、y為實型；為實型；i、j為整型。這個賦值為整型。這個賦值句產(chǎn)生的三地址代碼為：句產(chǎn)生的三地址代碼為：n T1:=i int* jn T3:=inttoreal T1n T2:=y real+ T3n x:=T2 關(guān)于產(chǎn)生式關(guān)于產(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:

31、=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 endelse if E1.type=integer 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 E2.type

32、=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小結(jié)小結(jié)n賦值語句的翻譯賦值語句的翻譯n簡單算術(shù)表達式及賦值語句簡單算術(shù)表達式及賦值語句n數(shù)組元素的引用數(shù)組元素的引用n產(chǎn)生有關(guān)類型轉(zhuǎn)換的指令產(chǎn)生有關(guān)類型轉(zhuǎn)換的指令第七章第七章 語義分析和中間代碼產(chǎn)生語義分析和中間代碼產(chǎn)生n中間語言中間語言n賦值語句的翻譯賦值語句的翻譯n布爾表達式的翻譯布爾表達式的翻譯n控制語句的翻譯控制語

33、句的翻譯n過程調(diào)用的處理過程調(diào)用的處理 布爾表達式的翻譯布爾表達式的翻譯n布爾表達式的兩個基本作用布爾表達式的兩個基本作用:n用于邏輯演算用于邏輯演算,計算邏輯值計算邏輯值;n用于控制語句的條件式用于控制語句的條件式.n產(chǎn)生布爾表達式的文法產(chǎn)生布爾表達式的文法:n EE or E | E andE | not E | (E) | i relop i | in計算布爾表達式通常采用兩種方法計算布爾表達式通常采用兩種方法:n1. 如同計算算術(shù)表達式一樣如同計算算術(shù)表達式一樣,一步步算一步步算n 1 or (not 0 and 0) or 0n =1 or (1 and 0) or 0n =1 or

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

35、翻譯法適合于作為條件表達式的布爾表達式使用爾表達式使用.1 數(shù)值表示法數(shù)值表示法 na or b and not c 翻譯成翻譯成nT1:=not cnT2:=b and T1nT3:=a or T1n關(guān)系表達式關(guān)系表達式ab 可等價地寫成可等價地寫成nif ab then 1 else 0 ，翻譯成三地址語句，翻譯成三地址語句序列序列n 100: if ab goto 103n101: T:=0n102: goto 104n103: T:=1n104:產(chǎn)生布爾表達式的三地址代碼的數(shù)值表示產(chǎn)生布爾表達式的三地址代碼的數(shù)值表示法翻譯模式法翻譯模式n過程過程emit將三地址代碼送到輸出文件中將三地

36、址代碼送到輸出文件中nnextstat給出輸出序列中下一條三地址語句的給出輸出序列中下一條三地址語句的地址索引地址索引n每產(chǎn)生一條三地址語句后，過程每產(chǎn)生一條三地址語句后，過程emit便把便把nextstat加加1 產(chǎn)生布爾表達式的三地址代碼的數(shù)值表示產(chǎn)生布爾表達式的三地址代碼的數(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.p

37、lace:=newtemp; emit(E.place := not E 1.place)E(E1) E.place:=E1.place產(chǎn)生布爾表達式的三地址代碼的數(shù)值表示法產(chǎn)生布爾表達式的三地址代碼的數(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

38、ab goto 103101:T:=0102:goto 104103:T:=1104:布爾表達式布爾表達式ab or cd and ef的翻譯結(jié)果的翻譯結(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 “真出口真出口 ngoto L1nL1:if bc or b c goto L2 “真出口真出口 goto L1L1:if bc or b c goto L2 “真出口真出口 goto L1L1:

39、if bd goto L2 “真出口真出口 goto L3 “假出口假出口 L2:(關(guān)于關(guān)于S1的三地址代碼序列的三地址代碼序列)goto LnextL3:(關(guān)于關(guān)于S2的三地址代碼序列的三地址代碼序列)考慮如下表達式：考慮如下表達式： ab or cd and ef產(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) EE1 or E2 E1.true:=E.true; E1.false:=newlabel; E2.true:=E.t

40、rue; E2.false:=E.false; E.code:=E1.code |gen(E1.false :) | E2.code 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考慮如下表達式：考慮如下表達式： ab or cd and ef假定整個表達式的真假出口已分別置為假定整個表達式的真假出口已分別置為Ltrue和和Lfalse，則按以上屬性定義將生成如下的代碼：，則按以上屬性定義

41、將生成如下的代碼：if ab goto Ltruegoto L1L1:if cd goto L2goto LfalseL2:if ef goto Ltruegoto Lfalse控制語句中布爾表達式的翻譯控制語句中布爾表達式的翻譯n兩遍掃描兩遍掃描n為給定的輸入串構(gòu)造一棵語法樹；為給定的輸入串構(gòu)造一棵語法樹；n對語法樹進行深度優(yōu)先遍歷，進行語義規(guī)對語法樹進行深度優(yōu)先遍歷，進行語義規(guī)則中規(guī)定的翻譯。則中規(guī)定的翻譯。n一遍掃描一遍掃描n 在自底向上的語法分析過程中生成布爾在自底向上的語法分析過程中生成布爾表達式的三地址代碼表達式的三地址代碼考慮如下表達式：考慮如下表達式： ab or cd and

42、 ef假定整個表達式的真假出口已分別置為假定整個表達式的真假出口已分別置為Ltrue和和Lfalseoror EabEEandand cdE efE兩遍掃描實現(xiàn)布爾表達式的翻譯兩遍掃描實現(xiàn)布爾表達式的翻譯 EE or E | E andE | not E | (E) | i relop i | ioror EabEEandand cdE efE產(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) EE1 or E2 E1.true:=E

43、.true; E1.false:=newlabel; E2.true:=E.true; E2.false:=E.false; E.code:=E1.code |gen(E1.false :) | E2.code 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.codeif ab goto Ltruegoto L1if cd goto L2goto Lfalse if ef goto Ltruegot

44、o Lfalse(Ltrue, Lfalse)(Ltrue, L1)(Ltrue, Lfalse)(L2, Lfalse)(Ltrue, Lfalse)L1:L2:一遍掃描實現(xiàn)布爾表達式的翻譯一遍掃描實現(xiàn)布爾表達式的翻譯n采用四元式形式采用四元式形式n把四元式存入一個數(shù)組中，數(shù)組下標(biāo)就代表四元把四元式存入一個數(shù)組中，數(shù)組下標(biāo)就代表四元式的標(biāo)號式的標(biāo)號n商定商定 n四元式四元式(jnz, a, -, p) 表示表示 if a goto p n四元式四元式(jrop, x, y, p)表示表示 if x rop y goto pn四元式四元式(j, -, -, p) 表示表示 goto p一遍掃描

45、實現(xiàn)布爾表達式的翻譯一遍掃描實現(xiàn)布爾表達式的翻譯ab or cd100: (j, a, b, ?)101: (j, -, -, 102) 102: (j, c, d, ?)103:(j, -, -, ?) 104: 110:n主要問題：主要問題：n產(chǎn)生跳轉(zhuǎn)指令四元式時，它的轉(zhuǎn)移地址無法立產(chǎn)生跳轉(zhuǎn)指令四元式時，它的轉(zhuǎn)移地址無法立即知道即知道n需要以后掃描到特定位置時才能回過頭來確定需要以后掃描到特定位置時才能回過頭來確定n把這個未完成的四元式地址作為把這個未完成的四元式地址作為E的語義值保的語義值保存存,待機待機回填回填。n為非終結(jié)符為非終結(jié)符E賦予兩個綜合屬性賦予兩個綜合屬性E.truelis

46、t和和E.falselist。它們分別記錄布爾表達式。它們分別記錄布爾表達式E所應(yīng)的所應(yīng)的四元式中需回填四元式中需回填“真真”、“假出口的四元式的標(biāo)假出口的四元式的標(biāo)號所構(gòu)成的鏈表號所構(gòu)成的鏈表 n例如例如:假定假定E的四元式中需要回填的四元式中需要回填真真出口的出口的p，q，r三個四元式，則三個四元式，則E.truelist為下列鏈為下列鏈:n(p) (x， x，x，0)nn(q) (x，x，x，p)nn(r) (x，x，x，q)鏈尾：鏈尾：0為鏈末標(biāo)志為鏈末標(biāo)志E. truelist =r，r為鏈?zhǔn)诪殒準(zhǔn)譶為了處理為了處理E.truelist和和E.falselist ，引入下列，引入下列

47、語義變量和過程語義變量和過程:n變量變量nextquad，它指向下一條將要產(chǎn)生但尚，它指向下一條將要產(chǎn)生但尚未形成的四元式的地址未形成的四元式的地址(標(biāo)號標(biāo)號)。nextquad的的初值為初值為1，每當(dāng)執(zhí)行一次，每當(dāng)執(zhí)行一次emit之后，之后，nextquad將自動增將自動增1。n函數(shù)函數(shù)makelist(i)，它將創(chuàng)建一個僅含，它將創(chuàng)建一個僅含i的新鏈的新鏈表，其中表，其中i是四元式數(shù)組的一個下標(biāo)是四元式數(shù)組的一個下標(biāo)(標(biāo)號標(biāo)號)；函；函數(shù)返回指向這個鏈的指針。數(shù)返回指向這個鏈的指針。n函數(shù)函數(shù)merge(p1,p2)，把以，把以p1和和p2為鏈?zhǔn)椎膬蔀殒準(zhǔn)椎膬蓷l鏈合并為一，作為函數(shù)值，回送

48、合并后的鏈條鏈合并為一，作為函數(shù)值，回送合并后的鏈?zhǔn)?。首。n過程過程backpatch(p, t)，其功能是完成，其功能是完成“回填回填”，把把p所鏈接的每個四元式的第四區(qū)段都填為所鏈接的每個四元式的第四區(qū)段都填為t。n例如例如:過程過程backpatch(p, t)，其功能是完成，其功能是完成“回回填填”，把，把p所鏈接的每個四元式的第四區(qū)段都填所鏈接的每個四元式的第四區(qū)段都填為為t。n(r) (x， x，x，t)nn(q) (x，x，x，t)nn(p) (x，x，x，t)鏈尾鏈尾p布爾表達式的文法布爾表達式的文法(1) E E1 or M E2(2) | E1 and M E2(3)| n

49、ot E1(4)| (E1)(5)| id1 relop id2(6)| id(7)M布爾表達式的翻譯模式布爾表達式的翻譯模式 (7) M M.quad:=nextquad (1) EE1 or M E2(2) | E1 and M E2布爾表達式的翻譯模式布爾表達式的翻譯模式 (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,

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

51、list; 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(nextquad); E.falselist:=makelist(nextquad+1); emit(jnz , id .place , ,0

52、)； emit( j, -, -, 0) 布爾表達式的翻譯模式布爾表達式的翻譯模式 n作為整個布爾表達式的作為整個布爾表達式的真真假假出口出口(轉(zhuǎn)移轉(zhuǎn)移目標(biāo)目標(biāo))仍待回填仍待回填.(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) (7) M M.quad:=nextquad 100: (j, a, b, 0)101: (j, -, -, 0) 102: (

53、j, c, d, 0)103:(j, -, -,0) 104: (j, e, f, 0)105: (j, -, -,0) abE(100,101)oror M(102)andand M(104)efE(104, 105) c dE(102, 103) ab or cd and ef c dEororandand abE(100,101) M(102) M(104)efE(104, 105)(102, 103)(1) EE1 or M E2 backpatch(E1.falselist, M.quad); E.truelist:=merge(E1.truelist, E2.truelist);

54、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) 100: (j, a, b, 0)101: (j, -, -, 0) 102: (j, c, d, 0)103:(j, -, -,0) 104: (j, e, f, 0)105: (j, -, -,0) E104(104，105,103)E(104，100,105.103)102103100ab or cd

55、 and ef 100 (j, a, b, 0)101 (j, -, -, 102)102 (j, c, d, 104)103 (j, -, -, 0)104 (j, e, f, 100) truelist105 (j, -, -, 103) falselist 小結(jié)小結(jié)n布爾表達式的翻譯布爾表達式的翻譯n 數(shù)值表示法數(shù)值表示法n作為條件控制的布爾表達式翻譯作為條件控制的布爾表達式翻譯n 一遍掃描的翻譯模式一遍掃描的翻譯模式第七章第七章 語義分析和中間代碼產(chǎn)生語義分析和中間代碼產(chǎn)生n中間語言中間語言n賦值語句的翻譯賦值語句的翻譯n布爾表達式的翻譯布爾表達式的翻譯n控制語句的翻譯控制語句的翻譯n

56、過程調(diào)用的處理過程調(diào)用的處理 7.5 控制語句的翻譯控制語句的翻譯 n考慮下列產(chǎn)生式所定義的語句考慮下列產(chǎn)生式所定義的語句n S if E then S1n | if E then S1 else S2n | while E do S1n其中其中E為布爾表達式。為布爾表達式。利用屬性文法定義語義利用屬性文法定義語義設(shè)計一遍掃描的翻譯模式設(shè)計一遍掃描的翻譯模式nif-then語句語句nS if E then S1E.codeS1.codeTo E.trueTo E.falseE.true:E.false:if-then語句的屬性文法語句的屬性文法 產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(guī)則 Sif E the

57、n S1 E.true:=newlabel; E.flase:=S.next; S1.next:=S.next S.code:=E.code | gen(E.true :) | S1.codeE.codeS1.codeTo E.trueTo E.falseE.true:E.false:nif-then-else語句語句nS if E then S1 else S2E.codeS1.codeS2.codeTo E.trueTo E.falsegoto S.nextS.nextE.true:E.false:if-then-else語句的屬性文法語句的屬性文法 產(chǎn)生式產(chǎn)生式 語義規(guī)則語義規(guī)則Sif

58、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.codeE.codeS1.codeS2.codeTo E.trueTo E.falsegoto S.nextS.nextE.true:E.false:nwhile-do語句語句nS while E do S1 E.codeS1.codeTo E.trueTo

59、E.falsegoto S.beginS.begin:E.true:E.false:while-do語句的屬性文法語句的屬性文法 產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(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)E.codeS1.codeTo E.trueTo E.falsegoto S.beginS.begin:E.true

60、:E.false:考慮如下語句考慮如下語句 :while ab doif cd thenx:=y+z else x:=y-zn生成下列代碼：生成下列代碼： nL1:if ab goto L2ngoto LnextnL2:if cd goto L3ngoto L4nL3:T1:=y+znx:=T1ngoto L1nL4:T2:=y-znx:=T2ngoto L1nLnext:一遍掃描翻譯控制流語句一遍掃描翻譯控制流語句 n考慮下列產(chǎn)生式所定義的語句考慮下列產(chǎn)生式所定義的語句:n(1) Sif E then Sn(2) | if E then S else Sn(3)| while E do Sn(4) | be