编译原理与实践(中英双语版)下ppt.ppt

zhangjing,1,编译原理与实践,Compiler Principle and Implementation,中英双语版,张菁 著 / 黄维通 Baikunth nath 审,Chapter 6 Symbol Table Manager and Type Checking,Zhang Jing, Wang HaiLing College of Computer Science & Technology Harbin Engineering University,zhangjing,3,some symbols must be collected and be put together into tablesSymbol Table. There are two functions in symbol table, the first one is to help check if the semantic is correct, the second one is to assist generating the code. To sum up, this chapter would introduce the functions, content, structure and operation of symbol table.,zhangjing,4,6.1 The Functions of Symbol Tables,The functions of symbol table are: （1） Store information （2）Types Checking （3） Data Address,zhangjing,5,Store information: Before store information, we firstly should divided the data into different types, then put them into the corresponded tables. Sometimes information is stored in table during lexical analysis, sometimes it is done in semantic analysis. . If the data is an identifier, it would be stored in an identifier table，else if the data is a constant, it will be put into a constant table.,zhangjing,6,Types Checking A compiler uses a symbol table to keep track of the type and binding information about names. The symbol table is searched every time by a name that is encountered in the source text. If a new name or new information about an existing name is discovered, the table is changed.,zhangjing,7,Data Address: When a data was stored, the datas address in the table was also recorded as an attribute of the table. In the period of code generation in compiler, the data address can be obtained from the symbol table and can be used directly. .,zhangjing,8,6.2 The Attribute of Symbol Table,Symbol table is created according to symbols name, so the keyword of the symbol table is symbols name. Except name attribute, there are also six attributes of a symbol in symbol table using for semantic checking. .,zhangjing,9,The six attributes of a symbol as follow:,Attribute of kind Attribute of dimension or size Attribute of parameter Attribute of address Attribute of level in program Attribute of line position in source program,zhangjing,10,Attribute of kind Kind can describe the characteristics of a symbol. Every symbol has its own type, such as constant, variable and procedure. . Attribute of dimension or size If an identifier is a name of an array, then we should store the dimension and boundary of identifier value as an attribute of it. .,zhangjing,11,Attribute of parameter If an identifier is a name of a procedure, the parameters of the procedure should be recorded as an attribute. . Attribute of address In source program, an identifier or a constant are often related with a unit address to accomplish some operation. So the addresses of them are put in symbol table as an attribute. .,zhangjing,12,Attribute of level in program Symbol in program or subprogram, the level of its position in program should be written as an attribute in symbol table. In some source languages, identifiers can have same name in different level of program, so attribute of level in program could help recognize them. . Attribute of line position in source program Sometimes the line position of symbol in source program is needed to be stored as an attribute in symbol table in order to obtain the correct semantic checking. .,zhangjing,13,Attribute of constant value If the symbol is a constant, then the value of it should been stored as a value attribute in symbol table. . Attributes above 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.,zhangjing,14,Example 6.1,The definition of constants is: Const pi=3.14 r=10 Its symbol table is: NameKindValuepireal3.14rint10,Name,pi,r,Kind,real,int,Value,3.14,10,zhangjing,15,Example 6.2,The definition of variables is: Var i, j: integer; x, y: real; Its symbol table is,zhangjing,16,Example 6.3,The definition of procedure is: Procedure Max；Var h , l: integer; 2 in size attribute means there are two parameters in the procedure,zhangjing,17,6.3 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. .,zhangjing,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, ,zhangjing,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. .,zhangjing,20,There 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.,zhangjing,21,zhangjing,22,(1)The attribute of name There are three ways to store identifiers name in symbol table. the 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. The 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.,zhangjing,23,The 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. . If 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. .,zhangjing,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 6.1. . The 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. . The 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.,zhangjing,25,zhangjing,26,zhangjing,27,(3)Array type in symbol table Different identifier need different attribute to store its information. for 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. .,zhangjing,28,6.4 The Structure of Symbol Table,6.4.1. The operation of symbol table The operation of symbol table includes search, find, insert, deleting and update. As a structure definition program, there are two ways to do the operation:,zhangjing,29,(1) If a symbol table is unordered, the operation of insert is simple. Because 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. .,zhangjing,30,(2) If a symbol table is ordered, we should first search the insert position in symbol table, secondly to do the insert operation, so it needs double time to do the insert operation than do it in first way. .,zhangjing,31,As a no structure definition program, any symbol is considered to be the first time to insert and it must be searched by all of symbol table to make sure if it is really used firstly. Only when there is no same symbol in symbol table, the insert operation could be done. .,zhangjing,32,As a subprogram, it is allowed same identifier in different subprogram, but there is no meaning if we dont define which subprogram the identifier belongs to. It needs two more operation except insert and search operations: create chain symbol table in subprogram entrance and deleting chain symbol table in the subprogram exit. .,zhangjing,33,(1) In the entrance of subprogram, we should build a chain symbol table to store some identifier information for: . for example, create chain symbol table 1 for subprogram 1, build chain symbol table 2 for subprogram 2, set up chain symbol table n for subprogram n, and so 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 n-1untill chain table 1 (2) In subprogram exit, the chain symbol table should be deleted to release the space. .,zhangjing,34,6.4.2. 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. .,zhangjing,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 6.1 is a kind of unordered symbol table. .,zhangjing,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.,zhangjing,37,3Stack 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 6.2 can explain it .,zhangjing,38,Example 6.4 A program with procedure.,zhangjing,39,The stack symbol table of the program is below.,zhangjing,40,During compiling there are three operations in stack symbol table, they are insert, search and release. The operation of insert: When main program (level 0) is compiled, 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. .,zhangjing,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.,zhangjing,42,6.5 Type checking,Semantic Checks include static and dynamic check. . Static means that it does checking during compilation, , Dynamic check is done during run-time.,zhangjing,43,Type checking is one of these static checking operations. Some systems also use dynamic type checking. . A programming language is strongly-typed, if every program its compiler accepts will execute without type. . errors. In practice, some of type checking operations are done at run-time, so most of the programming languages are not strongly-typed.,zhangjing,44,For example: int x100; xi most of the compilers cannot guarantee that i will be between 0 and 99. .,zhangjing,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(010,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 .,zhangjing,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 DR where D are R type expressions. For example: intint represents the type of a function that takes an int value as parameter, and its return type is also int. .,zhangjing,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.,zhangjing,48,Chapter 7 Storage Organization and Register Allocation,Zhang Jing, Wang HaiLing College of Computer Science & Technology Harbin Engineering University,zhangjing,50,There are two strategies that are often used: static allocation and dynamic allocation. Static allocation refer to that variables and constants are bound to stored when program is compiled, in addition, the storage of variables and constants would not be changed at run time. .,zhangjing,51,The storage of FORTRAN is static allocation. Dynamic allocation means that allocation is done at run time, namely, data structures can be created dynamically and sometime it is a kind of symbol table or subprogram. PASCAL program storage is a kind of dynamic allocation. .,zhangjing,52,static allocation and dynamic allocation are often used . Static allocation refer to that variables and constants are bound to stored when program is compiled, in addition, the storage of variables and constants would not be changed at run time. The storage of FORTRAN is static allocation. . Dynamic allocation means that allocation is done at run time, namely, data structures can be created dynamically and sometime it is a kind of symbol table or subprogram. PASCAL program storage is a kind of dynamic allocation. .,zhangjing,53,7.1 Static Storage Allocation,（1）The size of a data objects and constraints on its position in memory must be known before compiling. . （2）Recursive procedures are restricted, because all activations of procedure use the same bindings for local names. .,zhangjing,54,Compiler determines the amount of storage to set aside by the type of data. A data type, such as a character, integer or real, can usually be stored in some bytes, .,for example, integer is 2 bites, real is 4 bites. Storage for a combined type .,zhangjing,55,The length of data above is definite and their data are saved as fields in symbol table. Variable-length data is kept in other place outside this field。 such as a procedure data, its field in symbol table is only kept its address or use a pointer to label its memory location, the address or pointer is called relative address of it.,zhangjing,56,FORTUNE,A FORTUNE program consists of a main program, subroutines, and functions.,zhangjing,57,Each occurrence of name has a scope that is consisted in one procedure only. We need only preserve the names of procedures and common blocks that are external to the subroutines that were just processed. These names may not truly be external to the entire program being compiled, but must be preserved until the entire collection of procedures in processing. .,zhangjing,58,In FORTUNE, there are data area for each procedure and area for variables named COMMON block. The symbol table must record each names data area in which it belongs to and its offset in that data area, that is, its position relative to the beginning of the area. Each block is declared by COMMON block. .,The definition of declaration is, COMMON/BLOCK1/NAME1, NAME2,zhangjing,59,The storage procedure is as the following： (1) In the table for COMMON block, create a record for BLOCK1, if one does not already exist. . (2) In the symbol-table entries for NAME1 and NAME2, set a pointer to the symbol- table entry for BLOCK1, indicating that they are in COMMON and are members of BLOCK1.,zhangjing,60,(3) If the record has just now been created for BLOCK1, set a pointer to record the symbol-table entry for NAME1, indicating the first name in the COMMON block. . Then, link the symbol-table entry for NAME1 to that for NAME2, using a field of the symbol table reserved for link members of th