編譯原理第三版 第七章 語義分析和中間代碼產(chǎn)生

第七章語法制導(dǎo)翻譯和中間代碼生成

任務(wù):把語法單位翻譯為中間代碼內(nèi)容:

屬性文法的概念、語法制導(dǎo)翻譯方法的基本思想。

典型的中間代碼:逆波蘭式、三元式、四元式、樹等。

基本語法單位的翻譯。包括：說明語句、表達(dá)式、賦值語句、控制語句、數(shù)組元素引用、過程調(diào)用等的翻譯。

7.1語法制導(dǎo)翻譯概述 1、屬性文法在上下文無關(guān)文法的基礎(chǔ)上，在描述語義動(dòng)作時(shí)，為每個(gè)文法符號(hào)（終結(jié)符和非終結(jié)符）配備若干相關(guān)的“值”，如“類型”，“地址”等，稱為屬性。對(duì)文法的每個(gè)產(chǎn)生式配備一組屬性計(jì)算規(guī)則稱為語義規(guī)則，它的描述形式為b:=f(c1,c2,…ck),其中b,c1,c2…ck為文法符號(hào)的屬性，f是一個(gè)函數(shù)。對(duì)每個(gè)產(chǎn)生式都給出其語義規(guī)則的文法稱為屬性文法。記號(hào)表示對(duì)于某個(gè)文法符號(hào)X∈VT∪VN，用X.type（X的類型），X.cat（X的種別），X.val（X的值或地址）等表示它的屬性。用下標(biāo)（上角標(biāo)）區(qū)分同一產(chǎn)生式中相同符號(hào)的多次出現(xiàn)。例：簡(jiǎn)單臺(tái)式計(jì)算器的屬性文法產(chǎn)生式L→EnE→E1+TE→TT→T1*FT→FF→(E)F→digit語義規(guī)則Print(E.val)E.val:=E1.val+T.valE.val:=T.valT.val:=T1.val*F.valT.val:=F.valF.val:=E.valF.val:=digit.lexval屬性文法可以看作是關(guān)于語言翻譯的高級(jí)規(guī)范說明，其中隱去了實(shí)現(xiàn)細(xì)節(jié)。翻譯模式是適合語法制導(dǎo)翻譯的另一種語言翻譯的描述形式，它給出了使用語義規(guī)則進(jìn)行計(jì)算的次序，這樣就把某些實(shí)現(xiàn)細(xì)節(jié)表示出來了。在翻譯模式中，和文法符號(hào)相關(guān)的屬性和語義規(guī)則用{}括起來。也稱語義動(dòng)作，語義子程序

。2、語法制導(dǎo)翻譯方法語法制導(dǎo)翻譯的基本思想在語法分析過程中，隨著分析的步步進(jìn)展，在使用某個(gè)產(chǎn)生式進(jìn)行推導(dǎo)或歸約時(shí)便執(zhí)行相應(yīng)的語義子程序，完成既定的翻譯工作，生成中間代碼。

(1)擴(kuò)大語法分析器的功能,在使用某個(gè)產(chǎn)生式進(jìn)行歸約(或推導(dǎo))時(shí),調(diào)用相應(yīng)的子程序進(jìn)行翻譯(生成中間代碼)(2)分析棧改為語義棧。SmXm.VALXmSm-1Xm-1.VALXm-1...S0/#......STATEVALSYM語義棧語法制導(dǎo)翻譯方法的實(shí)現(xiàn)途徑1.后綴式后綴式表示法又稱逆波蘭表示法，是一種表示表達(dá)式的方法，它把運(yùn)算量（操作數(shù)）寫在前面，算符寫在后面例：中綴表示:a+b,a+b*c,m=1,(a+b)*c,(a+b)*(c-d)后綴表示:ab+,abc*+,m1=,ab+c*,ab+cd-*

特點(diǎn):

