编译原理与实践Compiler Principle and Implementation中英双语版张菁 著 / 黄维通 Baikunth nath 审 1zhangjinghrbeu.edu.cnChapter 6 Symbol Table Manager and Type Checking Zhang Jing, Wang HaiLing College of Computer Science x, y: real;Its symbol table is Name Kind Address i int 100j int 102x real 104y real 10815zhangjinghrbeu.edu.cnExample 6.3 nThe definition of procedure is:Procedure Max；Var h , l: integer;n2 in size attribute means there are two parameters in the procedureName Kind Level Address SizeMaxHlProcedureintint011308300306216zhangjinghrbeu.edu.cn6.3 The Design of Symbol TablenThis 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. . 17zhangjinghrbeu.edu.cnnIn 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, , 18zhangjinghrbeu.edu.cnnfor 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. . 19zhangjinghrbeu.edu.cnnThere are two steps to build the symbol table:(1)Build the attribute of symbol table. (2)Design the organization 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. 20zhangjinghrbeu.edu.cn21zhangjinghrbeu.edu.cn(1)The attribute of name nThere are three ways to store identifiers name in symbol table. nthe first way is shown by Table 6.1, it means we put the name with all letters in name attribute, the name length is 10 that is a definite. nThe second way is expressed in Fig 6.1(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. 22zhangjinghrbeu.edu.cnnThe third way is denoted by Fig.6.1(b), you can only see name address in name attribute, the name length and name letters are written in its chain table. . nIf a length of identifiers 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. . 23zhangjinghrbeu.edu.cn(2)The attribute of typenThere are also three ways to represent the type attribute. . nThe first way is putting the type directly into the type attribute, shown in Table 6.1. . nThe second way is creating a 4 bites table that is shown in Fig. 6.2, the first bite in Table 6.2 is 1, the type is integer, the second bite is 1, it is real, the third bite 1 means logic type and fourth one represent character type. . nThe third way to store the type is shown in Fig 6.3, in this way, there are only three bites that can represent the four bites type by the second way. 24zhangjinghrbeu.edu.cn25zhangjinghrbeu.edu.cn26zhangjinghrbeu.edu.cn(3)Array type in symbol tablenDifferent identifier need different attribute to store its information. nfor example, an identifier of array type needs to be described its dimension, scope etc., a procedure identifier should save the number of its parameters, their type if they are recursive. We often use chain table to store some special attributes and the chain table address would be as an attribute in symbol table. . 27zhangjinghrbeu.edu.cn6.4 The Structure of Symbol Table n6.4.1. The operation of symbol table nThe operation of symbol table includes search, find, insert, deleting and update. nAs a structure definition program, there are two ways to do the operation: 28zhangjinghrbeu.edu.cn(1) If a symbol table is unordered, the operation of insert is simple.nBecause it does not need to find a definite insert position, but it should be searched in the symbol table to be sure if there is no same symbol, the running time of search is not little. . 29zhangjinghrbeu.edu.cn(2) If a symbol table is ordered, we