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

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

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

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

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

5、程是：自左至右掃描后綴式，每碰到運(yùn)算量就把它推進(jìn)棧。每碰式，每碰到運(yùn)算量就把它推進(jìn)棧。每碰到到k目運(yùn)算符就把它作用于棧頂?shù)哪窟\(yùn)算符就把它作用于棧頂?shù)膋個(gè)項(xiàng)，個(gè)項(xiàng)，并用運(yùn)算結(jié)果代替這并用運(yùn)算結(jié)果代替這k個(gè)項(xiàng)。個(gè)項(xiàng)。把表達(dá)式翻譯成后綴式的語(yǔ)義規(guī)則描述把表達(dá)式翻譯成后綴式的語(yǔ)義規(guī)則描述 產(chǎn)生式產(chǎn)生式EE(1)op E(2)E (E(1)Eid語(yǔ)義規(guī)則語(yǔ)義規(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抽象語(yǔ)法樹抽象語(yǔ)法樹 7.1.2 圖表示法圖表示法 a+a*(b-c)+(b-c)*d的的DAG+*abd*-ca有兩個(gè)父結(jié)點(diǎn)（有兩個(gè)父結(jié)點(diǎn)（+，*）；）；表達(dá)式表達(dá)式b-c也有兩個(gè)父結(jié)點(diǎn)；也有兩個(gè)父結(jié)點(diǎn)； a:=b*(-c)+b*(-c)的圖表示法的圖表示法 assigna+*buminuscDAGassigna+*buminusc抽象語(yǔ)法樹抽象語(yǔ)法樹*buminusc抽象語(yǔ)法樹對(duì)應(yīng)的代碼：抽象語(yǔ)法樹對(duì)應(yīng)的代碼： T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5assigna+*bum

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

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

9、三地址語(yǔ)句的種類 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，以及返回語(yǔ)句，以及返回語(yǔ)句return ynx:=yi及及xi:=y的索引賦值的索引賦值nx:=&y, x:=*y和和*x:=y的地址和指針賦值的地址和指針賦值n編譯程序中，三地址語(yǔ)句的具體實(shí)現(xiàn)可以用記編譯程序中，三地址語(yǔ)句的具體實(shí)現(xiàn)可以用記錄來表示，記錄中包含運(yùn)算符和操作數(shù)的域。錄來表示，記錄中包含運(yùn)算符和操作數(shù)的域。n通常有三種表示方法：通常有三種表示方法：n四元式四元式 op,

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

11、錄結(jié)構(gòu)，這四個(gè)域分別稱為分別稱為op, arg1, arg2及及resultnoparg1arg2resultn(0)uminuscT1n(1)*bT1T2n(2)uminuscT3n(3)*bT3T4n(4)+T2T4T5n(5):=T5a 23 對(duì)于語(yǔ)句a:=b*-c+b*-c 的四元式表示 三地址語(yǔ)句的四元式表示 (- , 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)三地址語(yǔ)句的具體實(shí)現(xiàn)三地址語(yǔ)句的具體實(shí)現(xiàn)n三元式三元式 n通過計(jì)算臨時(shí)變量值的語(yǔ)句的位置來引通過計(jì)算臨時(shí)變量值的語(yǔ)句的位置來引用這個(gè)臨時(shí)變量用這個(gè)臨時(shí)變量n三個(gè)域：三個(gè)域：op、arg1和和arg2noparg1arg2n(0)uminuscn(1)*b(0)n(2)uminuscn(3)*b(2)n(4)+(1)(3)n(5)assigna(4)三地

13、址語(yǔ)句的具體實(shí)現(xiàn)三地址語(yǔ)句的具體實(shí)現(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)三地址語(yǔ)句的具體實(shí)現(xiàn)三地址語(yǔ)句的具體實(shí)現(xiàn)n間接三元式間接三元式 n為了便于優(yōu)化，用為了便于優(yōu)化，用 三元式表三元式表+間接碼表間接碼表 表示中間代碼表示中間代碼n間接碼表間接碼表:一張指示器表，按運(yùn)算的先后一張指示器表，按運(yùn)算的先后次序列出有關(guān)三元式在三元式表中的位次序列出有關(guān)三元式在三元式表中的位置。置。n優(yōu)點(diǎn)優(yōu)點(diǎn): 方便優(yōu)化，節(jié)省空間方便優(yōu)化，節(jié)省空間n例如，語(yǔ)句例如

14、，語(yǔ)句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常用的中間語(yǔ)言常用的中間語(yǔ)言n 后綴式，逆波蘭表示后綴式，逆波蘭表示n 圖表示：圖表示：DAG，抽象語(yǔ)法樹，抽象語(yǔ)法樹n 三地址代碼：三元式、四元式、間接三元三地址代碼：三元式、四元式、間接三元式式第七章第七章 語(yǔ)義分析和中間代碼產(chǎn)生語(yǔ)義分析和中間代碼產(chǎn)生n中間語(yǔ)言中間語(yǔ)言n賦值語(yǔ)句的翻譯賦值語(yǔ)句

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

16、mp的功能是，每次調(diào)用它時(shí)，的功能是，每次調(diào)用它時(shí)，將返回一個(gè)不同臨時(shí)變量名字將返回一個(gè)不同臨時(shí)變量名字,如如T1,T2,。為賦值語(yǔ)句生成三地址代碼的為賦值語(yǔ)句生成三地址代碼的S-屬性文法定義屬性文法定義 產(chǎn)生式產(chǎn)生式語(yǔ)義規(guī)則語(yǔ)義規(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)生賦值語(yǔ)句三地址代碼的翻譯模式產(chǎn)生賦值語(yǔ)句三地址代碼的翻譯模式 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)生賦值語(yǔ)句三地址代碼的翻譯模式產(chǎn)生賦值語(yǔ)句三地址代碼的翻譯模式 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ù)組元素地址的計(jì)算：數(shù)組元素地址的計(jì)算：nX:=Ai1,i2， ,ik+YnAi1,i2， ,ik=X+Y 賦值語(yǔ)句的翻譯賦值語(yǔ)句的翻譯 n設(shè)設(shè)A為為1維數(shù)組，每個(gè)元素寬度為維數(shù)組，每個(gè)元素寬度為w， low為下界，為下界，base為為A的第一個(gè)元素的第一個(gè)元素;n則則A(i)這個(gè)元素的相對(duì)地址為：這個(gè)元素的相對(duì)地址為：base+（i-low）wn上式可整理為：上式可整理為：iw+（base-loww）可變部分可變部分不變部分不變部分n設(shè)設(shè)A為為2維數(shù)組，按行存放，每個(gè)元

