編譯原理-第七章

第七章語義分析和中間代碼生成1、編譯程序的任務是把源語言程序翻譯成目標程序，有些編譯程序在編譯過程中，不產(chǎn)生中間語言，而是直接從源語言程序翻譯成目標語言程序。源程序編譯程序目標代碼

以上編譯過程省略了中間語言，它不利于編譯所產(chǎn)生的目標代碼的優(yōu)化.為了產(chǎn)生高質(zhì)量的代碼，可以將源語言程序首先翻譯成一種特殊形式的中間語言代碼形式，并對其進行優(yōu)化，然后再將它翻譯成最終的目標代碼。源程序語法分析中間代碼優(yōu)化優(yōu)化后中間代碼目標代碼代碼生成中間代碼

中間代碼也叫中間語言（Intermediatecode/language）是：源程序的一種內(nèi)部表示，不依賴目標機的結(jié)構，復雜性介于源語言和機器語言之間。中間代碼的優(yōu)點1、邏輯結(jié)構清楚；2、利于不同目標機上實現(xiàn)同一種語言；3、利于進行與機器無關的優(yōu)化；語義分析在詞法分析和語法分析之后，編譯程序要完成語義分析和翻譯工作。由于編譯器完成的分析是靜態(tài)定義的，所以，語義分析也可稱作靜態(tài)語義分析（staticsemanticanalysis）。語義分析的具體工作1、類型檢查；2、控制流檢查；3、一致性檢查；4、相關名字檢查語法制導翻譯對文法中的每個產(chǎn)生式都附加一個語義動作或語義子程序，且在語法分析過程中，每當需要使用一個產(chǎn)生式進行推導或規(guī)約時，語法分析程序除執(zhí)行相應的語法分析動作之外，還要執(zhí)行相應地語義動作或語義子程序。每個語義子程序都指明了相應產(chǎn)生式中各個符號的具體含義，并規(guī)定了使用該產(chǎn)生式進行分析時所應采取的語義動作。由此可見：抽象文法符號的具體語義信息，是在語法分析同步的語義處理過程中獲取和加工的。屬性文法

將語義以“屬性”的形式附加到各文法符號上，再根據(jù)產(chǎn)生式所蘊含的語義，給出每個文法符號的屬性的求值規(guī)則，從而形成一種帶有語義屬性的前后文無關文法，即屬性文法。屬性

一個文法符號X的語義信息我們稱之為語義屬性或簡稱為屬性（Atrributes）X.TYPE表示為X的類型X.VAL表示為X的值例:對于文法:E

→E+T|TT→digit

例語法制導翻譯的實質(zhì)

根據(jù)文法中每個產(chǎn)生式所蘊含的語義，為其配備一個（或多個）語句或子程序，對所要完成的功能進行描述，在語法分析過程中，當分析器使用該產(chǎn)生式進行語法分析時（不論是推導還是規(guī)約），除完成語法分析動作之外，還將調(diào)用為其配備的語義子程序，進行相應地語義處理，完成語義翻譯工作。中間代碼常見的幾種形式1、后綴式2、圖表示法抽象語法樹、DAG圖3、三地址代碼三元式、四元式、間接三元式后綴式

后綴式是波蘭邏輯學家盧卡西維奇（J.Lukasiewicz）提出的一種對表達式的表示方法：每一運算符都置于其運算對象之后，即操作數(shù)寫在前面，算符寫在后面。

它的特點是：表達式中各個運算是按運算符出現(xiàn)的順序進行的，故無需用括號來指示運算順序，因而又稱為無括號式。實例

表達式（中綴式）：A+B*（C-D）+E/（C-D）

后綴式：CD-B*A+CD-E/+表達式(中綴式):（a=0∧b>3）∨（e∧x

>y）后綴式:a0=b3>xy>e∧∨∧

結(jié)論從以上兩個例子我們可得出：1、在兩種表示中，運算對象出現(xiàn)的順序相同；2、在后綴表示中，運算符按實際計算順序從左到右排列，且每一運算符總是跟在運算對象之后。翻譯成后綴式的語義描述見P167表7.1。后綴式的推廣條件語句的翻譯：IfeTHENS1elseS2圖表示法-抽象語法樹