運(yùn)算分量的個(gè)數(shù)與先后次序不變；運(yùn)算符的個(gè)數(shù)不變,但其出現(xiàn)順序即為執(zhí)行順序無括號(hào)；7.2中間語言一個(gè)表達(dá)式E的后綴式可如下定義：(1)如果E是一個(gè)變量或常數(shù)，則E的后綴式是E自身；(2)如果E是E1opE2形式的表達(dá)式，op是二元操作符，則E的后綴式為E1’E2’op,E1’和E2‘分別為E1和E2的后綴式；(3)如果E是(E1)形式的表達(dá)式，則E1的后綴式就是E的后綴式

二叉樹遍歷法即后序遍歷二叉樹

例如：((a+b)/(c-d)）>e>/+-eabcd

中序遍歷(左中右):

((a+b)/(c-d)>e

后序遍歷(左右中):

ab+cd-/e>中綴到后綴的轉(zhuǎn)換后綴式的推廣[例]

條件算術(shù)表達(dá)式:ifethenXelseY

三目運(yùn)算

if-then-else:

￥

eXY￥={Xe≠0即e為.T.Ye=0即e為.F.

轉(zhuǎn)移指令:

無條件轉(zhuǎn):pjump

小于轉(zhuǎn):e1e2pjlt

為零轉(zhuǎn):epjezep1jezXp2jumpp1:YP2: p1p2

POST:ep1jezXp2jumpY...[例]if(x+y)*z=0then(a+b)↑c(diǎn)elsea↑b↑c(diǎn) 后綴式: (1)xy+z*0=ab+c↑abc↑↑￥ (2)xy+z*0=p1jezab+c↑p2jumpp1:abc↑↑p2:2、樹:

也可以用樹型結(jié)構(gòu)表示表達(dá)式或語句。對(duì)表達(dá)式中的每個(gè)子表達(dá)式表式為一棵子樹，即簡(jiǎn)單變量或常數(shù)的樹就是該變量或常數(shù)自身。如果表示e1和e2的樹為T1和T2，那么，e1+e2,e1*e2,-e1的樹分別為：+ *_(uminus)T1T2T1T`2T`1e1+e2e1*e2-e1+**ABCD

A*B+C*D的樹雙目運(yùn)算對(duì)應(yīng)二叉子樹，多目運(yùn)算對(duì)應(yīng)多叉子樹。后綴式是樹的后序遍歷序列。3、三地址代碼一般形式：x:=yopz如：x:=yopz 二元賦值

x:=opy 一元賦值

x:=y 復(fù)制賦值

gotoL 無條件轉(zhuǎn)移

ifxrelopygotoL 條件轉(zhuǎn)移

ifagotoL 條件轉(zhuǎn)移三地址代碼在具體實(shí)現(xiàn)時(shí)常表示為記錄結(jié)構(gòu)，如四元式、三元式、間接三元式。四元式

一個(gè)四元式是一個(gè)帶有四個(gè)域的記錄結(jié)構(gòu)

(op,arg1,arg2,result) op運(yùn)算符，arg1,arg2運(yùn)算數(shù)，result運(yùn)算結(jié)果[例]

a:=b*-c+b*-c

的四元式序列:

op

arg1

arg2

result (1)(@c_T1) (2)(*bT1T2) (3)(@c_T3) (4)(*bT3T4) (5)(+T2T4T5) (6)(:=T5_a)

四元式之間的聯(lián)系通過臨時(shí)變量實(shí)現(xiàn)。單目運(yùn)算只用arg1域，轉(zhuǎn)移語句將目標(biāo)標(biāo)號(hào)放入

result域。

arg1,arg2,result通常為指針，指向有關(guān)名字的符號(hào) 表入口，且臨時(shí)變量填入符號(hào)表。三元式

一個(gè)三元式有三個(gè)域(op,arg1,arg2),其中：arg1,arg2為指向符號(hào)表的指針（對(duì)程序中的名字或常量）或者是指向三元式表的指針（取代臨時(shí)變量）。

例：a:=b*-c+b*-c

的三元式序列：

op

arg1

arg2

(1)(@c_) (2)(*b(1)) (3)(@c_) (4)(*b(3)) (5)(+(2)(4)) (6)(:=a(5))間接三元式不直接使用三元式表，另設(shè)一張間接碼表，按運(yùn)算的先后次序列出有關(guān)三元式在三元式表中的位置，相同的三元式無需 重填三元式表。

例：

a:=b*-c+b*-c

的間接三 元式為：間接碼表

op

arg1

arg2

（1）

(1)(@c_)（2）(2)(*b(1))（1）(3)(+(1)(2))（2) (4)(:=a(3))(3)(4)三元式中使用了指向三元式的指針，優(yōu)化時(shí)修改較難。間接三元式優(yōu)化只需要更改間接碼表，并節(jié)省三元式表存儲(chǔ)空間。修改四元式表也較容易，只是臨時(shí)變量要填入符號(hào)表，占據(jù)一定存儲(chǔ)空間。

四元式、三元式和間接三元式比較

7.3說明語句的翻譯說明語句作用:

用關(guān)鍵字定義名字的性質(zhì)（數(shù)據(jù)類型）簡(jiǎn)單類型說明數(shù)組、記錄說明

語義動(dòng)作:

填符號(hào)表、信息向量表、除動(dòng)態(tài)數(shù)組外不生成四元式。

(1)文法

integeri1,i2,...,in

D→integernamelist │realnamelist namelist→namelist,i│i

問題:必須把所有名字都?xì)w約為namelist后才能把各個(gè)名字的 類型填入符號(hào)表,需要使用隊(duì)列或棧保存這些名字(2)改寫文法

integeri1

,i2

,...,in D→integeri │reali

│D,i D1.簡(jiǎn)單類型說明

namelistnamelistnamelist...DDD…D(3)語義變量與語義過程

D.att:

記錄說明語句D規(guī)定的類型；

fill(p,a):填表過程,把屬性a填入符號(hào)表入口p的有關(guān)欄中；

entry(i):

回送標(biāo)識(shí)符i在符號(hào)表中的入口（lookup());