21、素寬度為維數(shù)組，按行存放，每個(gè)元素寬度為w， lowi 為第為第i維維 的下界，的下界， ni 為第為第i維維 可取值的個(gè)數(shù)；可取值的個(gè)數(shù)；base為為A的第一個(gè)元素的相對(duì)地址；的第一個(gè)元素的相對(duì)地址；n則則A(i1,i2)這個(gè)元素的相對(duì)地址為：這個(gè)元素的相對(duì)地址為：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ù)組，按行存放，每個(gè)元素寬度為維數(shù)組，按行存放，每個(gè)元素寬度為w，nl

22、owi 為第為第i維維 的下界，的下界，upi 為第為第i維維 的上界的上界nni 為第為第i維維 可取值的個(gè)數(shù)（可取值的個(gè)數(shù)（ ni = upi - lowi +1）nbase為為A的第一個(gè)元素相對(duì)地址的第一個(gè)元素相對(duì)地址 n元素元素Ai1,i2,ik相對(duì)地址公式相對(duì)地址公式 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ù)組元素引用的賦值語(yǔ)句基礎(chǔ)文法產(chǎn)生帶數(shù)組元素引用的賦值語(yǔ)句基礎(chǔ)文法(1) SL:=E(2) EE+E(3) E(E)(4) EL(5) LElist (6) Lid(7) Elist Elist, E(8) Elistid En引入下列語(yǔ)義變量或語(yǔ)義過程屬性）引入下列語(yǔ)義變量或語(yǔ)義

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

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

26、then /*L是簡(jiǎn)單變量是簡(jiǎn)單變量*/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ù)組元素引用的賦值語(yǔ)句翻譯模式帶數(shù)組元素引用的賦值語(yǔ)句翻譯模式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對(duì)應(yīng)產(chǎn)生式對(duì)應(yīng)產(chǎn)生式EE1 op E2的語(yǔ)義動(dòng)作中關(guān)于的語(yǔ)義動(dòng)作中關(guān)于E.type的語(yǔ)義規(guī)則可定義為：的語(yǔ)義規(guī)則可定義為：n if E1.type=integer andE2.type=integern E.type:=integern else E.type:=real n算符區(qū)分為整型算符算符

