【正文】 ion. . 64 ? 65 ? There are five blocks in the program. ? T h e f i r s t one is t h e m a i n p r o g r a m , ? the others are subroutines. The relationship among subroutines is: subroutine 2 call subroutine 4, subroutine 3 call subroutine 5, , ? namely, subroutine 2 can reuse the space of subroutine 4, subroutine 3 can reuse the space of subroutine 5. The using space, start unit and end unit of each block are described in Table . ? In addition, the level of storage allocation is shown in Figure . . 66 ? Table Allocation of the example 表 例 存儲分配表 Block space10 Start unit End unit 1 10 20 29 subroutine2 8 10 17 subroutine3 10 10 19 subroutine4 9 1 9 subroutine5 8 1 8 67 ? Main 20~29 2 3 4 5 10~19 1~8 1~9 10~17 1 level storage allocation 圖 分層靜態(tài)存儲 68 ? The algorithm of static level storage is as follows： Step 1: ? If There is no relationship between block I and block J, we put matrix of A(I,J)=0 ( I,J=1， … ,n)。 c: real 。 ｛ 5｝ BEGIN …… 4 (d)。｛ 3｝ 85 ? BEGIN …… 2 (b)。 VAR f: real。 CONST e = 15。 so is B(3). ? Step 4, ? A(2,4)=0, A(3,4)=0, A(2,5)=0,A(3,5)=0, ). 75 ? The new value of A(I,J) are shown in Table . ? Step 5, Because not all the C(I) =0(I=1, … ,n), it returns to the step 2. 76 ? The second time of running static level storage algorithm: Step 2 ? b e c a u s e A(2 , J ) = 0 (J=1 ， … , 5 ), A(3,J)=0(J=1， … ,5), in addition C(2)=0, C(3)=0, P in block 2 is 8, P in block 3 is 10, so B(2)= 17 B(3 )= 19 C(2 )=1 C(3 )=1 . 77 ? Step 3： A(1,2)=1, B(1)=18 When A(1,3)=1, then B(1)=20, because that B(1)=20 that is larger than B(1)=18, the value of B(1 ) s h o u l d be changed as B(1 )=20 ? Step 4： A(1,2)=0, A(1,3)=0 ? Step 5： because of C(1)≠0, it should return to step 2 78 ? The third time of running static level storage algorithm: ? Step 2： because A(1,J)=0(J=1， … ,5), in addition C(1)=0, P in block 1 is 10 so B(1)= 29, C(1)=1 ? Step 3, there is no A(K,1)=1(K=1,… 5) ? Step 4, because all C(I)=1(I=1,… 5), so go to end of the algorithm. 79 Dynamic Storage Allocation ? Stack allocation Stack allocation is based on the idea of a control stack。 Its symbol table is Name Kind Address i int 100 j int 102 x real 104 y real 108 16 Example ? The definition of procedure is: Procedure Max； Var h , l: integer。 ? 2 in size attribute means there are two parameters in the procedure Name Kind Level Address Size Max H l Procedure int int 0 1 1 308 300 306 2 17 The Design of Symbol Table ? This section, we begin to discuss the storage and the scope of symbols in various parts of a program. Then we study how to design the structure of a symbol attribute in local symbol table. . 18 ? In order to obtain high running efficient and save the storage of symbol table, we should take into account a lot of things. Firstly, what are the features of program language? How many parts are in program? Which one should be checked by semantic? Secondly, we should discuss the running environment, , 19 ? for example, target machine performance, what kind of target code it will produce. Thirdly, we should think of the operation system that offer the way of storage and management. Finally, how many passes and how many tables according to the passes we should pay attention to. To sum up, if we want to design a symbol table, we should take all those elements into account in order to build a reasonable symbol table. . 20 ? There are two steps to build the symbol table: (1)Build the attribute of symbol table. (2)Design the anization of symbol table. The first one we will discuss in this section, the second one would be introduced in next section. In the part of attribute of symbol table, we mainly introduce the attribute of name, attribute of type and the identifier of array type. 21 22 (1)The attribute of name ? There are three ways to store identifier’s name in symbol table. ? the first way is shown by Table , it means we put the name with all letters in name attribute, the name length is 10 that is a definite. ? The second way is expressed in Fig (a), letters of name are stored in chain table, namely, in name attribute there are length of the name and the name address of connect table. 23 ? The third way is denoted by (b), you can only see name address in name attribute, the name length and name letters are written in its chain table. . ? If a length of identifier’s name is 2 bites, using symbol table in first way to store it needs 8 bites, on the other hand storing it by symbol table in second or third way would save the space, but it spends a lot of searching time. Totally, using which way is up to you. . 24 (2)The attribute of type ? There are also three ways to represent the type attribute. . ? The first way is putting the type directly into the type attribute, shown in Table .