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

Of the three options, this isprobably the least attractive.262 CHAPTER 5 Intermediate RepresentationsThe separate table approach has the advantage that any scoping issues—such as reclaiming the symbol table associated with a structure—fit naturallyinto the scope management framework for the principal symbol table. Whenthe structure can be seen, its internal symbol table is accessible through thecorresponding structure record.In the latter two schemes, the compiler writer will need to pay careful attention to scoping issues. For example, if the current scope declares a structurefee and an enclosing scope already has defined fee, then the scoping mechanism must correctly map fee to the structure (and its corresponding fieldentries). This may also introduce complications into the creation of qualifiednames.

If the code contains two definitions of fee, each with a field namedsize, then fee.size is not a unique key for either field entry. This problem can be solved by associating a unique integer, generated from a globalcounter, with each structure name.Linked Tables for Name Resolution in an Object-OrientedLanguageIn an object-oriented language, the name scoping rules are governed by thestructure of the data as much as by the structure of the code. This createsa more complicated set of rules; it also leads to a more complicated set ofsymbol tables.

Java, for example, needs tables for the code being compiled,for any external classes that are both known and referenced in the code, andfor the inheritance hierarchy above the class containing the code.A simple implementation attaches a symbol table to each class, with twonesting hierarchies: one for lexical scoping inside individual methods andthe other following the inheritance hierarchy for each class. Since a single class can serve as superclass to several subclasses, this latter hierarchyis more complicated than the simple sheaf-of-tables drawing suggests.However, it is easily managed.To resolve a name fee when compiling a method m in class C, the compilerfirst consults the lexically scoped symbol table for m. If it does not find fee inthis table, it then searches the scopes for the various classes in the inheritancehierarchy, starting with C and proceeding up the chain of superclasses fromC. If this lookup fails to find fee, the search then checks the global symboltable for a class or symbol table of that name.

The global table must containinformation on both the current package and any packages that have beenused.Thus, the compiler needs a lexically scoped table for each method, builtwhile it compiles the methods. It needs a symbol table for each class, withlinks upward through the inheritance hierarchy. It needs links to the other5.5 Symbol Tables 263classes in its package and to a symbol table for package-level variables. Itneeds access to the symbol tables for each used class.

The lookup processis more complex, because it must follow these links in the correct orderand examine only names that are visible. However, the basic mechanismsrequired to implement and manipulate the tables are already familiar.5.5.5 Other Uses for Symbol Table TechnologyThe basic ideas that underlie symbol table implementation have widespreadapplication, both inside a compiler and in other domains. Hash tables areused to implement sparse data structures; for example, a sparse array canbe implemented by constructing a hash key from the indices and only storing non-zero values. Runtime systems for lisp-like languages have reducedtheir storage requirements by having the cons operator hash its arguments—effectively enforcing a rule that textually identical objects share a singleinstance in memory.

Pure functions, those that always return the same values on the same input parameters, can use a hash table to produce animplementation that behaves as a memo function.SECTION REVIEWSeveral tasks inside a compiler require efficient mappings fromnoninteger data into a compact set of integers. Symbol table technology provides an efficient and effective way to implement many of thesemappings. The classic examples map a textual string, such as the nameof a variable or temporary, into an integer. Key considerations that arisein symbol table implementation include scalability, space efficiency, andcost of creation, insertion, deletion, and destruction, both for individualentries and for new scopes.This section presented a simple and intuitive approach to implementinga symbol table: linked sheafs of hash tables.

(Section B.4, in Appendix B,presents several alternative implementation schemes.) In practice, thissimple scheme works well in many applications inside a compiler, ranging from the parser’s symbol table to tracking information for superlocalvalue numbering (see Section 8.5.1).Review Questions1. Using the "sheaf-of-tables" scheme, what is the complexity of insertinga new name into the table at the current scope? What is the complexity of looking up a name declared at an arbitrary scope? Whatis, in your experience, the maximum lexical-scope nesting level forprograms that you write?Memo functiona function that stores results in a hash tableunder a key built from its arguments and uses thehash table to avoid recomputation of prior results264 CHAPTER 5 Intermediate Representations2. When the compiler initializes a scope, it may need to provide an initialsymbol table size. How might you estimate that initial symbol tablesize in the parser? How might you estimate it in subsequent passes ofthe compiler?5.6 SUMMARY AND PERSPECTIVEThe choice of an intermediate representation has a major impact on thedesign, implementation, speed, and effectiveness of a compiler.

None ofthe intermediate forms described in this chapter are, definitively, the rightanswer for all compilers or all tasks in a given compiler. The designer mustconsider the overall goals of a compiler project when selecting an intermediate form, designing its implementation, and adding auxiliary data structuressuch as symbol and label tables.Contemporary compiler systems use all manner of intermediate representations, ranging from parse trees and abstract syntax trees (often used insource-to-source systems) through lower-than-machine-level linear codes(used, for example, in the Gnu compiler systems). Many compilers usemultiple irs—building a second or third one to perform a particular analysisor transformation, then modifying the original, and definitive, one to reflectthe result.nCHAPTER NOTESThe literature on intermediate representations and experience with them issparse. This is somewhat surprising because of the major impact that decisions about irs have on the structure and behavior of a compiler.

The classicir forms have been described in a number of textbooks [7, 33, 147, 171].Newer forms like ssa [50, 110, 270] are described in the literature on analysis and optimization. Muchnick provides a modern treatment of the subjectand highlights the use of multiple levels of ir in a single compiler [270].The idea of using a hash function to recognize textually identical operationsdates back to Ershov [139].

Its specific application in Lisp systems seems toappear in the early 1970s [124, 164]; by 1980, it was common enough thatMcCarthy mentions it without citation [259].Cai and Paige introduced multiset discrimination as an alternative to hashing [65]. Their intent was to provide an efficient lookup mechanism withguaranteed constant time behavior.

Note that closure-free regular expressions, described in Section 2.6.3, can be applied to achieve a similar effect.The work on shrinking the size of Rn ’s ast was done by David Schwartzand Scott Warren.Exercises 265In practice, the design and implementation of an ir has an inordinately largeimpact on the eventual characteristics of the completed compiler. Large,complex irs seem to shape systems in their own image.

For example, thelarge asts used in early 1980s programming environments like Rn limitedthe size of programs that could be analyzed. The rtl form used in gcc hasa low level of abstraction. Accordingly, the compiler does a fine job of managing details such as those needed for code generation, but has few, if any,transformations that require source-like knowledge, such as loop blockingto improve memory hierarchy behavior.nEXERCISES1. A parse tree contains much more information than an abstract syntaxtree.a.

In what circumstances might you need information that is found inthe parse tree but not the abstract syntax tree?b. What is the relationship between the size of the input program andits parse tree? Its abstract syntax tree?c. Propose an algorithm to recover a program’s parse tree from itsabstract syntax tree.Section 5.22. Write an algorithm to convert an expression tree into a dag.3. Show how the following code fragmentif (c[i] 6= 0)Section 5.3then a[i] ← b[i] ÷ c[i];else a[i] ← b[i];might be represented in an abstract syntax tree, in a control-flowgraph, and in quadruples. Discuss the advantages of eachrepresentation. For what applications would one representation bepreferable to the others?4. Examine the code fragment shown in Figure 5.13.