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

編譯原理(第三版)

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

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

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

1o

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

2o

表達(dá)式中的運(yùn)算符，則與運(yùn)算符棧頂元素比較優(yōu)先數(shù)：162023/2/3逆波蘭表示表達(dá)式運(yùn)算對象運(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)算符為止。此時，才將表達(dá)式中當(dāng)前運(yùn)算符進(jìn)棧。172023/2/3例：畫出形成表達(dá)式a*(b+c/d)的逆波蘭表示過程a*(b+c/d)##步驟①a(b+c/d)#*#步驟②ab+c/d)#(*#步驟③ab+c/d)#(*#步驟④abc/d)#+(*#步驟⑤abc/d)#+(*#步驟⑥182023/2/3abcd)#/+(*#步驟⑦abcd)#/+(*#步驟⑧/+(*#abcd/)#步驟⑨+(*#abcd/+)#步驟⑩*#abcd/+*#步驟⑾192023/2/3形成逆波蘭表示的過程，實(shí)質(zhì)上是表達(dá)式的翻譯過程。（算法不難寫出）例：a/b/c+d=>ab/c/d+(a+b)*(c-d/e)=>ab+cde/-*202023/2/3數(shù)組POST存放后綴式：k為下標(biāo)，初值為1上述語義動作可實(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/2/37.1.2圖表示法圖表示法DAG抽象語法樹

222023/2/37.1.2圖表示法無循環(huán)有向圖(DirectedAcyclicGraph，簡稱DAG)對表達(dá)式中的每個子表達(dá)式，DAG中都有一個結(jié)點(diǎn)一個內(nèi)部結(jié)點(diǎn)代表一個操作符，它的孩子代表操作數(shù)在一個DAG中代表公共子表達(dá)式的結(jié)點(diǎn)具有多個父結(jié)點(diǎn)232023/2/3a:=b*(-c)+b*(-c)的圖表示法assigna+*buminuscDAGassigna+*buminusc抽象語法樹*buminusc242023/2/3抽象語法樹對應(yīng)的代碼：

T1:=-c T2:=b*T1

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

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

T1:=-c T2:=b*T1

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

a:=T5262023/2/3

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

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

產(chǎn)生式 語義規(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/2/3三地址語句四元式一個帶有四個域的記錄結(jié)構(gòu)，這四個域分別稱為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/2/3三地址語句三元式通過計(jì)算臨時變