Java Reference
In-Depth Information
We conclude this chapter with two examples of general trees. A parse tree is useful in the construc-
tion of a compiler; a game tree is a generalization of the decision tree that Segment 23.23 described.
23.34
Segment 7.44 in Chapter 7 gave the following rules to describe strings that are valid algebraic
expressions:
•
An algebraic expression is either a term or two terms separated by a
+
or
-
operator.
•
A term is either a factor or two factors separated by a
*
or
/
operator.
•
A factor is either a variable or an algebraic expression enclosed in parentheses.
•
A variable is a single letter.
These rules form a
grammar
for algebraic expressions, much like the grammar that describes the
English language. In fact, every programming language has a grammar.
Typically, computer scientists use a notation to write the rules of a grammar. For example, the
rules just given for algebraic expressions could appear as follows, where the symbol | means “or”:
<expression>
::=
<term> | <term>
+
<term> | <term>
-
<term>
<term>
::=
<factor> | <factor>
*
<factor> | <factor>
/
<factor>
<factor>
::=
<variable> |
(
<expression>
)
<variable>
::=
a
|
b
| … |
z
|
A
|
B
… |
Z
To see whether a string is a valid algebraic expression—that is, to check its syntax—we must
see whether we can derive the string from <
expression
> by applying these rules. If we can, the der-
ivation can be given as a
parse tree
with <
expression
> as its root and the variables and operators of
the algebraic expression as its leaves. A parse tree for the expression
a
*
(
b
+
c
) is shown in
Figure 23-21. Beginning at the tree's root, we see that an expression is a term. A term is the product
of two factors. The first factor is a variable, in particular,
a
. The second factor is an expression
enclosed in parentheses. That expression is the sum of two terms. Each of those terms is a factor;
each of those factors is a variable. The first variable is
b
; the second is
c
. Since we are able to form
this parse tree, the string
a
*
(
b
+
c
) is a valid algebraic expression.
A parse tree must be a general tree so that it can accommodate any expression. In fact, we are
not restricted to algebraic expressions. We can use a parse tree to check the validity of any string
according to any grammar. Since programming languages have grammars, compilers use parse
trees both to check the syntax of a program and to produce executable code.
Question 18
Draw a parse tree for the algebraic expression
a
*
b
+
c
.
23.35
For a two-person game such as tic-tac-toe, we can use a general decision tree to represent the possi-
ble moves in any situation. Such a decision tree is called a
game tree
. If a given node in the tree
represents the state of the game after one player has made a move, the node's children represent the
states possible after the second player makes a move. Figure 23-22 shows a portion of a game tree
for tic-tac-toe.
We can use a game tree like the one shown in the figure in a program that plays tic-tac-toe. We
could create the tree ahead of time or have the program build the tree as it plays. In either case, the
program could ensure that poor moves do not remain in the tree. In this way, the program could use
a game tree to improve its play.