(4)翻譯模式

(1)D→integeri

(2)D→reali(3)D→D1,i

{p:=entry(i);fill(p,int); D.att:=int}{p:=entry(i);fill(p,real); D.att:=real}{p:=entry(i);fill(p,D1.att);D.att:=D1.att}例：integeri1,i2,i32.數(shù)組說明(1)文法Darrayi[l1:u1,l2:u2,...,ln:un](2)信息向量表

l1u1 d1...lnundnnCtypeaAarray...符號(hào)表信息向量表說明:對(duì)于固定數(shù)組,將有關(guān)說明信息依次填入符號(hào)表信息向 量表；對(duì)于可變數(shù)組，需要形成中間代碼。(3)可變數(shù)組的處理

編譯時(shí):分配信息向量表區(qū)。產(chǎn)生運(yùn)行時(shí)建立信息向量表和分配數(shù)組空間的四元式。

運(yùn)行時(shí):填寫信息向量表。分配數(shù)組存貯空間。

子程序:

功能:建立信息向量表和分配數(shù)組空間參數(shù):n,type,li,ui,信息向量表首址BEGIN i:=1;N:=1;C:=0;/*i為維數(shù),N為體積,C為a-C中的C*/ WHILEi<nDO BEGIN

di:=ui-li+1;N:=N*di;C:=C*di+li;

把li,ui,di

填入信息向量表;i:=i+1 END;

申請(qǐng)N個(gè)單元的數(shù)組空間,令其首址為a;

把n,C,type,a填入信息向量表END 3.記錄說明的翻譯(1)f→typei(2)f→typeI[n](3)f1→f(4)f1→f1(1);f(5)type→record(6)type→char(7)type→nteger(8)type→pointer{f.NAME:=i.NAME;f.LEN:=type.LEN;FILN(i.NAME,f.LEN)}{f.NAME:=i.NAME;f.LEN:=type.LEN*n.VAL;FILN(i.NAME,f.LEN)}{FILO(f.NAME,0);f1.LEN:=f.LEN}{FILO(f.NAME,f1(1).LEN);f1.LEN:=f1(1).LEN+f.LEN}{type.LEN:=f1.LEN}{type.LEN:=1}{type.LEN:=4}{type.LEN:=4}#7.4簡(jiǎn)單算術(shù)表達(dá)式和賦值語句的翻譯只含整型變量的簡(jiǎn)單算術(shù)表達(dá)式，并符合運(yùn)算符的結(jié)合規(guī)則和優(yōu)先級(jí)規(guī)定。1.文法描述

