Cooper_Engineering_a_Compiler(Second Edition) (1157546), страница 50
Текст из файла (страница 50)
The resulting grammar is simplistic in that it allows only simple identifiers as variables and it contains nofunction calls. Nonetheless, it is complex enough to convey the issues thatarise in estimating runtime behavior.Figure 4.8 shows an attribute grammar that estimates the execution time of ablock of assignment statements. The attribution rules estimate the total cyclecount for the block, assuming a single processor that executes one operationat a time. This grammar, like the one for inferring expression types, usesonly synthesized attributes. The estimate appears in the cost attribute ofthe topmost Block node of the parse tree.
The methodology is simple. Costsare computed bottom up; to read the example, start with the productions forFactor and work your way up to the productions for Block. The functionCost returns the latency of a given iloc operation.Improving the Execution-Cost EstimatorTo make this example more realistic, we can improve its model for howthe compiler handles variables. The initial version of our cost-estimatingattribute grammar assumes that the compiler naively generates a separateload operation for each reference to a variable. For the assignment x = y + y,the model counts two load operations for y. Few compilers would generatea redundant load for y.
More likely, the compiler would generate a sequencesuch as:4.3 The Attribute-Grammar Framework 191loadAI rarp , @y ⇒ ryaddry , ry⇒ rxstoreAI rx⇒ rarp , @xthat loads y once. To approximate the compiler’s behavior better, we canmodify the attribute grammar to charge only a single load for each variableused in the block. This requires more complex attribution rules.To account for loads more accurately, the rules must track references to eachvariable by the variable’s name. These names are extra-grammatical, sincethe grammar tracks the syntactic category name rather than individual namessuch as x, y, and z. The rule for name should follow the general outline:if ( name has not been loaded )then Factor.cost ← Cost(load);else Factor.cost ← 0;The key to making this work is the test “name has not been loaded.”To implement this test, the compiler writer can add an attribute that holdsthe set of all variables already loaded.
The production Block → Assign caninitialize the set. The rules must thread the expression trees to pass the setthrough each assignment. This suggests augmenting each node with two sets,Before and After. The Before set for a node contains the lexemes of allnames that occur earlier in the Block; each of these must have been loadedalready. A node’s After set contains all the names in its Before set, plusany names that would be loaded in the subtree rooted at that node.The expanded rules for Factor are shown in Figure 4.9. The code assumesthat it can obtain the textual name—the lexeme—of each name.
The firstproduction, which derives ( Expr ), copies the Before set down into theExpr subtree and copies the After set up to the Factor. The second production, which derives num, simply copies its parent’s Before set into itsparent’s After set. num must be a leaf in the tree; therefore, no further actionsare needed. The final production, which derives name, performs the criticalwork.
It tests the Before set to determine whether or not a load is neededand updates the parent’s cost and After attributes accordingly.To complete the specification, the compiler writer must add rules that copythe Before and After sets around the parse tree. These rules, sometimescalled copy rules, connect the Before and After sets of the various Factornodes. Because the attribution rules can reference only local attributes—defined as the attributes of a node’s parent, its siblings, and its children—the attribute grammar must explicitly copy values around the parse tree to192 CHAPTER 4 Context-Sensitive AnalysisProductionFactor → (Expr)Attribution Rules{ Factor.cost ← Expr.cost;Expr.Before ← Factor.Before;Factor.After ← Expr.After }|num{ Factor.cost ← Cost(loadI);Factor.After ← Factor.Before }|name{ if (name.lexeme ∈/ Factor.Before)thenFactor.cost ← Cost(load);Factor.After ← Factor.Before∪ { name.lexeme }elseFactor.cost ← 0;Factor.After ← Factor.Before }n FIGURE 4.9 Rules to Track Loads in Factor Productions.ensure that they are local.
Figure 4.10 shows the required rules for the otherproductions in the grammar. One additional rule has been added; it initializesthe Before set of the first Assign statement to ∅.This model is much more complex than the simple model. It has over threetimes as many rules; each rule must be written, understood, and evaluated.It uses both synthesized and inherited attributes, so the simple bottom-upevaluation strategy will no longer work.
Finally, the rules that manipulatethe Before and After sets require a fair amount of attention—the kind oflow-level detail that we would hope to avoid by using a system based onhigh-level specifications.Back to Inferring Expression TypesIn the initial discussion about inferring expression types, we assumed thatthe attributes name.type and num.type were already defined by some external mechanism. To fill in those values using an attribute grammar, thecompiler writer would need to develop a set of rules for the portion of thegrammar that handles declarations.Those rules would need to record the type information for each variablein the productions associated with the declaration syntax. The rules wouldneed to collect and aggregate that information so that a small set of attributescontained the necessary information on all the declared variables.
The ruleswould need to propagate that information up the parse tree to a node that isan ancestor of all the executable statements, and then to copy it downwardinto each expression. Finally, at each leaf that is a name or num, the ruleswould need to extract the appropriate facts from the aggregated information.4.3 The Attribute-Grammar Framework 193ProductionBlock0 → Block1 Assign|AssignAttribution Rules{ Block0 .cost ← Block1 .cost + Assign.cost;Assign.Before ← Block1 .After;Block0 .After ← Assign.After{ Block0 .cost ← Assign.cost;Assign.Before ← ∅;Block0 .After ← Assign.After }Assign → name = Expr;{ Assign.cost ← Cost(store) + Expr.cost;Expr.Before ← Assign.Before;Assign.After ← Expr.After }Expr0{ Expr0 .cost ← Expr1 .cost + Cost(add) + Term.cost;Expr1 .Before ← Expr0 .Before;Term.Before ← Expr1 .After;Expr0 .After ← Term .
After }→ Expr1 + Term|Expr1 − Term{ Expr0 .cost ← Expr1 .cost + Cost(sub) + Term . cost;Expr1 .Before ← Expr0 .Before;Term.Before ← Expr1 .After;Expr0 .After ← Term.After }|Term{ Expr0 .cost ← Term . cost;Term.Before ← Expr0 .Before;Expr0 .After ← Term . After }Term0 → Term1 × Factor{ Term0 .cost ← Term1 .cost + Cost(mult) + Factor . cost;Term1 .Before ← Term0 .Before;Factor.Before ← Term1 .After;Term0 .After ← Factor . After }|Term1 ÷ Factor{ Term0 .cost ← Term1 .cost + Cost(div) + Factor.cost;Term1 .Before ← Term0 .Before;Factor.Before ← Term1 .After;Term0 .After ← Factor . After }|Factor{ Term0 .cost ← Factor .
cost;Factor.Before ← Term0 .Before;Term0 .After ← Factor . After }n FIGURE 4.10 Copy Rules to Track Loads.The resulting set of rules would be similar to those that we developed fortracking loads but would be more complex at the detailed level. These rulesalso create large, complex attributes that must be copied around the parsetree. In a naive implementation, each instance of a copy rule would create anew copy. Some of these copies could be shared, but many of the versionscreated by merging information from multiple children will differ (and, thus,need to be distinct copies).
The same problem arises with the Before andAfter sets in the previous example.194 CHAPTER 4 Context-Sensitive AnalysisA Final Improvement to the Execution-Cost EstimatorWhile tracking loads improved the fidelity of the estimated execution costs,many further refinements are possible. Consider, for example, the impact offinite register sets on the model. So far, our model has assumed that the targetcomputer provides an unlimited set of registers. In reality, computers providesmall register sets.
To model the capacity of the register set, the estimatorcould limit the number of values allowed in the Before and After sets.As a first step, we must replace the implementation of Before and After.They were implemented with arbitrarily sized sets; in this refined model,the sets should hold exactly k values, where k is the number of registersavailable to hold the values of variables. Next, we must rewrite the rulesfor the production Factor → name to model register occupancy. If a valuehas not been loaded, and a register is available, it charges for a simple load.If a load is needed, but no register is available, it can evict a value fromsome register and charge for the load. The choice of which value to evictis complex; it is discussed in Chapter 13. Since the rule for Assign alwayscharges for a store, the value in memory will be current.
Thus, no store isneeded when a value is evicted. Finally, if the value has already been loadedand is still in a register, then no cost is charged.This model complicates the rule set for Factor → name and requires aslightly more complex initial condition (in the rule for Block → Assign).It does not, however, complicate the copy rules for all the other productions.Thus, the accuracy of the model does not add significantly to the complexityof using an attribute grammar.
All of the added complexity falls into the fewrules that directly manipulate the model.4.3.4 Problems with the Attribute-Grammar ApproachThe preceding examples illustrate many of the computational issues thatarise in using attribute grammars to perform context-sensitive computationson parse trees. Some of these pose particular problems for the use of attributegrammars in a compiler. In particular, most applications of attribute grammars in the front end of a compiler assume that the results of attributionmust be preserved, typically in the form of an attributed parse tree.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
