Cooper_Engineering_a_Compiler(Second Edition) (Rice), страница 66

Inside level 2b, a referenceto b again refers to the level 1 parameter. In a similar way, the declarationsstatic int w;int x;/* level 0 */void example(int a, int b) {int c;/* level 1 */{int b, z;.../* level 2a */}{int a, x;/* level 2b */...{int c, x; /* level 3 */b = a + b + c + w;}}}n FIGURE 5.10 Simple Lexical Scoping Example in C.LevelNames012a2b3w, x, examplea, b, cb, za, xc, x258 CHAPTER 5 Intermediate Representationsof a and × in level 2b hide their earlier declarations (at level 1 and level 0,respectively).This context creates the naming environment in which the assignment statement executes.

Subscripting names to show their level, we find that theassignment refers tob1 = a2b + b1 + c3 + w0Notice that the assignment cannot use the names declared in level 2a becausethat block closes, along with its scope, before level 2b opens.To compile a program that contains nested scopes, the compiler must mapeach variable reference to its specific declaration. This process, calledname resolution, maps each reference to the lexical level at which it isdeclared. The mechanism that compilers use to accomplish this name resolution is a lexically scoped symbol table. The remainder of this sectiondescribes the design and implementation of lexically scoped symbol tables.The corresponding runtime mechanisms, which translate the lexical level ofa reference to an address, are described in Section 6.4.3. Scoped symboltables also have direct application in code optimization.

For example, thesuperlocal value-numbering algorithm presented in Section 8.5.1 relies on ascoped hash table for efficiency.The ConceptTo manage nested scopes, the parser must change, slightly, its approach tosymbol-table management. Each time the parser enters a new lexical scope,it can create a new symbol table for that scope. This scheme creates a sheafof tables, linked together in an order that corresponds to the lexical nestinglevels. As it encounters declarations in the scope, it enters the informationinto the current table. Insert operates on the current symbol table. Whenit encounters a variable reference, LookUp must first check the table for thecurrent scope. If the current table does not hold a declaration for the name, itchecks the table for the surrounding scope.

By working its way through thesymbol tables for successively lower-numbered lexical levels, it either findsthe most recent declaration for the name, or fails in the outermost scope,indicating that the variable has no declaration visible in the current scope.Figure 5.11 shows the symbol table built in this fashion for our example program, at the point where the parser has reached the assignment statement.When the compiler invokes the modified LookUp function for the name b,it will fail in level 3, fail in level 2, and find the name in level 1.

Thiscorresponds exactly to our understanding of the program—the most recent5.5 Symbol Tables 259Level 3CurrentLevelLevel 2bLevel 1Level 0b,...x,...x,...x,...c,...c,...a,...a,...exa ...w,...n FIGURE 5.11 Simple "Sheaf-of-Tables" Implementation.declaration for b is as a parameter to example, at level 1. Since the first blockat level 2, block 2a, has already closed, its symbol table is not on the searchchain.

The level where the symbol is found, 1 in this case, forms the firstpart of an address for b. If the symbol-table record includes a storage offset for each variable, then the pair hlevel, offseti specifies where to find b inmemory—at offset from the start of storage for the level scope. We call thispair b’s static coordinate.The DetailsTo handle this scheme, two additional calls are required.

The compiler needsa call that initializes a new symbol table for a scope and one that finalizesthe table for a scope.1. InitializeScope() increments the current level and creates a newsymbol table for that level. It links the new table to the enclosing level’stable and updates the current level pointer used by LookUp andInsert.2.

FinalizeScope() changes the current-level pointer so that it points tothe table for the scope surrounding the current level and then decrementsthe current level. If the compiler needs to preserve the level-by-leveltables for later use, FinalizeScope can either leave the table intact inmemory or write the table to external media and reclaim its space.To account for lexical scoping, the parser calls InitializeScope each timeit enters a new lexical scope and FinalizeScope each time it exits a lexicalStatic coordinatea pair, < l,o> , that records address informationabout some variable xl specifies the lexical level where x is declared; ospecifies the offset within the data area for thatlevel.260 CHAPTER 5 Intermediate Representationsscope.

This scheme produces the following sequence of calls for the programin Figure 5.10:1. InitializeScope2. Insert(w)3. Insert(×)4. Insert(example)5. InitializeScope6. Insert(a)7. Insert(b)8. Insert(c)9. InitializeScope10. Insert(b)11. Insert(z)12. FinalizeScope13. InitializeScope14. Insert(a)15. Insert(×)16. InitializeScope17. Insert(c)18. Insert(×)19.

LookUp(b)20. LookUp(a)21. LookUp(b)22. LookUp(c)23. LookUp(w)24. FinalizeScope25. FinalizeScope26. FinalizeScope27. FinalizeScopeAs it enters each scope, the compiler calls InitializeScope. It adds eachname to the table using Insert. When it leaves a given scope, it callsFinalizeScope to discard the declarations for that scope. For the assignment statement, it looks up each of the names, as encountered. (The orderof the LookUp calls will vary, depending on how the assignment statement istraversed.)If FinalizeScope retains the symbol tables for finalized levels in memory,the net result of these calls will be the symbol table shown in Figure 5.12.The current level pointer is set to a null value.

The tables for all levels areleft in memory and linked together to reflect lexical nesting. The compilercan provide subsequent passes of the compiler with access to the relevantsymbol-table information by storing a pointer to the appropriate table in theLevel 3Level 1Level 2bb,...Level 2aCurrentLevelx,...x,...x,...b,...c,...c,...a,...n FIGURE 5.12 Final Table for the Example.Level 0z,...a,...exa ...w,...5.5 Symbol Tables 261ir at the start of each new level. Alternatively, identifiers in the ir can pointdirectly to their symbol-table entries.5.5.4 The Many Uses for Symbol TablesThe preceding discussion focused on a central symbol table, albeit one thatmight be composed of several tables.

In reality, compilers build multiplesymbol tables that they use for different purposes.Structure TableThe textual strings used to name fields in a structure or record exist in a distinct name space from the variables and procedures. The name size mightoccur in several different structures in a single program. In many programming languages, such as c or Ada, using size as a field in a structure doesnot preclude its use as a variable or function name.For each field in a structure, the compiler needs to record its type, its size,and its offset inside the record.

It gleans this information from the declarations, using the same mechanisms that it uses for processing variabledeclarations. It must also determine the overall size for the structure, usuallycomputed as the sum of the field sizes, plus any overhead space required bythe runtime system.There are several approaches for managing the name space of field names:1.

Separate Tables The compiler can maintain a separate symbol table foreach record definition. This is the cleanest idea, conceptually. If theoverhead for using multiple tables is small, as in most object-orientedimplementations, then using a separate table and associating it with thesymbol table entry for the structure’s name makes sense.2. Selector Table The compiler can maintain a separate table for fieldnames. To avoid clashes between fields with identical names in differentstructures, it must use qualified names—concatenate either the name ofthe structure or something that uniquely maps to the structure, such asthe structure name’s symbol-table index, to the field name.

For thisapproach, the compiler must somehow link together the individual fieldsassociated with each structure.3. Unified Table The compiler can store field names in its principalsymbol table by using qualified names. This decreases the number oftables, but it means that the principal symbol table must support all ofthe fields required for variables and functions, as well as all of the fieldsneeded for each field-selector in a structure.