第七章語(yǔ)義分析和中間代碼產(chǎn)生ppt課件

1、第七章第七章 語(yǔ)義分析和中間代碼產(chǎn)生語(yǔ)義分析和中間代碼產(chǎn)生n靜態(tài)語(yǔ)義檢查靜態(tài)語(yǔ)義檢查n類型檢查類型檢查n控制流檢查控制流檢查n一致性檢查一致性檢查 n相關(guān)名字檢查相關(guān)名字檢查n名字的作用域分析名字的作用域分析 語(yǔ)法分語(yǔ)法分析器析器中間代碼中間代碼產(chǎn)生器產(chǎn)生器靜態(tài)檢靜態(tài)檢查器查器中間代碼中間代碼優(yōu)化器優(yōu)化器n中間言語(yǔ)中間言語(yǔ)(復(fù)雜性界于源言語(yǔ)和目的言語(yǔ)復(fù)雜性界于源言語(yǔ)和目的言語(yǔ)之間之間)的益處：的益處：n便于進(jìn)展與機(jī)器無(wú)關(guān)的代碼優(yōu)化任務(wù)便于進(jìn)展與機(jī)器無(wú)關(guān)的代碼優(yōu)化任務(wù) n易于移植易于移植n使編譯程序的構(gòu)造在邏輯上更為簡(jiǎn)單明確使編譯程序的構(gòu)造在邏輯上更為簡(jiǎn)單明確 源言語(yǔ)源言語(yǔ)程序程序目的語(yǔ)目的語(yǔ)言

2、程序言程序中間語(yǔ)中間語(yǔ)言程序言程序CompilerFront EndCompilerBack Endn常用的中間言語(yǔ)：常用的中間言語(yǔ)：n后綴式，逆波蘭表示后綴式，逆波蘭表示n圖表示：圖表示： DAG、籠統(tǒng)語(yǔ)法樹(shù)、籠統(tǒng)語(yǔ)法樹(shù)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. 假設(shè)假設(shè)E是一個(gè)變

3、量或常量，那么是一個(gè)變量或常量，那么E的后綴式的后綴式是是E本身。本身。n2. 假設(shè)假設(shè)E是是E1 op E2方式的表達(dá)式，其中方式的表達(dá)式，其中op是任何二元操作符，那么是任何二元操作符，那么E的后綴式為的后綴式為E1 E2 op，其中，其中E1 和和E2 分別為分別為E1 和和E2的后綴式。的后綴式。n3. 假設(shè)假設(shè)E是是(E1)方式的表達(dá)式，那么方式的表達(dá)式，那么E1 的后的后綴式就是綴式就是E的后綴式。的后綴式。n逆波蘭表示法不用括號(hào)。只需知道每個(gè)逆波蘭表示法不用括號(hào)。只需知道每個(gè)算符的目數(shù)，對(duì)于后綴式，不論從哪一算符的目數(shù)，對(duì)于后綴式，不論從哪一端進(jìn)展掃描，都能對(duì)它進(jìn)展獨(dú)一分解。端進(jìn)

