Tree Traversals
Introduction: There are many different applications of trees and are many different algorithms for manipulating them. . Tree traversals will be used for describing attribute evaluation and for specifying the execution of code fragments in a translation scheme. A traversal of a tree starts at the root and visits each node of the tree in some order. However, many of the different tree algorithms have in common the characteristic that they systematically visit all the nodes in the tree. That is, the algorithm walks through the tree data structure and performs some computation at each node in the tree. This process of walking through the tree is called a tree traversal.
A depth-first traversal starts at the root and recursively visits the children of each node in any order, not necessarily from left to right. It is called "depth-first" because it visits an unvisited child of a node whenever it can, so it visits nodes as far away from the root (as "deep") as quickly as it can. The procedure visit (N) in Fig. 2.11 is a depth first traversal that visits the children of a node in left-to-right order, as shown in Fig. 2.12. In this traversal, we have included the action of evaluating translations at each node, just before we finish with the node (that is, after translations at the children have surely been computed). In general, the actions associated with a traversal can be whatever we choose or nothing at all.
A syntax-directed definition does not impose any specific order for the evaluation of attributes on a parse tree; any evaluation order that computes an attribute a after all the other attributes that a depends on is acceptable. Synthesized attributes can be evaluated during any bottom-up traversal, that is, a traversal that evaluates attributes at a node after having evaluated attributes at its children. In general, with both synthesized and inherited attributes, the matter of evaluation order is quite complex; see Section 5.2.
Translation Schemes: The syntax-directed definition in Fig. 2.10 builds up a translation by attaching strings as attributes to the nodes in the parse tree. We now consider an alternative approach that does not need to manipulate strings; it produces the same translation incrementally, by executing program fragments.
Translation Schemes: The syntax-directed definition in builds up a translation by attaching strings as attributes to the nodes in the parse tree. We now consider an alternative approach that does not need to manipulate strings; it produces the same translation incrementally, by executing program fragments.
Preorder and Post-order Traversals: Preorder and post-order traversals are two important special cases of depth-first traversals in which we visit the children of each node from left to right. Often, we traverse a tree to perform some particular action at each node. If the action is done when we first visit a node, then we may refer to the traversal as a preorder traversal. Similarly, if the action is done just before we leave a node for the last time, and then we say it is a postorder traversal of the tree. The procedure visit (N) in Fig. 2.11 is an example of a postorder traversal.
Preorder and postorder traversals define corresponding orderings on nodes, based on when the action at a node would be performed. The preorder of a (sub) tree rooted at node JV consists of N, followed by the preorders of the subtrees of each of its children, if any, from the left. The postorder of a (sub) tree rooted at TV" consists of the postorders of each of the subtrees for the children of N, if any, from the left, followed by N itself.
A syntax-directed translation scheme is a notation for specifying a translation by attaching program fragments to productions in a grammar. A translation scheme is like a syntax-directed definition, except that the order of evaluation of the semantic rules is explicitly specified. Program fragments embedded within production bodies are called semantic actions. The position at which an action is to be executed is shown by enclosing it between curly braces and writing it within the production body, as in
rest —> term {print(' ')} rest\
We shall see such rules when we consider an alternative form of grammar for expressions, where the nonterminal rest represents "everything but the first term of an expression." This form of grammar is discussed in Section 2.4.5. Again, the subscript in rest\ distinguishes this instance of nonterminal rest in the production body from the instance of rest at the head of the production. When drawing a parse tree for a translation scheme, we indicate an action by constructing an extra child for it, connected by a dashed line to the node that corresponds to the head of the production. For example, the portion of the parse tree for the above production and action is shown in Fig. 2.13. The node for a semantic action has no children, so the action is performed when that node is first seen.