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