Java Reference
In-Depth Information
Start
Num
Digs
Digs
1 Start
→
Num $
2 Num
→
oDigs
Digs
3
|
Digs
4 Digs
→
Digs d
5
|
d
o
d
d
d
$
4
3
1
(a)
(b)
Figure 7.4: (a) Grammar and (b) parse tree for the input o431$.
actions such as these are often called
copy rules
because they serve only
to propagate values up the parse tree.
Digs
→
Digs d Each subsequent d is processed by Rule 2. The semantic action
up
←
below
×
+
next
multiplies the value computed thus far (
below
)by
10 and then adds in the semantic value of the current d (
next
).
10
This example illustrates that left-recursive rules are amenable to semantic
processing of input text from left to right in a bottom-up parser. Exercise 1
considers the problem of computing a digit string's value when the grammar
rule is right recursive.
Figure 7.4(a) extends our language slightly, so that a string of digits is
optionally prefaced with an o; a parse tree showing the new syntax is shown
in Figure 7.4(b). Rule 3 generates strings of digits that should be interpreted
base-10. Rule 2 generates an o followed by a string of digits that should be
interpreted base-8 (octal).
While the grammar in Figure 7.4(a) su
ces toparse the language described
above, it su
ff
ers from the following drawbacks:
•
The nonterminal Digs generates a string of decimal digits, even in cases
where those digits should be interpreted base-8. Octal digits should be
restricted to 0-7, but the grammar of Figure 7.4(a) is inconvenient to
enforce that restriction. Rules 4 and 5 need to process base-10 as well as
base-8 digits. Enforcing base-8 digits at Rule 2 would require rescanning
the digits that reduced to Digs.