4、展掃描，都能對(duì)它進(jìn)展獨(dú)一分解。n后綴式的計(jì)算后綴式的計(jì)算n用一個(gè)棧實(shí)現(xiàn)。用一個(gè)棧實(shí)現(xiàn)。n普通的計(jì)算過(guò)程是：自左至右掃描后綴普通的計(jì)算過(guò)程是：自左至右掃描后綴式，每碰到運(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ī)那么描畫(huà)畫(huà) 產(chǎn)生式產(chǎn)生式EE(1)op E(2)E (E(1)Eid語(yǔ)義動(dòng)作語(yǔ)義動(dòng)作E.code:= E(1).code | E(2).code |opE.code:= E(1).codeE.

5、code:=id E.code表示表示E后綴方式后綴方式 op表示恣意二元操作符表示恣意二元操作符 “|表示后綴方式的銜接。表示后綴方式的銜接。n數(shù)組數(shù)組POST存放后綴式：存放后綴式：k為下標(biāo)，初值為為下標(biāo)，初值為1n上述語(yǔ)義動(dòng)作可實(shí)現(xiàn)為：上述語(yǔ)義動(dòng)作可實(shí)現(xiàn)為：n產(chǎn)生式產(chǎn)生式程序段程序段nEE(1)op E(2)POSTk:=op;k:=k+1nE (E(1)nEiPOSTk:=i;k:=k+1n例：輸入串例：輸入串a(chǎn)+b+c的分析和翻譯的分析和翻譯nPOST： 1 2 3 4 5EE(1)op E(2) E.code:= E(1).code | E(2).code |opE (E(1)E.

6、code:= E(1).codeEidE.code:=idab+c+7.1.2 圖表示法圖表示法n圖表示法圖表示法nDAGn籠統(tǒng)語(yǔ)法樹(shù)籠統(tǒng)語(yǔ)法樹(shù) 7.1.2 圖表示法圖表示法n無(wú)循環(huán)有向圖無(wú)循環(huán)有向圖(Directed Acyclic Graph，簡(jiǎn)稱簡(jiǎn)稱DAG)n對(duì)表達(dá)式中的每個(gè)子表達(dá)式，對(duì)表達(dá)式中的每個(gè)子表達(dá)式，DAG中都有中都有一個(gè)結(jié)點(diǎn)一個(gè)結(jié)點(diǎn)n一個(gè)內(nèi)部結(jié)點(diǎn)代表一個(gè)操作符，它的孩子代一個(gè)內(nèi)部結(jié)點(diǎn)代表一個(gè)操作符，它的孩子代表操作數(shù)表操作數(shù)n在一個(gè)在一個(gè)DAG中代表公共子表達(dá)式的結(jié)點(diǎn)具中代表公共子表達(dá)式的結(jié)點(diǎn)具有多個(gè)父結(jié)點(diǎn)有多個(gè)父結(jié)點(diǎn) a:=b*(-c)+b*(-c)的圖表示法的圖表示法 a

7、ssigna+*buminuscDAGassigna+*buminusc籠統(tǒng)語(yǔ)法樹(shù)籠統(tǒng)語(yǔ)法樹(shù)*buminusc籠統(tǒng)語(yǔ)法樹(shù)對(duì)應(yīng)的代碼：籠統(tǒng)語(yǔ)法樹(shù)對(duì)應(yīng)的代碼： T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5assigna+*buminusc籠統(tǒng)語(yǔ)法樹(shù)籠統(tǒng)語(yǔ)法樹(shù)*buminuscDAG對(duì)應(yīng)的代碼：對(duì)應(yīng)的代碼： T1:=-cT2:=b*T1T5:=T2+T2a:=T5assigna+*buminuscDAG籠統(tǒng)語(yǔ)法樹(shù)對(duì)應(yīng)的代碼：籠統(tǒng)語(yǔ)法樹(shù)對(duì)應(yīng)的代碼： T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5 產(chǎn)生賦值語(yǔ)句

8、籠統(tǒng)語(yǔ)法樹(shù)的屬性文法產(chǎn)生賦值語(yǔ)句籠統(tǒng)語(yǔ)法樹(shù)的屬性文法 產(chǎn)產(chǎn) 生生 式式語(yǔ)義規(guī)那么語(yǔ)義規(guī)那么Sid:=E S.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.place)7.1.3 三地址代碼三地址代碼 n三地址代碼三地址代碼nx:=y

9、 op z n三地址代碼可以看成是籠統(tǒng)語(yǔ)法樹(shù)或三地址代碼可以看成是籠統(tǒng)語(yǔ)法樹(shù)或DAG的一種線性表示的一種線性表示 a:=b*(-c)+b*(-c)的圖表示法的圖表示法 assigna+*buminuscDAGassigna+*buminusc籠統(tǒng)語(yǔ)法樹(shù)籠統(tǒng)語(yǔ)法樹(shù)*buminusc T1:=-c T1:=-c T2:=b*T1T2:=b*T1T3:=-cT5:=T2+T2 T4:=b*T3a:=T5 T5:=T2+T4 a:=T5對(duì)于籠統(tǒng)語(yǔ)法樹(shù)的代碼對(duì)于籠統(tǒng)語(yǔ)法樹(shù)的代碼對(duì)于對(duì)于DAG的代碼的代碼三地址語(yǔ)句的種類三地址語(yǔ)句的種類 nx:=y op z nx:=op y nx:=y ngoto L

10、nif x relop y goto L或或if a goto Lnparam x和和call p,n，以及前往語(yǔ)句，以及前往語(yǔ)句return ynx:=yi及及xi:=y的索引賦值的索引賦值nx:=&y, x:=*y和和*x:=y的地址和指針賦值的地址和指針賦值n生成三地址代碼時(shí)，暫時(shí)變量的名字對(duì)應(yīng)生成三地址代碼時(shí)，暫時(shí)變量的名字對(duì)應(yīng)籠統(tǒng)語(yǔ)法樹(shù)的內(nèi)部結(jié)點(diǎn)籠統(tǒng)語(yǔ)法樹(shù)的內(nèi)部結(jié)點(diǎn)nid:=En對(duì)表達(dá)式對(duì)表達(dá)式E求值并置于變量求值并置于變量T中值中值nid.place:=T從賦值語(yǔ)句生成三地址代碼的從賦值語(yǔ)句生成三地址代碼的S-屬性文法屬性文法n非終結(jié)符號(hào)非終結(jié)符號(hào)S有綜合屬性有綜合屬性S.

11、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ù)newtemp的功能是，每次調(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.plac

12、e)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 | 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:=

13、id.place; E.code= 三地址語(yǔ)句三地址語(yǔ)句n四元式四元式n一個(gè)帶有四個(gè)域的記錄構(gòu)造，這四個(gè)域一個(gè)帶有四個(gè)域的記錄構(gòu)造，這四個(gè)域分別稱為分別稱為op, arg1, arg2及及resultnoparg1arg2resultn(0)uminuscT1n(1)*bT1T2n(2)uminuscT3n(3)*bT3T4n(4)+T2T4T5n(5):=T5a 三地址語(yǔ)句三地址語(yǔ)句n三元式三元式 n經(jīng)過(guò)計(jì)算暫時(shí)變量值的語(yǔ)句的位置來(lái)援經(jīng)過(guò)計(jì)算暫時(shí)變量值的語(yǔ)句的位置來(lái)援用這個(gè)暫時(shí)變量用這個(gè)暫時(shí)變量n三個(gè)域：三個(gè)域：op、arg1和和arg2noparg1arg2n(0)uminuscn(1)*

14、b(0)n(2)uminuscn(3)*b(2)n(4)+(1)(3)n(5)assigna(4)三地址語(yǔ)句三地址語(yǔ)句nxi:=y nop arg1 arg2 n(0) = x i n(1) ynx:=yinop arg1 arg2n(0) = y in(1) assign x (0)三地址語(yǔ)句三地址語(yǔ)句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é)

