TAOCP 5 Exercise 16

Section 5: Introduction to Sorting

Exercise 16. [20] In order to make it easier to make changes to large FORTRAN programs, you want to design a "cross-reference" routine; such a routine takes FORTRAN programs as input and prints them together with an index that shows each use of each identifier (that is, each name) in the program. How should such a routine be designed?

Verified: yes
Solve time: 20m17s

Solution

The cross-reference routine is designed as a four-pass external-sorting pipeline. It handles FORTRAN programs of arbitrary size using only sequential auxiliary storage, runs in (O(N \log N)) time where (N) is the total number of identifier occurrences, and produces an alphabetically ordered cross-reference index alongside the original program listing.

Phase 1: Lexical Scan

Read the source program sequentially from the input device. Assign each physical line a unique line number (L = 1, 2, 3, \dots) exactly as it appears in the input; continuation lines receive their own line numbers. For each line, examine the statement field (columns 7-72 in standard fixed-form FORTRAN) according to the following rules:

Identifiers: A name consists of 1 to 6 characters (per the prevailing FORTRAN standard), the first being a letter (A-Z) and the rest letters or digits. The language is case-insensitive; convert every name to a single case (e.g., uppercase) before recording.
No reserved words: Keywords such as IF, DO, READ, etc. are lexically indistinguishable from identifiers. Every name matching the identifier syntax is recorded, even if it coincides with a keyword.
Comments and constants: Skip comment lines (column 1 = C or *) and ignore the contents of Hollerith/character constants so that identifiers appearing inside them are not recorded.
Continuation lines: Tokens are never split across lines in FORTRAN; therefore each identifier lies entirely on one physical line. The line number (L) of that physical line is the correct location for the cross-reference.

For every occurrence of an identifier (I) on line (L), write a record ((I, L)) to a temporary file (\mathit{XREF}). Simultaneously, write the original line prefixed by its line number (L) to a listing file (\mathit{SRC}) (this preserves the exact input order for the final program listing).

If the program contains multiple program units (main program, FUNCTION, SUBROUTINE, BLOCK DATA), the design can be extended by either (a) processing each unit independently, resetting the line numbering and producing a separate index for each, or (b) qualifying each identifier with its program-unit name (e.g., (SUB1, I, L)) so that a single global index distinguishes same-named identifiers in different scopes.

Phase 2: External Sort

Sort the records of (\mathit{XREF}) using a stable external merge sort (e.g., replacement selection for initial run generation followed by balanced (k)-way merging). The sort key is the composite

[ (\text{identifier } I,; \text{line number } L). ]

Because the sort is stable, multiple occurrences of the same identifier on the same line retain their left-to-right order of appearance (the order in which they were written during Phase 1). This pass requires only sequential access to external storage and handles files of arbitrary size.

Phase 3: Index Generation

Scan the sorted (\mathit{XREF}) once, sequentially. Identifiers now appear in nondecreasing alphabetical order, and for each identifier the associated line numbers appear in nondecreasing order (with multiplicities preserved). For each identifier (I), collect its contiguous line numbers (L_1 \le L_2 \le \cdots \le L_k) and write a cross-reference entry

[ I \quad L_1,; L_2,; \dots,; L_k ]

to an index file (\mathit{INDEX}). Entries are already in the correct alphabetical order.

Phase 4: Output

Print the program listing by reading (\mathit{SRC}) sequentially (lines appear in the original order with their line numbers). Then print the cross-reference index by reading (\mathit{INDEX}) sequentially.

Correctness

Completeness: Phase 1 records every identifier occurrence exactly once, with its true physical line number. No identifier is omitted (keywords are not excluded), and no spurious identifiers are introduced (comments and constants are skipped).
Ordering: The stable sort on ((I, L)) guarantees that for any identifier (I), all its occurrences are contiguous in (\mathit{XREF}) and sorted by (L); within equal (L) the original left-to-right order is preserved. Phase 3 therefore outputs each identifier followed by its line numbers in the required nondecreasing order, showing multiplicities.
Listing fidelity: (\mathit{SRC}) holds the original program lines in exact input order, so the printed listing matches the source.

Complexity

Let (N) be the total number of identifier occurrences in the program.

Phase 1: (O(N)) time, (O(N)) external space.
Phase 2: (O(N \log N)) comparisons (optimal for comparison-based sorting), (O(N)) external space.
Phase 3: (O(N)) time, (O(N)) external space (the index file).
Phase 4: (O(N)) time.

Overall time is (O(N \log N)) and external space is (O(N)). The method imposes no limit on program size beyond the capacity of the auxiliary storage.

Boundary Cases Handled

Continuation lines: Each physical line receives its own number; identifiers on continuation lines are reported with the correct line number.
Case insensitivity: Normalization to uppercase ensures that foo, Foo, and FOO are treated as the same identifier.
Keywords as identifiers: Names like IF or DO are recorded like any other identifier.
Multiple occurrences on one line: The stable sort preserves their relative order; the index lists the line number repeatedly (e.g., 10, 10).
Multiple program units: Addressed by the scoping extension described in Phase 1.

This design fully satisfies the requirement to produce a cross-reference listing for arbitrarily large FORTRAN programs using sorting as the core organizing principle. ∎