K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 51
Текст из файла (страница 51)
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. Thissection details the impact of the problems that we have seen in the precedingexamples.Handling Nonlocal InformationSome problems map cleanly onto the attribute-grammar paradigm, particularly those problems in which all information flows in the same direction.However, problems with a complex pattern of information flow can bedifficult to express as attribute grammars.
An attribution rule can name only4.3 The Attribute-Grammar Framework 195values associated with a grammar symbol that appears in the same production; this constrains the rule to using only nearby, or local, information. If thecomputation requires a nonlocal value, the attribute grammar must includecopy rules to move those values to the points where they are used.Copy rules can swell the size of an attribute grammar; compare Figures 4.8,4.9, and 4.10. The implementor must write each of those rules. In the evaluator, each of the rules must be executed, creating new attributes and additionalwork. When information is aggregated, as in the declare-before-use rule orthe framework for estimating execution times, a new copy of the information must be made each time a rule changes an aggregate’s value. Thesecopy rules add another layer of work to the tasks of writing and evaluatingan attribute grammar.Storage ManagementFor realistic examples, evaluation produces large numbers of attributes.
Theuse of copy rules to move information around the parse tree can multiplythe number of attribute instances that evaluation creates. If the grammaraggregates information into complex structures—to pass declaration information around the parse tree, for example—the individual attributes can belarge. The evaluator must manage storage for attributes; a poor storagemanagement scheme can have a disproportionately large negative impacton the resource requirements of the evaluator.If the evaluator can determine which attribute values can be used after evaluation, it may be able to reuse some of the attribute storage by reclaimingspace for values that can never again be used.
For example, an attributegrammar that evaluated an expression tree to a single value might returnthat value to the process that invoked it. In this scenario, the intermediatevalues calculated at interior nodes might be dead—never used again—and,thus, candidates for reclamation.
On the other hand, if the tree resulting fromattribution is persistent and subject to later inspection—as might be the casein an attribute grammar for type inference—then the evaluator must assumethat a later phase of the compiler can traverse the tree and inspect arbitraryattributes. In this case, the evaluator cannot reclaim the storage for any ofthe attribute instances.This problem reflects a fundamental clash between the functional nature ofthe attribute-grammar paradigm and the imperative use to which it mightbe put in the compiler.
The possible uses of an attribute in later phasesof the compiler have the effect of adding dependences from that attributeto uses not specified in the attribute grammar. This bends the functionalparadigm and removes one of its strengths: the ability to automaticallymanage attribute storage.196 CHAPTER 4 Context-Sensitive AnalysisInstantiating the Parse TreeAn attribute grammar specifies a computation relative to the parse tree for avalid sentence in the underlying grammar.
The paradigm relies, inherently,on the availability of the parse tree. The evaluator might simulate the parsetree, but it must behave as if the parse tree exists. While the parse tree isuseful for discussions of parsing, few compilers actually build a parse tree.Some compilers use an abstract syntax tree (ast) to represent the programbeing compiled.
The ast has the essential structure of the parse tree buteliminates many of the internal nodes that represent nonterminal symbolsin the grammar (see the description starting on page 226 of Section 5.2.1).If the compiler builds an ast, it could use an attribute grammar tied to agrammar for the ast. However, if the compiler has no other use for the ast,then the programming effort and compile-time cost associated with buildingand maintaining the ast must be weighed against the benefits of using theattribute-grammar formalism.Locating the AnswersOne final problem with attribute-grammar schemes for context-sensitiveanalysis is more subtle.
The result of attribute evaluation is an attributedtree. The results of the analysis are distributed over that tree, in the formof attribute values. To use these results in later passes, the compiler musttraverse the tree to locate the desired information.The compiler can use carefully constructed traversals to locate a particular node, which requires walking from the root of the parse tree down tothe appropriate location—on each access. This makes the code both slowerand harder to write, because the compiler must execute each of these traversals and the compiler writer must construct each of them. The alternative isto copy the important answers to a point in the tree where they are easilyfound, typically the root. This introduces more copy rules, exacerbating thatproblem.Breakdown of the Functional ParadigmOne way to address all of these problems is to add a central repository forattributes.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