在語法樹中去掉一些對翻譯不必要的信息后，獲得的更有效的源程序的中間表示，這種經(jīng)過變換后的語法樹稱為抽象語法樹。在抽象語法樹中，操作符和關鍵字都不作為葉子節(jié)點出現(xiàn)，而是把它們作為內(nèi)部節(jié)點，即這些葉子節(jié)點的父節(jié)點。

例1

if-then-elseBS1S2S→ifBthenS1elseS2例1

++*a*-da-bcbca+a*（b-c）+（b-c）*d翻譯成抽象語法樹的屬性文法見P169表7.2圖表示法-DAG圖DAG（DirectedAcyclicGraph）有向無循環(huán)圖對表達式中的每個子表達式，DAG都有一個結(jié)點，一個內(nèi)部結(jié)點代表一個操作符，他的孩子代表操作數(shù)。在一個DAG中代表公共子表達式的節(jié)點具有多個父結(jié)點（與抽象語法樹中公共子表達式被表示為重復的子樹不同）例

++**da-bca+a*（b-c）+（b-c）*d抽象語法樹的表示方法1、每一個結(jié)點用一個記錄來表示，該記錄包括一個運算符域和若干個指向子結(jié)點的指針域。例：a：=b*-c+b*-cassignassigna+a+***b-b-b-ccc

抽象語法樹DAG方法1assign??ida+??*??idbuminus?idc*??idbUminus?idc方法2把所有的結(jié)點安排在一個記錄的數(shù)組中，結(jié)點的位置或索引作為指向地點的指針。

三地址代碼三地址代碼最基本的用法形式:

x:=yopz其中x、y、z為名字、常數(shù)或編譯時產(chǎn)生的臨時變量；op代表運算符號。每個語句的右邊只能有一個運算符。例如：x+y*z可以翻譯為：

T1：=y*zT2：=x+T1T1、T2位編譯時產(chǎn)生的臨時變量三地址代碼可以看成是抽象語法樹一種線性表示assigna+**b-b-cc

抽象語法樹

T1:=-cT2:=b*T1T3:=-cT4:=b*T3T5:=T2+T4a:=T5三地址代碼三地址代碼可以看成是DAG的一種線性表示assigna+*b-c

DAG

T1:=-cT2:=b*T1T3:=T2+T2a:=T3三地址代碼最后看P171，表7.3三地址碼的各種形式：P170x:=yopzx:=opz

x:=yGotoLifxrelopygotoL

ifagotoL

Paramxcallp,n

returnyx:=y[i]x[i]:=yx:=&y

x:=*y

*x:=y

賦值語句翻譯為三地址碼的屬性文法P171，表7.3三地址代碼—四元式四元式實際上是一種“三地址語句”的等價表示，是一個帶有四個域的記錄結(jié)構。它的一般形式為：（op，arg1，arg2，result）需要指出的是：每個四元式只能有一個運算符，所以，一個復雜的表達式只能由多個四元式構成的序列表示。例

a：=b*-c+b*-c三地址代碼-三元式

三元式顧名思義就是帶有三個域的記錄結(jié)構，他的一般形式為（i）（op，arg1，arg2）其中，（i）為三元式的編號，也代表了該式的運算結(jié)果，op，arg1，arg2的含義與四元式類似，區(qū)別在于arg可以是某三元式的序號，表示用該三元式的結(jié)果作為運算對象。例a：=b*-c+b*-c三元式和四元式的比較1、無論在一個三元式序列還是四元式序列中，各個三元式或四元式都是按相應表達式的實際運算順序出現(xiàn)的；相同點：2、對同一表達式而言，所需的三元式或四元式的個數(shù)一般都是相同的。三元式和四元式的比較1、由于三元式?jīng)]有result字段，且不需要臨時變量，故三元式比四元式占用的存儲空間少；不同點：2、在進行代碼優(yōu)化處理時，常常需要挪動一些運算的位置，這對于三元式序列來說是很困難的，但對于四元式來說，由于四元式之間的相互聯(lián)系是通過臨時變量來實現(xiàn)的，所以，更改其中一些四元式給整個系列帶來的影響就比較小。三地址代碼-間接三元式

