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

The specific detailsof those rules determine how difficult it is to infer a type for each variable.212 CHAPTER 4 Context-Sensitive AnalysisThis, in turn, has a direct effect on the strategies that a compiler can use toimplement the language.Type-Consistent Uses and Constant Function TypesConsider a declaration-free language that requires consistent use of variablesand functions. In this case, the compiler can assign each name a general typeand narrow that type by examining each use of the name in context. Forexample, a statement such as a ← b × 3.14159 provides evidence that a andb are numbers and that a must have a type that allows it to hold a decimalnumber.

If b also appears in contexts where an integer is expected, such as anarray reference c(b), then the compiler must choose between a nonintegernumber (for b × 3.14159) and an integer (for c(b)). With either choice, itwill need a conversion for one of the uses.If functions have return types that are both known and constant—that is,a function fee always returns the same type—then the compiler can solvethe type inference problem with an iterative fixed-point algorithm operatingover a lattice of types.Type-Consistent Uses and Unknown Function TypesMap can also handle functions with multiplearguments. To do so, it takes multiple argumentlists and treats them as lists of arguments, inorder.If the type of a function varies with the function’s arguments, then theproblem of type inference becomes more complex.

This situation arises inScheme, for example. Scheme’s library procedure map takes as arguments afunction and a list. It returns the result of applying the function argument toeach element of the list. That is, if the argument function takes type α to β,then map takes a list of α to a list of β. We would write its type signature asmap: (α →β) × list of α → list of βSince map’s return type depends on the types of its arguments, a propertyknown as parametric polymorphism, the inference rules must include equations over the space of types. (With known, constant return types, functionsreturn values in the space of types.) With this addition, a simple iterativefixed-point approach to type inference is not sufficient.The classic approach to checking these more complex systems relies on unification, although clever type-system design and type representations canpermit the use of simpler or more efficient techniques.Dynamic Changes in TypeIf a variable’s type can change during execution, other strategies may berequired to discover where type changes occur and to infer appropriate types.4.5 Advanced Topics 213In principle, a compiler can rename the variables so that each definition sitecorresponds to a unique name.

It can then infer types for those names basedon the context provided by the operation that defines each name.To infer types successfully, such a system would need to handle pointsin the code where distinct definitions must merge due to the convergenceof different control-flow paths, as with φ-functions in static single assignment form (see Sections 5.4.2 and 9.3). If the language includes parametricpolymorphism, the type-inference mechanism must handle it, as well.The classic approach to implementing a language with dynamically changing types is to fall back on interpretation.

Lisp, Scheme, Smalltalk, and aplall have similar problems. The standard implementation practice for theselanguages involves interpreting the operators, tagging the data with theirtypes, and checking for type errors at runtime.In apl, the programmer can easily write a program where a × b multipliesintegers the first time it executes and multiplies multidimensional arrays offloating-point numbers the next time. This led to a body of research on checkelimination and check motion.

The best apl systems avoided most of thechecks that a naive interpreter would need.4.5.2 Changing AssociativityAs we saw in Section 3.5.4, associativity can make a difference in numericalcomputation. Similarly, it can change the way that data structures are built.We can use syntax-directed actions to build representations that reflect adifferent associativity than the grammar would naturally produce.In general, left-recursive grammars naturally produce left associativity,while right-recursive grammars naturally produce right associativity. Tosee this, consider the left-recursive and right-recursive list grammars, augmented with syntax-directed actions to build lists, shown at the top ofFigure 4.17.

The actions associated with each production build a list representation. Assume that L(x,y) is a list constructor; it can be implementedas MakeNode2 (cons,x,y). The lower part of the figure shows the result ofapplying the two translation schemes to an input consisting of five elts.The two trees are, in many ways, equivalent. An in-order traversalof both trees visits the leaf nodes in the same order. If we addparentheses to reflect the tree structure, the left-recursive tree is((((elt1 ,elt2 ),elt3 ),elt4 ),elt5 ) while the right-recursive treeis (elt1 ,(elt2 ,(elt3 ,(elt4 ,elt5 )))). The ordering produced by leftrecursion corresponds to the classic left-to-right ordering for algebraicoperators. The ordering produced by right recursion corresponds to thenotion of a list found in Lisp and Scheme.214 CHAPTER 4 Context-Sensitive AnalysisProductionActionsList → List elt| elt{$$ ← L($1,$2)}{$$ ← $1}elt5elt4elt3elt1ProductionActionsList → elt List| elt{$$ ← L($1,$2)}{$$ ← $1}elt1elt2elt3elt2elt4 elt5Left RecursionRight Recursionn FIGURE 4.17 Recursion versus Associativity.Sometimes, it is convenient to use different directions for recursion and associativity.

