編譯7語(yǔ)義分析和中間代碼產(chǎn)生1

編譯原理(第三版)

陳火旺等編著（2015年9月-10月）主講：朱世松計(jì)算機(jī)學(xué)院22023/7/24概述一、語(yǔ)義分析的任務(wù)審查每一個(gè)語(yǔ)法結(jié)構(gòu)的靜態(tài)語(yǔ)義，即驗(yàn)證語(yǔ)法正確的結(jié)構(gòu)是否有意義。 如：賦值語(yǔ)句：x=x+y,左邊變量類型與右邊變量類型是否一致。在語(yǔ)義正確的基礎(chǔ)上生成一種中間代碼或目標(biāo)代碼。32023/7/24二、語(yǔ)義分析的范圍1.確定類型：確定標(biāo)識(shí)符所關(guān)聯(lián)的數(shù)據(jù)類型。2.類型檢查：按語(yǔ)言的類型規(guī)則，檢查運(yùn)算的合法性與運(yùn)算分量類型的一致性，必要時(shí)作類型轉(zhuǎn)換。3.識(shí)別含義：根據(jù)語(yǔ)言的語(yǔ)義定義（形式或非形式），識(shí)別程序中各構(gòu)造成分組合到一起的含義，并作相應(yīng)的語(yǔ)義處理（生成中間代碼或目標(biāo)代碼）42023/7/244.控制流檢查：控制流語(yǔ)句必須轉(zhuǎn)移到合法的地方。如：C中，break語(yǔ)句規(guī)定跳出最內(nèi)層的循環(huán)或switch語(yǔ)句.5.一致性檢查：在很多場(chǎng)合要求對(duì)象只能被說(shuō)明一次(避免重復(fù)定義)。6.相關(guān)名字檢查：如：Ada，循環(huán)或塊可以有一個(gè)名字，它出現(xiàn)在這些結(jié)構(gòu)的開頭或結(jié)尾。編譯程序必須檢查這兩個(gè)地方用的名字是否相同。52023/7/24三、語(yǔ)義描述工具和語(yǔ)義分析方法語(yǔ)義描述工具目前流行：用屬性文法作為描述語(yǔ)義的工具。語(yǔ)義分析方法 根據(jù)描述屬性文法的語(yǔ)義規(guī)則的方式不同，語(yǔ)義分析方法分為：語(yǔ)法制導(dǎo)定義方法翻譯方案62023/7/241中間語(yǔ)言中間語(yǔ)言：它介于源程序到目標(biāo)語(yǔ)言程序中間程序的語(yǔ)言中間語(yǔ)言程序：用中間語(yǔ)言表示的程序。作用：用于編譯程序，將源程序翻譯成等價(jià)的中間語(yǔ)言程序，再將中間語(yǔ)言程序轉(zhuǎn)化成目標(biāo)程序（即將語(yǔ)義分析和目標(biāo)代碼生成分開處理）源程序 中間語(yǔ)言程序 目標(biāo)程序中間語(yǔ)言是表示語(yǔ)法制導(dǎo)翻譯的結(jié)果。等價(jià)變換轉(zhuǎn)化7.1中間語(yǔ)言72023/7/24好處：中間語(yǔ)言與機(jī)器無(wú)關(guān)，使采用中間語(yǔ)言進(jìn)行翻譯的編譯程序系統(tǒng)易于移植。易于優(yōu)化翻譯后的代碼。使編譯程序的結(jié)構(gòu)在邏輯上更簡(jiǎn)單明確。2中間語(yǔ)言的表示常見：逆波蘭表示 四元式表示和三地址代碼、三元式 圖表示：DAG和樹形表示82023/7/247.1.1逆波蘭表示由波蘭邏輯學(xué)家J.Lukasiewicz(盧卡西維茲)首先提出用來(lái)表示表達(dá)式的方法，后來(lái)推廣到表示程序設(shè)計(jì)語(yǔ)言中的其它語(yǔ)法成分。表達(dá)式的逆波蘭表示表達(dá)式的表示：中綴表示： 運(yùn)算符居中，運(yùn)算對(duì)象在左右兩邊:a+b波蘭表示：前綴表示：運(yùn)算符在前，運(yùn)算對(duì)象在后：+ab后綴表示：運(yùn)算對(duì)象在前，運(yùn)算符在后：ab+…(逆波蘭表示)92023/7/24例：逆波蘭表示的例子中綴表示(一般表示)逆波蘭表示a+b*cabc*+a*(b+c/d)abcd/+*a*b+cab*c+a*b+(c-d)/eab*cd-e/+102023/7/24(1)表達(dá)式逆波蘭表示的定義：設(shè)E是一般表達(dá)式，則：

