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

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

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

L-Attributed Definitions Syntax Tree

Related Searches to Syntax tree in Compiler Design | Construction of Syntax Tree