Compiler Algorithms and Data Table Design for COBOL

Key Insight

Designing a COBOL compiler requires three primary algorithms: Operation 1, to process name and level number descriptions into internal tables; Operation 2, to validate qualified references and locate the corresponding data items; and Operation 3, to identify all corresponding item pairs for 'MOVE CORRESPONDING' statements. These operations rely on a 'Symbol Table' that maps alphabetic names to their entries, and a larger 'Data Table' containing one entry for each data item in the COBOL source program.

The Data Table entries are designed with five specific link fields to efficiently support Operations 2 and 3. These links are: PREV (linking to the previous entry with the same name, if any), PARENT (linking to the smallest containing group), NAME (linking to the Symbol Table entry for the item), CHILD (linking to the first subitem of a group), and SIB (linking to the next subitem within the same group). The PARENT, CHILD, and SIB links collectively form a triply linked tree structure, while PREV and NAME links superimpose additional crucial information for navigation and reference resolution.

These five links significantly enhance the speed of Algorithms B and C by making addresses immediately available, virtually eliminating the need for searches. PREV links are critical for Algorithm B's efficiency in finding specific named items. PARENT links are utilized in both Algorithms B and C. NAME links are essential for fast name comparisons in steps like B6 and C3, directly impacting the speed of inner loops. Although not all links are strictly essential and some redundancy exists, this 'complete set' optimizes the algorithms, making them fast. While Algorithm A, which builds the table, runs slower due to filling these links, this is a one-time operation. Historically, similar five-link (or four-link) Data Table designs were independently developed by COBOL compiler writers in the early 1960s, with later techniques like David Dahm's in 1965 achieving comparable effects with just two links.