(1)S→i:=E (2)E→E1+E2 (3)E→E1*E2 (4)E→-E1

(5)E→(E1) (6)E→i2.語義變量和語義過程

E.place:存放E值的變量名在符號(hào)表的入口或臨時(shí)變量的編號(hào)；

:表示i所代表的名字本身，或直接用i表示；

newtemp:

函數(shù)過程,生成一個(gè)新的臨時(shí)單元,

返回其編號(hào)；entry(i):

函數(shù)過程,返回i在符號(hào)表的入口（或 lookup())；

gen(op,arg1,arg2,result):語義過程，

生成一個(gè)四元式并將它送到四元式表中；或emit(x,”:=“,y,op,z):語義過程，把三地址語句

x:=yopz發(fā)送到輸出文件。(1)S→i:=E {gen(:=,E.place,_,entry(i)}(2)E→E1+E2

{T:=newtemp; gen(+,E1.place,E2.place,T);E.place:=T}(3)E→E1*E2{T:=newtemp; gen(*,E1.place,E2.place,T);E.place:=T}(4)E→-E1{T:=newtemp; gen(@,E1.place,_,T);E.place:=T}(5)E→(E1){E.place:=E1.place}(6)E→i{E.place:=entry(i)}3.語義子程序

產(chǎn)生式

語義動(dòng)作例:

a:=-b*(c+d)

的語法制導(dǎo)翻譯過程 棧 輸入串 i.place 四元式#

a:=-b*(c+d)##i

:=-b*(c+d)#a#i:=

-b*(c+d)#a_#i:=-

b*(c+d)#a__#i:=-i

*(c+d)#a__b#i:=-E

*(c+d)#a__b

#i:=E

*(c+d)#a_T1

#i:=E*

(c+d)#a_T1_

#i:=E*(

c+d)#a_T1__

#i:=E*(i

+d)#a_T1__c

#i:=E*(E

+d)#a_T1__c

#i:=E*(E+

d)#a_T1__c_#i:=E*(E+i

)#a_T1__c_d#i:=E*(E+E

)#a_T1__c_d#i:=E*(E

)#a_T1__T2

#i:=E*(E)

#a_T1__T2_#i:=E*E

#a_T1_T2#i:=E

#a_T3#S

#(@,b,_,T1)(+,c,d,T2)(*,T1,T2,T3)(:=,T3,_,a)4.類型轉(zhuǎn)換

若i的類型不同,則拒絕或做類型轉(zhuǎn)換

運(yùn)算符:實(shí)型+r,×r,@r

整型+i,×i,@i

語義變量E.type=

轉(zhuǎn)換指令(itr,A1,_,T)intrealE→E1opE2

的語義子程序(帶有語義轉(zhuǎn)換功能)

T:=NEWTEMP；IFE1.type=intANDE2.type=intTHENBEGINGEN(opi,E1.PLACE,E2.PLACE,T);E.type:=intENDELSEIFE1.type=realANDE2.type=realTHENBEGINGEN(opr,E1.PLACE,E2.PLACE,T);E.type:=realENDELSEIFE1.type=int/*andE2.type=real*/THENBEGINU:=NEWTEMP GEN(itr,E1.PLACE,_,U); GEN(opr,U,E2.PLACE,T); E.type:=real ENDELSE/*E1.type=realandE2.type=int*/THEN BEGIN U:=NEWTEMP; GEN(itr,E2.PLACE,_,U); GEN(opr,E1.PLACE,U,T); E.type:=real END； E.PLACE:=T7.5布爾表達(dá)式的翻譯1.布爾表達(dá)式的定義構(gòu)成:用布爾運(yùn)算符把布爾量、關(guān)系表達(dá)式聯(lián)結(jié)起 來的式子。

布爾運(yùn)算符：and,or,not

；關(guān)系運(yùn)算符＜,≤,＝,≠，＞,≥(2)作用:

控制語句的條件計(jì)算邏輯值(3)文法:

E→EandE│EorE│not

E│(E)│i│i1relopi2

運(yùn)算符優(yōu)先級(jí):布爾運(yùn)算由高到低:notandor,同級(jí)左結(jié)合.

關(guān)系運(yùn)算符同級(jí),且高于布爾運(yùn)算符(4)計(jì)值:

按優(yōu)先級(jí)(與算術(shù)表達(dá)式相同)

2.數(shù)值表示法的布爾式翻譯：與算術(shù)表達(dá)式翻譯相同將andornot看作運(yùn)算符關(guān)系表達(dá)式翻譯為含轉(zhuǎn)移語句的序列:

即：a<b表示ifa<bthen1else0例：關(guān)系表達(dá)式a<b翻譯為四元式:100（j<,a,b,103)101(:=,0,_,T)102(j,_,_,104)103(:=,1,_,T)104例:布爾表達(dá)式aorbandnotc翻譯為四元式:(not,c,_,T1)(and,b,T1,T2)(or,a,T2,T3)產(chǎn)生以上結(jié)果的語義子程序?yàn)椋篍→E1orE2

{T:=newtemp; gen(orE1.place,E2.place,T);E.place:=T}

E→E1andE2{T:=newtemp; gen(andE1.place,E2.place,T);E.place:=T}E→notE1

{T:=newtemp; gen(notE1.place,_,T);E.place:=T}E→(E1) {E.place:=E1.place}E→id1relopid2{T:=newtemp; gen(jrelop,id1.place,id2.place,nextstart+3); gen(:=,0,_,T); gen(j,_,_,nextstart+2); gen(:=,1,_,T); E.place:=T;}E→id {E.place:=id.place}nextstart為四元式序列中下一條四元式地址索引，每產(chǎn)生一條四元式，過程gen將nextstart加1例：布爾表達(dá)式a<borc<dande<f的四元式序列：100（j<,a,b,103)101(:=,0,_,T1)102(j,_,_,104)103(:=,1,_,T1)104（j<,c,d,107)105(:=,0,_,T2)106(j,_,_,108)107(:=,1,_,T2)108（j<,e,f,111)109(:=,0,_,T3)110(j,_,_,112)111(:=,1,_,T3)112(and,T2,T3,T4)113(or,T1,T4,T5)##3.作為條件控制的布爾表達(dá)式的翻譯(1)考察條件語句:ifEthenS1elseS2

E的作用:控制對(duì)S1和S2的選擇,其值無需保留。(2)代碼結(jié)構(gòu):E的代碼S1的代碼S2的代碼(3)E的四元式形式:全部為條件或無條件轉(zhuǎn)移指令(jnz,A1,_,p) A1為真轉(zhuǎn)p(jθ,A1,A2,p) A1θA2為真轉(zhuǎn)p（θ為關(guān)系運(yùn)算符）(j,_,_,p)無條件轉(zhuǎn)p真出口假出口(4)E的真、假出口的確定E形如a<b時(shí)，生成四元式(j<,a,b,E.true) (j,_,_,E.false)E形如E1orE2

E1

為真:E1

的真出口即為E的真出口，不必求E2；

E1

為假:E2

需要計(jì)值,其第一個(gè)四元式為E1

的假出口；

E2

的真假出口為E的真假出口。

E形如E1andE2

E1為假:E1

的假出口即為E的假出口,不必求E2；

E1為真:E2

需要計(jì)值,其第一個(gè)四元式為E1

的真出口；

E2

的真假出口為E的真假出口。

E形如notE1

E1

的真出口為E的假出口；

E1

的假出口為E的真出口。(5)回填技術(shù)

問題:

在自下而上語法分析中,真假出口往往不能在生成四元式的同時(shí)填上。解決：一種解決方法是兩遍掃描；另一種解決方法是采用一遍掃描，這時(shí)需要把相應(yīng)四元式的地址保存,到適當(dāng)?shù)臅r(shí)機(jī)再填入。這就是回填技術(shù)。