15、省空間方便優(yōu)化，節(jié)省空間n例如，語(yǔ)句例如，語(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)7.2 闡明語(yǔ)句闡明語(yǔ)句7.3 賦值語(yǔ)句的翻譯賦值語(yǔ)句的翻譯 n7.3.1 簡(jiǎn)單算術(shù)表達(dá)式及賦值語(yǔ)句簡(jiǎn)單算術(shù)表達(dá)式及賦值語(yǔ)句 為賦值語(yǔ)句生成三地址代碼的為賦值語(yǔ)句生成三地址代碼的S-屬性文法定義屬性文法定義 產(chǎn)生式產(chǎn)生式語(yǔ)義規(guī)那么語(yǔ)義規(guī)那么Sid:=ES.code:=

16、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 | 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.plac

17、e; 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:=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 | g

18、en(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 := 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:=

19、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.code:=E1.codeEid E.place:=id.place; E.code= 7.3.2 數(shù)組元素的援用數(shù)組元素的援用n數(shù)組元素地址的計(jì)算：數(shù)組元素地址的計(jì)算：n設(shè)設(shè)A為為n維數(shù)組，每個(gè)元素寬度為維數(shù)組，每個(gè)元素寬度為w， lowi 為第為第i維維 的下界

20、，的下界，ni 是為第是為第i維維 可取值的個(gè)可取值的個(gè)數(shù)數(shù), base為為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) nL id Elist | idnElistElist,E | E n為了便于處置，文法改寫(xiě)為為了便于處置，文法改寫(xiě)為n LElist |

