Java Reference
In-Depth Information
Start
Digs
431
1 Start
→
Digs
ans
$
Digs
43
call
print
(
ans
)
2 Digs
up
→
Digs
below
d
next
up
←
below
×
Digs
4
10
+
next
3
|
d
f irst
up
←
first
d
d
d
$
4
3
1
(a)
(b)
Figure 7.3: (a) Grammar with semantic actions; (b) Parse tree and
propagated semantic values for the input 431$.
specified as the semantic value associated with the Digs symbol in Rule 1. The
code associated with a production is shown indented beneath the production.
For example, the code beneath Rule 1 causes the final value passed up the
parsetree(
ans
)tobeprinted.
Because each nonterminal is the resultofsomeproduction,thesemantic
values associated with nonterminals are computed by semantic action code
segments. The values associated with terminal symbols must be established
by the scanner. For example, Rule 3 in Figure 7.3 includes the symbol d
f irst
.The
syntactic element d represents a decimal digit, as discovered by the scanner;
the semantic tag
f irst
represents the digit's value, which must also be provided
by the scanner. Parser generators o
er methods for declaring the
type
of the
semantic symbols; for the sake of simplicity we omit type declarations in our
examples. In the grammar of Figure 7.3(a), all semantic tags would be declared
of type integer.
We now analyze how the semantic actions in Figure 7.3(a) compute the
base-10 value of the digit string. To appreciate the interaction of Rules 2
and 3, we examine the order in which a bottom-up parse applies these rules.
Figure 7.3(b) shows a parse tree for the input string 431$.InChapter6we
learned that a bottom-up parse traces a rightmost derivation in reverse. The
rules for Digs are therefore applied as follows:
ff
Digs
→
d In a bottom-up parse, Rule 1 must be applied first, so d corresponds
to the first input digit 4. The semantic action
up
←
f irst
causes the value
of the first digit (4) to be assigned to the semantic value for Digs.Semantic