order of evaluation compiler design code example

Example: 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 . •