語義分析和中間代碼生成

一.符號(hào)表的一般形式每個(gè)名字對(duì)應(yīng)一個(gè)表項(xiàng)一個(gè)表項(xiàng)包括名字域和信息域。名字信息

信息域通常設(shè)若干子域及標(biāo)志位，其內(nèi)容可以是和名字有關(guān)的任何信息類型,種屬,長度,相對(duì)地址形參標(biāo)志,說明標(biāo)志,賦值標(biāo)志等。

名字的長度、信息域的組成及長度可能是各不相同的采用間接表技術(shù)。二.常用的符號(hào)表結(jié)構(gòu)1.線性表:用N個(gè)數(shù)組A1,A2,…,AN來存放符號(hào)表的N個(gè)子域

2.HASH表第一節(jié)語義分析概論一.語義分析的主要工作(1)語義檢查:

如類型是否一致,數(shù)組維數(shù)是否正確(2)語義處理:

說明語句:登記信息；執(zhí)行語句,生成中間代碼。

每個(gè)產(chǎn)生式配上一個(gè)語義子程序；在語法分析過程中,當(dāng)用一個(gè)產(chǎn)生式進(jìn)行匹配或歸約時(shí)；就調(diào)用相應(yīng)的語義程序；進(jìn)行語義分析。二.語法制導(dǎo)翻譯LR分析法制導(dǎo)的語義分析在LR分析過程中,當(dāng)用一個(gè)產(chǎn)生式進(jìn)行句柄的歸約時(shí)調(diào)用該產(chǎn)生式相應(yīng)的語義程序完成對(duì)應(yīng)的語義分析語義子程序既包含語義檢查也包含語義處理核心是為了生成相應(yīng)的中間代碼在分析過程中必須保存語義值“類型”、“種屬”、“地址”等例：語法分析采用自底向上的LR分析法XABYCDZXY狀態(tài)棧符號(hào)棧語義棧BA

B的語義值A(chǔ)的語義值

狀態(tài)棧符號(hào)棧語義棧X

X的語義值

XABYCDZXY狀態(tài)棧符號(hào)棧語義棧DCX

D的語義值C的語義值X的語義值

XABYCDZXY狀態(tài)棧符號(hào)棧語義棧YX

Y的語義值X的語義值

XABYCDZXY狀態(tài)棧符號(hào)棧語義棧Z

Z的語義值

XABYCDZXY(op,ARG1,ARG2,RESULT)op—運(yùn)算符ARG1—第一運(yùn)算量ARG2—第二運(yùn)算量RESULT—結(jié)果三.四元式（三地址代碼）如:A:=-B*(C+D)翻譯成

n

(@,B,_,t1)t1:=-Bn+1(+,C,D,t2)t2:=C+Dn+2(*,t1,t2,t3)t3:=t1*t2n+3(:=,t3,_,A)A:=t3

四元式順序和表達(dá)式計(jì)值順序一致;

四元式之間通過臨時(shí)變量實(shí)現(xiàn)聯(lián)系。四元式編號(hào)使用ip表示,從1開始一.語義變量及過程(1)E.place:語義變量與非終結(jié)符E相關(guān)聯(lián)表示存放E值的變量名在符號(hào)表的入口或其整數(shù)編碼(臨時(shí)變量)

采用變量名或臨時(shí)變量名表示第二節(jié)簡(jiǎn)單賦值語句的翻譯(2)newtemp:語義函數(shù)返回一個(gè)可用的臨時(shí)變量地址采用臨時(shí)變量名代表表示為t1,t2,…(3)entry(i):語義函數(shù)對(duì)變量i查符號(hào)表，返回i在符號(hào)表中的入口采用變量名表示(4)gen(OP,ARG1,ARG2,RESULT):

語義過程產(chǎn)生四元式并填入四元式表中；同時(shí)ip:=ip+1(四元式編號(hào)增加1)E→i{E.place:=entry(i)}E→(E1){E.place:=E1.place}E→-E1

