K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 55
Текст из файла (страница 55)
As it reduces the various productions in the declaration syntax, itcan adjust the values in the structure accordingly.nnnOn a reduction of auto to StorageClass, it can check that the field forstorage class has not already been set, and then set it to auto. Similaractions for static, extern, and register complete the handling ofthose properties of a name.The type specifier productions will set other fields in the structure. Theymust include checks to insure that only valid combinations occur.Reduction from ident to DirectDeclarator should trigger an action thatcreates a new symbol-table entry for the name and copies the currentsettings from the properties structure into that entry.210 CHAPTER 4 Context-Sensitive AnalysisnReducing by the productionInitDeclaratorList → InitDeclaratorList , InitDeclaratorcan reset the properties fields that relate to the specific name, includingthose set by the Pointer, Initializer, and DirectDeclarator productions.By coordinating a series of actions across the productions in the declaration syntax, the compiler writer can arrange to have the properties structurecontain the appropriate settings each time a name is processed.When the parser finishes building the DeclarationList, it has built a symboltable entry for each variable declared in the current scope.
At that point, itmay need to perform some housekeeping chores, such as assigning storagelocations to declared variables. This can be done in an action for the production that reduces the DeclarationList. If necessary, that production canbe split to create a convenient point for the action.SECTION REVIEWThe introduction of parser generators created the need for amechanism to tie context-sensitive actions to the parse-timebehavior of the compiler. Ad hoc syntax-directed translation, asdescribed in this section, evolved to fill that need.
It uses some of thesame intuitions as the attribute-grammar approach. It allows only oneevaluation order. It has a limited name space for use in the code snippetsthat form semantic actions.Despite these limitations, the power of allowing arbitrary code insemantic actions, coupled with support for this technique in widely usedparser generators, has led to widespread use of ad hoc syntax-directedtranslation. It works well in conjunction with global data structures, suchas a symbol table, to perform nonlocal communication.
It efficiently andeffectively solves a class of problems that arise in building a compiler’sfront end.Calc → ExprExpr → Expr + Term| Expr − Term| TermTerm → Term × num| Term ÷ num| numFour function calculatorHint: Recall that an attribute grammar does notspecify order of evaluation.Review Questions1. Consider the problem of adding ad hoc actions to an LL(1) parser generator. How would you modify the LL(1) skeleton parser to includeuser-defined actions for each production?2. In review question 1 for Section 4.3, you built an attribute-grammarframework to compute values in the “four function calculator” grammar.
Now, consider implementing a calculator widget for the desktopon your personal computer. Contrast the utility of your attributegrammar and your ad hoc syntax-directed translation scheme for thecalculator implementation.4.5 Advanced Topics 2114.5 ADVANCED TOPICSThis chapter has introduced the basic notions of type theory and used themas one motivating example for both attribute-grammar frameworks and forad hoc syntax-directed translation.
A deeper treatment of type theory and itsapplications could easily fill an entire volume.The first subsection lays out some language design issues that affect theway that a compiler must perform type inference and type checking. Thesecond subsection looks at a problem that arises in practice: rearranginga computation during the process of building the intermediate representationfor it.4.5.1 Harder Problems in Type InferenceStrongly typed, statically checked languages can help the programmer produce valid programs by detecting large classes of erroneous programs. Thesame features that expose errors can improve the compiler’s ability to generate efficient code for a program by eliminating runtime checks and exposingwhere the compiler can specialize special case code for some construct toeliminate cases that cannot occur at runtime. These facts account, in part,for the growing role of type systems in modern programming languages.Our examples, however, have made assumptions that do not hold in allprogramming languages.
For example, we assumed that variables and procedures are declared—the programmer writes down a concise and bindingspecification for each name. Varying these assumptions can radically changethe nature of both the type-checking problem and the strategies that thecompiler can use to implement the language.Some programming languages either omit declarations or treat them asoptional information. Scheme programs lack declarations for variables.Smalltalk programs declare classes, but an object’s class is determined onlywhen the program instantiates that object. Languages that support separatecompilation—compiling procedures independently and combining them atlink time to form a program—may not require declarations for independentlycompiled procedures.In the absence of declarations, type checking is harder because the compilermust rely on contextual clues to determine the appropriate type for eachname.
For example, if i is used as an index for some array a, that might constrain i to have a numeric type. The language might allow only integersubscripts; alternatively, it might allow any type that can be converted toan integer.Typing rules are specified by the language definition. 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
