Chapter 10.4 – Programming with the Collection Framework | Introduction to Programming Using Java

10.4 Programming with the Collection Framework

In this section, we’ll look at some programming examples that use classes from the Java Collection Framework. The Collection Framework is easy to use, especially compared to the difficulty of programming new data structures from scratch.

10.4.1 Symbol Tables

We begin with a straightforward but important application of maps. When a compiler reads the source code of a program, it encounters definitions of variables, subroutines, and classes. The names of these things can be used later in the program.

The compiler has to remember the definition of each name, so that it can recognize the name and apply the definition when the name is encountered later in the program. This is a natural application for a Map. The name can be used as a key in the map. The value associated to the key is the definition of the name, encoded somehow as an object. A map that is used in this way is called a symbol table.

In a compiler, the values in a symbol table can be quite complicated, since the compiler has to deal with names for various sorts of things, and it needs a different type of information for each different type of name. We will keep things simple by looking at a symbol table in another context.

Suppose that we want a program that can evaluate expressions entered by the user, and suppose that the expressions can contain variables, in addition to operators, numbers, and parentheses. For this to make sense, we need some way of assigning values to variables. When a variable is used in an expression, we need to retrieve the variable’s value.

A symbol table can be used to store the data that we need. The keys for the symbol table are variable names. The value associated with a key is the value of that variable, which is of type double. The symbol table will be an object of type Map<String,Double>. (Remember that primitive types such as double can’t be used as type parameters; a wrapper class such as Double must be used instead. See Subsection 10.1.7.)

To demonstrate the idea, we’ll use a rather simple-minded program in which the user types commands such as:

The program is an interpreter for a very simple language. The only two commands that the program understands are “print” and “let”. When a “print” command is executed, the computer evaluates the expression and displays the value. If the expression contains a variable, the computer has to look up the value of that variable in the symbol table. A “let” command is used to give a value to a variable.

The computer has to store the value of the variable in the symbol table. (Note: The “variables” I am talking about here are not variables in the Java program. The Java program is executing a sort of program typed in by the user. I am talking about variables in the user’s program. The user gets to make up variable names, so there is no way for the Java program to know in advance what the variables will be.)

In Subsection 9.5.2, we saw how to write a program, SimpleParser2.java, that can evaluate expressions that do not contain variables. Here, I will discuss another example program, SimpleInterpreter.java, that is based on the older program. I will only talk about the parts that are relevant to the symbol table.

The program uses a HashMap as the symbol table. A TreeMap could also be used, but since the program does not need to access the variables in alphabetical order, we don’t need to have the keys stored in sorted order. The symbol table in the program is represented by a variable named symbolTable of type HashMap<String,Double>. At the beginning of the program, the symbol table object is created with the command:

This creates a map that initially contains no key/value associations. To execute a “let” command, the program uses the symbol table’s put() method to associate a value with the variable name. Suppose that the name of the variable is given by a String, varName, and the value of the variable is stored in a variable val of type double. The following command would then set the value associated with the variable in the symbol table:

In the program SimpleInterpreter.java, you’ll find this in the method named doLetCommand(). The actual value that is stored in the symbol table is an object of type Double. We can use the double value val in the call to put because Java does an automatic conversion of type double to Double when necessary. The double value is “wrapped” in an object of type Double, so that, in effect, the above statement is equivalent to symbolTable.put( varName, new Double(val) );

Just for fun, I decided to pre-define two variables named “pi” and “e” whose values are the usual mathematical constants π and e. In Java, the values of these constants are given by Math.PI and Math.E. To make these variables available to the user of the program, they are added to the symbol table with the commands:

When the program encounters a variable while evaluating an expression, the symbol table’s get() method is used to retrieve its value. The function symbolTable.get(varName) returns a value of type Double. It is possible that the return value is null; this will happen if no value has ever been assigned to varName in the symbol table. It’s important to check this possibility. It indicates that the user is trying to use a variable that the user has not defined. The program considers this to be an error, so the processing looks something like this:

You will find this code, more or less, in a method named primaryValue() in SimpleInterpreter.java.

As you can see from this example, Maps are very useful and are really quite easy to use.

Chapter 10.4 – Programming with the Collection Framework | Introduction to Programming Using Java

10.4 Programming with the Collection Framework

10.4.1 Symbol Tables

SEE MORE:

1 thought on “Chapter 10.4 – Programming with the Collection Framework | Introduction to Programming Using Java”

Leave a Comment Cancel reply