Slide 4.5: Evaluation orders for SDDs Slide 5.1: Synthesized attributes Home

Evaluation Orders for SDDs (Cont.)

---

A portion of the dependency graphs for every parse tree of the previous attribute grammar are as follows:

• The dotted lines are for parse tree edges and the solid lines are for the edges of the dependency graphs.


• The edge to Base(<num>) from Base(<basechar>) shows that Base(<num>) depends on Base(<basechar>).

If an attribute b at a node in a parse tree depends on an attribute c, then the semantic rule for b at that node must be evaluated after the semantic rule that defines c. A traversal order of the dependency graph that obeys this restriction is called a topological sort. The dependency graph of the number 345o is as follows:


The topological sort is applied to directed acyclic graphs (DAGs). Another topological sort is “12 6 9 1 2 11 3 8 4 5 7 10 13 14 .”