1 Construction of Syntax Trees
2 The Structure of a Type
3 Exercises for Section 5.3

**Applications of Syntax-Directed
Translation**

*1 Construction of Syntax Trees*

*2 The Structure of a Type*

*3 Exercises for Section 5.3*

The syntax-directed translation techniques in this chapter will be
applied in Chapter 6 to type checking and intermediate-code generation. Here,
we consider selected examples to illustrate some representative SDD's.

The main application in this section is the construction of syntax
trees. Since some compilers use syntax trees as an intermediate representation,
a common form of SDD turns its input string into a tree. To complete the
translation to intermediate code, the compiler may then walk the syntax tree,
using another set of rules that are in effect an SDD on the syntax tree rather
than the parse tree. (Chapter 6 also discusses approaches to intermediate-code
generation that apply an SDD without ever constructing a tree explicitly.)

We consider two SDD's for constructing syntax trees for expressions. The
first, an S-attributed definition, is suitable for use during bottom-up
parsing. The second, L-attributed, is suitable for use during top-down parsing.

The final example of this section is an L-attributed definition that
deals with basic and array types.

**1. Construction of Syntax Trees**

As discussed in Section 2.8.2, 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 + E** _{2}* has
label + and two children representing the subexpressions

We shall implement the nodes of a syntax tree 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,ci,c2,... ,ck) creates an object with first
field op and k additional fields for the k children c1,... , .

**Example 5.11 :** The S-attributed definition in Fig. 5.10 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, Ei.node and T.node, for the
subexpressions.

The second production has a similar rule.

For production 3, *E -> T,*
no node is created, since *E.node* is
the same as *T.node. *Similarly, no
node is created for production 4, T (* E *)
. The value* *of *T.node* is the same as *E.node,*
since parentheses are used only for grouping; they influence the structure of
the parse tree and the syntax tree, but once their job is done, there is no
further need to retain them in the syntax tree.

The last two T-productions have a single terminal on the right. We use
the constructor *Leaf* to create a
suitable node, which becomes the value of *T.node.*

Figure 5 . 1 1 shows the construction of a syntax tree for the input *a —* 4 + *c.* The nodes of the syntax tree are shown as records, with the *op* field first. Syntax-tree edges are
now shown as solid lines. The underlying parse tree, which need not actually be
constructed, is shown with dotted edges. The third type of line, shown dashed,
represents the values of *E.node* and *T-node;* each line points to the
appropriate syntax-tree node.

At the bottom we see leaves for a, 4 and c, constructed by Leaf. We
suppose that the lexical value id. entry points into the symbol table, and the
lexical value uum.ual is the numerical value of a constant. These leaves, or
pointers to them, become the value of T.node at the three parse-tree nodes
labeled T, according to rules 5 and 6. Note that by rule 3, the pointer to the
leaf for a is also the value of E.node for the leftmost E in the parse tree.

Rule 2 causes us to create a node with op equal to the minus sign and
pointers to the first two leaves. Then, rule 1 produces the root node of the
syntax tree by combining the node for — with the third leaf.

If the rules are evaluated during a postorder traversal of the parse
tree, or with reductions during a bpttom-up parse, then the sequence of steps
shown in Fig. 5 . 1 2 ends with p5 pointing to the root of the constructed
syntax tree. •

With a grammar designed for top-down parsing, the same syntax trees are
constructed, using the same sequence of steps, even though the structure of the
parse trees differs significantly from that of syntax trees.

**Example 5.12 : **The L-attributed definition in Fig. 5 . 1 3 performs the same** **translation as the S-attributed
definition in Fig. 5 . 1 0 . The attributes for the grammar symbols *E, T,* **id,** and **n u m** are as
discussed in Example 5 . 1 1 .

The rules for building syntax trees in this example are similar to the
rules for the desk calculator in Example 5.3.
In the desk-calculator example,
a term x * y was evaluated by passing
x as an inherited attribute, since x
and * y appeared in different
portions of the parse tree. Here, *the*
idea is to build a syntax tree for *x + y*
by passing *x* as an inherited
attribute, since *x* and + *y* appear in different subtrees.
Nonterminal *E'* is the counterpart of
nonterminal T" in Example 5.3. Compare the dependency graph for *a* — 4 + c in Fig. 5.14 with that for 3 *
5 in Fig. 5.7.

