Evaluation Orders for SDD\'s
Introduction: "Dependency graphs" are a useful tool for determining an evaluation order for the attribute instances in a given parse tree. While an annotated parse tree shows the values of attributes, a dependency graph helps us determine how those values can be computed.
In this section, in addition to dependency graphs, we define two important classes of SDD's: the "S-attributed" and the more general "L-attributed" SDD's. The translations specified by these two classes fit well with the parsing methods we have studied, and most translations encountered in practice can be written to conform to the requirements of at least one of these classes.
A dependency graph depicts the flow of information among the attribute instances in a particular parse tree; an edge from one attribute instance to another means that the value of the first is needed to compute the second. Edges express constraints implied by the semantic rules. In more detail:
- For each parse-tree node, say a node labeled by grammar symbol X, the dependency graph has a node for each attribute associated with X.
- Suppose that a semantic rule associated with a production p defines the value of synthesized attribute A.b in terms of the value of X.c (the rule may define A.b in terms of other attributes in addition to X.c). Then, the dependency graph has an edge from X.c to A.b. More precisely, at every node N labeled A where production p is applied; create an edge to attribute b at N, from the attribute c at the child of N corresponding to this instance of the symbol X in the body of the production.2
- Suppose that a semantic rule associated with a production p defines the value of inherited attribute B.c in terms of the value of X.a. Then, the dependency graph has an edge from X.a to B.c. For each node N labeled B that corresponds to an occurrence of this B in the body of production p, create an edge to attribute c at N from the attribute a at the node M that corresponds to this occurrence of X. Note that M could be either the parent or a sibling of N.
Example: Consider the following production and rule:
PRODUCTION SEMANTIC RULE
E -> Ei T E.val - Ei.val T.val
At every node N labeled E, with children corresponding to the body of this production, the synthesized attribute val at N is computed using the values of val at the two children, labeled E and T. Thus, a portion of the dependency graph for every parse tree in which this production is used looks like Fig. 5.6. As a convention, we shall show the parse tree edges as dotted lines, while the edges of the dependency graph are solid.
Example: An example of a complete dependency graph appears in Fig. 5.7. The nodes of the dependency graph, represented by the numbers 1 through 9, correspond to the attributes in the annotated parse tree.
Nodes 1 and 2 represent the attribute lexval associated with the two leaves labeled digit. Nodes 3 and 4 represent the attribute val associated with the two nodes labeled F. The edges to node 3 from 1 and to node 4 from 2 result from the semantic rule that defines F.val in terms of digit. Lexval In fact, F.val equals digit .lexval, but the edge represents dependence, not equality.
Nodes 5 and 6 represent the inherited attribute T'.inh associated with each of the occurrences of nonterminal T'. The edge to 5 from 3 is due to the rule T'.inh = F.val, which defines T'.inh at the right child of the root from F.val at the left child. We see edges to 6 from node 5 for T'.inh and from node 4 for F.val, because these values are multiplied to evaluate the attribute inh at node 6.
Nodes 7 and 8 represent the synthesized attribute syn associated with the occurrences of X". The edge to node 7 from 6 is due to the semantic rule T'.syn = T'. The edge to node 8 from 7 is due to a semantic rule associated with production 2. Finally, node 9 represents the attribute T.val. The edge to 9 from 8 is due to the semantic rule, T.val = T'.syn, associated with production 1.