編譯原理與實(shí)踐（中英雙語版）下ppt課件

1、1編譯原理與實(shí)際編譯原理與實(shí)際 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 U3nsome symbols mus

2、t 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

3、symbol table. 46.1 The Functions of Symbol Tables nThe functions of symbol table are:n 1 Store informationn 2Types Checkingn 3 Data A5nStore information: n Before store information, we firstly should divided the data into different types, then put them into

4、the corresponded tables. Sometimes information is stored in table during lexical analysis, sometimes it is done in semantic analysis. . n 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. 6n

5、Types CheckingnA 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. zhangjin

6、7nData Address:nWhen 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. . 86.2 The Attribute of Sy

7、mbol Table nSymbol 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. . 9The six attributes of a symbol as follow:nAttribute of

8、 kindnAttribute of dimension or sizenAttribute of parameternAttribute of addressnAttribute of level in programnAttribute of line position in source 10nAttribute of kindn Kind can describe the characteristics of a symbol. Every symbol has its own type, such as constant, varia

9、ble and procedure. .nAttribute of dimension or sizen 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. . 11nAttribute of parameter n If an identifier is a name of a procedure, the parameters of the pro

10、cedure should be recorded as an attribute. . nAttribute of addressn 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. .n 12nAttribute of level in progr

11、amn 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. .nAttribute of line positio

12、n in source programn 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. .13nAttribute of constant valuen If the symbol is a constant, then the value of it should been store

13、d as a value attribute in symbol table. . n 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. 14Exampl

14、e 6.1nThe definition of constants is:n Const pi=3.14n r=10n Its symbol table is: n NameKindValuepireal3.14rint10 Name pi r Kind real int Value 3.14 1015Example 6.2 nThe definition of variables is:n Var i, j: integer;n x, y: real;n Its symbol table is Name Kind Address i int 100 j i

15、nt 102 x real 104 y real 10816Example 6.3 nThe definition of procedure is:n Procedure Max；Var h , l: integer;n2 in size attribute means there are two parameters in the procedure Name Kind Level Address Size Max H lProcedure int int 0 1 1 308 300 306 2176.3 The Des

16、ign 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 t a b l e . . 18nIn order to obtain high running efficient and save the storage

17、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, , 19nfor example, target machine performanc

18、e, 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

19、all those elements into account in order to build a reasonable symbol table. . 20nThere are two steps to build the symbol table:n (1)Build the attribute of symbol table. n (2)Design the organization of symbol table. n The first one we will discuss in this section, the second one wo

20、uld 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. 22(1)The attribute of name There are three ways to store identifiers name in symbol table.

21、 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 addre

22、ss of connect table. 23nThe 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 t a b l e . . nIf a length of identifiers name is 2 bites, using symbol table in first way to store it needs 8

23、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 typeThere are also three ways to represent the type attribute. . The first way is p

24、utting 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

25、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. 25 26 27(3)Array type in symbol tableDifferent identifier need different attribute to s

26、tore 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 wou

27、ld be as an attribute in symbol table. . 286.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: zhangjin

28、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. . 30(2) If a

29、 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 w a y . . 31nAs a no structure definition program, any symbol is considered to be the fi

30、rst 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. . 32nAs a subprogram, it is allowed same identifier in different subprogram, but there

31、 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 e x i t . . 33n(1) In the entrance of sub

32、program, we should build a chain symbol table to store some identifier information for: . nfor 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 sh

33、ould search it begin from chain table n, if there is no the symbol in it, search it in chain table n-1untill chain table 1n (2) In subprogram exit, the chain symbol table should be deleted to release the space. .346.4.2. The structure of symbol tablenWhich kind of symbol structure

34、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: unord

35、ered symbol table, ordered symbol table and stack symbol table. . 351 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 tab

36、le. . 362 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 s

37、ome identifiers name and attributes in symbol table. . Step 3. Insert identifiers at the position in symbol table. 373Stack 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 symbo

38、l table. . Example 6.2 can explain it . 38Example 6.4 A program with procedure. 39nThe stack symbol table of the program is below. 40nDuring compiling there are three operations in stack symbol table, they are insert, search and release.nThe oper

39、ation of insert: nWhen 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

40、 5, start address of level 2 is 8, and the top address of stack is 10. .41nThe operation of search:nSearching 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 semanti

41、c check is not correct and should return error information. nThe operation of release:nWhen 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 chang

42、e from 10 to 7.426.5 Type checking nSemantic Checks include static and dynamic c h e c k . . nStatic means that it does checking during c o m p i l a t i o n , , nDynamic check is done during run-time.n 43nType checking is one of these static checking operations.

43、Some systems also use dynamic type checking. . nA programming language is strongly-typed, if every program its compiler accepts will execute without type. . nerrors. In practice, some of type checking operations are done at run-time, so most of the programming languages are not strongly-typed.zhangj

44、44nFor example: int x100; xi most of the compilers 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 express

45、ion, 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 .46npointers: If T is a type expression, then pointer(

46、T) is a type expression. For example: pointer(int). .nfunctions: 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

47、type of a function that takes an int value as parameter, and its return type is also i n t . . 472 Type Checking nType checking consists of Expressions type checking, statements type checking, functions type checking and structural expressions type checking. They are introduced by

48、the next tables and their algorithms are in the right of the 48Chapter 7 Storage Organization and Register Allocation Zhang Jing, Wang HaiLing College of Computer Science & Technology Harbin Engineering U50nThere are two strategies that are ofte

49、n 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. . 51nThe storage of FORTRAN is static alloca

50、tion. 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. . 52nstatic allocation and dynamic allocation are

51、often used . nStatic 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. . nDynamic allocation means that allocation is done a

52、t 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. . 537.1 Static Storage Allocation n1The size of a data objects and constraints on its position in memory m

53、ust be known before compiling. .n2Recursive procedures are restricted, because all activations of procedure use t h e s a m e b i n d i n g s f o r l o c a l n a m e s . . 54nCompiler determines the amount of storage to set aside by the type of data. A data type, such as a characte

54、r, integer or real, can usually be stored in some bytes, .nfor example, integer is 2 bites, real is 4 bites. Storage for a combined type . 55nThe length of data above is definite and their data are saved as fields in symbol table. nVariable-length data is kept in other place outsid

55、e this field。 nsuch 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. 56FORTUNEnA FORTUNE program consists of a main program, subroutines, and functions. zh

56、57nEach 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, b

57、ut must be preserved until the entire collection of procedures in processing. . 58nIn 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

58、, that is, its position relative to the beginning of the area. Each block is declared by COMMON block. . nThe definition of declaration is, nCOMMON/BLOCK1/NAME1, NAME2 59nThe storage procedure is as the following：n(1) In the table for COMMON block, create a record for BLOCK1, if on

59、e does not already exist. .n(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. 60n(3) If the record has just now been created for BLOCK1, set a pointer to record the

60、 symbol-table entry for NAME1, indicating nthe first name in the COMMON block. . nThen, link the symbol-table entry for NAME1 to that for NAME2, using a field of the symbol table reserved for link members of the same COMMON block. . nFinally, set a pointer in the record for BLOCK1 to the symbol-table entry