编译原理课件：8-第八章-存储空间组织-3节

§8.3静态存储分配——FORTRAN语言如果编译时能确定一个程序在运行时所需的存贮空间大小，则可以在编译时安排目标程序的全部数据空间，并确定每个数据项的单元地址。这种存贮空间分配方法称为——“静态存储分配”。静态存储分配特点

1).编译时刻确定存储位置；

2).目标程序执行时不必进行存储管理。目标程序代码特别简单、高效。FORTRAN语言的特点：（FORTRAN77）

1).过程不允许递归调用一个过程的两个活动的生存期不相交，因此一个过程的所有活动可以使用同一个活动记录；

2).每个数据名所需的存储空间大小是常数，没有可变数组等；

3).数据名的性质完全确定；不能动态地建立数据结构；因此可以采用“静态存储分配”。由于每个FORTRAN程序段可以独立编译，运行前由装入程序把各段连成可运行的整体。通常按数据区组织存储:每个程序段定义一个局部数据区，用来存放程序段中未出现在COMMON里的局部名的值。每个公用块定义一个公用数据区，用来存放公用块里各个名字的值。每个数据区有一个编号，地址分配时，在符号表中，对每个数据名登记：（所属数据区编号，在该区中的相对位置）§8.3.1FORTRAN数据区数据区=局部区(1个/程序段)＋全局区主程序子程序1子程序n编译目标代码常数局部数据区主程序......无名公共区有名公共区1有名公共区m...1.各数据区编号，并统计长度，便于分配空间；2.数据区仅分配地址，构成映象(虚空间)，真正的空间运行时才建立，并可以使用；全局区目标代码常数局部数据区子程序

1目标代码常数局部数据区子程序

n局部数据区的内容：

返回地址：存放此程序段结束时的返回地址。寄存器保护区：调用本程序段时寄存器中的信息，当本程序段结束后，可以恢复到调用前的状态；形式单元：存放实在参数的地址或值。FORTRAN语言采用两种方式共存的形式。传地址：一个单元，存放地址；得结果：二个单元，存放地址、值；数组：按列存放；临时变量：语义分析引入。临时变量数组简单变量形式单元寄存器保护区返回地址寄存器保护区返回地址ATBa临时变量数组简单变量形式单元寄存器保护区返回地址考虑子程序段：SUBROUTINESWAP(A,B)T=AA=BB=TRETURNEND设：实型量占2个机器字§8.3.2公共语句、等价语句介绍数据对象的物理存储空间管理，对程序的空间利用效率有很大的影响，COMMON和EQUIVALENCE这两个语句提供了足够强大的控制存储空间的功能。COMMON

：处理不同程序单位之间的数据共享。通常用于在不同程序单位之间进行数据的批量传递，它比采用参数传递的方式效率要高。EQUIVALENCE

：*）处理同一个程序单元中的多个对象共享一个存储空间，以节省内存。因此，主程序和过程之间；过程相互之间不同变量不能用EQUIVALENCE语句来指定共用存储单元。*）允许用两个或更多的变量名代表同一个量。COMMON、EQUVILENCE：这两个语句功能过于强大，滥用会导致对程序的理解和维护变得非常困难。存储关联：

通过直接访问数据对象的存储空间，使得不同的名称能够共享同一个数据实体。在FORTRAN90，对存储空间的控制改用：模块、指针、可分配数组、动态数据等对象。因此公共语句、等价语句的作用逐渐减小。作为：“向后兼容”特性保留。FORTRAN语言存储空间的模式描述：1).存储单位：存储单个FORTRAN数据值的内存空间;

integer,real,boolean：占一个机器字;Complex(复数),double(双精度实型)：

占两个相继的机器字;例：INTEGERI,J,K(3)

COMPLEXXREALA

IJK(1)K(2)K(3)A…X数据区2).存储序列：

任意多个连续的数据单位就构成了一个存储序列；一个数组对象构成一个存储序列；

一个公用块构成一个存储序列；

等价语句中的等价列表的所有对象构成一个存储序列；3).两个数据对象如果共享了同一个存储序列，那么它们就称为具有存储关联的关系。如果它们只是共享了同一个存储序列的部分存储单位，那么它们称为具有部分存储关联的关系。公共区：一块有名字的、被共享的存储空间。无名公共区：一个；有名公共区：多个；公共语句：

