Syntax Tree

Download pdf

What is Syntax Tree?

Tree in which each leaf node describes an operand & each interior node an operator. The syntax tree is shortened form of the Parse Tree.

Example1 − Draw Syntax Tree for the string a + b ∗ c − d.

Rules for constructing a syntax tree

Each node in a syntax tree can be executed as data with multiple fields. In the node for an operator, one field recognizes the operator and the remaining field includes a pointer to the nodes for the operands. The operator is known as the label of the node. The following functions are used to create the nodes of the syntax tree for the expressions with binary operators. Each function returns a pointer to the recently generated node.

·        mknode (op, left, right) − It generates an operator node with label op and two field including pointers to left and right.

·        mkleaf (id, entry) − It generates an identifier node with label id and the field including the entry, a pointer to the symbol table entry for the identifier.

·        mkleaf (num, val) − It generates a number node with label num and a field including val, the value of the number. For example, construct a syntax tree for an expression a − 4 + c. In this sequence, p₁, p₂, … . . p₅are pointers to the symbol table entries for identifier 'a' and 'c' respectively.

p₁− mkleaf (id, entry a);

p₂− mkleaf (num, 4);

p₃− mknode ( ′−′, p₁, p₂)

p₄− mkleaf(id, entry c)

p₅− mknode(′+′, p₃, p₄);

The tree is generated in a bottom-up fashion. The function calls mkleaf (id, entry a) and mkleaf (num 4) construct the leaves for a and 4. The pointers to these nodes are stored using p₁and p₂. The call mknodes (′−′, p₁, p₂ ) then make the interior node with the leaves for a and 4 as children. The syntax tree will be

Syntax Directed Translation of Syntax Trees

Production	Semantic Action
E → E(1) + E(2)	{E. VAL = Node (+, E(1). VAL, E(2). VAL)}
E → E(1) ∗ E(2)	{E. VAL = Node (∗, E(1). VAL, E(2). VAL)})
E → (E(1))	{E. VAL = E(1). VAL}
E → E(1)	{E. VAL = UNARY (−, E(1). VAL}
E → id	{E. VAL = Leaf (id)}

Node (+, ^(𝟏), 𝐕𝐀𝐋, 𝐄^(𝟐). 𝐕𝐀𝐋) will create a node labeled +.

E⁽¹⁾. VAL &E⁽²⁾. VAL are left & right children of this node.

Similarly, Node (∗, E⁽¹⁾. VAL, E⁽²⁾. VAL) will make the syntax as −

Function UNARY (−, E⁽¹⁾. VAL)will make a node – (unary minus) & E⁽¹⁾. VAL will be the only child of it.

Function LEAF (id) will create a Leaf node with label id.

Example2 − Construct a syntax tree for the expression.

a = b ∗ −c + d

Solution

Example3 − Construct a syntax tree for a statement.

If a = b then b = 2 * c

Solution

Example4 − Consider the following code. Draw its syntax Tree

If x > 0 then x = 2 * (a + 1) else x = x + 1.

Example5 − Draw syntax tree for following arithmetic expression a * (b + c) – d /2. Also, write given expression in postfix form.

Postfix Notation

a b c + * d 2 / -

 

Parse tree and Syntax tree

When you create a parse tree then it contains more details than actually needed. So, it is very difficult to compiler to parse the parse tree. Take the following parse tree as an example:

• In the parse tree, most of the leaf nodes are single child to their parent nodes.
• In the syntax tree, we can eliminate this extra information.
• Syntax tree is a variant of parse tree. In the syntax tree, interior nodes are operators and leaves are operands.
• Syntax tree is usually used when represent a program in a tree structure.

A sentence id + id * id would have the following syntax tree:

Abstract syntax tree can be represented as:

Abstract syntax trees are important data structures in a compiler. It contains the least unnecessary information.

 

Download pdf