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 .”