【正文】 ve are not all the attributes a symbol table has, some symbols used for special may has particular attributes. To sum up, the function of symbol table is for checking up if the semantic in source program is correct. 14 Example ? The definition of constants is: Const pi= r=10 Its symbol table is: Name pi r Kind real int Value 10 15 Example ? The definition of variables is: Var i, j: integer。 … x[i] most of the pilers cannot guarantee that i will be between 0 and 99. . 45 1 Type expression A type expression can be: ? A basic type: a primitive data type such as integer, real, char, boolean, … ? Structured Types: ? arrays: if T is a type expression, then array(I,T) is a type expression where I denotes index range. For example: array(0..10,int) . ? products: if T1 and T2 are type expressions, then their cartesian product T1 x T2 is a type expression. For example: int x int . 46 ? pointers: If T is a type expression, then pointer(T) is a type expression. For example: pointer(int). . ? functions: We may treat functions in a programming language as mapping from a domain type D to a range type R. So, the type of a function can be denoted by the type expression D→R where D are R type expressions. For example: int→int represents the type of a function that takes an int value as parameter, and its return type is also int. . 47 2 Type Checking ? Type checking consists of Expressions type checking, statements type checking, functions type checking and structural expressions type checking. They are introduced by the next tables and their algorithms are in the right of the table. 48 Chapter 7 Storage Organization and Register Allocation Zhang Jing, Wang HaiLing College of Computer Science amp。 then B(I)=P,C(I)=1,(If space P is not allocated, P means the space of the storage of block I). Judge if the matrix of C(I)=0 (I =1， … ,n), , ? then go to step 2,otherwise go to end 70 Step 3: ? If A(K,J)=1(J=I,K=1， … ,n) and B(K)≤P, then B(K)=P+1,(because the units before unit P have been allocated, If B(K)≤P represents that the unit P has been reused. So the allocation of B(K) should begin from the unit of P+1). If B ( K ) P , t h e n B ( K ) w o u l d n o t be changed. . 71 Step 4: ? Turn matrix A(K,J)=1 into A(K,J)=0 Step 5: ? Judge if the matrix of C(I)=0 (I =1， … ,n), then go to step 2,otherwise go to end 72 Table . The relation matrix of example 表 例 模塊間關(guān)系矩陣 ? 73 ? The first time of running static level storage algorithm: : ? Step 1, B(I) =0, C(I) =0 the value of A(I,J) is shown in Table . ? S t e p 2, b e c a u s e A(4,J ) = 0 ( J= 1， … , 5), A(5,J)=0(J=1， … ,5), in addition C(4)=0, C(5)=0. The value of P in block 4 is 9, P in block 5 is 8。 CONST a = 1。 VAR d: real。 ｛ 4｝ two parallel procedures that are procedure 2 and procedure 3. 83 ? PROCEDURE 5(z: real) VAR i: integer。 …… 84 END 。 …… 5 (f)。 …… END.｛ main｝ two parallel procedures that are procedure 2 and procedure 3. Procedure 2 calls procedure 4 and procedure 5, procedure 3 runs procedure 4 and procedure 5 too 86 ? In the main program, there are one constant a and two identifiers b and c that need to be pushed into stack S1, then we first run procedure 2 and at the same time to allocate stack S2 that includes identifiers x and d, next allocate identifiers y and e to S3 for procedure 4, furthermore, it is the turn of procedure 5 that are allocated by stack S4, its identifiers are z and i. Because procedure 3 also calls procedure 4 and procedure 5, the allocation of procedure 3 is stack S5, the identifiers in stack S6 and S7 are same with stack S3 and S4. All of the stack allocation is shown in figure . 87 ? When procedure returns to main program, stacks are firstly released from the top of the stack, that is stack S7, then stack S6 is released, next is the turn of S5 and so on , the program can not be finished until stack S1 is released. ? a, b, c S1 (a) x, d S2 S1 (b) a, b, c (c) y, e S3 S2 S1 a, b, c x, d 88 ? (d) z, i S1 S2 S3 S4 x, d a, b, c y, e z, i S1 S2 S3 S4 x, d a, b, c y, e h, f S5 (e) z, i y, e z, i S1 S2 S3 S4 x, d a, b, c y, e h, f S5 (f) Fig. Runtime stack 圖 示例的運行棧 S 89 ? Allocation with nested procedure 90 ? From example , we know that there are nested procedures in it. Such as procedure 4 and procedure 5 are nested in procedure 2, so is procedure 3. But, how to connect the nested calling procedure with called procedure? We add a pointer named access link to each activation record. If procedure 4 is nested within the most recent activation procedure 2, the access link in activation record for procedure 4 points to the access link in the record for procedure 2, it is shown in figure . . 91 ? In figure b, we can see that there is procedure 4 in the stack. If we want to find the calling of procedure 4 quickly, it is better to know the depth of procedure 4, namely, when we should label the nesting depth of every procedure. Let the main program be at nesting dep