語義分析和中間代碼生成

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

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

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

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

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

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

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

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

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

X的語義值

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

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

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

Y的語義值X的語義值

XABYCDZXY狀態(tài)棧符號棧語義棧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í)現(xiàn)聯(lián)系。四元式編號使用ip表示,從1開始一.語義變量及過程(1)E.place:語義變量與非終結(jié)符E相關(guān)聯(lián)表示存放E值的變量名在符號表的入口或其整數(shù)編碼(臨時變量)

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

語義過程產(chǎn)生四元式并填入四元式表中；同時ip:=ip+1(四元式編號增加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)

符號棧PLACE輸入四元式a:=-b*(c+d)的翻譯過程三.類型轉(zhuǎn)換對表達(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é)填表,

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

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

對一個子程序來說，offset的初值為0

針對這個賦初值的語義動作引進(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

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

B→iB→i1ropi2

控制條件的布爾表達(dá)式為真或假時，要轉(zhuǎn)移到不同的地方。2.語義變量（1）B.T:B為真時轉(zhuǎn)移語句的地址（2）B.F:B為假時轉(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:.../*此時，將L登記入符號表*/…gotoL;/*查表,L已定義,生成四元式*/…二.無條件轉(zhuǎn)移語句的翻譯…gotoL;/*將L記入符號表，定義否標(biāo)記為“未”*/…gotoL;/*拉鏈*/…L:…/*定義否標(biāo)記改為“已”，回填*/…（2）L未定義名字類型…定義否地址L標(biāo)號未p……(p)(j,_,_,0)……(q)(j,_,_,p)……(r)(j,_,_,q)……………qr設(shè)文法：S→labelS1label→i:當(dāng)用label→i:進(jìn)行歸約時(1)若i（假定為L）不在符號表中則把它填入，類型為“標(biāo)號”定義否為“已”地址為ip的當(dāng)前值；2.帶標(biāo)號語句的處理方法(2)若L已在符號表中但類型欄不為“標(biāo)號”或定義否欄為“已”則名字重復(fù)(3)若L已在符號表中類型為“標(biā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

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

B.TDB.F:goto

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

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

B為真假時的轉(zhuǎn)向不同在翻譯B時，真假出口有待“回填”(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)向地址均相同的四元式(這些四元式形成一個鏈,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

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

B.TDB.F:goto

S.nextB.TD:┇//語句S對應(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

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

B.TDB.F:goto

B.FD

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

goto

S.nextB.FD:┇//語句S2對應(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對應(yīng)的控制可以表示為（中間代碼形式）again:ifBgoto

B.TDgoto

S.nextB.TD:┇//語句S對應(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對應(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具有三個語義值

F.CHAIN:記錄F+2F.place:記錄i在符號表入口

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(