建立兩個與三元式有關的表格，一個稱為三元式表，用于存放各三元式本身；另一個稱為執(zhí)行表，它按照三元式的執(zhí)行順序，依次列出相應各三元式在三元式表中的位置，也就是說我們用一個三元式表連同執(zhí)行表來表示中間代碼。通常我們稱這種表示方法為間接三元式。例x：=（a+b）*cb：=a+by：=c*（a+b）三元式x：=（a+b）*cb：=a+by：=c*（a+b）

（1）（+，a，b）（5）（+，a，b）（2）（*，（1），c）（6）（*，c，（5））（3）（：=，x，（2））（7）（：=，y，（6））（4）（：=，b，（1））

間接三元式x：=（a+b）*c

b：=a+b

y：=c*（a+b）執(zhí)行表三元式表（1）（1）（+，a，b）（2）（2）（*，（1），c）（3）（3）（：=，x，（2））（4）（4）（：=，b，（1））（1）（5）（：=，y，（2））（2）（5）三元式與間接三元式之間的區(qū)別1、由于間接三元式在執(zhí)行表中已經(jīng)依次列出每次要執(zhí)行的那個三元式，若其中有相同的三元式，則僅需在三元式表中保存其中之一，即三元式的項數(shù)一般比執(zhí)行表的項數(shù)少；2、當進行代碼優(yōu)化需要挪動運算順序時，則只需對執(zhí)行表進行相應地調(diào)整，而不必再改動三元式本身，這樣，就避免了前面講到的因改變?nèi)降捻樞蛩鸬穆闊Ｋ脑剑阂话阈问?(Op，arg1，arg2，result)arg1、arg2為參加運算的兩個分量result為運算結(jié)果若為單目運算，arg2為空，用“-”表示舉例說明：1.表達式的四元式：例1.a*b+c/d(*,a,b,T1)(/,c,d,T2)(+,T1,T2,T)例2.-(a*b-c)(*,a,b,T1)(-,T1,c,T2)(@,T2,-,T)@表示單目運算減2.賦值語句的四元式：把賦值看成一種運算，arg2為空例1：x:=10(:=,10,-,x)例2：x:=-(a*b-c)(*,a,b,T1)

(-,T1,c,T2)

(@,T2,-,T)

(:=,T,-,x)3.轉(zhuǎn)向語句的四元式：有以下三種跳轉(zhuǎn)四元式：(jnz,a,-,p)表示ifagotop；(jrop,x,y,p)表示ifxropygotop；(j,-,-,p)表示gotop；rop為：=，<>，<=<，>=，>

4.條件語句的四元式：例1：ifa<bthenx:=a+belsex:=a-b對應的四元式為：(1)(j<,a,b,

)(2)(j,-,-,

)(3)(+,a,b,T1)(4)(:=,T1,-,x)(5)(j,-,-,

)(6)(-,a,b,T2)(7)(:=,T2,-,x)(8)……685.循環(huán)語句的四元式

待討論循環(huán)語句的翻譯時介紹?；靥罨靥罨靥?例2：ifa<bande＞dthenx:=a+belsex:=a-b例3：ifa<bore＞dthenx:=a+belsex:=a-b

語法制導的翻譯方法：

就是對文法中的每個產(chǎn)生式都附加一個語義動作或語義子程序，且在語法分析過程中，每當需要使用一個產(chǎn)生式進行推導或歸約時，語法分析程序除執(zhí)行相應的語法分析動作之外，還要執(zhí)行相應地語義動作或語義子程序。每個語義子程序都指明了相應產(chǎn)生式中各個符號的具體含義，并規(guī)定了使用該產(chǎn)生式進行分析時所應采取的語義動作。翻譯過程見P171表7。3。這種模式既把語法分析與語義處理分開，又令其平行地進行，讓其在同一遍掃描中同時完成語法分析和語義處理兩項工作。一.過程中的說明語句說明語句的翻譯，主要工作是填符號表、分配地址說明語句的文法產(chǎn)生式及語義動作如下：T→integer {T.type:=integer;T.width:=4}T→real {T.type:=real;T.width:=8}T→array[num]ofT1 {T.type:=array(num.val,T1.type); T.width:=num.val*T1.width}T→↑T1 {T.type:=pointer(T1.type); T.width:=4}D→D;DD→id:T {enter(,T.type,offset);offset:=offset+T.width}P→MD {offset:=0}M→ε{offset:=0}offset為存儲空間分配指針，每個過程均從0開始。enter為填符號表過程7.2說明語句的翻譯