To build the right-recursive tree from the left-recursive grammar,we could use a constructor that adds successive elements to the end of thelist. A straightforward implementation of this idea would have to walk thelist on each reduction, making the constructor itself take O(n2 ) time, wheren is the length of the list. To avoid this overhead, the compiler can create alist header node that contains pointers to both the first and last nodes in thelist. This introduces an extra node to the list. If the system constructs manyshort lists, the overhead may be a problem.A solution that we find particularly appealing is to use a list header nodeduring construction and discard it after the list has been built. Rewriting thegrammar to use an -production makes this particularly clean.GrammarList→ |List eltQuux → ListActions{ $$ ← MakeListHeader ( ) }{ $$ ← AddToEnd($1, $2) }{ $$ ← RemoveListHeader($1) }A reduction with the -production creates the temporary list header node;with a shift-reduce parser, this reduction occurs first.

The List → List eltproduction invokes a constructor that relies on the presence of the temporary header node. When List is reduced on the right-hand side of any otherproduction, the corresponding action invokes a function that discards thetemporary header and returns the first element of the list.This approach lets the parser reverse the associativity at the cost of a smallconstant overhead in both space and time. It requires one more reduction perlist, for the -production. The revised grammar admits an empty list, while4.6 Summary and Perspective 215the original grammar did not.

To remedy this problem, RemoveListHeadercan explicitly check for the empty case and report the error.4.6 SUMMARY AND PERSPECTIVEIn Chapters 2 and 3, we saw that much of the work in a compiler’s frontend can be automated. Regular expressions work well for lexical analysis.

Context-free grammars work well for syntax analysis. In this chapter,we examined two ways to perform context-sensitive analysis: attributegrammar formalism and an ad hoc approach. For context-sensitive analysis, unlike scanning and parsing, formalism has not displaced the ad hocapproach.The formal approach, using attribute grammars, offers the hope of writing high-level specifications that produce reasonably efficient executables.While attribute grammars are not the solution to every problem in contextsensitive analysis, they have found application in several domains, rangingfrom theorem provers to program analysis. For problems in which theattribute flow is mostly local, attribute grammars work well.

Problems thatcan be formulated entirely in terms of one kind of attribute, either inheritedor synthesized, often produce clean, intuitive solutions when cast as attributegrammars. When the problem of directing the flow of attributes around thetree with copy rules comes to dominate the grammar, it is probably time tostep outside the functional paradigm of attribute grammars and introduce acentral repository for facts.The ad hoc technique, syntax-directed translation, integrates arbitrary snippets of code into the parser and lets the parser sequence the actions and passvalues between them. This approach has been widely embraced because ofits flexibility and its inclusion in most parser-generator systems. The ad hocapproach sidesteps the practical problems that arise from nonlocal attributeflow and from the need to manage attribute storage.

Values flow in one direction alongside the parser’s internal representation of its state (synthesizedvalues for bottom-up parsers and inherited for top-down parsers). Theseschemes use global data structures to pass information in the other directionand to handle nonlocal attribute flow.In practice, the compiler writer often tries to solve several problems atonce, such as building an intermediate representation, inferring types, andassigning storage locations. This tends to create significant attribute flowsin both directions, pushing the implementor toward an ad hoc solutionthat uses some central repository for facts, such as a symbol table.

Thejustification for solving many problems in one pass is usually compiletime efficiency. However, solving the problems in separate passes can216 CHAPTER 4 Context-Sensitive Analysisoften produce solutions that are easier to understand, to implement, and tomaintain.This chapter introduced the ideas behind type systems as an example of thekind of context-sensitive analysis that a compiler must perform. The studyof type theory and type-system design is a significant scholarly activity witha deep literature of its own. This chapter scratched the surface of type inference and type checking, but a deeper treatment of these issues is beyond thescope of this text. In practice, the compiler writer needs to study the type system of the source language thoroughly and to engineer the implementationof type inference and type checking carefully.

The pointers in this chapterare a start, but a realistic implementation requires more study.nCHAPTER NOTESType systems have been an integral part of programming languages sincethe original fortran compiler. While the first type systems reflected theresources of the underlying machine, deeper levels of abstraction soonappeared in type systems for languages such as Algol 68 and Simula 67.The theory of type systems has been actively studied for decades, producing a string of languages that embodied important principles. These includeRussell [45] (parametric polymorphism), clu [248] (abstract data types),Smalltalk [162] (subtyping through inheritance), and ml [265] (thoroughand complete treatment of types as first-class objects).