**Branch :**Computer Science and Engineering

**Subject :**Compiler design

**Unit :**Syntax-directed Translation

## Variants of Syntax Trees

**Introduction**: Nodes in a syntax tree represent constructs in the source program; the children of a node represent the meaningful components of a construct. A directed acyclic graph (hereafter called a DAG) for an expression identifies the common subexpressions (subexpressions that occur more than once) of the expression. As we shall see in this section, DAG's can be constructed by using the same techniques that construct syntax trees.

**Directed Acyclic Graphs for Expressions: **Like the syntax tree for an expression, a DAG has leaves corresponding to atomic operands and interior codes corresponding to operators. The difference is that a node N in a DAG has more than one parent if N represents a common subexpression; in a syntax tree, the tree for the common subexpression would be replicated as many times as the subexpression appears in the original expression. Thus, a DAG not only represents expressions more succinctly, it gives the compiler important clues regarding the generation of efficient code to evaluate the expressions.

**Example 1**: Figure 6.3 shows the DAG for the expression

a a * (b - c) (b - c) * d

The leaf for a has two parents, because a appears twice in the expression. More interestingly, the two occurrences of the common subexpression b - c are represented by one node, the node labeled —. That node has two parents, representing its two uses in the subexpressions a* ( b - c ) and (b-c)*d. Even though b and c appear twice in the complete expression, their nodes each have one parent, since both uses are in the common subexpression b - c.

The SDD of Fig. 6.4 can construct either syntax trees or DAG's. It was used to construct syntax trees in Example 5.11, where functions Leaf and Node created a fresh node each time they were called. It will construct a DAG if, before creating a new node, these functions first check whether an identical node already exists. If a previously created identical node exists, the existing node is returned. For instance, before constructing a new node, Node(op, left, right) we check whether there is already a node with label op, and children left and right, in that order. If so, Node returns the existing node; otherwise, it creates a new node.

**Example 2** : The sequence of steps shown in Fig. 6.5 constructs the DAG in Fig. 6.3, provided Node and Leaf return an existing node, if possible, as

discussed above. We assume that entry-a points to the symbol-table entry for a, and similarly for the other identifiers. When the call to Leaf (id, entry-a) is repeated at step 2, the node created by the previous call is returned, so p2 = Pi • Similarly, the nodes returned at steps 8 and 9 are the same as those returned at steps 3 and 4 (i.e., ps = p3 and PQ = p^). Hence the node returned at step 10 must be the same at that returned at step 5; i.e., pio = P5-