Java Reference
In-Depth Information
size(aSequence) size(aSequence) + 1
bSequence ::=
b
condition : iSize(bSequence) = 1
j bSequence
b
iSize(bSequence) iSize(bSequence) - 1
cSequence ::=
c
condition : iSize(cSequence) = 1
j cSequence
c
iSize(cSequence) iSize(cSequence) - 1
For the non-terminal a Sequence, size is a synthesized attribute; but for the non-terminals
bSequence and cSequence, iSize is an inherited attribute passed from the parent to child.
As before, the attribute grammar above cannot parse illegal sequences such as
abbcc
, as
these sequences do not satisfy all the conditions associated with attribute values.
In this grammar, the sequence of
a
's determines the desired length against which the
other sequences are checked. Consider the sequence
abbcc
. It could be argued that the
sequence of
a
's is at fault and not the other two sequences. However, in a programming
language with declarations, we use the declarations to determine the desired types against
which the remainder of the program is checked. In other words, the declaration information
is synthesized up and is inherited by the entire program for checking.
In our next example, we illustrate the use of attribute grammars in specifying semantics
using an example from Donald Knuth's 1968 seminal paper on attribute grammars [Knuth,
1968]. The example grammar computes the values of binary numbers. The grammar uses
both synthesized and inherited attributes.
Consider the following context-free grammar describing the structure of binary numbers.
N stands for binary numbers, L stands for bit lists, and B stands for individual bits.
N ::= L
N ::= L
.
L
L ::= B
L ::= L B
B ::=
0
B ::=
1
Examples of binary numbers that follow the above grammar are both integral numbers such
as
0
,
1
,
10
,
11
,
100
, and so on, and rational numbers with integral fractional part such as
1.1
,
1.01
,
10.01
, and so on.
We want to compute the values of the binary numbers using an attribute grammar. For
example,
0
has the value 0,
1
the value 1,
0.1
the value 0.5,
10.01
the value 2.25, and so
on.
Knuth provides a couple of different attribute grammars to define the computation; the
first one uses only synthesized attributes, and the second uses both inherited and synthesized
attributes. We will illustrate the latter.
In this attribution, each bit has a synthesized attribute value, which is a rational number
that takes the position of the bit into account. For example, the first bit in the binary number
Search WWH ::
Custom Search