Java Reference
In-Depth Information
0
S
A
1
x
A
x
2
x
A
x
3
x
x
Syntax
Semantic Values
(a)
(b)
Figure 7.2: (a) Parse tree for the displayed input string; (b) Inherited
attributes pass from parent to child.
ure 7.1(a) is generated by the standard expression grammar from Figure 6.21
on page 205. As shown in Figure 7.1(b), a rule such as E
EplusTsynthesizes
a result at the parent that is the sum of the values transmitted by its first and
third children. Section 7.2 considers synthesized attributes and bottom-up
parsing in much greater detail.
→
On the other hand, consider the problem of counting the position of each
x in a string. The parse tree in Figure 7.2(a) is derived from a simple right-
linear grammar. Each A node computes its semantic value in Figure 7.2(b)
by incrementing the value received from its parent. Values that flow in this
manner are called
inherited attributes
. Section 7.3 considers the more general
case of synthesized and inherited attributes in the context of top-down parsing.
Syntax-directed translation of most programming languages requires both
synthesized and inherited attributes. While a given style of parsing favors
attribute flow in one direction, value flow in the other direction is managed
using other techniques. For example, symbol tables (introduced in Section 2.7.1
on page 47 with details in Chapter 8) e
ectively allow type information to
propagate up the tree (from a variable's declaration) and down the tree (to a
variable's use).
ff
