編譯原理(4)語(yǔ)義-4(數(shù)組元素、過(guò)程、說(shuō)明語(yǔ)句的翻譯)

第12講編譯原理西北農(nóng)林科技大學(xué)本科教程

主講教師：趙建邦第四章語(yǔ)義分析和中間代碼生成4.1語(yǔ)義分析概述4.2屬性文法4.3幾種常見的中間語(yǔ)言4.4表達(dá)式及賦值語(yǔ)句的翻譯4.5控制語(yǔ)句的翻譯4.6數(shù)組元素的翻譯4.7過(guò)程或函數(shù)調(diào)用語(yǔ)句的翻譯4.8說(shuō)明語(yǔ)句的翻譯4.9遞歸下降語(yǔ)法制導(dǎo)翻譯方法簡(jiǎn)介第四章《語(yǔ)義分析和中間代碼生成》4.6數(shù)組元素的翻譯4.7過(guò)程或函數(shù)調(diào)用語(yǔ)句的翻譯4.8說(shuō)明語(yǔ)句的翻譯重點(diǎn)掌握二維數(shù)組賦值語(yǔ)句的翻譯本講目標(biāo)

4.6數(shù)組元素的翻譯關(guān)于數(shù)組數(shù)組是用來(lái)存儲(chǔ)一批同類型數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，數(shù)組中的每一個(gè)元素具有同樣長(zhǎng)度的存儲(chǔ)空間。如果在編譯時(shí)就知道一個(gè)數(shù)組存儲(chǔ)空間的大小，則稱其為靜態(tài)數(shù)組，否則為動(dòng)態(tài)數(shù)組。

例：inta[3][4];a[2][1]=5;

void*malloc(unsignedintsize);void*calloc(unsignedintnum,

unsignedintsize);我們主要討論靜態(tài)數(shù)組元素的引用如何翻譯。關(guān)鍵問(wèn)題：1.數(shù)組元素的地址計(jì)算方法2.數(shù)組元素的表示4.6數(shù)組元素的翻譯4.6.1數(shù)組元素的地址計(jì)算及中間代碼形式數(shù)組元素的地址計(jì)算

數(shù)組元素的存放方式?jīng)Q定了數(shù)組元素的地址計(jì)算方法，地址計(jì)算方法決定了數(shù)組元素四元式的產(chǎn)生形式。

數(shù)組元素的存放方式：按行存放和按列存放。我們主要討論按行存放的數(shù)組元素地址計(jì)算方法。123456789A=1234567891472583694.6數(shù)組元素的翻譯1(a)234i1A:l1u1關(guān)鍵問(wèn)題：的地址是什么？4.6數(shù)組元素的翻譯123456789101112A=A[3,3]的地址：1+(3-1)*4+(3-1)=114.6數(shù)組元素的翻譯4.6數(shù)組元素的翻譯4.6數(shù)組元素的翻譯實(shí)現(xiàn)數(shù)組元素的地址計(jì)算時(shí)，將產(chǎn)生兩組四元式序列：

一組計(jì)算CONSPART，其值存放在臨時(shí)變量T中；

另一組計(jì)算VARPART，其值存放在臨時(shí)變量T1中；關(guān)鍵問(wèn)題2：數(shù)組元素的表示

用T[T1](“基址”+“變址”)表示數(shù)組元素的地址。對(duì)數(shù)組元素的賦值和引用就有如下兩種不同的四元式：(1)

變址存數(shù)：若有T[T1]=X，則可以用四元式

([?]=，X，_，

T[T1])表示。(2)變址取數(shù)：若有X=T[T1]，則可用四元式

(=[?]，

T[T1]，_，X)表示。4.6數(shù)組元素的翻譯4.6.2賦值語(yǔ)句中數(shù)組元素的翻譯為了便于語(yǔ)法制導(dǎo)翻譯，我們定義一個(gè)含有數(shù)組元素的賦值語(yǔ)句文法G[A]如下：G[A]:

(1)

A→V=E

(2)

V→i[elist]|i

(3)

elist→elist,E|E

(4)

