K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 50
Текст из файла (страница 50)
With these assumptions, we can writesimple attribution rules that define a type attribute for each node in the tree.Figure 4.7 shows the attribution rules.If a has type integer (denoted I ) and c has type real (denoted R), thenthis scheme generates the following attributed parse tree for the input stringa - 2 × c:Exprtype:Exprtype:Termtype:<name,a>type:-Termtype:Termtype:× <name,c>type:<num,2>type:The leaf nodes have their type attributes initialized appropriately. Theremainder of the attributes are defined by the rules from Figure 4.7, withthe assumption that F+ , F− , F× , and F÷ reflect the fortran 77 rules.A close look at the attribution rules shows that all the attributes are synthesized attributes.
Thus, all the dependences flow from a child to its parentin the parse tree. Such grammars are sometimes called S-attributed grammars. This style of attribution has a simple, rule-based evaluation scheme.It meshes well with bottom-up parsing; each rule can be evaluated whenthe parser reduces by the corresponding right-hand side. The attributegrammar paradigm fits this problem well. The specification is short. It iseasily understood.
It leads to an efficient evaluator.Careful inspection of the attributed expression tree shows two cases in whichan operation has an operand whose type is different from the type of the4.3 The Attribute-Grammar Framework 189ProductionAttribution RulesExpr0 → Expr1 + Term| Expr1 − Term| TermExpr0 .type ← F+ (Expr1 .type,Term.type)Expr0 .type ← F− (Expr1 .type,Term.type)Expr0 .type ← Term.typeTerm0 → Term1 Factor| Term1 Factor| FactorTerm0 .type ← F× (Term1 .type,Factor.type)Term0 .type ← F÷ (Term1 .type,Factor.type)Term0 .type ← Factor.typeFactor → (Expr)| num| nameFactor.type ← Expr.typenum.type is already definedname.type is already definedn FIGURE 4.7 Attribute Grammar to Infer Expression Types.operation’s result.
In fortran 77, this requires the compiler to insert a conversion operation between the operand and the operator. For the Term nodethat represents the multiplication of 2 and c, the compiler would convert 2from an integer representation to a real representation. For the Expr nodeat the root of the tree, the compiler would convert a from an integer toa real. Unfortunately, changing the parse tree does not fit well into theattribute-grammar paradigm.To represent these conversions in the attributed tree, we could add anattribute to each node that holds its converted type, along with rules toset the attributes appropriately. Alternatively, we could rely on the processthat generates code from the tree to compare the two types—parent andchild—during the traversal and insert the necessary conversion.
The formerapproach adds some work during attribute evaluation, but localizes all of theinformation needed for a conversion to a single parse-tree node. The latterapproach defers that work until code generation, but does so at the cost ofdistributing the knowledge about types and conversions across two separateparts of the compiler. Either approach will work; the difference is largely amatter of taste.A Simple Execution-Time EstimatorAs a second example, consider the problem of estimating the executiontime of a sequence of assignment statements.
We can generate a sequenceof assignments by adding three new productions to the classic expressiongrammar:Block→|Block AssignAssignAssign → name = Expr;190 CHAPTER 4 Context-Sensitive AnalysisProductionAttribution RulesBlock0 → Block1 Assign|{ Block0 .cost ← Block1 .cost + Assign.cost }{ Block0 .cost ← Assign.cost }AssignAssign → name = Expr;{ Assign.cost ← Cost(store) + Expr.cost }Expr0{ Expr0 .cost ← Expr1 .cost + Cost(add) + Term.cost }{ Expr0 .cost ← Expr1 .cost + Cost(sub) + Term.cost }{ Expr0 .cost ← Term.cost }→ Expr1 + Term||Expr1 − TermTermTerm0 → Term1 × Factor| Term1 ÷ Factor| Factor{ Term0 .cost ← Term1 .cost + Cost(mult) + Factor.cost }{ Term0 .cost ← Term1 .cost + Cost(div) + Factor.cost }{ Term0 .cost ← Factor.cost }Factor → (Expr)| num| name{ Factor.cost ← Expr.cost }{ Factor.cost ← Cost(loadI) }{ Factor.cost ← Cost(load) }n FIGURE 4.8 Simple Attribute Grammar to Estimate Execution Time.where Expr is from the expression grammar.
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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