一般表達(dá)式

逆波蘭表達(dá)式若E為變量或常量 E（E） E的逆波蘭式E(1)opE(2)(二目運(yùn)算) E(1)的逆波蘭式E(2)的逆波蘭式opopE(單目運(yùn)算) E的逆波蘭式op112023/7/24把表達(dá)式翻譯成后綴式的語(yǔ)義規(guī)則描述產(chǎn)生式E→E(1)opE(2)E→(E(1))E→id

語(yǔ)義動(dòng)作E.code:=E(1).code||E(2).code||opE.code:=E(1).codeE.code:=idE.code表示E后綴形式op表示任意二元操作符“||”表示后綴形式的連接。122023/7/24(2)逆波蘭表示的特點(diǎn)a.標(biāo)識(shí)符(運(yùn)算對(duì)象)出現(xiàn)的順序（從左到右）和原有順序相同。b.運(yùn)算符是按實(shí)際計(jì)算順序（從左到右）出現(xiàn)的。c.運(yùn)算符緊跟在運(yùn)算對(duì)象的后面出現(xiàn)，并且沒(méi)有括號(hào)。132023/7/24(3)好處：易于對(duì)表達(dá)式的計(jì)算處理對(duì)于一般表達(dá)式的計(jì)算，系統(tǒng)需要用兩個(gè)工作棧分別處理運(yùn)算對(duì)象和運(yùn)算符。對(duì)于逆波蘭表示的表達(dá)式計(jì)算處理只用一個(gè)工作棧。一般的計(jì)算過(guò)程是：自左至右掃描后綴式，每碰到運(yùn)算量就把它推進(jìn)棧。每碰到k目運(yùn)算符就把它作用于棧頂?shù)膋個(gè)項(xiàng)，并用運(yùn)算結(jié)果代替這k個(gè)項(xiàng)。142023/7/24例：逆波蘭式ab+c*的計(jì)算處理過(guò)程遇運(yùn)算對(duì)象a,b入棧掃描ab+c*ba棧遇二目運(yùn)算符+c*取出a,b，運(yùn)算結(jié)果T入棧TcT取出c,T作運(yùn)算，設(shè)結(jié)果T1T1遇運(yùn)算符*c*遇運(yùn)算對(duì)象c入棧152023/7/242.形成逆波蘭表示 怎樣將一般表達(dá)式轉(zhuǎn)換成逆波蘭表示？

基本思想:從左到右掃描表達(dá)式，每遇到：

1o

表達(dá)式中的運(yùn)算對(duì)象則往左去。

2o

表達(dá)式中的運(yùn)算符，則與運(yùn)算符棧頂元素比較優(yōu)先數(shù)：162023/7/24逆波蘭表示表達(dá)式運(yùn)算對(duì)象運(yùn)算符進(jìn)棧出棧運(yùn)算符棧

如果運(yùn)算符棧頂元素的優(yōu)先數(shù)大于或等于表達(dá)式中當(dāng)前的運(yùn)算符優(yōu)先數(shù)，則棧頂元素退棧向左去。然后當(dāng)前運(yùn)算符繼續(xù)與棧頂?shù)男略乇容^優(yōu)先數(shù)。直到棧頂元素的優(yōu)先數(shù)小于表達(dá)式中當(dāng)前運(yùn)算符為止。此時(shí)，才將表達(dá)式中當(dāng)前運(yùn)算符進(jìn)棧。172023/7/24例：畫出形成表達(dá)式a*(b+c/d)的逆波蘭表示過(guò)程a*(b+c/d)##步驟①a(b+c/d)#*#步驟②ab+c/d)#(*#步驟③ab+c/d)#(*#步驟④abc/d)#+(*#步驟⑤abc/d)#+(*#步驟⑥182023/7/24abcd)#/+(*#步驟⑦abcd)#/+(*#步驟⑧/+(*#abcd/)#步驟⑨+(*#abcd/+)#步驟⑩*#abcd/+*#步驟⑾192023/7/24形成逆波蘭表示的過(guò)程，實(shí)質(zhì)上是表達(dá)式的翻譯過(guò)程。（算法不難寫出）例：a/b/c+d=>ab/c/d+(a+b)*(c-d/e)=>ab+cde/-*202023/7/24數(shù)組POST存放后綴式：k為下標(biāo)，初值為1上述語(yǔ)義動(dòng)作可實(shí)現(xiàn)為： 產(chǎn)生式 程序段

E→E(1)opE(2) {POST[k]:=op;k:=k+1} E→(E(1)) {} E→i {POST[k]:=i;k:=k+1}例：輸入串a(chǎn)+b+c的分析和翻譯

