evaluation order in compiler design
2. Ordering the Evaluation of Attributes:
The dependency graph characterizes the possible orders in which we can
evalu-ate the attributes at the various nodes of a parse tree.
If the dependency graph has an edge from node M to node N,
then the attribute corresponding to M must be evaluated before the attribute
of N. Thus, the only allowable orders of evaluation are those sequences of
nodes N1, N2,... ,Nk such that if there is an edge of the dependency graph
from Ni to Nj, then i < j. Such an ordering embeds a directed graph into a
linear order, and is called a topological sort of the graph.
If there is any cycle in the graph, then there are no topological sorts;
that is, there is no way to evaluate the SDD on this parse tree.
If there are no cycles, however, then there is always at least one topological
sort. To see why, since there are no cycles, we can surely find a node with no
edge entering. For if there were no such node, we could proceed from
predecessor to predecessor until we came back to some node we had already seen,
yielding a cycle. Make this node the first in the topological order, remove it
from the dependency graph, and repeat the process on the remaining nodes.
E x a m p l e 5 . 6 : The dependency graph of Fig. 5.7 has no cycles.
One topologi-cal sort is the order in which the nodes have already been
numbered: 1,2, ... ,9 . Notice that every edge of the graph goes from a
node to a higher-numbered node, so this order is surely a topological sort.
There are other topological sorts as well, such as 1,3,5,2,4,6,7,8,9 . •