COMMON[/[公共块名1]/]变量名表1[[,]/[公共块名2]/变量名表2]...其中：*)变量名不得是哑元、可分配数组、自动对象等。*)不同程序单元中,同一公用区中的变量名可以不同。按位置一一对应共享同一存储单元中的数值。*)COMMON语句是说明语句，必须在可执行语句之前。公共语句：

COMMON[/[公共块名1]/]变量名表1[[,]/[公共块名2]/变量名表2]...COMMON/B1/we,you,theyCOMMON//our,your,theirCOMMON/B1/i,he,sheCOMMON/B2/dog,cat,mouseCOMMONmy,his,her

COMMON/B1/we,you,they,i,he,sheCOMMON/B2/dog,cat,mouseCOMMON//our,your,their,my,his,her其中：

//是无名区等价于公共语句：

COMMON[/[公共块名1]/]变量名表1[[,]/[公共块名2]/变量名表2]...主程序中的语句COMMONX,Y,Z(3),I子程序中的语句COMMONA,B,C(3),J效果：无名公共区中，变量X和A，Y和B，数组Z和C，I和J分别被分配在相同的存储单元中。在不同的程序单位中占用公共区同一个存储单元的那些变量，它们的名字不需要相同。注意：一个程序段中，同一个名字只能出现在一个公共区。例：主程序:common//X,Ycommon/B1/A,B,C//D,E,F(5)common/B1/X子程序1:common//I,Q(5)common/B1/F(5)/B2/P(3)子程序2:common/B1/X(4)common/B2/Y,Z

ComplxY,Z定义错误与主程序中的X，代表不同的含义主:common//X,Ycommon/B1/A,B,C//D,E,F(5)

子1:common//I,Q(5)common/B1/F(5)/B2/P(3)子2:common/B1/X(4)common/B2/Y,Z

ComplxY,Z无名区XYDEF(1)F(2)F(3)F(4)F(5)IQ(1)Q(2)Q(3)Q(4)Q(5)B1区ABCF(1)F(2)F(3)F(4)F(5)X(1)X(2)X(3)X(4)B2区P(1)P(2)P(3)YZ无名区B1区B2区主930子1653子2044最终长度954F、Q部分存储关联X、I存储关联COMMON/COM/M(5),N(4)CALLFIB

WRITE(*,'(1X,4I3)')N

ENDSUBROUTINEFIBCOMMON/COM/J(5),K(4)DO10I=1,4K(I)=J(I+1)－

J(I)

10CONTINUE

ENDBLOCKDATA

COMMON/COM/K(5),L(4)

DATAK/8,7,10,4,13/

END答案：

-13-69

COM区主程序FIBDATAM(1)J(1)K(1)8M(2)J(2)K(2)7M(3)J(3)K(3)10M(4)J(4)K(4)4M(5)J(5)K(5)13N(1)K(1)-1L(1)N(2)K(2)3L(2)N(3)K(3)-6L(3)N(4)K(4)9L(4)等价语句：EQUIVALENCE(变量名表1),(变量名表2),…

其中：

1）等价语句是说明语句，应出现在执行语句之前；

2）每一个(变量名表)，称为一个等价片；

3）等价片中的名字称为等价元。等价元可以是简单变量或下标为常数的下标变量。例：INTEGERI,J,K(3)

COMPLEXXREALA(3,3)EQUIVALENCE(X，A(2,3)),(I,J,A(1,2),K(2))等价片4）等价片中的每一个等价元都被分配到同一个存储单元，只要某一个等价元赋予某值，其它的等价元也就同时具有相同的值。如有赋值：I=2

则J,A(1,2)值也为2。

（注意：这种效果不是数学上的等值，而是由于共享一个存储单元而得到的方便。)INTEGERI,J,K(3)

COMPLEXXREALA(3,3)EQUIVALENCE(X,A(2,3)),(I,J,A(1,2),K(2))5).不同等价片中若有相同名字(包括数组名)，则称为等价相关，应将其合并，让更多等价元共享存储单元。(如A)6).若两个数组的某一个元素等价，则数组的其他元素也产生等价关系（如A,K）INTEGERI,J,K(3)

COMPLEXXREALA(3,3)EQUIVALENCE(X，A(2,3)),(I,J,A(1,2),K(2))例：INTEGERI,J,K(3)COMPLEXXREALA(3,3)

