1 Inherited and Synthesized Attributes
2 Evaluating an SDD at the Nodes of a Parse Tree
3 Exercises for Section 5.1

**Syntax-Directed Definitions**

*1 Inherited and Synthesized
Attributes*

*2 Evaluating an SDD at the Nodes
of a Parse Tree*

*3 Exercises for Section 5.1*

A *syntax-directed definition*
(SDD) is a context-free grammar together with attributes and rules. Attributes
are associated with grammar symbols and rules are associated with productions.
If *X* is a symbol and *a* is one of its attributes, then we
write *X.a* to denote the value of a at
a particular parse-tree node labeled *X.*
If we implement the nodes of the parse tree by records or objects, then the
attributes of *X* can be implemented by
data fields in the records that represent the nodes for *X.* Attributes may be of any kind: numbers, types, table references,
or strings, for instance. The strings may even be long sequences of code, say
code in the intermediate language used by a compiler.

**1. Inherited and Synthesized
Attributes**

We shall deal with two kinds of attributes for nonterminals:

1. A synthesized attribute for a nonterminal A at a parse-tree node N is
defined by a semantic rule associated with the production at N. Note that the
production must have A as its head. A synthesized attribute at node N is
defined only in terms of attribute values at the children of N and at N itself.

2. An inherited attribute for a nonterminal B at a parse-tree node N is
defined by a semantic rule associated with the production at the parent of N.
Note that the production must have B as a symbol in its body. An inherited
attribute at node N is defined only in terms of attribute values at JV's
parent, N itself, and N's siblings.

**An Alternative Definition of
Inherited Attributes**

No additional translations are enabled if we allow an inherited
attribute B.c at a node N to be defined in terms of attribute values at the
children of A?", as well as at N itself, at its parent, and at its
siblings. Such rules can be "simulated" by creating additional
attributes of B, say B.ci,B.c2,....

These are synthesized attributes that copy the needed attributes of the
children of the node labeled B. We then compute B.c as an inherited attribute,
using the attributes B.ci, B.c2,... in place of attributes at the children.
Such attributes are rarely needed in practice.

While we do not allow an inherited attribute at node *N* to be defined in terms of attribute
values at the children of node *N,* we
do allow a synthesized attribute at node *N*
to be defined in terms of inherited attribute values at node *N* itself.

Terminals can have synthesized attributes, but not inherited attributes.
At-tributes for terminals have lexical values that are supplied by the lexical
analyzer; there are ho semantic rules in the SDD itself for computing the value
of an attribute for a terminal.

**Example 5.1 : **The SDD in Fig. 5 . 1 is based on our familiar grammar for** **arithmetic expressions with operators
+ and *. It evaluates expressions termi-nated by an endmarker **n.** In the SDD, each of the nonterminals
has a single synthesized attribute, called *val*
We also suppose that the terminal **digit**
has a synthesized attribute *lexval,*
which is an integer value returned by the lexical analyzer.

The rule for production 1, L ->• E n, sets L.val to E.val, which we
shall see is the numerical value of the entire expression.

Production 2, E -> Ex + T, also has one rule, which computes the val
attribute for the head E as the sum of the values at E1 and T. At any parse
tree node N labeled E, the value of val for E is the sum of the values of val
at the children of node N labeled E and T.

Production 3, E -»• T, has a single rule that defines the value of val
for E to be the same as the value of val at the child for T. Production 4 is similar
to the second production; its rule multiplies the values at the children
instead of adding them. The rules for productions 5 and 6 copy values at a
child, like that for the third production. Production 7 gives F.val the value
of a digit, that is, the numerical value of the token digit that the lexical
analyzer returned.

An SDD that involves only synthesized attributes is called S-attributed;
the SDD in Fig. 5.1 has this property. In an S-attributed SDD, each rule
computes an attribute for the nonterminal at the head of a production from
attributes taken from the body of the production.

For simplicity, the examples in this section have semantic rules without
side effects. In practice, it is convenient to allow SDD's to have limited side
effects, such as printing the result computed by a desk calculator or
interacting with a symbol table. Once the order of evaluation of attributes is
discussed in Section 5.2, we shall allow semantic rules to compute arbitrary
functions, possibly involving side effects.

An S-attributed SDD can be implemented naturally in conjunction with an
LR parser. In fact, the SDD in Fig. 5.1 mirrors the Yacc program of Fig. 4.58,
which illustrates translation during LR parsing. The difference is that, in the
rule for production 1, the Yacc program prints the value E.val as a side
effect, instead of defining the attribute L.val.

An SDD without side effects is sometimes called an attribute grammar.
The rules in an attribute grammar define the value of an attribute purely in
terms of the values of other attributes and constants.

**2. Evaluating an SDD at the Nodes
of a Parse Tree**

To visualize the translation specified by an SDD, it helps to work with
parse trees, even though a translator need not actually build a parse tree.
Imagine therefore that the rules of an SDD are applied by first constructing a
parse tree and then using the rules to evaluate all of the attributes at each
of the nodes of the parse tree. A parse
tree, showing the value(s) of its attribute(s) is called an annotated parse
tree.