例：a:integer;b:real7.3賦值語句的翻譯S→id:=E{p:=lookup();ifp<>nilthenemit(id.place,‘:=’,E.place)elseerror }E→(E1){E.place:=E1.place;}E→-E1{E.place:=newtemp;emit(E.place,‘:=’,‘uminus’,E1.place)}E→E1*E2{E.place:=newtemp; emit(E.place,‘:=’,E1.place‘*’,E2.place)}E→E1+E2{E.place:=newtemp; emit(E.place,‘:=’,E1.place‘+’,E2.place)}7.3.1簡單算術表達式及賦值語句的翻譯簡單算術表達式及賦值語句的產(chǎn)生式及語義動作如下：Lookup為查符號表過程Emit過程用于生成三地址碼指令語句并送往輸出文件E→id{p:=lookup();ifp<>nilthenE.place:=pelseerror}掌握1、2、lookup()3、

emit(…)的含義7.3.2數(shù)組元素的引用一、數(shù)組元素的地址計算1、一維數(shù)組設數(shù)組A[low..n],每個元素占w個單元，則LOC(A[i])=base+(i-low)*w

=i*w+(base-low*w)其中varpart=i*wC=low*wconspart=base-C即地址D=varpart+conspart7.3.2數(shù)組元素的引用一、數(shù)組元素的地址計算2、二維數(shù)組(按行存放）設i1,i2的下界為low1,low2,數(shù)組是n1×n2,每個元素占w個單元，則LOC(A[i1,i2])=base+((i1-low1)*n2+i2-low2)*w

=((i1*n2)+i2)*w+(base-((low1*n2)+low2)*w)其中varpart=((i1*n2)+i2)*w

C=((low1*n2)+low2)*w)conspart=base-C即地址D=varpart+conspart推廣到k維數(shù)組(按行存放）LOC(A[i1,i2，…,ik])=(…(i1*n2+i2)n3+i3)…)nk+ik)*w+base-(…(low1*n2+low2)n3+low3)…)nk+lowk)*w對C或varpart的計算，可用遞歸公式e1=i1em=em-1*nm+im當m=k時，ek*w7.3.2數(shù)組元素的引用一、數(shù)組元素的地址計算例：A[x]

地址可變部分為x*W,應生成指令：

(T’:=X*W)A[x,y]地址可變部分為(x*n2+y)*W,應生成指令：

(T1:=X*n2)

(T1:=T1+y)

(T’:=T1*W)A[x,y,z]地址可變部分為((x*n2+y)*n3+z)*W,應生成指令：(T1:=X*n2)

(T1:=T1+y)(T2:=T1*n3)

(T3:=T2+z)

(T’:=T3*W)地址不變部分的指令為:

(T=A-C)地址結(jié)果指令為:

(T’’=T[T’])二、賦值語句中數(shù)組元素的翻譯賦值語句的文法：S→id:=EE→E1+E2E→E1*E2E→-E1E→(E1)E→id

增加L→id[Elist]|idElist→Elist,E|E為便于語義處理，再改為L→Elist]|idElist→Elist,E|id[ELL含數(shù)組元素的賦值語句的文法p181-183(1)S→L:=E(2)E→E+E(3)E→(E)(4)E→L(5)L→Elist](6)L→id(7)Elist→Elist,E(8)Elist→id[E引進如下語義變量和過程：1.Elist.array2.Elist.ndim3.limit(array,j)4.Elist.place5.L.place,L.offset

含有數(shù)組的賦值語句文法產(chǎn)生式如下： (1)S→L:=E

(2)E→E+E

(3)E→(E)

(4)E→L

(5)L→id

(6)Elist→id[E

(7)Elist→Elist,E

(8)L→Elist]例：x:=A[y,z]的語法樹如右圖：xSL:=ELE]ElistEElist,Lz[LAy（3）L→Elist]

{L.place:=newtemp;emit(L.place‘:=’Elist.array‘-’C);

L.offset:=neswtemp;

emit(L.offset‘:=’w‘﹡’Elist.place)}（1）Elist