{E.place:=newtemp;gen(@,E1.place,_,E.place)}二.翻譯方案E→E1opE2{E.place:=newtemp;gen(op,E1.place,E2.place,E.place)}A→i:=E{gen(:=,E.place,_,entry(i))}a:=-b*(c+d)a:=-E1*(c+d)a:=E2*(c+d)a:=E2*(E3+d)a:=E2*(E3+E4)a:=E2*(E5)a:=E2*E6a:=E7A----賦值語句舉例:a:=-b*(c+d)的移進(jìn)-歸約過程ii:=i:=-i:=-ii:=-E1i:=E2i:=E2*i:=E2*(i:=E2*(ii:=E2*(E3i:=E2*(E3+i:=E2*(E3+ii:=E2*(E3+E4i:=E2*(E5i:=E2*(E5)i:=E2*E6i:=E7A

aa_a__a___a__ba_t1a_t1_a_t1__a_t1___a_t1__ca_t1__c_a_t1__c__a_t1__c_da_t1__t2a_t1__t2_a_t1_t2a_t3

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

(@,b,_,t1)(+,c,d,t2)(*,t1,t2,t3)(:=,t3,_,a)

符號(hào)棧PLACE輸入四元式a:=-b*(c+d)的翻譯過程三.類型轉(zhuǎn)換對(duì)表達(dá)式E增加類型屬性E.type

引進(jìn)類型轉(zhuǎn)換指令(itr,x,_,t)E→E1opE2的語義子程序?yàn)閠:=newtemp;ifE1.type=integerandE2.type=integerthenbegingen(opi,E1.place,E2,place,t);

E.type:=integerendelseifE1.type=realandE2.type=realthenbegingen(opr,E1.place,E2.place,t);

E.type:=realend

elseifE1.type=integerthenbegint1:=newtemp;gen(itr,E1.place,_,t1);gen(opr,t1,E2.place,t);

E.type:=realend

elsebegint1:=newtemp;

gen(itr,E2.place,_,t1);gen(opr,E1.place,t1,t);

E.type:=realend;E.place:=t;一.文法

D→D1;D2│i:TT→real│integer│array[num]ofT1│↑T1

非終結(jié)符D產(chǎn)生一系列

i:T形式的說明語句。第三節(jié)說明語句的翻譯二.主要工作不產(chǎn)生可執(zhí)行指令,僅負(fù)責(zé)填表,

將被說明對(duì)象的類型及相對(duì)存儲(chǔ)位置記入各自的符號(hào)表中。(1)offset:相對(duì)位移量，初值為0

是一個(gè)全局變量(2)T.type:數(shù)據(jù)類型(3)T.width:數(shù)據(jù)寬度(4)enter:語義過程,將變量名及其類型和相對(duì)存儲(chǔ)位置記入符號(hào)表中。三.語義變量及過程

對(duì)一個(gè)子程序來說，offset的初值為0

針對(duì)這個(gè)賦初值的語義動(dòng)作引進(jìn)了非終結(jié)符M及M→ε四.翻譯方案S→MD{}M→ε{offset:=0}D→D1;D2{}T→integer

{T.type:=integer;T.width:=2}T→real

{T.type:=real;T.width:=4}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→i:T

{enter(,T.type,offset);offset:=offset+T.width}(1)說明語句可能為如下形式D→integernamelist│realnamelistnamelist→namelist,i│i先改寫為D→D,i│integeri│reali五.其它說明語句(2)說明語句也可為如下形式

D→namelistinteger|namelistrealnamelist→namelist,i|i

翻譯時(shí)需引進(jìn)隊(duì)列namelist.QUEUE用以存放變量名(3)對(duì)數(shù)組說明的翻譯：分配內(nèi)情向量表區(qū)產(chǎn)生在運(yùn)行時(shí)動(dòng)態(tài)地建立內(nèi)情向量和分配數(shù)組空間的目標(biāo)指令。第四節(jié)控制語句的翻譯一.布爾表達(dá)式的翻譯1.文法及其分析

B→iB→i1ropi2

控制條件的布爾表達(dá)式為真或假時(shí)，要轉(zhuǎn)移到不同的地方。2.語義變量（1）B.T:B為真時(shí)轉(zhuǎn)移語句的地址（2）B.F:B為假時(shí)轉(zhuǎn)移語句的地址nifBgoto

0n+1goto

0其中：n----B.Tn+1----B.F3.轉(zhuǎn)移語句的四元式條件轉(zhuǎn)移

(jrop,i1,i2,0)或ifi1ropi2goto0(jnz,i1,-,0)或ifi1

goto0無條件轉(zhuǎn)移

(j,-,-,0)或goto04.翻譯方案B→i{B.T:=ip;gen(jnz,entry(i),-,0);B.F:=ip;gen(j,-,-,0)}或B→i{B.T:=ip;B.F:=ip+1;gen(jnz,entry(i),-,0);gen(j,-,-,0)}B→i1ropi2{B.T:=ip;gen(jrop,entry(i1),entry(i2),0);B.F:=ip;gen(j,-,-,0)}或B→i1ropi2{B.T:=ip;B.F:=ip+1;gen(jrop,entry(i1),entry(i2),0);gen(j,-,-,0)}1.gotoL的兩種情形（1）L已經(jīng)定義

…L:.../*此時(shí)，將L登記入符號(hào)表*/…gotoL;/*查表,L已定義,生成四元式*/…二.無條件轉(zhuǎn)移語句的翻譯…gotoL;/*將L記入符號(hào)表，定義否標(biāo)記為“未”*/…gotoL;/*拉鏈*/…L:…/*定義否標(biāo)記改為“已”，回填*/…（2）L未定義名字類型…定義否地址L標(biāo)號(hào)未p……(p)(j,_,_,0)……(q)(j,_,_,p)……(r)(j,_,_,q)……………qr設(shè)文法：S→labelS1label→i:當(dāng)用label→i:進(jìn)行歸約時(shí)(1)若i（假定為L）不在符號(hào)表中則把它填入，類型為“標(biāo)號(hào)”定義否為“已”地址為ip的當(dāng)前值；2.帶標(biāo)號(hào)語句的處理方法(2)若L已在符號(hào)表中但類型欄不為“標(biāo)號(hào)”或定義否欄為“已”則名字重復(fù)(3)若L已在符號(hào)表中類型為“標(biāo)號(hào)”，把標(biāo)志“未”改為“已”把“地址欄”中的鏈?zhǔn)譺取出把ip當(dāng)前值填入其中執(zhí)行

backpatch（r，ip）進(jìn)行回填。

backpatch（r，ip）語義過程把r為鏈?zhǔn)椎逆溕纤兴脑降牡谒膮^(qū)段都填為ip1.文法

S→ifBthenS1│ifBthenS1elseS2

L→S│L;S三.條件語句的翻譯單選控制結(jié)構(gòu)語句ifBthenS

對(duì)應(yīng)的控制可以表示為（中間代碼形式）B.T:ifBgoto

B.TDB.F:goto

S.nextB.TD:┇//語句S對(duì)應(yīng)的中間代碼段S.next:

B為假BS1?ifBthenS1B為真S1的第一條四元式用以回填真出口需要拉鏈B2為假B2為真B1為假B1S1?ifB1thenifB2thenS1B1為真B2(1)B具有真假出口

B為真假時(shí)的轉(zhuǎn)向不同在翻譯B時(shí)，真假出口有待“回填”(2)因if語句的嵌套,需記錄轉(zhuǎn)移目標(biāo)相同的四元式的地址—拉鏈技術(shù)特點(diǎn)3.語句變量及過程(1)N.CHAIN:轉(zhuǎn)移目標(biāo)相同的四元式形成的鏈(頭)

如：S.CHAIN記錄了S中不確定轉(zhuǎn)移目標(biāo)的且轉(zhuǎn)向地址均相同的四元式(這些四元式形成一個(gè)鏈,S.CHAIN為鏈頭)(p)(j,-,-,0)……(q)(j,-,-,p)……(r)(j,-,-,q)S.CHAIN=r(2)merge(t1,t2):語義函數(shù)將t1、t2合并，返回合并后的鏈頭t2;(3)backpatch(t1,code):語義過程用code回填鏈頭為t1的鏈。即把t1為鏈?zhǔn)椎逆溕纤兴脑降牡谒膮^(qū)段都填為code(p)(j,-,-,)……(q)(j,-,-,p)……(r)(j,-,-,q)

t1=r(u)(j,-,-,0)…...(v)(j,-,-,u)……(w)(j,-,-,v)

t2=w(p)(j,-,-,0)……(q)(j,-,-,p)……(r)(j,-,-,q)

(u)(j,-,-,r)…...(v)(j,-,-,u)……(w)(j,-,-,v)

t2=w執(zhí)行merge(t1,t2)后(p)(j,-,-,120)(u)(j,-,-,120)………...(q)(j,-,-,120)(v)(j,-,-,120)………...(r)(j,-,-,120)(w)(j,-,-,120)執(zhí)行backpatch(t2,120)后單選控制結(jié)構(gòu)語句ifBthenS

對(duì)應(yīng)的控制可以表示為（中間代碼形式）B.T:ifBgoto

B.TDB.F:goto

S.nextB.TD:┇//語句S對(duì)應(yīng)的中間代碼段S.next:

B為假BS1?ifBthenS1B為真S1的第一條四元式用以回填真出口需要拉鏈B2為假B2為真B1為假B1S1?ifB1thenifB2thenS1B1為真B2處理方法(其他參考書)S→ifBthenTS1

T→ε

原文法

S→ifBthenS1改寫為

S→MS1M→ifBthen改寫文法翻譯方案M→ifBthen{backpatch(B.T,ip);

M.CHAIN:=B.F}S→MS1{S.CHAIN:=

merge(S1.CHAIN,M.CHAIN)}二選一控制語句

ifBthenS1elseS2

對(duì)應(yīng)的控制可以表示為B.T:ifBgoto

B.TDB.F:goto

B.FD

B.TD:┇//語句S1對(duì)應(yīng)的中間代碼段

goto

S.nextB.FD:┇//語句S2對(duì)應(yīng)的中間代碼段S.next:

B為假BS1S2?ifBthenS1elseS2B為真S1、S2的第一條四元式用以“回填”此處產(chǎn)生一無條件轉(zhuǎn)移語句需要拉鏈處理方法(其他參考書)S→ifBthenTS1

elseFS2

T→ε

F→εMM→ε原文法

S→ifBthenS1elseS2改寫為

S→NS1N→MS1else

M→ifBthen//同ifthen語句改寫文法4.翻譯方案M→ifBthen{backpatch(B.T,ip);

M.CHAIN:=B.F}N→MS1else{q:=ip;gen(j,-,-,0);

backpatch(M.CHAIN,ip);N.CHAIN:=merge(S1.CHAIN,q)}S→NS2{S.CHAIN:=merge(S2.CHAIN,N.CHAIN)}如何回填S.CHAIN原文法

L→S│L1;S

改寫為

L→SL→XS

X→L;L→S{L.CHAIN:=S.CHAIN}L→XS{L.CHAIN:=S.CHAIN}X→L;{backpatch(L.CHAIN,ip)}例1:ifa<bthena:=a+b的翻譯ifa<bifBB.T=100100:(j<,a,b,0)B.F=101101:(j,-,-,0)ifBthenMM.CHAIN=101backpatch(100,102)Ma:=a+b

M

A102:(+,a,b,t1)103:(:=,t1,-,a)MS1S1.CHAIN=0SS.CHAIN=merge(S1.CHAIN,M.CHAIN)=101

102例2:ifa<bthena:=a+belsea:=a-b的翻譯ifa<bifBB.T=100100:(j<,a,b,0)B.F=101101:(j,-,-,0)ifBthenMM.CHAIN=101backpatch(100,102)Ma:=a+b

MS1S1.CHAIN=0102:(+,a,b,t1)103:(:=,t1,-,a)MS1elseNq=ip=104104:(j,-,-,0)backpatch(M.CHAIN,105)N.CHAIN=merge(S1.CHAIN,q)=104Na:=a-bNS2S2.CHAIN=0105:(-,a,b,t2)106:(:=,t2,-,a)S

S.CHAIN=merge(S2.CHAIN,N.CHAIN)=104102105四.while語句的翻譯1.文法

S→whileBdoS1循環(huán)控制結(jié)構(gòu)語句whileBdoS對(duì)應(yīng)的控制可以表示為（中間代碼形式）again:ifBgoto

B.TDgoto

S.nextB.TD:┇//語句S對(duì)應(yīng)的中間代碼段

goto

againS.next:?BS1B為假B為真whileBdoS1B的第一條四元式需記錄、S1的第一條四元式用以“回填”此處產(chǎn)生一無條件轉(zhuǎn)移語句2.改寫文法S→DS1D→WBdoW→whileW→while{W.code:=ip}D→WBdo{backpatch(B.T,ip);D.CHAIN:=B.F;

D.code:=W.code}3.翻譯方案S→DS1{backpatch(S1.CHAIN,D.code);gen(j,-,-,D.code);S.CHAIN:=D.CHAIN}例3:whilea>bdoifc<dthene:=f+g;的翻譯whileWW.code=100Wa>b

WB1B1.T=100100(j>,a,b,0)B1.F=101101(j,-,-,0)WB1doDbackpatch(100,102)D.CHAIN=101D.code=W.code=100Difc<dDifB2B2.T=102102(j<,c,d,0)B2.F=103103(j,-,-,0)102107104100DifB2thenDMbackpatch(102,104)M.CHAIN=103DMe:=f+gDMS1S1.CHAIN=0104(+,f,g,t1)105(:=,t1,-,E)DS2S2.CHAIN=merge(103,0)=103Sbackpatch(103,100)S.CHAIN=101106(j,-,-,100)LL.CHAIN=S.CHAIN=101L;Xbackpatch(101,107)五．FOR循環(huán)語句的翻譯

1.文法及其語義

S→fori:=1toNdoS1其語義為

i:=1;again:ifi

NthenbeginS1;i:=i+1;gotoagainend代碼結(jié)構(gòu)可為：F+0:i:=1F+1:ifi<=Ngoto

F+3F+2:goto

S.nextF+3:

…...

//語句S1對(duì)應(yīng)的中間代碼段D+0:i:=i+1D+1:gotoF+1S.next:i

N?S1不成立成立fori:=1toNdoS1此處產(chǎn)生一無條件轉(zhuǎn)移語句i:=1i:=1+1原文法

S→fori:=1toNdoS1改寫為

F→fori:=1toNdo

S→FS12.翻譯方案(2)F具有三個(gè)語義值

F.CHAIN:記錄F+2F.place:記錄i在符號(hào)表入口

F.again:記錄F+1F→fori:=1toNdo{gen(:=,’1’,-,entry(i));

F.again:=ip;//F+1gen(j

,entry(i),N,F.again+2);

F.CHAIN:=ip;//F+2gen(j,-,-,0);

F.place:=entry(i)}(3)語義子程序S→FS1{backpatch(S1.CHAIN,ip);gen(+,F.place,’1’,F.place);gen(