EQUIVALENCE(X,A(2,3)),(I,J,A(1,2),K(2))XA(1,1)A(2,1)A(3,1)A(1,2)A(2,2)A(3,2)A(1,3)A(2,3)A(3,3)IJK(1)K(2)K(3)7).占用单元数不同的名字等价时，占用单元少的名字和占用单元多的名字的前半部分占用同一单元；(X,A)

存储区公共语句与等价语句同时出现：⑴.若一个名字与公共区中元素等价，则该名字分配到公共区；⑵.等价语句不能改变公共语句确定好的次序和位置，但可以用EQUIVALENCE语句来扩大公共区；A(1)A(2)A(3)A(4)CB(1)B(2)B(3)B(4)DIMENSIONA(4),B(4)

COMMONA,C

EQUIVALENCE(A(3),B(1))公共语句与等价语句同时出现：⑶.等价语句不能改变公共语句确定好的次序和位置，等价元素位置不得小于公共区起始位置（否则称为“冒头”）A(1)A(2)A(3)A(4)CB(1)B(2)B(3)B(4)DIMENSIONA(4),B(4)

COMMONA,C

EQUIVALENCE(A(1),B(2))B是由等价语句带进来的，但B的元素向前越过了公用区的第一个存储单元——“冒头”不要混淆EQUIVALENCE和COMMON语句。EQUIVALENCE语句是给同一程序单位中的不同变量分配同一个存储单元，而COMMON语句则用于给不同程序单位的变量分配同一存储单元。因此不允许在同一程序单位中写：ABCBCOMMONA，B，CEQUIVALENCE（A，B）COMMON语句把变量A、B、C分配在公用区中相邻的三个存储单元中；EQUIVALENCE语句又把A、B分配在同一个存储单元中——矛盾PROGRAMMAINCOMMON/A1/X,Y,ZCOMMONS1,S2EQUIVALENCE(X,X3)S1=2.0S2=3.0CALLS(X1,X2)PRINT*,X,Y,ZPRINT*,X1,X2,X3PRINT*,S1,S2ENDSUBROUTINES(Y1,Y2)COMMON/A1/A,B,C//Q1A=A+3.0B=B+4.0C=C+5.0Y1=A+BY2=C-AQ1=Q1+2.0ENDBLOCKDATACOMMON/A1/P,Q,RDATAP,Q,R/3*1.0/ENDXYZX3ABCPQRS1S2Q1

X1X2Y1Y21.01.01.02.03.0

4.05.06.09.02.0

4.0输出：4.05.06.09.02.04.04.03.0A1区无名区局部区例：SUBROUTINESS(I)；

INTEGERK,T,Q,S；

REALB(5),C(6),MCOMMON//Y,Z,D

COMPLEXD(2)

EQUIVALENCE(Z,C(1)),(C(3),S),(Q,B(2)),(T,B(4))无名公共区0Y1ZC(1)2D(1)C(2)3SC(3)4D(2)C(4)5C(5)6C(6)局部数据区0I1K2B(1)↑3QB(2)│4B(3)等价片5TB(4)│6B(5)↓7M等价片分配后§8.3.3公共语句的处理1).新增公共块表(COMLIST)，主要栏目项如下：2).符号表中增加一个栏目项CMP，将同一公共区中的元素按出现顺序拉成一条链(指向同一条公共链的下一个元素)；

COMLISTNAMELENGTHFTLT公共块名长度链首在符号表中的入口地址链尾在符号表中的入口地址符号表Name…CMPCOMMONX,YCOMMON/B1/A,B,C//D,E,F(100)

符号表Name…DACMP1X22Y63AB144BB155CB106D77E88F0COMLISTNameLengthFTLT18B135无名公共区：

X→Y→D→E→FB1区：

A→B→CLength栏：地址分配时确定3)遇到公共语句的处理

COMMON/BLK/name1,name2,…namena)若块名BLK未在COMLIST中出现，则新增一项，其中：Name=BLK，FT=null，LT=null；b)读取名字namei，查符号表中是否有该名字，若无则填入此名；将CMP栏填0(链尾)；设该符号在符号表中的行号为P；

