Evaluation Orders for SDDs

In this article, we learn about evaluation orders for syntax-directed definitions. Dependency graphs are used to determine an evaluation order for instances of attributes in a parse tree.

Table of contents.

1. Introduction.
2. Dependency graphs.
3. Ordering the evaluation of attributes.
4. S-Attributed Definitions.
5. L-Attributed Definitions.
6. Semantic rules with controlled side effects.
7. Summary.
8. References.

Prerequisites.

Syntax Directed Definitions

Introduction.

We use dependency graphs to determine an evaluation order for an attribute instance when we are given a parse tree.
As we have learned in the prerequisite article, an annotated parse tree shows the values of attributes. The dependency graph assists us in computing those values.

In addition to dependency graphs, we also learn about two classes of SDDs namely, S-Attributed and L-Attributed SDDs.

Dependency graphs.

We use dependency graphs to show the flow of information among attribute instances in a parse tree. An instance is an edge from one attribute to another. This means that the computation of the second value is dependent on the first value. These edges are also used to express constraints by semantic rules.

For each node X in the parse tree, the dependency graph has a node for each attribute that is associated with X.

If the semantic rule associated with production p defines the value of a synthesized attribute A.b in terms of the value of X.c, then the graph is said to have an edge from X.c to A.b. That is, at every node N labeled A where production p is applied, we create an edge to attribute b at N, from the attribute c at the child of N that corresponds to this instance of symbol X in the production body.

If a semantic rule that is associated with production p defines the value of the inherited attribute B.c in terms of the value of X.a, then there exists an edge from X.a to B.c. For each node N labeled B corresponding to Bs occurrence in the production body p, we create an edge to attribute c at N from the attribute a at node M corresponding to Xs occurrence. Note, M could be a parent or sibling of N.

Ordering the evaluation of attributes.

The graph groups all possible orderings that we can use to evaluate the attributes at various nodes in the tree. If there exists an edge between node A and node B, the attribute corresponding to A is evaluated before B.
The allowed evaluation orderings are those of nodes B1, B2, ..., Bk such that if there is an edge between Ai and Aj then I < j. These orderings embedded in a directed graph are referred to as a topological sort ordering.

A cycle cannot exist in a topological sort, this is because we cannot evaluate an SDD on this parse tree. On the other hand, if no cycles exist then there will be at least one topological sort. This is because if there are no cycles, we can find a node without an edge entering it. If there were no such node, we could proceed from predecessor to predecessor until we came back to a node we had already visited and this would be a cycle. We make this node the first in the ordering, remove it from the graph and repeat on the remaining nodes.

S-Attributed Definitions.

When we have an SDD(Syntax-directed definition), It is difficult to tell if cycles exist in the dependency graphs of the parse trees. Practically, we use classes of SDDs that guarantee an evaluation order since they don't permit cycles in dependency graphs to implement translations.

We conclude with the following statement; An SDD is S-Attributed if every attribute is synthesized.

L-Attributed Definitions.

Between attributes that are associated with the body of a production, graph edges can go from left to right but not vice versa hence the name L-attributed.
Each attribute can be synthesized or inherited. In case the attribute is inherited its rules are limited. That is if there is a production A -> X1, X2, ..., Xn and an inherited attribute Xi.a computed by a rule that is associated with this production that only uses;

• Inherited attributes associated with head A.
• Either inherited or synthesized attributes associated with occurrences of X1, X2, ..., Xi-1 located to the left of X.
• Inherited/synthesized attributes that are associated with X1 itself, only such that there are no cycles in the graph formed by the attributes of Xi.

For more information about L-attributed and S-attributed definitions and grammar, this article is helpful.

Semantic rules with controlled side effects.

Even though translations have side effects, using syntax-directed definitions enables us to balance between attribute grammars and translation schemes.
Attribute grammars don't have side effects and allow evaluation orders that are consistent with the graph.
Translation schemes impose a left-right-evaluation and allow semantic actions to have program fragments.

We can control side effects in syntax-directed definitions by;

• Allowing accompanying side effects that do not constrain attribute evaluation. That is, permit side effects when attribute evaluation based on any topological sort of the graph produces a correct translation where correct is dependent on the application.
• Secondly, we constrain allowed evaluation orders so that the same translation can be produced for any allowed order. Constrains are thought of as implicit edges added to the graph.

Summary.

If we have a parse tree, we can use a dependency graph to show to flow of information among attribute instances.
The difference between an annotated parse tree and a dependency graph is, while the former shows the values of its attributes, the latter assists us in computing those values.

References.

Compilers Principles, Techniques, & Tools - Alfred V. Aho Monica S. Lam Ravi Sethi Jeffrey D. Ullman