30、區(qū)分為整型算符int op和實(shí)型算符和實(shí)型算符real op，nx:=yi*jn 其中其中x、y為實(shí)型；為實(shí)型；i、j為整型。這個(gè)賦值為整型。這個(gè)賦值句產(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 的語(yǔ)義動(dòng)作的語(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:

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

33、句的翻譯n過程調(diào)用的處理過程調(diào)用的處理 布爾表達(dá)式的翻譯布爾表達(dá)式的翻譯n布爾表達(dá)式的兩個(gè)基本作用布爾表達(dá)式的兩個(gè)基本作用:n用于邏輯演算用于邏輯演算,計(jì)算邏輯值計(jì)算邏輯值;n用于控制語(yǔ)句的條件式用于控制語(yǔ)句的條件式.n產(chǎn)生布爾表達(dá)式的文法產(chǎn)生布爾表達(dá)式的文法:n EE or E | E andE | not E | (E) | i relop i | in計(jì)算布爾表達(dá)式通常采用兩種方法計(jì)算布爾表達(dá)式通常采用兩種方法:n1. 如同計(jì)算算術(shù)表達(dá)式一樣如同計(jì)算算術(shù)表達(dá)式一樣,一步步算一步步算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)第二種翻譯法適合于作為條件表達(dá)式的布第二種

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

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

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

38、ab goto 103101:T:=0102:goto 104103:T:=1104:布爾表達(dá)式布爾表達(dá)式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的三地址代碼序列的三地址代碼序列)考慮如下表達(dá)式：考慮如下表達(dá)式： ab or cd and ef產(chǎn)生式產(chǎn)生式語(yǔ)義規(guī)則語(yǔ)義規(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考慮如下表達(dá)式：考慮如下表達(dá)式： ab or cd and ef假定整個(gè)表達(dá)式的真假出口已分別置為假定整個(gè)表達(dá)式的真假出口已分別置為L(zhǎng)true和和Lfalse，則按以上屬性定義將生成如下的代碼：，則按以上屬性定義

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

42、 ef假定整個(gè)表達(dá)式的真假出口已分別置為假定整個(gè)表達(dá)式的真假出口已分別置為L(zhǎng)true和和Lfalseoror EabEEandand cdE efE兩遍掃描實(shí)現(xiàn)布爾表達(dá)式的翻譯兩遍掃描實(shí)現(xiàn)布爾表達(dá)式的翻譯 EE or E | E andE | not E | (E) | i relop i | ioror EabEEandand cdE efE產(chǎn)生式產(chǎn)生式語(yǔ)義規(guī)則語(yǔ)義規(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:一遍掃描實(shí)現(xiàn)布爾表達(dá)式的翻譯一遍掃描實(shí)現(xiàn)布爾表達(dá)式的翻譯n采用四元式形式采用四元式形式n把四元式存入一個(gè)數(shù)組中，數(shù)組下標(biāo)就代表四元把四元式存入一個(gè)數(shù)組中，數(shù)組下標(biāo)就代表四元式的標(biāo)號(hào)式的標(biāo)號(hà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、實(shí)現(xiàn)布爾表達(dá)式的翻譯一遍掃描實(shí)現(xiàn)布爾表達(dá)式的翻譯ab or cd100: (j, a, b, ?)101: (j, -, -, 102) 102: (j, c, d, ?)103:(j, -, -, ?) 104: 110:n主要問題：主要問題：n產(chǎn)生跳轉(zhuǎn)指令四元式時(shí)，它的轉(zhuǎn)移地址無法立產(chǎn)生跳轉(zhuǎn)指令四元式時(shí)，它的轉(zhuǎn)移地址無法立即知道即知道n需要以后掃描到特定位置時(shí)才能回過頭來確定需要以后掃描到特定位置時(shí)才能回過頭來確定n把這個(gè)未完成的四元式地址作為把這個(gè)未完成的四元式地址作為E的語(yǔ)義值保的語(yǔ)義值保存存,待機(jī)待機(jī)回填回填。n為非終結(jié)符為非終結(jié)符E賦予兩個(gè)綜合屬性賦予兩個(gè)綜合屬性E.truelis

46、t和和E.falselist。它們分別記錄布爾表達(dá)式。它們分別記錄布爾表達(dá)式E所應(yīng)的所應(yīng)的四元式中需回填四元式中需回填“真真”、“假出口的四元式的標(biāo)假出口的四元式的標(biāo)號(hào)所構(gòu)成的鏈表號(hào)所構(gòu)成的鏈表 n例如例如:假定假定E的四元式中需要回填的四元式中需要回填真真出口的出口的p，q，r三個(gè)四元式，則三個(gè)四元式，則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、語(yǔ)義變量和過程語(yǔ)義變量和過程:n變量變量nextquad，它指向下一條將要產(chǎn)生但尚，它指向下一條將要產(chǎn)生但尚未形成的四元式的地址未形成的四元式的地址(標(biāo)號(hào)標(biāo)號(hào))。nextquad的的初值為初值為1，每當(dāng)執(zhí)行一次，每當(dāng)執(zhí)行一次emit之后，之后，nextquad將自動(dòng)增將自動(dòng)增1。n函數(shù)函數(shù)makelist(i)，它將創(chuàng)建一個(gè)僅含，它將創(chuàng)建一個(gè)僅含i的新鏈的新鏈表，其中表，其中i是四元式數(shù)組的一個(gè)下標(biāo)是四元式數(shù)組的一個(gè)下標(biāo)(標(biāo)號(hào)標(biāo)號(hào))；函；函數(shù)返回指向這個(gè)鏈的指針。數(shù)返回指向這個(gè)鏈的指針。n函數(shù)函數(shù)merge(p1,p2)，把以，把以p1和和p2為鏈?zhǔn)椎膬蔀殒準(zhǔn)椎膬蓷l鏈合并為一，作為函數(shù)值，回送

48、合并后的鏈條鏈合并為一，作為函數(shù)值，回送合并后的鏈?zhǔn)住Ｊ?。n過程過程backpatch(p, t)，其功能是完成，其功能是完成“回填回填”，把把p所鏈接的每個(gè)四元式的第四區(qū)段都填為所鏈接的每個(gè)四元式的第四區(qū)段都填為t。n例如例如:過程過程backpatch(p, t)，其功能是完成，其功能是完成“回回填填”，把，把p所鏈接的每個(gè)四元式的第四區(qū)段都填所鏈接的每個(gè)四元式的第四區(qū)段都填為為t。n(r) (x， x，x，t)nn(q) (x，x，x，t)nn(p) (x，x，x，t)鏈尾鏈尾p布爾表達(dá)式的文法布爾表達(dá)式的文法(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布爾表達(dá)式的翻譯模式布爾表達(dá)式的翻譯模式 (7) M M.quad:=nextquad (1) EE1 or M E2(2) | E1 and M E2布爾表達(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,

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

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

52、)； emit( j, -, -, 0) 布爾表達(dá)式的翻譯模式布爾表達(dá)式的翻譯模式 n作為整個(gè)布爾表達(dá)式的作為整個(gè)布爾表達(dá)式的真真假假出口出口(轉(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布爾表達(dá)式的翻譯布爾表達(dá)式的翻譯n 數(shù)值表示法數(shù)值表示法n作為條件控制的布爾表達(dá)式翻譯作為條件控制的布爾表達(dá)式翻譯n 一遍掃描的翻譯模式一遍掃描的翻譯模式第七章第七章 語(yǔ)義分析和中間代碼產(chǎn)生語(yǔ)義分析和中間代碼產(chǎn)生n中間語(yǔ)言中間語(yǔ)言n賦值語(yǔ)句的翻譯賦值語(yǔ)句的翻譯n布爾表達(dá)式的翻譯布爾表達(dá)式的翻譯n控制語(yǔ)句的翻譯控制語(yǔ)句的翻譯n

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

59、E.falsegoto S.beginS.begin:E.true:E.false:while-do語(yǔ)句的屬性文法語(yǔ)句的屬性文法 產(chǎn)生式產(chǎn)生式語(yǔ)義規(guī)則語(yǔ)義規(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:考慮如下語(yǔ)句考慮如下語(yǔ)句 :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:一遍掃描翻譯控制流語(yǔ)句一遍掃描翻譯控制流語(yǔ)句 n考慮下列產(chǎn)生式所定義的語(yǔ)句考慮下列產(chǎn)生式所定義的語(yǔ)句:n(1) Sif E then Sn(2) | if E then S else Sn(3)| while E do Sn(4) | be