實(shí)現(xiàn)：建立一個(gè)鏈表，把跳轉(zhuǎn)到相同目標(biāo)的四元式標(biāo)號(hào)鏈在同一個(gè)表中，當(dāng)目標(biāo)確定后，再將它回填到有關(guān)的指令中。

可以有兩種方式組織鏈表：利用需要回填的跳轉(zhuǎn)四元式的第四個(gè)域(result)構(gòu)造鏈表；或者建立單獨(dú)鏈表記錄需要回填的跳轉(zhuǎn)四元式的標(biāo)號(hào)。鏈表的組織方式 設(shè)鏈表的頭指針為E.truelist（需回填E的真值的的鏈），E.falselist（需要回填E的假值的鏈）E.truelist(r)(x,x,x,q)(q)(x,x,x,p)(p)(x,x,x,0)…………E.truelistrqpnull(5)語義變量和過程、函數(shù)

nextquad:

變量，下一個(gè)將形成的四元式地址， 初值為1,每執(zhí)行一次GEN自動(dòng)加1.

makelist(i):

函數(shù)，創(chuàng)建一個(gè)僅含i的新鏈表，i為四元式地 址（標(biāo)號(hào)）.merge(p1,p2):

函數(shù)過程,

把以p1,p2為 鏈?zhǔn)椎膬蓚€(gè)鏈合并回送合并后的鏈?zhǔn)?backpatch(p,t):過程,把鏈?zhǔn)譸所指 鏈中的四元式第4域回填為t。merge(p1,p2);{ifp2=0thenmerge=p1else{p:=p2;whilep.result<>0dop=p.result;p.result=p1; merge=P2;}}00p2p1p1

…

…(6)語義子程序?qū)ξ姆óa(chǎn)生式稍作修改，引入標(biāo)記非終結(jié)符M，以便在適當(dāng)?shù)臅r(shí)候執(zhí)行一個(gè)語義動(dòng)作，記下下一個(gè)要產(chǎn)生四元式標(biāo)號(hào)。E→i {E.truelist:=makelist(nextquad);

E.falselist:=makelist(nextquad+1);

gen(jnz,i.place,_,0);

gen(j,_,_,0)}

(2)E→i1relopi2

{E.truelist:=makelist(nextquad);

E.falselist:=makelist(nextquad+1);

gen(jnz,i.place,_,0);

gen(j,_,_,0)}

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

{E.truelist:=E1.falselist;E.falselist:=E1.truelist}(5)E→E1andME2{backpatch(E1.truelist,M.quad);

E.truelist:=E2.truelist;

E.falselist:=merge(E1.falselist,E2.falselist)}

(6)E→E1orME2

{backpatch(E1.falselist,M.quad);

E.truelist:=merge(E1.truelist,E2.truelist);

E.falselist:=E2.falselist)}(7)M→ε {M.quad:=nextquad}例：將布爾式a<borc<dande<f翻譯為四元式EE1orM1E4i1<i2εE2andME3i1<i1i1<i1ε100(j<,a,b,0)101(j,_,_,0)102(j<,c,d,0)103(j,_,_,0)104(j<,e,f,0)105(j,_,_,0)鏈表：E1.truelist={100},E1.falselist={101}Nextquad=102M1.quad=102E2.truelist={102},E2.falselist={103}nextquad=104M.quad=104E3.truelist={104},E3.falselist={105}nextquad=106E4.truelist={104}E4.falselist={103,105}E.truelist={100,104}E.falselist={103,105}104102四元式：###7.6控制語句的翻譯

1.控制流語句考察if-then,if-then-else,while–do語句的翻譯,

三種語句的形式為:ifEthenS1,ifEthenS1elseS2,

WhileEdoS1,其中E為布爾表達(dá)式.三種語句的代碼結(jié)構(gòu)If-then語句代碼結(jié)構(gòu)

E.codeS1.code…E.trueE.falseIf-then語句的代碼就是E的代碼后跟S1的代碼。

If-then語句只是控制了這些代碼中的轉(zhuǎn)移目標(biāo)。即E為”真”時(shí),執(zhí)行S1第一條語句,E的真出口E.true為S1的第一條指令,E中某些四元式得到回填;E為”假”時(shí)