Java Reference
In-Depth Information
10.01
will have the value 2 and the last bit will have the value 0.25. In order to define these
attributes, each bit also has an inherited attribute scale used to compute the value of a
1-bit as value = 2
scale
. So for the bits in
10.01
, scale will be 1, 0, 1, 2, respectively.
If we have the values of the individual bits, these values can simply be summed up to the
total value. Adding synthesized attributes value both for bit lists and for binary numbers
does this. In order to compute the scale attribute for the individual bits, an inherited
attribute scale is added also for bit lists (representing the scale of the rightmost bit in that
list), and a synthesized attribute length for bit lists, holding the length of the list.
Knuth uses the abbreviations v, s, and l for the value, scale, and length attributes. Here
is the resulting attribute grammar:
N ::= L
v(N) v(L)
s(L) 0
N ::= L
1
.
L
2
v(N) v(L
2
) + v(L
2
)
s(L
1
) 0
s(L
2
) - l(L
2
)
L ::= B
v(L) v(B)
s(B) s(L)
l(L) 1
L
1
::= L
2
B
v(L
1
) v(L
2
) + v(B)
s(B) s(L
1
)
s(L
2
) s(L
1
) + 1
l(L
1
) l(L
2
) + 1
B ::=
0
v(B) 0
B ::=
1
v(B) 2
s(B)
4.8.2 Formal Definition
An attribute grammar is a context-free grammar augmented with attributes, semantic rules,
and conditions. Let G = (N;T;S;P) be a context-free grammar. For each non-terminal
X 2 N in the grammar, there are two nite disjoint sets I(X) and S(X) of inherited and
synthesized attributes. For X = S, the start symbol I(X) = ;.
Let A(X) = I(A) [S(X) be the set of attributes of X. Each attribute A 2 A(X) takes
a value from some semantic domain (such as integers, strings of characters, or structures of
some type) associated with that attribute. These values are defined by semantic functions
or semantic rules associated with the productions in P.
Consider a production p 2 P of the form X
0
::= X
1
X
2
:::X
n
. Each synthesized attribute
A 2 S(X
0
) has its value defined in terms of the attributes in A(X
1
)[A(X
2
)[[A(X
n
)[
I(X
0
). Each inherited attribute A 2 I(X
k
) for 1 k n has its value dened in terms of
the attributes in A(X
0
) [S(X
1
) [S(X
2
) [[S(X
n
). Each production may also have a
Search WWH ::
Custom Search