Thinking Recursively with Java

10.3. Expression Trees

In addition to offering a computationally efficient mechanism for maintaining sorted collections of data, tree structures have many useful applications in computer science. One of the most important arises in the design and implementation of compilers, which are responsible for translating statements in a programming language into a form more easily handled by the computer itself. The process of compilation consists of translating statements in a humanreadable programming language into an internal form called machine language while preserving the semantics of the program.

As an illustration, consider the Java expression

To translate this expression into machine language, the compiler must first determine whether it follows the rules for Java expressions and, if so, construct an internal representation of the expression that keeps track of what values are involved in the expression and the order in which the operators need to be executed to determine the proper value. The process of checking the syntax of an expression and constructing the internal form is called parsing.

The output of the parsing phase of a compiler is typically a recursive structure called a parse tree. The parse tree for the sample expression would look something like this:

The structure ...