K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 49
Текст из файла (страница 49)
Figure 4.6b shows that the value and negative attributes aresynthesized, while the position attribute is inherited.Any scheme for evaluating attributes must respect the relationships encodedimplicitly in the attribute-dependence graph. Each attribute must be definedby some rule. If that rule depends on the values of other attributes, it cannotbe evaluated until all those values have been defined. If the rule depends onno other attribute values, then it must produce its value from a constant orsome external source.
As long as no rule relies on its own value, the rulesshould uniquely define each value.Of course, the syntax of the attribution rules allows a rule to reference itsown result, either directly or indirectly. An attribute grammar containingsuch rules is ill formed. We say that such rules are circular because theycan create a cycle in the dependence graph. For the moment, we will ignorecircularity; Section 4.3.2 addresses this issue.The dependence graph captures the flow of values that an evaluator mustrespect in evaluating an instance of an attributed tree. If the grammar isnoncircular, it imposes a partial order on the attributes. This partial orderdetermines when the rule defining each attribute can be evaluated. Evaluation order is unrelated to the order in which the rules appear in thegrammar.Consider the evaluation order for the rules associated with the uppermostList node—the right child of Number.
The node results from applying production five, List → List Bit; applying that production adds three rules tothe evaluation. The two rules that set inherited attributes for the List node’schildren must execute first. They depend on the value of List.position andset the position attributes for the node’s subtrees. The third rule, whichsets the List node’s value attribute, cannot execute until the two subtreesboth have defined value attributes. Since those subtrees cannot be evaluateduntil the first two rules at the List node have been evaluated, the evaluationsequence will include the first two rules early and the third rule much later.To create and use an attribute grammar, the compiler writer determines aset of attributes for each symbol in the grammar and designs a set of rulesto compute their values.
These rules specify a computation for any validparse tree. To create an implementation, the compiler writer must create anevaluator; this can be done with an ad hoc program or by using an evaluator generator—the more attractive option. The evaluator generator takes asinput the specification for the attribute grammar. It produces the code for anevaluator as its output.
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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