E→E+E|(E)|V思考當(dāng)前文法所能表達(dá)的語(yǔ)言？其中，A代表賦值語(yǔ)句；V代表變量名；E代表算術(shù)表達(dá)式；elist代表由逗號(hào)分隔的表達(dá)式，它表示數(shù)組的一個(gè)下標(biāo)；i代表簡(jiǎn)單變量名或數(shù)組名。4.6數(shù)組元素的翻譯4.6.2賦值語(yǔ)句中數(shù)組元素的翻譯在用產(chǎn)生式(2)、(3)進(jìn)行歸約時(shí)，為了能夠及時(shí)計(jì)算數(shù)組元素的VARPART，我們將產(chǎn)生式(2)、(3)改寫為：(2)

V→i[elist]|i

(3)

elist→elist,E|E(2')

V→elist]|i

(3')

elist→elist,E|i[E則數(shù)組元素賦值語(yǔ)句文法變?yōu)椋篏[A]:

(1)

A→V=E

(2')

V→elist]|i

(3')

elist→elist,E|i[E

(4)

E→E+E|(E)|V4.6數(shù)組元素的翻譯關(guān)鍵非終結(jié)符之１：Ｖ使用G[A]規(guī)約如下句子：

x=A［２，３］

A［２，３］=

x可見，Ｖ有可能是簡(jiǎn)單變量規(guī)約得到，也可能是數(shù)組元素規(guī)約得到。因此，為Ｖ設(shè)置兩個(gè)語(yǔ)義值：Ｖ.place和V.offset。

G[A]:

(1)

A→V=E

(2')

V→elist]|i

(3')

elist→elist,E|i[E

(4)

E→E+E|(E)|V4.6數(shù)組元素的翻譯關(guān)鍵非終結(jié)符之１：Ｖ如果V是一個(gè)簡(jiǎn)單變量名，V.place保存該變量的入口地址，V.offset=null;

如果V是一個(gè)數(shù)組元素，V.place保存該數(shù)組元素的CONSPART，V.offset保存VARPART;4.6數(shù)組元素的翻譯關(guān)鍵非終結(jié)符之2：elist對(duì)于類似于如下形式的句子：

A［E，E，E，…，E］=

x最終規(guī)約為elist]=x，繼而V=x；

可見，elist負(fù)責(zé)規(guī)約數(shù)組元素中除了]之外的部分。對(duì)elist設(shè)置三個(gè)屬性：elist.ARRAY，elist.DIM，elist.place。

G[A]:

(1)

A→V=E

(2')

V→elist]|i

(3')

elist→elist,E|i[E

(4)

E→E+E|(E)|V4.6數(shù)組元素的翻譯非終結(jié)符之2：elist

(1)elist.ARRAY：表示數(shù)組名在符號(hào)表中的入口。例如：數(shù)組元素A[3,4,6,3,2]在規(guī)約過(guò)程中，所有elist.ARRAY的值是Ａ；

(2)elist.DIM：數(shù)組維數(shù)的計(jì)數(shù)器。例如：

A[3,4,6,3,2]規(guī)約為elist,4,6,3,2]，elist.DIM=1；

elist,4,6,3,2]規(guī)約為elist,6,3,2]，elist.DIM=2；

最終規(guī)約為elist]，則elist=5;

(3)elist.place：登錄已生成VARPART中間結(jié)果的單元名字在符號(hào)表中的存放位置，或是一個(gè)臨時(shí)變量的整數(shù)碼。因此，在逐次對(duì)elist歸約的過(guò)程中，將逐步產(chǎn)生計(jì)算VARPART的四元式VARPART=((…((i1d2

+

i2)d3

+

i3)d4

+

…

)+

in?1)dn

+

in4.6數(shù)組元素的翻譯(1)

A→V=E{if(V.offset==null)

emit(=,E.place,_,V.place);/*V是簡(jiǎn)單變量*/

else

emit([]=,E.place,_,V.place[V.offset]);

/*V是下標(biāo)變量*/

}含有數(shù)組元素的賦值語(yǔ)句對(duì)應(yīng)的文法G[A]及相應(yīng)的語(yǔ)義子程序如下(省略語(yǔ)義檢查，僅給出主要語(yǔ)義動(dòng)作)：CONSPARTVARPART4.6.2賦值語(yǔ)句中數(shù)組元素的翻譯(語(yǔ)義子程序)(2)

E→E(1)+E(2){T=newtemp;

emit(+,E(1).place,E(2).place,T);

E.place=T;}

(3)

E→(E(1)){E.place=E(1).place;}4.6數(shù)組元素的翻譯(4)

E→V{if(V.offset==null)

E.place=V.place;/*V是簡(jiǎn)單變量*/

else{T=newtemp;/*V是下標(biāo)變量*/

emit(=[],V.place[V.offset],_,T);

E.place=T;

}

}將數(shù)組元素的值賦給T4.6數(shù)組元素的翻譯(5)

V→elist]{T=newtemp;

emit(?，elist.ARRAY,C,T);

V.place=T;V.offset=elist.place;}

