Cooper_Engineering_a_Compiler(Second Edition) (Rice), страница 48

Sketch a scheme that can check the validity of thosefunction prototypes.182 CHAPTER 4 Context-Sensitive Analysis4.3 THE ATTRIBUTE-GRAMMAR FRAMEWORKAttributea value attached to one or more of the nodes in aparse treeOne formalism that has been proposed for performing context-sensitiveanalysis is the attribute grammar, or attributed context-free grammar. Anattribute grammar consists of a context-free grammar augmented by a setof rules that specify computations. Each rule defines one value, or attribute,in terms of the values of other attributes.

The rule associates the attributewith a specific grammar symbol; each instance of the grammar symbol thatoccurs in a parse tree has a corresponding instance of the attribute. The rulesare functional; they imply no specific evaluation order and they define eachattribute’s value uniquely.To make these notions concrete, consider a context-free grammar forsigned binary numbers. Figure 4.4 defines the grammar SBN = (T,NT,S,P).SBN generates all signed binary numbers, such as -101, +11, -01, and+11111001100. It excludes unsigned binary numbers, such as 10.From SBN, we can build an attribute grammar that annotates Number withthe value of the signed binary number that it represents. To build an attributegrammar from a context-free grammar, we must decide what attributes eachnode needs, and we must elaborate the productions with rules that definevalues for these attributes.

For our attributed version of SBN, the followingattributes are needed:SymbolAttributesNumberSignListBitvaluenegativeposition, valueposition, valueIn this case, no attributes are needed for the terminal symbols.Figure 4.5 shows the productions of SBN elaborated with attribution rules.Subscripts are added to grammar symbols whenever a specific symbolNumberSignP=ListBit→→|→|→|Sign List +−List Bit Bit0T= { +, -, 0, 1 }NT = { Number, Sign, List, Bit }S= { Number }1n FIGURE 4.4 An Attribute Grammar for Signed Binary Numbers.4.3 The Attribute-Grammar Framework 183ProductionAttribution Rules1Number → Sign ListList.position ← 0if Sign.negativethen Number.value← - List.valueelse Number.value ← List.value2Sign → +Sign.negative ← false3Sign → -Sign.negative ← true4List → BitBit.position ← List.positionList.value ← Bit.value5List0 → List1 BitList1 .position ← List0 .position + 1Bit.position ← List0 .positionList0 .value ← List1 .value + Bit.value6Bit → 07Bit → 1Bit.value ← 0Bit.value ← 2Bit.positionn FIGURE 4.5 Attribute Grammar for Signed Binary Numbers.appears multiple times in a single production.

This practice disambiguatesreferences to that symbol in the rules. Thus, the two occurrences ofList in production 5 have subscripts, both in the production and in thecorresponding rules.The rules add attributes to the parse tree nodes by their names. An attributementioned in a rule must be instantiated for every occurrence of that kind ofnode.Each rule specifies the value of one attribute in terms of literal constantsand the attributes of other symbols in the production. A rule can pass information from the production’s left-hand side to its right-hand side; a rulecan also pass information in the other direction.

The rules for production4 pass information in both directions. The first rule sets Bit.position toList.position, while the second rule sets List.value to Bit.value. Simpler attribute grammars can solve this particular problem; we have chosenthis one to demonstrate particular features of attribute grammars.Given a string in the SBN grammar, the attribution rules set Number.valueto the decimal value of the binary input string. For example, the string -101causes the attribution shown in Figure 4.6a. (The names for value, number,and position are truncated in the figure.) Notice that Number.value hasthe value -5.To evaluate an attributed parse tree for some sentence in L(S B N ), theattributes specified in the various rules are instantiated for each node in184 CHAPTER 4 Context-Sensitive Analysisthe parse tree. This creates, for example, an attribute instance for bothvalue and position in each List node.

Each rule implicitly defines a setof dependences; the attribute being defined depends on each argument to therule. Taken over the entire parse tree, these dependences form an attributedependence graph. Edges in the graph follow the flow of values in theevaluation of a rule; an edge from nodei .field j to nodek .fieldl indicates thatthe rule defining nodek .fieldl uses the value of nodei .field j as one of itsinputs. Figure 4.6b shows the attribute-dependence graph induced by theparse tree for the string -101.Synthesized attributean attribute defined wholly in terms of theattributes of the node, its children, and constantsInherited attributean attribute defined wholly in terms of thenode’s own attributes and those of its siblings orits parent in the parse tree (plus constants)The rule node.field←1 can be treated as eithersynthesized or inherited.The bidirectional flow of values that we noted earlier (in, for example, production 4) shows up in the dependence graph, where arrows indicate bothflow upward toward the root (Number) and flow downward toward theleaves.

The List nodes show this effect most clearly. We distinguish betweenattributes based on the direction of value flow. Synthesized attributes aredefined by bottom-up information flow; a rule that defines an attribute forthe production’s left-hand side creates a synthesized attribute. A synthesizedattribute can draw values from the node itself, its descendants in the parsetree, and constants.

Inherited attributes are defined by top-down and lateralinformation flow; a rule that defines an attribute for the production’s righthand side creates an inherited attribute. Since the attribution rule can nameany symbol used in the corresponding production, an inherited attribute candraw values from the node itself, its parent and its siblings in the parse tree,Numberval:-5Numberval:-5pos:0Signneg:truepos:0pos:1pos:2pos:1Bit val:1List val:4List val:4pos:1pos:2Bit val:0List val:4Bit val:1pos:1Bit val:0pos:2pos:21pos:0List val:4Bit val:4Bit val:4-pos:0List val:5Signneg:trueList val:501(a) Parse Tree for-101n FIGURE 4.6 Attributed Tree for the Signed Binary Number −101.-10(b) Dependence Graph for-10114.3 The Attribute-Grammar Framework 185and constants. 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.