c)根据公共块名BLK查COMLIST表,ifCOMLIST[BLK].FT=nullthen/*该公共区的第一个元素*/{COMLIST[BLK].FT=P；

COMLIST[BLK].LT=P；}else{符号表[COMLIST[BLK].LT].cmp=P；

COMLIST[BLK].LT=P；

}COMMONX,YCOMMON/B1/A,B,C

符号表Name…DACMP12345678COMLISTNameLengthFTLT无名公共区：

X→Y→D→E→FB1区：

A→B→CLength栏：地址分配时确定B1B1B12012B135450→6780→8//D,E,F(100)XYABCDEF§8.3.4等价语句的处理1).主要工作：找出存在等价关系的等价元，将它们构成等价环；指出各等价元的首地址关系，以便进行内存分配。EQUIVALENCE(X,Y),(I,J,K(2))XYPIJPK等价元的首地址关系

X首地址=Y首地址,I首地址=J首地址=K的首地址+12).实现方式：在符号表中增设两栏：EQ和OFFSET。

EQ：等价环形链，指向下一个等价元的入口；若为null，则说明该名字不是等价元；（若等价环中只有一个等价元，则指向自身）

OFFSET：相对位移量，用来指出各等价元存储首地址之间的地址相对关系。INTEGERI,J,K(3)REALX,YEQUIVALENCE(X,Y),(I,J,K(2))NAME…OFFSETEQ1I032J013K-124X055Y04XYPIJPK引入：

P：现行等价环的链首指针；

Base：计算现行等价环的offset的基准；

L：一个元素占用的单元数；

J：足标，简单变量=0，数组元素

=“与首地址之间相差的元素数”；等价语句处理算法等价语句处理算法1).初始化：符号表中，EQ=null2).准备处理下一个等价片，

P=null，Base=03).取等价片中的元素X，设X在符号表的入口为N，

z:=Base－J*L；4).若X不在等价链中(EQ[N]=null),将X加入当前等价环

IFP=nullthenP:=NelseEQ[N]:=EQ[P];EQ[P]:=N;Offset[N]:=z;X空链：PX非空链：P×P：现行等价环的链首指针L：一个元素占用的单元数Base:计算现行环offset的基准J：足标，“与首地址之间相差的元素数”5).若X已在某等价链中(EQ[N]≠null)，则当前链与X

所在链合并a)调整当前链中各元素的相对数，及基准(Base)D:=OFFSET[N]-z(OFFSET[N]：X的老值，z:新值)

对链中每一元素，OFFSET[m]:=OFFSET[m]+D;Base:=Base+D;b)两链合并,设新链链头P，链尾Q1，

ifP=nullthenP:=Nelse{EQ[Q1]:=EQ[N]；EQ[N]:=P；}6).若现行片还有等价元，转3）7).若还有其他等价片，转2）Ｘ当前链PQ1

链尾×N形式化的归并算法P251Name…offsetEQ1234

5

INTEGERI,J,K(3)COMPLEXXREALA(3,3)EQUIVALENCE(X,A(2,3)),(I,J,A(1,2),K(2))XPXPAIJKXA04-745P：现行等价环的链首指针；L：一个元素占用的单元数；Base：计算现行环offset的基准J：足标，与首地址之间相差的元素数等价元不在等价环中：IFP=nullthenP:=NelseEQ[N]:=EQ[P];EQ[P]:=N;Offset[N]:=z;basePnameNLJz0nullX420004A517-7J=(i1-1)+(i2-1)*d1z:=Base-J*LName…offsetEQ1I2J3K4X05

5A-74XAIPIPJbasePnameNLJz0nullI110001J2100INTEGERI,J,K(3)COMPLEXXREALA(3,3)EQUIVALENCE(X,A(2,3)),(I,J,A(1,2),K(2))P：现行等价环的链首指针；L：一个元素占用的单元数；Base：计算现行环offset的基准J：足标，与首地址之间相差的元素数20101basePnameNLJz01A513-3归并;D=－7－(－3)=－4,调整当前链中元素的offset,base,链合并IPJXAIJXAKPName…offsetEQ1I022J013K4X055A-74已知：XAIPJQ1链尾J=(i1-1)+(i2-1)*d1z:=Base-J*LINTEGERI,J,K(3)COMPLEXXREALA(3,3)EQUIVALENCE(X,A(2,3)),(I,J,A(1,2),K(2))－41K311－5-52413-4-4§8.3.5地址分配先分配公用区，再分配局部区

