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

Adblocker detected! Please consider reading this notice.

We've detected that you are using AdBlock Plus or some other adblocking software which is preventing the page from fully loading.

We don't have any banner, Flash, animation, obnoxious sound, or popup ad. We do not implement these annoying types of ads!

We need money to operate the site, and almost all of it comes from our online advertising.

Please add to your ad blocking whitelist or disable your adblocking software.