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

Address takes a variable name as its argument. It returns the number ofa register that contains the value specified by name. If necessary, itgenerates code to load that value.2. Emit handles the details of creating a concrete representation for thevarious iloc operations. It might format and print them to a file.Alternatively, it might build an internal representation for later use.3. NextRegister returns a new register number.

A simple implementationcould increment a global counter.4. Value takes a number as its argument and returns a register number. Itensures that the register contains the number passed as its argument. Ifnecessary, it generates code to move that number into the register.Figure 4.15 shows the syntax-directed framework for this problem. Theactions communicate by passing register names in the parsing stack.

Theactions pass these names to Emit as needed, to create the operations thatimplement the input expression.4.4 Ad Hoc Syntax-Directed Translation 207ProductionExprSyntax-Directed Actions→ Expr + Term{ $$ ← NextRegister;Emit(add, $1, $3, $$) }| Expr − Term{ $$ ← NextRegister;Emit(sub, $1, $3, $$) }| Term{ $$ ← $1 }Term → Term × Factor{ $$ ← NextRegister;Emit(mult, $1, $3, $$) }| Term ÷ Factor{ $$ ← NextRegister;Emit(div, $1, $3,$$) }| Factor{ $$ ← $1 }Factor → ( Expr ){ $$ ← $2 }| num{ $$ ← Value(scanned text); }| name{ $$ ← Address(scanned text); }n FIGURE 4.15 Emitting ILOC for Expressions.Processing DeclarationsOf course, the compiler writer can use syntax-directed actions to fill in muchof the information that resides in the symbol table. For example, the grammar fragment shown in Figure 4.16 describes a limited subset of the syntaxfor declaring variables in c.

(It omits typedefs, structs, unions, the typequalifiers const, restrict, and volatile, as well as the details of theinitialization syntax. It also leaves several nonterminals unelaborated.) Consider the actions required to build symbol-table entries for each declaredvariable. Each Declaration begins with a set of one or more qualifiers thatspecify the variable’s type and storage class. These qualifiers are followedby a list of one or more variable names; each variable name can includespecifications about indirection (one or more occurrences of *), about arraydimensions, and about initial values for the variable.For example, the StorageClass production allows the programmer to specifyinformation about the lifetime of a variable’s value; an auto variable has alifetime that matches the lifetime of the block that declares it, while staticvariables have lifetimes that span the program’s entire execution.

The register specifier suggests to the compiler that the value should be kept in alocation that can be accessed quickly—historically, a hardware register. Theextern specifier tells the compiler that declarations of the same name indifferent compilation units are to be linked as a single object.208 CHAPTER 4 Context-Sensitive AnalysisDeclarationList→|DeclarationSpecifierList→→Specifier→StorageClass→|||||TypeSpecifier→||||||||InitDeclaratorList→|InitDeclarator→Declarator→Pointer→|||DirectDeclarator→||||||DeclarationList DeclarationDeclarationSpecifierList InitDeclaratorList ;Specifier SpecifierListSpecifierStorageClassTypeSpecifierautostaticexternregistervoidcharshortintlongsignedunsignedfloatdoubleInitDeclaratorList , InitDeclaratorInitDeclaratorDeclarator = InitializerDeclaratorPointer DirectDeclaratorDirectDeclarator** Pointerident( Declarator )DirectDeclarator ( )DirectDeclarator ( ParameterTypeList )DirectDeclarator ( IdentifierList )DirectDeclarator [ ]DirectDeclarator [ ConstantExpr ]n FIGURE 4.16 A Subset of C’s Declaration Syntax.While such restrictions can be encoded in thegrammar, the standard writers chose to leave itfor semantic elaboration to check, rather thancomplicate an already large grammar.The compiler must ensure that each declared name has at most one storageclass attribute.

The grammar places the specifiers before a list of one or morenames. The compiler can record the specifiers as it processes them and applythem to the names when it later encounters them. The grammar admits anarbitrary number of StorageClass and TypeSpecifier keywords; the standardlimits the ways that the actual keywords can be combined. For example,it allows only one StorageClass per declaration. The compiler must enforce4.4 Ad Hoc Syntax-Directed Translation 209WHAT ABOUT CONTEXT-SENSITIVE GRAMMARS?Given the progression of ideas from the previous chapters, it might seemnatural to consider the use of context-sensitive languages to performcontext-sensitive checks, such as type inference.

After all, we used regular languages to perform lexical analysis and context-free languages toperform syntax analysis. A natural progression might suggest the study ofcontext-sensitive languages and their grammars. Context-sensitive grammars can express a larger family of languages than can context-freegrammars.However, context-sensitive grammars are not the right answer for two distinct reasons. First, the problem of parsing a context-sensitive grammaris P-Space complete. Thus, a compiler that used such a technique couldrun very slowly.

Second, many of the important questions are difficult,if not impossible, to encode in a context-sensitive grammar. For example, consider the issue of declaration before use. To write this rule intoa context-sensitive grammar would require the grammar to encode eachdistinct combination of declared variables.

With a sufficiently small namespace (for example, Dartmouth BASIC limited the programmer to singleletter names, with an optional single digit), this might be manageable; in amodern language with a large name space, the set of names is too large toencode in a context-sensitive grammar.this restriction through context-sensitive checking. Similar restrictions applyto TypeSpecifiers.

For example, short is legal with int but not with float.To process declarations, the compiler must collect the attributes from thequalifiers, add any indirection, dimension, or initialization attributes, andenter the variable in the table. The compiler writer might set up a propertiesstructure whose fields correspond to the properties of a symbol-table entry.At the end of a Declaration, it can initialize the values of each field in thestructure. 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.