1)、公用区地址分配：按公共链分配，若公共元又是等价元，等价环上的元素同时分配。同时，检查是否有“冒头”，并计算公共区的长度（等价元可能延长公共区）。公共区的段号从128开始。定义：DA[N]：符号表中段地址；

d：地址的段号；Addr[N]：符号表中段内地址；len：公用区长度；a：分配地址的计数器；分配算法：对comlist表中的每一个FT≠null的项i,执行：⑴d=127+i;a:=0;len:=0;⑵沿公共链，取下一元素X，(行号=N)，若链已为空，转⑷

a)若X已分配了地址，则“冲突”

{(DA[N]≠0)and(DA[N]≠dORAddr[N]≠a)/*在不同的公共区，或在同一公共区的不同地址*/}b)若X非等价元，DA[N]:=d;Addr[N]:=a;

c)若X是等价元，f:=offset[N];//公共元的相对数

对等价环上的每一个元素，行号=Ni；

DA[Ni]:=d;a1:=a＋(offset[Ni]－f)；若a1<0，报错；//冒头

Addr[Ni]:=a1;len:=max(len,a1+size[Ni])//len—分配该等价环之前公用区的长度，

//size[Ni]为等价元Ni占用单元数⑶a:=a+size[N]；

//size[N]为公共元N占用单元数

len:=max(len,a)；//以占用空间多的长度为准

转⑵⑷comlist

表中，length[i]:=max(length[i],len)//以占用空间最长的段的长度为准公用区地址分配算法

P252COMMONX,YCOMMON/B1/A,B,C//D,E,F(100)COMLISTNameLengthFTLT10418B1335无名公共区，分配顺序：

X→Y→D→E→FB1区，分配顺序：

A→B→C符号表Name…SizeCMPDAAddr1X1212802Y1612813A1412904B1512915C1012926D1712827E1812838F10001284无名公共区0Y1ZC(1)2D(1)C(2)3SC(3)4D(2)C(4)5C(5)6C(6)INTEGERS；

REALC(6)COMMON//Y,Z,D

COMPLEXD(2)EQUIVALENCE(Z,C(1)),(C(3),S)等价环：C→S→Z→C无名公共区，分配顺序：

Y→Z→C→S→DLength=7Name…SizeCMPoffsetEQDAAddr1S12412832C60112813Y1412804Z150212815D401282COMLISTNameLengthFTLT7352)局部区地址分配

a)局部区地址分配策略

选择等价环中offset最小的等价元开始分配地址，以解决冒头问题；等价环中变量与非该等价环中的变量不占有相同存储单元。

除了等价环元素之外，局部区变量的地址分配严格按照变量出现的顺序进行。

b)局部区地址分配算法：⑴初始化，a=0;d=现行程序段序号；

(局部区程序段序号从0开始)⑵自上而下扫描符号表，找未分配(DA=null)的符号X,

设行号=N，若未找到分配结束；⑶a)若X非等价元，则：DA[N]:=d;Addr[N]:=a;a:=a+size[N]；

b)若X为等价元，等价环上的元素为：N1,N2,…NmⅠ)求：f＝min(f1,f2,…,fm)，fi是Ni的offsetⅡ)对等价环上的每个元素Ni（i=1～m）

DA[Ni]:=d;Addr[Ni]:=a＋(offset[Ni]－f);

len:=max(len,(offset[Ni]－f）+size[Ni])Ⅲ)a:=a+len

；\本等价元占用单元长度⑷转⑵

局部区等价环分配算法

P253{N1:=N;f:=OFFSET[N];WHILEEQ[N1]<>NDO/*找等价环中最小相对位移量，存于f*/{N1:=EQ[N1];f:=MIN(f,OFFSET[N1])};

len:=-∞;N1:=N;/*从入口开始为等价环各元素分配地址*/REPEATDA[N1]:=现行程序段序号；

ADDR[N1]:=a+(OFFSET[N1]-f);

len:=MAX(len,(OFFSET[N1]-f)+SIZE(N1));N1:=EQ[N1];UNTILN1=N;a:=a+len;}分配公共区,处理一个等价环后，公共区长度：

len:=max(len,a＋MAX(fi－f＋size[Ni]))