/*假定通過(guò)數(shù)組名的符號(hào)表入口不僅能獲得地址a而且也能得到常數(shù)C(CONSPART=a-C)*/(6)

V→i{V.place=entry(i);V.offset=null;}(8)

elist→i[E{elist.place=E.place;elist.DIM:=1;

elist.ARRAY=

entry(i);}(7)

elist→elist(1),E{T=newtemp;k=elist(1).DIM+1;

dk=limit(elist(1).ARRAY,k);

emit(*,elist(1).place,dk,T);

emit(+,E.place,T,T);

elist.ARRAY=elist(1).ARRAY;

elist.place=T;elist.DIM=k;}

VARPART=(…((i1d2

+

i2)d3

+

i3)d4

+

…

+

in?1dn)+in

4.6數(shù)組元素的翻譯其它函數(shù)：

limit(ARRAY,k)計(jì)算數(shù)組ARRAY的第k維長(zhǎng)度dk4.6數(shù)組元素的翻譯4.6數(shù)組元素的翻譯例4.10

已知A是一個(gè)10

×

20的數(shù)組(每維下界均為1)且按行存放，求：

(1)賦值語(yǔ)句X

=

A[I,J]的四元式序列；

(2)賦值語(yǔ)句A[I

+

2，J

+

1]

=

M

+

N的四元式序列

要求給出語(yǔ)法制導(dǎo)翻譯過(guò)程。[解答]

由于A是10

×

20的數(shù)組，故:

d1

=

10，d2

=

20，C

=

l1d2

+

l2

=

21。

(1)根據(jù)文法G[A]及對(duì)應(yīng)的語(yǔ)義加工子程序，賦值語(yǔ)句X=A[I,

J]的語(yǔ)法制導(dǎo)翻譯過(guò)程如圖4-17所示。104(=,T3,_,X)4.6數(shù)組元素的翻譯例4.10

已知A是一個(gè)10

×

20的數(shù)組(每維下界均為1)且按行存放，求：

(1)賦值語(yǔ)句X

=

A[I,J]的四元式序列:

100(*,I,20,T1) /*d2=20*/

101(+,J,T1,T1) /*得到20I+J*/102(?,A,21,T2) /*得到A?21*/103(=[

],T2[T1],_,T3)/*T2[T1]即為A[I,J]，即

T3=T2[1]*/105(+，M，N，T5)4.6數(shù)組元素的翻譯例4.9

已知A是一個(gè)10

×

20的數(shù)組(每維下界均為1)且按行存放，求：

(2)賦值語(yǔ)句A[I

+

2，J

+

1]

=

M

+

N的四元式序列:

100(+，I，2，T1)

101(+，J，1，T2)

102(*，T1，20，T3)

103(+，T2，T3，T3)104(?，A，21，T4)106([

]=，T5，_，T4[T3]) /*T4[T3]

=

T5*/4.6數(shù)組元素的翻譯例.設(shè)A為一個(gè)10*20的數(shù)組，即n1=10,n2=20,并設(shè)w=4.對(duì)賦值語(yǔ)句x:=A[y,z]翻譯成四元式。注意：數(shù)組下界為1應(yīng)該生成的三地址序列為：T1:=y*20T1:=T1+zT2:=4*T1T3:=A-84T4=T3[T2]

x:=T4C=((l1*n2)+l2)*w4.6數(shù)組元素的翻譯VAR=((i1*n2)+i2)*w4.7過(guò)程或函數(shù)調(diào)用語(yǔ)句的翻譯4.7.1過(guò)程調(diào)用1.定義和調(diào)用過(guò)程(函數(shù)、方法等)是程序語(yǔ)言的主要特征之一。主要功能有：

(1)是模塊化程序設(shè)計(jì)的主要手段；

(2)節(jié)省程序代碼；

(3)擴(kuò)充語(yǔ)言能力。2.過(guò)程調(diào)用：實(shí)質(zhì)是把程序控制轉(zhuǎn)到子程序。3.過(guò)程調(diào)用中遇到的主要問(wèn)題：

(1)如何進(jìn)行參數(shù)傳遞；

(2)子程序執(zhí)行完之后如何回到主調(diào)程序；

(3)子程序回到主調(diào)程序時(shí)，運(yùn)行環(huán)境的恢復(fù)。4.7過(guò)程或函數(shù)調(diào)用語(yǔ)句的翻譯在編譯階段對(duì)過(guò)程調(diào)用語(yǔ)句的翻譯，所做的工作主要是參數(shù)傳遞。1.參數(shù)：

(1)實(shí)在參數(shù)：來(lái)自于主調(diào)過(guò)程

(2)形式參數(shù)：存在于被調(diào)過(guò)程2.傳遞方式：

(1)傳地址(callbyreference)：把實(shí)參的地址傳給形參；

(2)傳值(callbyvalue)：把實(shí)參值的拷貝傳給形參。4.7過(guò)程或函數(shù)調(diào)用語(yǔ)句的翻譯如何傳遞實(shí)參地址？

(1)如果實(shí)參是一個(gè)變量（包括下標(biāo)變量），則直接傳遞該變量的地址；

(2)如果實(shí)參是一個(gè)常量或表達(dá)式(如：2或者X+2)，現(xiàn)將它的值計(jì)算出來(lái)并存放在臨時(shí)變量T中，然后傳遞T的地址。被調(diào)過(guò)程執(zhí)行的時(shí)候，會(huì)在棧中為其分配內(nèi)存空間。

被調(diào)過(guò)程的每個(gè)形參都有一個(gè)單元(稱為形式單元)，用來(lái)存放對(duì)應(yīng)實(shí)參的地址。

因此，在被調(diào)過(guò)程的內(nèi)部語(yǔ)句執(zhí)行之前，必須先把實(shí)參的地址取到對(duì)應(yīng)的形參單元中。然后才能執(zhí)行本過(guò)程中的語(yǔ)句。4.7過(guò)程或函數(shù)調(diào)用語(yǔ)句的翻譯4.7.2過(guò)程調(diào)用語(yǔ)句的翻譯(傳址)1.文法：

G[S]:S→calli(elist)

elist→elist,E|EP(){…Q(x,y,z);…}Q(inta,intb,intc){……}calli(E(1),E(2),E(3));1.使用隊(duì)列保存E(i);2.傳遞E(i)的地址;3.callQ;4.7過(guò)程或函數(shù)調(diào)用語(yǔ)句的翻譯2.語(yǔ)義子程序：{for(隊(duì)列queue中的每個(gè)P)

emit(par,_,_,P);

emit(call,_,_,i.place);}{將E.place加入到queue的隊(duì)尾}

G[S]:S→calli(elist)elist→elist,Eelist→E{初始化queue,僅包含E.place}例如：callQ(A+B,Z)被翻譯為：(100)(+,A,B,T)(101)(par,_,_,T)(102)(par,_,_,Z)(103)(call,_,_,Q)4.8說(shuō)明語(yǔ)句的翻譯4.8.1變量說(shuō)明的翻譯說(shuō)明語(yǔ)句的功能是說(shuō)明源程序中每一個(gè)名字及其性質(zhì)。文法1：文法2：

G[D]:D→intnamelist|floatnamelistnamelist→namelist,i|i

G'[D]:D→D,i|inti|floati(1)D→inti{fill(i,int);D.att=int;}缺點(diǎn)：變量列表先規(guī)約成namelist,最后才能確定變量的類型優(yōu)點(diǎn)：每掃描一個(gè)變量，就