Utilities - Data Structures and Problem Solving Using Java - page 495

a cross-reference generator

12.2

In this section, we design a program called a cross-reference generator that
scans a Java source file, sorts the identifiers, and outputs all the identifiers,
along with the line numbers on which they occur. One compiler application is
to list, for each method, the names of all other methods that it directly calls.
However, this is a general problem that occurs in many other contexts.
For instance, it can be used to generalize the creation of an index for a book.
Another use, spell checking, is described in Exercise 12.23. As a spelling
checker detects misspelled words in a document, those words are gathered,
along with the lines on which they occur. This process avoids repeatedly
printing out the same misspelled word and indicates where the errors are.

A cross-reference
generator lists iden-
tifiers and their line
numbers. It is a
common applica-
tion because it is
similar to creating
an index.

12.2.1 basic ideas

Our main algorithmic idea is to use a map to store each identifier and the line
numbers on which it occurs. In the map, the identifier is the key, and the list of
line numbers is the value. After the source file has been read and the map
built, we can iterate over the collection, outputting identifiers and their corre-
sponding line numbers.

We use a map to
store identifiers and
their line numbers.
We store the line
numbers for each
identifier in a list.

12.2.2 java implementation

The Xref class skeleton is shown in Figure 12.26. It is similar to (but simpler than)
the Balance class shown in Figure 11.3, which was part of a balanced symbol pro-
gram. Like that class, it makes use of the Tokenizer class defined in Figure 11.2.
We can now discuss the implementation of the two remaining routines in
the Tokenizer class: getNextID and getRemainingString . These new parsing rou-
tines deal with recognizing an identifier.

The routine shown in Figure 12.27 tests whether a character is part of an
identifier. In the getRemainingString routine shown in Figure 12.28 we assume
that the first character of an identifier has already been read and is stored in
the Tokenizer class data member ch . It repeatedly reads characters until one
that is not part of an identifier appears. At that point we put the character back
(at line 12) and then return a String . The StringBuilder is used to avoid
repeated, expensive, String concatenations. Section 15.4 describes the issues
involved.

The parsing rou-
tines are straight-
forward, though as
usual they require
some effort.