（i=1～m）其中：fi是等价元的offset，

f是公共元的offset，

分配局部区，处理一个等价环后，局部区长度：

len:=max(len,a＋MAX(fi－f＋size[Ni]))

（i=1～m）其中：fi是等价元的offset，

f是本等价环中，offset最小值，

即，f＝min(f1,f2,…,fm)SubroutineSS(I)IntegerK,T,Q；RealB(5),C(6)Common//Y,Z,D；ComplexD(2)RealMEquivalence(Z,C(1)),(Q,B(2)),(T,B(4))Name…SizeoffsetEQCmp1I12K13T14Q15B56C67⑴符号表中登记一般名字:I，

K，T，Q，

B，C⑵处理公共语句，

a)在Comlist，登记“无名区”，

b)符号表中登记名字：

Y，Z，Dc)拉链，Comlist表中，

FT指向Y，LT指向D

符号表中Cmp：7→8→9⑶登记一般名字：M

COMLISTNameLengthFTLT无名79Name…SizeoffsetEQCmp1I12K13T14Q15B56C678910

……Common//Y,Z,D；ComplexD(2)RealMEquivalence(Z,C(1)),(Q,B(2)),(T,B(4))Y18Z19D40M1

Equivalence(Z,C(1)),(Q,B(2)),(T,B(4))Name…SizeoffsetEQCmp……3T14Q1

5B56C67Y188Z1

99D40……

ZPZPC片2：(Q,B(2))⑷对等价片1：(Z,C(1))

QPPBQ6080804-145Name…SizeoffsetEQCmp……3T1

4Q1055B5-146C6087Y188Z10699D40……

⑷对等价片3：(T,B(4))TP∵EQ[B]≠null∴B已在某个等价环中，

a)D=(-1)-(-3)=2b)调整offset(对T),Basec)链归并老环BQTPBQTPEquivalence(Z,C(1)),(Q,B(2)),(T,B(4))2J=(i1-1)+(i2-1)*d1z:=Base-J*L0343

COMLISTNameLengthFTLT无名779符Name…SizeoffsetEQCMPDAAddr号6C6081281表7Y1812808Z106912819D401282地址分配1.公用区(及等价元),有:Y,Z,D,C

段号从128开始。分配过程等价元顺序NameaSizeDAAddrffia1len新a最终len1Y011280112Z1112810012273C16128100174D24128267f:公共元的offsetfi:等价元的offset

len=max(len,a1+size[N])新a=a+size[N]最终len=max(len,a)2.局部区,有：I,K,T,Q,B,M,段号从0开始。分配过程顺序Addr等价元新aNameaSizeDA非等价元等价元ffilen非等价元等价元1I010012K110123T2105-1244Q2103-1045B2502-1-152+5=76M71078Addr：非等价元=a

等价元=a+(fi-f)f＝min(f1,…fm)

fi=offset[Ni]

len=max(len,(fi-f)+size[N])新a：非等价元=a+size[N]等价元=a+len符Name…SizeoffsetEQCmpDAAddr号1I100表2K1013T124054Q105035B5-130210M1

07Addr[Ni]=a＋(fi－f)=2+(2-(-1))=5Len=max(len,(fi-f)+size[N])=max(0,2-(-1)+1)=4

无名公共区0Y1ZC(1)2D(1)C(2)3C(3)4D(2)C(4)5C(5)6C(6)符号表Name…Size…DAAddr1I1002K1013T1054Q1035B5026C612817Y112808Z112819D4128210M107SubroutineSS(I)IntegerK,T,QRealB(5),C(6)Common//Y,Z,DComplexD(2)RealMEquivalence(Z,C(1)),(Q,B(2)),(T,B(4))

COMLISTNameLengthFTLT无名779局部数据区0I1K2B(1)↑3QB(2)│4B(3)等价片5TB(4)│6B(5)↓7M符号表Name…Size…DAAddr1I1002K1013T1054Q1035B5026C612817Y112808Z112819D4128210M107SubroutineSS(I)IntegerK,T,QRealB(5),C(6)Common//Y,Z,DComplexD(2)RealMEquiv(Z,C(1)),(Q,B(2)),(T,B(4))作业：P268第2题

，要求：⑴对公共语句、等价语句处理后，反映在符号表中的内容；⑵分配的地址；