Cooper_Engineering_a_Compiler(Second Edition) (1157546), страница 49
Текст из файла (страница 49)
This is the attraction of attribute grammars for thecompiler writer; the tools take a high-level, nonprocedural specification andautomatically produce an implementation.CircularityAn attribute grammar is circular if it can, for someinputs, create a cyclic dependence graph.186 CHAPTER 4 Context-Sensitive AnalysisOne critical insight behind the attribute-grammar formalism is the notionthat the attribution rules can be associated with productions in the contextfree grammar. Since the rules are functional, the values that they produceare independent of evaluation order, for any order that respects the relationships embodied in the attribute-dependence graph.
In practice, any orderthat evaluates a rule only after all of its inputs have been defined respects thedependences.4.3.1 Evaluation MethodsThe attribute-grammar model has practical use only if we can build evaluators that interpret the rules to evaluate an instance of the problemautomatically—a specific parse tree, for example. Many attribute evaluation techniques have been proposed in the literature. In general, they fallinto three major categories.1.
Dynamic Methods These techniques use the structure of a particularattributed parse tree to determine the evaluation order. Knuth’s originalpaper on attribute grammars proposed an evaluator that operated in amanner similar to a dataflow computer architecture—each rule “fired”as soon as all its operands were available. In practical terms, this mightbe implemented using a queue of attributes that are ready for evaluation.As each attribute is evaluated, its successors in the attribute dependencegraph are checked for “readiness” (see Section 12.3). A related schemewould build the attribute dependence graph, topologically sort it, anduse the topological order to evaluate the attributes.2. Oblivious Methods In these methods, the order of evaluation isindependent of both the attribute grammar and the particular attributedparse tree.
Presumably, the system’s designer selects a method deemedappropriate for both the attribute grammar and the evaluationenvironment. Examples of this evaluation style include repeatedleft-to-right passes (until all attributes have values), repeatedright-to-left passes, and alternating left-to-right and right-to-left passes.These methods have simple implementations and relatively smallruntime overheads.
They lack, of course, any improvement that can bederived from knowledge of the specific tree being attributed.3. Rule-Based Methods Rule-based methods rely on a static analysis of theattribute grammar to construct an evaluation order. In this framework,the evaluator relies on grammatical structure; thus, the parse tree guidesthe application of the rules. In the signed binary number example, theevaluation order for production 4 should use the first rule to setBit.position, recurse downward to Bit, and, on return, use Bit.value toset List.value. Similarly, for production 5, it should evaluate the first4.3 The Attribute-Grammar Framework 187two rules to define the position attributes on the right-hand side, thenrecurse downward to each child.
On return, it can evaluate the third ruleto set the List.value field of the parent List node. Tools that perform thenecessary static analysis offline can produce fast rule-based evaluators.4.3.2 CircularityCircular attribute grammars can give rise to cyclic attribute-dependencegraphs. Our models for evaluation fail when the dependence graph containsa cycle.
A failure of this kind in a compiler causes serious problems—forexample, the compiler might not be able to generate code for its input. Thecatastrophic impact of cycles in the dependence graph suggests that this issuedeserves close attention.If a compiler uses attribute grammars, it must handle circularity in anappropriate way.
Two approaches are possible.1. Avoidance The compiler writer can restrict the attribute grammar to aclass that cannot give rise to circular dependence graphs. For example,restricting the grammar to use only synthesized and constant attributeseliminates any possibility of a circular dependence graph. More generalclasses of noncircular attribute grammars exist; some, like stronglynoncircular attribute grammars, have polynomial-time tests formembership.2. Evaluation The compiler writer can use an evaluation method thatassigns a value to every attribute, even those involved in cycles.
Theevaluator might iterate over the cycle and assign appropriate or defaultvalues. Such an evaluator would avoid the problems associated with afailure to fully attribute the tree.In practice, most attribute-grammar systems restrict their attention to noncircular grammars. The rule-based evaluation methods may fail to constructan evaluator if the attribute grammar is circular. The oblivious methods andthe dynamic methods will attempt to evaluate a circular dependence graph;they will simply fail to define some of the attribute instances.4.3.3 Extended ExamplesTo better understand the strengths and weaknesses of attribute grammars asa tool, we will work through two more detailed examples that might arisein a compiler: inferring types for expression trees in a simple, Algol-likelanguage, and estimating the execution time, in cycles, for a straight-linesequence of code.188 CHAPTER 4 Context-Sensitive AnalysisInferring Expression TypesAny compiler that tries to generate efficient code for a typed language mustconfront the problem of inferring types for every expression in the program.This problem relies, inherently, on context-sensitive information; the typeassociated with a name or num depends on its identity—its textual name—rather than its syntactic category.Consider a simplified version of the type inference problem for expressionsderived from the classic expression grammar given in Chapter 3.
Assumethat the expressions are represented as parse trees, and that any node representing a name or num already has a type attribute. (We will return to theproblem of getting the type information into these type attributes later inthe chapter.) For each arithmetic operator in the grammar, we need a function that maps the two operand types to a result type. We will call thesefunctions F+ , F− , F× , and F÷ ; they encode the information found in tablessuch as the one shown in Figure 4.1.
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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