→id[E

{Elist.place:=E.place;Elist.ndim:=1;

Elist.array:=id.place}（2）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}（4）L→id

{L.place:=id.place;L.offset:=null}其相應的語義動作如下：計算：Em=Em-1*nm+im賦初值：(E1=i1)例見P183（7）E

→E1+E2

{E.place:=newtemp;

emit(E.place‘:=’E1.place‘+’E2.place)}（6）E

→(E1)

{E.place:=E1.place}（5）E→L

{ifL.offset=nullthenE.place:=L.place

elsebeginE.place:=newtemp;

emit(E.place‘:=’L.place‘[’L.offset‘]’)

end}（8）S→L:=E

{ifL.offset=nullthen/*L是簡單變量*/

emit(L.place‘:=’E.place)

elseemit(L.place‘[’L.offset‘]’‘:=’E.place)}7.4布爾表達式的翻譯文法：E→EorE|EandE|notE|(E)|idrelopid|id

布爾表達式是由布爾運算符作用于布爾變量或關系表達式組成。布爾運算符：notandor關系表達式：E1ropE27.4布爾表達式的翻譯布爾表達式的計算通常有兩種方法：

1.嚴格按計算規(guī)則進行：例：1or(not0and0)or0=1or(1and0)or0=1or0or0=1or0=12.采取優(yōu)化措施，省略計算步驟：即：AorB→ifAthen1elseBAandB→ifAthenBelse0notA→ifAthen0else1在程序中布爾表達式的作用有兩個方面：計算邏輯值；控制程序流程；因此討論布爾表達式的兩種翻譯方式：邏輯值計算：Ex1.aorbandnotc翻譯為：T1:=notcT2:=bandT1T3:=aorT2Ex2.a<b翻譯為:100:ifa<bgoto103101:T:=0102:goto104103:T:=1104:Ex3.a<borc<dande<f的三地址代碼100)ifa<bgoto103105)T2:=0110)goto112101)T1:=0106)goto108111)T3:=1102)goto104107)T2:=1112)T4:=T2andT3103)T1:=1108)ife<fgoto111113)T5:=T1orT4104)ifc>dgoto107109)T3:=0則計算邏輯值的布爾表達式的語義動作為：P186E→id{E.place:=id.place}E→id1relopid2{E.place:=newtemp;emit(‘if’id1.placerelop.Opid2.Place‘goto’nextstat+3); emit(E.place‘:=’‘0’); emit(‘goto’nextstat+2);emit(E.place‘:=’‘1’)}E→(E1) {E.place:=E1.place}E→notE1 {E.place:=newtemp;emit(E.place‘:=’‘not’E1.place)}E→E1andE2 {E.place:=newtemp; emit(E.place‘:=’E1.place‘a(chǎn)nd’E2.place)}E→E1orE2 {E.place:=newtemp; emit(E.place‘:=’E1.place‘or’E2.place)}二、作為條件控制的布爾式翻譯

由于條件語句：if

E

thenS1elseS2中

E的作用僅在于控制對

S1或S2

的選擇，而E的值無須保留,因此賦予E兩個新的語義值:

E.true(真出口,出向S1)

E.false(假出口,出向S2)其含義及作用見圖：E.codeS1.codeGotos.nextS2.code…

E.true

E.falseE.true：E.false：

S.next:ifEthenS1elseS2Ex1:ifa>corb<dthens1elses2翻譯：ifa>cgotoL2gotoL1L1:ifb<dgotoL2gotoL3L2:S1的代碼

gotoSnextL3:S2的代碼Snext:二、作為條件控制的布爾式翻譯思路對布爾表達式E,引入標號E.ture和E.falseE形如a<bE形如E1orE2E形如E1andE2E形如notE1seeP188table7.7Ex2.a<borc<dande<f的三地址代碼設整個表達式的真假出口為Etrue和Efalse,則代碼：Ifa<bgotoEturegotoL1L1:ifc<dgotoL2gotoEfalseL2:ife<fgotoEturegotoEfalse

seeP188table7.71、四元式形式表示三地址碼（jnz,a,,p)(jrop,x,y,p)(j,,,p)2、關于拉鏈回填問題寫出以下語句的四元式形式：Ex1:a<borc<dande<fEx2:Aor(Bandnot(CorD))seeP190二.作為條件控制的布爾表達式的翻譯（一遍掃描）