How do we construct an annotated parse tree? In what order do we
evaluate attributes? Before we can evaluate an attribute at a node of a parse
tree, we must evaluate all the attributes upon which its value depends. For
example, if all attributes are synthesized, as in Example 5.1, then we must
evaluate the val attributes at all of the children of a node before we can
evaluate the val attribute at the node itself.

With synthesized attributes, we can evaluate attributes in any bottom-up
order, such as that of a postorder traversal of the parse tree; the evaluation
of S-attributed definitions is discussed in Section 5.2.3.

For SDD's with both inherited and synthesized attributes, there is no
guar-antee that there is even one order in which to evaluate attributes at
nodes. For instance, consider nonterminals *A*
and *B,* with synthesized and inherited
attributes *A.s* and *BA,* respectively, along with the
production and rules

These rules are circular; it is impossible to evaluate either *A.s* at a node *N* or *BA* at the child of *N* without first evaluating the other.
The circular dependency of *A.s* and *BA* at some pair of nodes in a parse tree
is suggested by Fig. 5.2.

Figure 5.2: The circular
dependency of *A.s* and *BA* on one another

It is computationally difficult to determine whether or not there exist
any circularities in any of the parse trees that a given SDD could have to
translate.^{1} Fortunately, there are useful subclasses of SDD's that are sufficient
to guarantee that an order of evaluation exists, as we shall see in Section
5.2.

Example 5.2 : Figure 5.3 shows an annotated parse tree for the input
string 3 * 5 + 4 n, constructed using the grammar and rules of Fig. 5.1. The
values of lexval are presumed supplied by the lexical analyzer. Each of the
nodes for the nonterminals has attribute val computed in a bottom-up order, and
we see the resulting values associated with each node. For instance, at the
node with a child labeled *, after computing T.val = 3 and F.val = 5 at its
first and third children, we apply the rule that says T.val is the product of
these two values, or 15.

Inherited attributes are useful when the structure of a parse tree does
not "match" the abstract syntax of the source code. The next example
shows how inherited attributes can be used to overcome such a mismatch due to a
grammar designed for parsing rather than translation.

1 Without going into details, while the problem is decidable, it cannot
be solved by a polynomial-time algorithm, even if V = NT, since it has
exponential time complexity.

Example 5.3 : The SDD in Fig. 5.4 computes terms like 3 * 5 and 3 * 5 *
7 .

The top-down parse of input 3 * 5 begins with the production T ^ FT'.
Here, F generates the digit 3, but the operator * is generated by X".
Thus, the left operand 3 appears in a different subtree of the parse tree from
*. An inherited attribute will therefore be used to pass the operand to the
operator.

The grammar in this example is an excerpt from a non-left-recursive
version of the familiar expression grammar; we used such a grammar as a running
example to illustrate top-down parsing in Section 4.4.

Figure 5.4: An SDD based on a
grammar suitable for top-down parsing

Each of the nonterminals *T* and
*F* has a synthesized attribute *val;* the terminal **digit** has a synthesized attribute *lexval.* The nonterminal *T*
has two attributes: an inherited attribute *inh*
and a synthesized attribute *syn.*

The semantic rules are based on the idea that the left operand of the
operator * is inherited. More precisely, the head T" of the production T'
* F T[ inherits the left operand of * in the production body. Given a term x *
y * z, the root of the subtree for * y * z inherits x. Then, the root of the
subtree for * z inherits the value of x * y, and so on, if there are more
factors in the term.

Once all the factors have been accumulated, the result is passed back up
the tree using synthesized attributes.

To see how the semantic rules are used, consider the annotated parse
tree for 3 * 5 in Fig. 5.5. The leftmost leaf in the parse tree, labeled digit,
has attribute value lexval = 3, where the 3 is supplied by the lexical
analyzer. Its parent is for production 4, F -> digit. The only semantic rule
associated with this production defines F.val = digit.lexval, which equals 3.

At the second child of the root, the inherited attribute T'.inh is
defined by the semantic rule T'.inh = F.val associated with production 1. Thus,
the left operand, 3, for the * operator is passed from left to right across the
children of the root.

The production at the node for V is X" -»• * FT[. (We retain the
subscript 1 in the annotated parse tree to distinguish between the two nodes
for T'.) The inherited attribute T[.inh is defined by the semantic rule T[.inh
= T'.inhx F.val associated with production 2.

With T'.inh =
3 and F.val = 5, we get T[.inh =
1 5 . At the lower node for T[, the production is T" ->• e. The semantic rule
T'.syn —
T'.inh defines T{.syn — 15. The syn attributes at the nodes for X"
pass the value 15 up the tree to the node for X, where T.val = 15.

**3. Exercises for Section 5.1**

Exercise 5.1.1 : For the SDD of Fig. 5.1, give annotated parse trees for
the following expressions:

a) (3 + 4 ) * ( 5 + 6 ) n .

1 * 2 * 3
* (4 + 5) **n.**

(9 + 8 *
(7 + 6 ) + 5) * 4 **n .**

E x e r c i s e 5 . 1 . 2: Extend the SDD of Fig.
5.4 to handle expressions as in Fig. 5.1.

E x e r c i s e 5 . 1 . 3 : Repeat Exercise 5.1.1, using your SDD from
Exercise 5.1.2.

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

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

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

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