Java Reference
In-Depth Information
1 Start
→
E$
2 E
→
EplusT
3
|
T
4 T
→
T times num
5
|
num
Start
E
T
E
T
T
num plus
num times
num
$
Figure 6.21: Grammar for sums of products.
shows that this grammar is LR(0). However, it does not produce the parse
trees that structure the expressions appropriately. The parse tree shown in
Figure 6.20 structures the computation by adding the first two numsandthen
multiplying that sumby the third num. As such, the input string 3
7would
produce a value of 49 if evaluation were guided by the computation's parse
tree.
A common convention in mathematics is that multiplication has prece-
dence over addition. Thus, the computation 3
+
4
∗
+
4
∗
7shouldbeviewedas
adding 3 to the product 4
7, resulting in the value 31. Such conventions
are typically adopted in programming language design, in an e
∗
ort to sim-
plify program authoring and readability. We therefore seek a parse tree that
appropriately structures expressions involving multiplication and addition.
To develop the grammar that achieves the desired e
ff
ect, we first observe
that a string in the language of Figure 6.20 should be regarded as a
sum of
products
. The grammar in Figure 6.18 generates sums of nums. A common
technique to expand a language involves replacing a terminal symbol in the
grammar by a nonterminal whose role in the grammar is equivalent. To
produce a sum of Ts rather than a sum of nums, we need only replace num
with T to obtain the rules for E shown in Figure 6.21.
ff
To achieve a sum
