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
Search WWH ::




Custom Search