# 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
**E**has label_{1}+ E_{2}**+**and two children representing the subexpressions**E**_{1}and E_{2} - 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 -> E**is used, its rule creates a node with_{1}+ T**'+'**for**op**and two children,**E**and_{1}.node**T.node**, for the subexpressions. The second production has a similar rule.

Production | Semantic rule |
---|---|

E -> E_{1} + T |
E.node = new Node('+', E_{1}.node, T.node) |

E -> E_{1} -T |
E.node = new Node('-', E_{1}.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

p_{1} = new Leaf ( id, entry-a ); |

p_{2} = new Leaf ( num, 4 ); |

p_{3} = new Node ( '-', p1, p2 ); |

p_{4} = new Leaf ( id, entry-c ); |

p_{5} = new Node ( '+', p3, p4 ); |

L-Attributed Definitions Syntax Tree