Nonterminal *E'* has an
inherited attribute *iinh* and a
synthesized attribute *syn. *Attribute* E'.inh *represents the partial syntax
tree constructed so far.* *Specifically,
it represents the root of the tree for the prefix of the input string that is
to the left of the subtree for *E'.* At
node 5 in the dependency graph in Fig. 5.14, *E'.inh* denotes the root of the partial syntax tree for the
identifier a; that is, the leaf for *a.*
At node 6, *E'.inh* denotes the root
for the partial syntax

tree for the input a — 4. At node 9, E'.inh denotes the syntax tree for
a — 4 + c. Since there is no more input, at node 9, E'.inh points to the root
of the entire syntax tree. The syn attributes pass this value back up the parse
tree until it becomes the value of E.node. Specifically, the attribute value at
node 10 is defined by the rule E'.syn = E'.inh associated with the production
E' —> e.

The attribute value at node 11 is defined by the rule E'.syn = E[ .syn
associated with production 2 in Fig. 5 . 1 3 . Similar rules define the
attribute values at nodes 12 and 1 3 .

**2. The Structure of a Type**

Inherited attributes are useful when the structure of the parse tree
differs from the abstract syntax of the input; attributes can then be used to
carry information from one part of the parse tree to another. The next example
shows how a mismatch in structure can be due to the design of the language, and
not due to constraints imposed by the parsing method.

Example 5.13 : In C, the type int [2][3] can be read as, "array of
2 arrays of 3 integers." The corresponding type expression array(2,
array(3, integer)) is represented by the tree in Fig. 5.15. The operator array
takes two parameters, a number and a type. If types are represented by trees,
then this operator returns a tree node labeled array with two children for a
number and a type.

With the SDD in Fig. 5.16, nonterminal *T* generates either a basic type or an array type. Nonterminal *B* generates one of the basic types **int** and **float.** *T *generates a
basic type when* T *derives* B C *and* C *derives e. Otherwise,* C *generates
array components consisting of a sequence of integers, each integer surrounded
by brackets.

The nonterminals *B* and *T* have a synthesized attribute *t* representing a type. The nonterminal *C* has two attributes: an inherited
attribute *b* and a synthesized
attribute *t.* The inherited *b* attributes pass a basic type down the
tree, and the synthesized *t*
attributes accumulate the result.

An annotated parse tree for the input string **int [** 2 ] [ 3 ] is shown in Fig. 5.17. The corresponding type
expression in Fig. 5.15 is constructed by passing the type *integer* from *B,* down the
chain of C's through the inherited attributes *b.* The array type is synthesized up the chain of C's through the
attributes *t.*

In more detail, at the root for *T*
-» *B C,* nonterminal *C* inherits the type from *B,* using the inherited attribute *C.b.* At the rightmost node for C, the production
is C e, so C.t equals C.6. The semantic
rules for the production C [ num ] C1 form C.t by applying the operator array
to the operands num.ua/ and C1.t.

**3. Exercises for Section 5.3**

**Exercise 5 . 3 . 1 **: Below is a grammar for expressions involving operator 4- and** **integer or floating-point operands.
Floating-point numbers are distinguished by having a decimal point.

Give an SDD to determine the type
of each term *T* and expression *E.*

Extend your SDD of (a) to
translate expressions into postfix notation. Use the unary operator **intToFloat** to turn an integer into an
equivalent float.

**Exercise 5.3.2 **: Give an SDD to translate infix expressions with + and * into** **equivalent expressions without
redundant parentheses. For example, since both operators associate from the
left, and * takes precedence over +, ((a*(6+c))*(<i))** **translates into *a * (b + c)
* d.*

**Exercise 5 . 3 . 3 **: Give an SDD to differentiate expressions such as** ***x*** *** (3 *** ***x +***
***x * x) *involving the operators +
and *, the variable* x, *and constants.
Assume* *that no simplification occurs,
so that, for example, 3 * *x* will be
translated into 3 * **1** + 0 * *x.*

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Compilers : Principles, Techniques, & Tools : Syntax-Directed Translation : Applications of Syntax-Directed Translation |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.