Syntax tree in Compiler Design | Construction of Syntax Tree
Construction of Syntax Tree
- Syntax directed definitions are very useful for construction of syntax trees. Each node in a syntax tree represents a construct. The children of the node represent the meaningful components of the construct.
- A syntax-tree node representing an expression E1 + E2 has label + and two children representing the subexpressions E1 and E2
- The nodes of a syntax tree are implemented by objects with a suitable number of fields. Each object will have an op field that is the label of the node.
- The objects will have additional fields as follows:
- If the node is a leaf, an additional field holds the lexical value for the leaf. A constructor function Leaf( op, val) creates a leaf object. Alternatively, if nodes are viewed as records, then Leaf returns a pointer to a new record for a leaf.
- If the node is an interior node, there are as many additional fields as the node has children in the syntax tree. A constructor function Node takes two or more arguments: Node(op, c1, c2, . . . , ck) creates an object with first field op and k additional fields for the k children c1, . . . , ck.
Construction Syntax Tree
Example 1
- The S-attributed definition constructs syntax trees for a simple expression grammar involving only the binary operators + and -. As usual, these operators are at the same precedence level and are jointly left associative. All nonterminals have one synthesized attribute node, which represents a node of the syntax tree.
- Every time the first production E -> E1 + T is used, its rule creates a node with '+' for op and two children, E1.node and T.node, for the subexpressions. The second production has a similar rule.
| Production | Semantic rule |
|---|---|
| E -> E1 + T | E.node = new Node('+', E1.node, T.node) |
| E -> E1 -T | E.node = new Node('-', E1.node, T.node) |
| E -> T | E.node = T.node |
| T -> (E) | T.node = E.node |
| T -> id | T.node = new Leaf(id, id.entry) |
| T -> num | T.node = new Leaf(num, num.val) |
S-Attributed Definitions Syntax Tree
Example 2
- The L-attributed definition performs the same translation as the S-attributed definition
| p1 = new Leaf ( id, entry-a ); |
| p2 = new Leaf ( num, 4 ); |
| p3 = new Node ( '-', p1, p2 ); |
| p4 = new Leaf ( id, entry-c ); |
| p5 = new Node ( '+', p3, p4 ); |
L-Attributed Definitions Syntax Tree