computevalue(current).pptVIP

Talk at VCU - Computer Science - School of Engineering - 8/10/01 Attribute Grammars Prepared by Manuel E. Bermúdez, Ph.D. Associate Professor University of Florida Functional Graphs Definition: A functional graph is a directed graph in which: Nodes represent functions. Incoming edges are parameters. Outgoing edges represent functional values. Edges represent data transmission among functions. Example Here we have three functions: Constant function 2. Constant function 3. Binary function + (addition). After some delay, the output value is 5. Cycles in Functional Graphs Can make sense only if the graph can achieve a steady state. Example: No steady state is achieved, because the output value keeps incrementing. Example A steady state is achieved. If the AND were changed to a NAND, no steady state. Undecidable (halting problem) whether a steady state will ever occur. We will assume that all functional graphs are acyclic. Evaluation of Functional Graphs First insert registers. Then propagate values along the edges. Register insertion: Given edges E1 ... En from node A to nodes B1 ... Bn, insert a register R: one edge from A to R, and n edges from R to B1 ... Bn. Example All registers initialized to some undefined value. Top-most registers have no outgoing edges. Functional Value Propagation Two algorithms: Data Flow Analysis: repeated passes on the graph, evaluating functions whose inputs (registers) are defined. Lazy Evaluation, performs a depth-first search, backwards on the edges. Data Flow Algorithm While any top-most register is undefined { for each node N in the graph { if all inputs of N come from defined  register then evaluate N; update Ns output register } } Lazy Evaluation for each top-most register R, { push (stack, R) } while stack not empty { current := top (stack); if current = undefined { computable := true; for each R in dependency (current), while computable {