【正文】 on. When search an identifier in subprogram n, we should search it begin from chain table n, if there is no the symbol in it, search it in chain table n1untill chain table 1 ? (2) In subprogram exit, the chain symbol table should be deleted to release the space. . 34 . The structure of symbol table ? Which kind of symbol structure you will design or choose mostly depends on storing efficiency and operation speed. There are many symbol structure tables, such as unordered symbol table, ordered symbol table, stack symbol table, tree symbol table and hash symbol table. Next we will introduce three typical symbol structures: unordered symbol table, ordered symbol table and stack symbol table. . 35 1 Unordered symbol table ? Unordered symbol table is built according to the order of identifiers appearing. unordered symbol table is suitable to little scale symbol table. Table is a kind of unordered symbol table. . 36 2 Ordered symbol table ? If identifiers are ordered by its first letter in dictionary, the symbol table is ordered symbol table. There are three steps to build ordered symbol table. . ? Step 1. Do the search operation in order to find its position in symbol table. ? Step 2. Move some identifiers’ name and attributes in symbol table. . ? Step 3. Insert identifiers at the position in symbol table. 37 3． Stack symbol table array or procedure identifiers often use chain table to store their special attributes. the chain table address would be as an attribute in symbol table. . Example can explain it . 38 Example A program with procedure. 39 ? The stack symbol table of the program is below. 40 ? During piling there are three operations in stack symbol table, they are insert, search and release. ? The operation of insert: ? When main program (level 0) is piled, identifiers and constants are pushed into stack by their appearing order. Address1 means stack start address and it is also the bottom address of this stack, address 4 represents top address of level 0. Similarly, start address of level 1 is 5, start address of level 2 is 8, and the top address of stack is 10. . 41 ? The operation of search: ? Searching an identifier is beginning from the order of stack top address, level 2, level 1 and level 0. If the identifier is not found until bottom address of this stack, the semantic check is not correct and should return error information. ? The operation of release: ? When retreat from a procedure, the identifiers of the procedure should be released and the top address of stack will change. For instance, procedure q releases from the stack, the top address of the stack is change from 10 to 7. 42 Type checking ? Semantic Checks include static and dynamic check. . ? Static means that it does checking during pilation, , ? Dynamic check is done during runtime. 43 ? Type checking is one of these static checking operations. Some systems also use dynamic type checking. . ? A programming language is stronglytyped, if every program its piler accepts will execute without type. . ? errors. In practice, some of type checking operations are done at runtime, so most of the programming languages are not stronglytyped. 44 ? For example: int x[100]。 on the other hand, If block I call block J, then A(I,J)=1. initial C(I)=0(I=1， … ,n), C(I)=0 refers to block I has not been allocated. We use B(I) to store the allocation of block I. The initial B(I)=0 (I=1 , … , n ) . . 69 Step 2: ? From I=1 to n, we judge if all the matrix of A(I,J)= 0(J=1， … ,n), and C(I)=0。 storage is anized as a stack, activation records are pushed into stack when activations begin, and they are popped after activations ending. . 80 ? Identifier, constant and variable are named records, name it local. Locals are bound to fresh each activation storage, When the activation ends, the storage for locals disappears when the activation record is popped . 81 ? We use register pointer to mark the top of the stack. At running time, an activation record can be allocated by incrementing by the size of the record, and deallocated by decrementing top according to the size of the record. For example, Procedure P has an activation record of size a, then the top is incremented by a, as P is released, top is d e c r e m e n t e d by a . 82 Example ? PROGRAM main (input, output)。 PROCEDURE 2 (x: integer)。 …… END 。 …… 5 (d)。 BEGIN …… 4 (f)。 …… 3 (c)。 …… END。｛ 2｝ PROCEDURE 3 (h: real)。 BEGIN …… z=z+a …… END 。 PROCEDURE 4 (y: real)。 VAR b: integer。 the results are B(4)=9 B(5)=8 C(4)=1 C(5)=1 . 74 ? Step 3： A(2,4)=1, B(2)=10 A(3,4)=1, B(3)=10 ? According to A(2,5)=1, A(3,5)=1,the value of B(2) and B(3) should be 9, however, B(2)=9 that is less than B(2)=10, the value of B(2) should not be changed according to step 3。 Technology Harbin Engineering University 50 ? There are two