對于條件語句：if

E

thenS1elseS2翻譯分析到

E

時，S1、S2并未進行翻譯，既使計算出E的結(jié)果也不知跳轉(zhuǎn)到何處，因此賦予E兩個新的語義值:

E.true

(真出口,記錄跳往S1的語句號,待回填)

E.false(假出口,記錄跳往S2的語句號,待回填)其含義及作用見圖：E.codeS1.codeGotos.nextS2.code…

E.true

E.false[E.true][E.false]

S.next

另外：當E自身較復雜時，跳往S1、S2的語句可能為多條，為記錄這多條語句，可以將這些語句建一鏈表:并改：E.true為

E.truelist(記錄跳往S1的語句鏈表表頭)

E.false為E.falselist(記錄跳往S2的語句鏈表表頭)

(※,※,※,0)0為鏈尾標識

……(q)(※,※,※,P)……(r)(※,※,※,q)←鏈表表頭為r此外：為記錄下一條即將產(chǎn)生的四元式號，以便及時回填跳往該四元式的語句，我們在文法中插入非終結(jié)符M，用于在翻譯分析時遇見M即記錄四元式號，則布爾表達式文法修改為：

(1)M→ε

(2)E→E1orME2|E1and

ME2|notE1|(E1)|id1relopid2|id上述文法的語義動作如下：(1)M→ε

{M.quad:=nextquad}(7)E→id {E.truelist:=makelist(nextquad);E.falselist:=makelist(nextquad+1);emit(‘jnz’‘,’id.place‘,’‘-‘‘,’‘0’);emit(‘j,-,-,0’)}(6)E→id1relopid2{E.truelist:=makelist(nextquad);E.falselist:=makelist(nextquad+1);emit(‘j’relop.op‘,’id1.place‘,’id2.place‘,’‘0’);emit(‘j,-,-,0’)(5)E→(E1)

{E.truelist:=E1.truelist;E.falselist:=E1.falselist}

(4)E→notE1{E.truelist:=E1.falselist;E.falselist:=E1.truelist}(2)

E→E1orME2{backpatch(E1.falselist,M.quad);E.truelist:=merge(E1.truelist,E2.truelist);E.falselist:=E2.falselist}(3)

E→E1andME2{backpatch(E1.truelist,M.quad);E.truelist:=E2.truelist;E.falselist:=merge(E1.falselist,E2.falselist)}即將產(chǎn)生的四元式號（地址）將M.quad回填至E1.truelist為表頭的鏈表上各四元式中將E1.falselist和E2.falselist為表頭的兩條鏈合并創(chuàng)建一條新鏈表nextquad為該鏈中唯一一個四元式的地址寫出以下語句的四元式形式：Ex1:a<borc<dande<f7.5控制語句的翻譯一.控制流語句S→ifEthenS1|ifEthenS1elseS2|whileEdoS1上述的紅色跳轉(zhuǎn)語句相當于S的出口，在對S語句進行翻譯分析時，其跳轉(zhuǎn)目標并不確定，因此賦予S語義值:S.next。E.falselistE.codeS1.code…E.truelist[E.truelist][E.falselist]E.codeS1.codeGotos.nextS2.code…E.truelistE.falselist[E.truelist][E.falselist]S.nextE.codeS1.codegotoS.begin…E.truelistE.falselist[E.truelist][E.falselist]S.begin此外，考慮到語句可以嵌套等因素，S的出口語句可能有多條，也需要建立鏈表，因此將S.next改為S.nextlist。S.nextlist：記錄S的出口語句鏈表表頭,待回填。S.next：S的出口,記錄跳出S的語句號,待回填。例：

ifE1then

{ifE2thenS1}

elseS2E1.codeE2.codeS1.codeGotoS.nextlistS2.code…E2.truelistE2.falselist[E2.truelist]S.nextlist

[E2.falselist]E1.truelistE1.falselist[E1.truelist][E1.falselist]更為完整的控制語句文法產(chǎn)生式如下：

(1)S→ifEthenS(6)L→L;S(2)|ifEthenSelseS(7)

|S(3)