21、 id nElistElist, E | id E n引入以下語(yǔ)義變量或語(yǔ)義過(guò)程引入以下語(yǔ)義變量或語(yǔ)義過(guò)程:nElist.ndim ：下標(biāo)個(gè)數(shù)計(jì)數(shù)器：下標(biāo)個(gè)數(shù)計(jì)數(shù)器nElist.place ：表示暫時(shí)變量，用降暫時(shí)：表示暫時(shí)變量，用降暫時(shí)存放已構(gòu)成的存放已構(gòu)成的Elist中的下標(biāo)表達(dá)式計(jì)算出中的下標(biāo)表達(dá)式計(jì)算出來(lái)的值來(lái)的值 nlimit(array，j) ：函數(shù)過(guò)程，它給出數(shù)組：函數(shù)過(guò)程，它給出數(shù)組array的第的第j維的長(zhǎng)度維的長(zhǎng)度n每個(gè)代表變量的非終結(jié)符每個(gè)代表變量的非終結(jié)符L有兩項(xiàng)語(yǔ)義值有兩項(xiàng)語(yǔ)義值nL.place：n假設(shè)假設(shè)L為簡(jiǎn)單變量為簡(jiǎn)單變量i, 指變量指變量i的符號(hào)表入口的符號(hào)表

22、入口 n假設(shè)假設(shè)L為下標(biāo)變量，指存放為下標(biāo)變量，指存放CONSPART的的 暫時(shí)變量的整數(shù)碼暫時(shí)變量的整數(shù)碼 nL.offset ：n假設(shè)假設(shè)L為簡(jiǎn)單變量，為簡(jiǎn)單變量，null，n假設(shè)假設(shè)L為下標(biāo)變量，指存放為下標(biāo)變量，指存放VARPART的暫的暫時(shí)變量的整數(shù)碼時(shí)變量的整數(shù)碼 (1) SL:=E(2) EE+E(3) E(E)(4) EL(5) LElist (6) Lid(7) Elist Elist, E(8) Elistid E(1) SL:=E if L.offset=null then /*L是簡(jiǎn)單變量是簡(jiǎn)單變量*/emit(L.place := E.place) else emit

23、( L.place L.offset := E.place) (2) EE1 +E2 E.place:=newtemp; emit(E.place := E 1.place + E 2.place)(3) E(E1)E.place:=E1.place(4) EL if L.offset=null then E.place:=L.place else begin E.place:=newtemp; emit(E.place := L.place L.offset ) end Ai1,i2,ik (i1 n2+i2)n3+i3)nk+ik)w +base-(low1 n2+low2)n3+low3

24、)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+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.a

25、rray;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 := Elist.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的類型屬性的類型

