The Choice of an Evaluation Order for Global Attributes.

Suppose a family of directed acyclic graphs (dags) is generated by a grammar. The dags represent expressions to be evaluated; a node represents the value of a subexpression and an edge x "-" z says that the value of x is needed for the computation of z . An evaluation order for a dag is a linear ordering of its nodes, in which x appears before z if x "-" z is an edge. Evaluation orders must satisfy an additional constraint, motivated by the storage cells needed to hold values-a label attached to a node specifies the global cell that the node must be computed into. The following constraint prevents the value in a cell (l) from being overwritten and destroyed prematurely: as long as the value of x with label (l) is needed for computing a node z , we cannot compute any y with label (l). The problem is: give an algorithm that takes a graph grammar as input and determines if, for all generated dags, there exists an evaluation order satisfying constraints like the above. Note that the evaluation order is not fixed in advance. Furthermore, determining an evaluation order for a particular dag is a special case (use a single production to generate the dag from the start symbol).