POST：12345E→E(1)opE(2) E.code:=E(1).code||E(2).code||opE→(E(1)) E.code:=E(1).codeE→id E.code:=idab+c+…212023/7/247.1.2圖表示法圖表示法DAG抽象語(yǔ)法樹

222023/7/247.1.2圖表示法無(wú)循環(huán)有向圖(DirectedAcyclicGraph，簡(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)232023/7/24a:=b*(-c)+b*(-c)的圖表示法assigna+*buminuscDAGassigna+*buminusc抽象語(yǔ)法樹*buminusc242023/7/24抽象語(yǔ)法樹對(duì)應(yīng)的代碼：

T1:=-c T2:=b*T1

T3:=-c T4:=b*T3 T5:=T2+T4

a:=T5assigna+*buminusc抽象語(yǔ)法樹*buminusc252023/7/24DAG對(duì)應(yīng)的代碼：T1:=-cT2:=b*T1T5:=T2+T2a:=T5assigna+*buminuscDAG抽象語(yǔ)法樹對(duì)應(yīng)的代碼：

T1:=-c T2:=b*T1

T3:=-c T4:=b*T3 T5:=T2+T4

a:=T5262023/7/24

產(chǎn)生賦值語(yǔ)句抽象語(yǔ)法樹的屬性文法

產(chǎn)生式 語(yǔ)義規(guī)則S→id:=E S.nptr:=mknode(‘a(chǎn)ssign’,

mkleaf(id,id.place),E.nptr)E→E1+E2

E.nptr:=mknode(‘+’,E1.nptr,E2.nptr)E→E1*E2

E.nptr:=mknode(‘*’,E1.nptr,E2.nptr)E→-E1

E.nptr:=mknode(‘uminus’,E1.nptr)E→(E1) E.nptr:=E1.nptrE→id E.nptr:=mkleaf(id,id.place)272023/7/247.1.3三地址代碼三地址代碼x:=yopz三地址代碼可以看成是抽象語(yǔ)法樹或DAG的一種線性表示282023/7/24a:=b*(-c)+b*(-c)的圖表示法assigna+*buminuscDAGassigna+*buminusc抽象語(yǔ)法樹*buminusc292023/7/24 T1:=-c T1:=-c T2:=b*T1 T2:=b*T1 T3:=-c T5:=T2+T2 T4:=b*T3 a:=T5 T5:=T2+T4

a:=T5對(duì)于抽象語(yǔ)法樹的代碼 對(duì)于DAG的代碼302023/7/24三地址語(yǔ)句的種類x:=yopzx:=opyx:=ygotoLifxrelopygotoL或ifagotoLparamx和callp,n,以及返回語(yǔ)句returnyx:=y[i]及x[i]:=y的索引賦值x:=&y,x:=*y和*x:=y的地址和指針賦值312023/7/24生成三地址代碼時(shí)，臨時(shí)變量的名字對(duì)應(yīng)抽象語(yǔ)法樹的內(nèi)部結(jié)點(diǎn)id:=E對(duì)表達(dá)式E求值并置于變量T中值id.place:=T322023/7/24從賦值語(yǔ)句生成三地址代碼的S-屬性文法非終結(jié)符號(hào)S有綜合屬性S.code，它代表賦值語(yǔ)句S的三地址代碼。非終結(jié)符號(hào)E有如下兩個(gè)屬性：E.place表示存放E值的名字。E.code表示對(duì)E求值的三地址語(yǔ)句序列。函數(shù)newtemp的功能是，每次調(diào)用它時(shí)，將返回一個(gè)不同臨時(shí)變量名字,如T1,T2,…。gen(x‘:=’y‘+’z)表示生成三地址代碼。332023/7/24為賦值語(yǔ)句生成三地址代碼的S-屬性文法定義

產(chǎn)生式 語(yǔ)義規(guī)則S→id:=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(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.codeE→id E.place:=id.place; E.code=‘’342023/7/24三地址語(yǔ)句四元式一個(gè)帶有四個(gè)域的記錄結(jié)構(gòu)，這四個(gè)域分別稱為op,arg1,arg2及result op arg1 arg2 result(0) uminus c T1(1) * b T1 T2(2) uminus c T3(3) * b T3 T4(4) + T2 T4 T5(5) := T5 a

352023/7/24三地址語(yǔ)句三元式通過(guò)計(jì)算臨時(shí)變量值的語(yǔ)句的位置來(lái)引用這個(gè)臨時(shí)變量三個(gè)域：op、arg1和arg2 op arg1 arg2(0) uminus c (1) * b (0)(2) uminus c (3) * b (2)(4) + (1) (3)(5) assign a (4)362