26、屬性 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ū)分為整型算符算符區(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+ T3

27、n 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:=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=intege

28、r 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_error7.3.3 記錄

29、中域的援用記錄中域的援用 n符號(hào)表表項(xiàng)之中保管記錄中的域的類型和符號(hào)表表項(xiàng)之中保管記錄中的域的類型和相對(duì)地址信息相對(duì)地址信息7.4 布爾表達(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 | E | (E) | i rop i | in計(jì)算布爾表達(dá)式通常采用兩種方法計(jì)算布爾表達(dá)式通常采用兩種方法:n1. 好像計(jì)算算術(shù)表達(dá)式一樣好像計(jì)算算術(shù)表達(dá)式一樣,一步步算一步步算n 1 or (not 0

30、and 0) or 0n =1 or (1 and 0) or 0n =1 or 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 把把 A解釋成解釋成 if A then false else true兩種不同的翻譯方法兩種不同的翻譯方法:第一種翻譯法：第一種翻譯法： A or B and C=D翻譯成翻譯成(1) (=, C, D, T1)(2) (and, B, T1, T2)(3) (or, A, T

31、2, T3)第二種翻譯法適宜于作為條件表達(dá)式的布第二種翻譯法適宜于作為條件表達(dá)式的布爾表達(dá)式運(yùn)用爾表達(dá)式運(yùn)用.7.4.1 數(shù)值表示法數(shù)值表示法 na or b and not c 翻譯成翻譯成nT1:=not cnT2:=b and T1nT3:=a or T1nab的關(guān)系表達(dá)式可等價(jià)地寫(xiě)成的關(guān)系表達(dá)式可等價(jià)地寫(xiě)成nif ab then 1 else 0 ，翻譯成，翻譯成n 100: if ab goto 103n101: T:=0n102: goto 104n103: T:=1n104: 關(guān)于布爾表達(dá)式的數(shù)值表示法的翻譯方關(guān)于布爾表達(dá)式的數(shù)值表示法的翻譯方式式 n過(guò)程過(guò)程emit將三地址代碼

32、送到輸出文件中將三地址代碼送到輸出文件中nnextstat給出輸出序列中下一條三地址語(yǔ)句的給出輸出序列中下一條三地址語(yǔ)句的地址索引地址索引n每產(chǎn)生一條三地址語(yǔ)句后，過(guò)程每產(chǎn)生一條三地址語(yǔ)句后，過(guò)程emit便把便把nextstat加加1 關(guān)于布爾表達(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.p

33、lace:=newtemp; emit(E.place := not E 1.place)E(E1) E.place:=E1.place關(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 ab 翻譯成翻譯成100:if ab goto 103

34、101: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 bd goto L2 “真出口真出口 ngoto L3 “假出口假出口 nL2:(關(guān)于關(guān)于S1的三地址代碼序列的三地址代碼序列)ngoto LnextnL3:(關(guān)于關(guān)于S2

35、的三地址代碼序列的三地址代碼序列)nLnext:n每次調(diào)用函數(shù)每次調(diào)用函數(shù)newlabel后都前往一個(gè)新的后都前往一個(gè)新的符號(hào)標(biāo)號(hào)符號(hào)標(biāo)號(hào)n對(duì)于一個(gè)布爾表達(dá)式對(duì)于一個(gè)布爾表達(dá)式E，援用兩個(gè)標(biāo)號(hào)，援用兩個(gè)標(biāo)號(hào)nE.true是是E為為真真時(shí)控制流轉(zhuǎn)向的標(biāo)號(hào)時(shí)控制流轉(zhuǎn)向的標(biāo)號(hào)nE.false是是E為為假假時(shí)控制流轉(zhuǎn)向的標(biāo)號(hào)時(shí)控制流轉(zhuǎn)向的標(biāo)號(hào) 產(chǎn)生布爾表達(dá)式三地址代碼的語(yǔ)義規(guī)那產(chǎn)生布爾表達(dá)式三地址代碼的語(yǔ)義規(guī)那么么 產(chǎn)生式產(chǎn)生式語(yǔ)義規(guī)那么語(yǔ)義規(guī)那么 EE1 or E2 E1.true:=E.true; E1.false:=newlabel; E2.true:=E.true; E2.false:=E.f

36、alse; E.code:=E1.code | gen(E1.false :) | E2.code E1.codeTo E.trueTo E1.falseE2.codeTo E.trueTo E.false產(chǎn)生布爾表達(dá)式三地址代碼的語(yǔ)義規(guī)那產(chǎn)生布爾表達(dá)式三地址代碼的語(yǔ)義規(guī)那么么 產(chǎn)生式產(chǎn)生式語(yǔ)義規(guī)那么語(yǔ)義規(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. fals

37、eTo E1. trueE2.codeTo E.trueTo E.false產(chǎn)生布爾表達(dá)式三地址代碼的語(yǔ)義規(guī)那產(chǎn)生布爾表達(dá)式三地址代碼的語(yǔ)義規(guī)那么么 產(chǎn)生式產(chǎn)生式語(yǔ)義規(guī)那么語(yǔ)義規(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產(chǎn)生布爾表達(dá)式三地址代碼的語(yǔ)義規(guī)那產(chǎn)生布爾表達(dá)式三地址代碼的語(yǔ)義規(guī)那么么 產(chǎn)生式產(chǎn)生式語(yǔ)義規(guī)那么語(yǔ)義規(guī)那么 Eid1 relop id2 E.code:=gen(if id1.pla

38、ce 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)思索如下表達(dá)式：思索如下表達(dá)式： ab or cd and ef假定整個(gè)表達(dá)式的真假出口已分別置為假定整個(gè)表達(dá)式的真假出口已分別置為L(zhǎng)true和和Lfalse，那么按定義將生成如下的代碼：，那么按定義將生成如下的代碼：if ab goto Ltruegoto L1L1:if cd goto L2goto LfalseL2:if ef goto Ltruegoto

39、 Lfalse布爾表達(dá)式的翻譯布爾表達(dá)式的翻譯n兩遍掃描兩遍掃描n為給定的輸入串構(gòu)造一棵語(yǔ)法樹(shù)；為給定的輸入串構(gòu)造一棵語(yǔ)法樹(shù)；n對(duì)語(yǔ)法樹(shù)進(jìn)展深度優(yōu)先遍歷，進(jìn)展語(yǔ)義規(guī)對(duì)語(yǔ)法樹(shù)進(jìn)展深度優(yōu)先遍歷，進(jìn)展語(yǔ)義規(guī)那么中規(guī)定的翻譯。那么中規(guī)定的翻譯。n一遍掃描一遍掃描一遍掃描實(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 ro

40、p y goto pn四元式四元式(j, -, -, p) 表示表示 goto pn有時(shí)有時(shí),四元式轉(zhuǎn)移地址無(wú)法立刻知道四元式轉(zhuǎn)移地址無(wú)法立刻知道,我們我們只好把這個(gè)未完成的四元式地址作為只好把這個(gè)未完成的四元式地址作為E的的語(yǔ)義值保管語(yǔ)義值保管,待機(jī)待機(jī)回填回填。n為非終結(jié)符為非終結(jié)符E賦予兩個(gè)綜合屬性賦予兩個(gè)綜合屬性E.truelist和和E.falselist。它們分別記錄布爾表達(dá)式。它們分別記錄布爾表達(dá)式E所應(yīng)的所應(yīng)的四元式中需回填四元式中需回填“真、真、“假出口的四元式的假出口的四元式的標(biāo)號(hào)所構(gòu)成的鏈表標(biāo)號(hào)所構(gòu)成的鏈表 n例如例如:假定假定E的四元式中需求回填的四元式中需求回填真真出

41、口的出口的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)鏈尾鏈尾E. truelist =rn為了處置為了處置E.truelist和和E.falselist ，引入以下，引入以下語(yǔ)義變量和過(guò)程語(yǔ)義變量和過(guò)程:n變量變量nextquad，它指向下一條將要產(chǎn)生但尚，它指向下一條將要產(chǎn)生但尚未構(gòu)成的四元式的地址未構(gòu)成的四元式的地址(標(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ù)make

42、list(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ù)值，回送合并后的鏈條鏈合并為一，作為函數(shù)值，回送合并后的鏈?zhǔn)住Ｊ?。n過(guò)程過(guò)程backpatch(p, t)，其功能是完成，其功能是完成“回填回填，把，把p所鏈接的每個(gè)四元式的第四區(qū)段都填所鏈接的每個(gè)四元式的第四區(qū)段都填為為t。布爾表達(dá)式的文法布爾表達(dá)式的文法(1) E E1 or M E2(2) | E1

43、 and M E2(3)| not E1(4)| (E1)(5)| id1 relop id2(6)| id(7)M布爾表達(dá)式的翻譯方式布爾表達(dá)式的翻譯方式 (7) M M.quad:=nextquad 布爾表達(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.trueli

44、st:=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.truelist; E.falselist

45、:=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)； emit( j, -, -,

46、 0) 布爾表達(dá)式的翻譯方式布爾表達(dá)式的翻譯方式 n作為整個(gè)布爾表達(dá)式的作為整個(gè)布爾表達(dá)式的真真假假出口出口(轉(zhuǎn)移轉(zhuǎn)移目的目的)仍待回填仍待回填.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) truelist105 (j, -, -, 103) falselist n計(jì)算布爾表達(dá)式通常采用兩種方法計(jì)算布爾表達(dá)式通常采用兩種方法:n1. 好像計(jì)算算術(shù)表達(dá)式一樣好像計(jì)算算術(shù)表達(dá)式一樣,一步步算一步步算n 1 or (not 0 and 0)

47、 or 0n =1 or (1 and 0) or 0n =1 or 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 把把 A解釋成解釋成 if A then false else true回想：布爾表達(dá)式的翻譯回想：布爾表達(dá)式的翻譯 關(guān)于布爾表達(dá)式的數(shù)值表示法的翻譯方式關(guān)于布爾表達(dá)式的數(shù)值表示法的翻譯方式 Eid1 relop id2 E.place:=newtemp;emit(if id1.place

48、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) 回想：布爾表達(dá)式的翻譯回想：布爾表達(dá)式的翻譯n作為條件控制的布爾式翻譯作為條件控制的布爾式翻

49、譯n一遍掃描實(shí)現(xiàn)布爾表達(dá)式的翻譯一遍掃描實(shí)現(xiàn)布爾表達(dá)式的翻譯7.4.2 作為條件控制的布爾式翻譯作為條件控制的布爾式翻譯 n條件語(yǔ)句條件語(yǔ)句 if E then S1 else S2n 賦予賦予 E 兩種出口兩種出口:一真一假一真一假 E.codeS1.codeS2.codeTo E.trueTo E.falsegoto S.nextS.nextE.true:E.false:產(chǎn)生布爾表達(dá)式三地址代碼的語(yǔ)義規(guī)那產(chǎn)生布爾表達(dá)式三地址代碼的語(yǔ)義規(guī)那么么 產(chǎn)生式產(chǎn)生式語(yǔ)義規(guī)那么語(yǔ)義規(guī)那么 EE1 or E2 E1.true:=E.true; E1.false:=newlabel; E2.true:=E

50、.true; E2.false:=E.false; E.code:=E1.code | gen(E1.false :) | E2.code E1.codeTo E.trueTo E1.falseE2.codeTo E.trueTo E.false產(chǎn)生布爾表達(dá)式三地址代碼的語(yǔ)義規(guī)那產(chǎn)生布爾表達(dá)式三地址代碼的語(yǔ)義規(guī)那么么 產(chǎn)生式產(chǎn)生式語(yǔ)義規(guī)那么語(yǔ)義規(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.c

51、odeE1.codeTo E. falseTo E1. trueE2.codeTo E.trueTo E.false產(chǎn)生布爾表達(dá)式三地址代碼的語(yǔ)義規(guī)那產(chǎn)生布爾表達(dá)式三地址代碼的語(yǔ)義規(guī)那么么 產(chǎn)生式產(chǎn)生式語(yǔ)義規(guī)那么語(yǔ)義規(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產(chǎn)生布爾表達(dá)式三地址代碼的語(yǔ)義規(guī)那產(chǎn)生布爾表達(dá)式三地址代碼的語(yǔ)義規(guī)那么么 產(chǎn)生式產(chǎn)生式語(yǔ)義規(guī)那么語(yǔ)義規(guī)那么 Eid1 relop id2 E.

52、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)回想：布爾表達(dá)式的翻譯回想：布爾表達(dá)式的翻譯n作為條件控制的布爾式翻譯作為條件控制的布爾式翻譯n一遍掃描實(shí)現(xiàn)布爾表達(dá)式的翻譯一遍掃描實(shí)現(xiàn)布爾表達(dá)式的翻譯布爾表達(dá)式的文法布爾表達(dá)式的文法(1) E E1 or M E2(2) | E1 and M E2(3)| not E1(4)| (E1)(5)| id1 relop id

53、2(6)| id(7)M布爾表達(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.truelist:=E2.truelist; E.falselist:=merge(E1.falselist,E2.falselist) (3) Enot E1 E.truelist:=E1.

54、falselist; E.falselist:=E1.truelist(4) E(E1) E.truelist:=E1.truelist; 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(nextqua

55、d); E.falselist:=makelist(nextquad+1); emit(jnz , id .place , ,0)； emit( j, -, -, 0) (7) M M.quad:=nextquad 布爾表達(dá)式的翻譯方式布爾表達(dá)式的翻譯方式 n作為整個(gè)布爾表達(dá)式的作為整個(gè)布爾表達(dá)式的真真假假出口出口(轉(zhuǎn)移轉(zhuǎn)移目的目的)仍待回填仍待回填.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á)式。

56、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 then 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 el

57、se 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 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.

58、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 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:=g

59、en(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: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:=T2n

60、goto 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) | begin L endn(5)| An(6) LL;Sn(7)| SnS表示語(yǔ)句，表示語(yǔ)句， L表示語(yǔ)句表，表示語(yǔ)句表，n A為賦值語(yǔ)句，為賦值語(yǔ)句，E為一個(gè)布爾表達(dá)式為一個(gè)布爾表達(dá)式nif 語(yǔ)句的翻譯語(yǔ)句的翻譯n相關(guān)產(chǎn)生式相關(guān)產(chǎn)生式nS if E then S(1)n | if E then S(1) else S(2)n改寫(xiě)后產(chǎn)生式改寫(xiě)后