Browse Prior Art Database

COMPILE-TIME ANALYSIS OF DATA :FIST-FORMAT LIST CORRESPONDENCES

IP.com Disclosure Number: IPCOM000128172D
Original Publication Date: 1979-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 11 page(s) / 34K

Publishing Venue

Software Patent Institute

Related People

Paul Abrahams: AUTHOR [+4]

Abstract

Formatted input-output is available in a number of Programming languages. In the most general case, the correspondence between data items and format items cannot be determined during compilation, and so it is determined dynamically during execution. However, in most pairs of data and format lists that occur in practice, determination of the correspondence is in fact possible during compilation. Although some commercial compilers make this determination, there is little published literature on the subject. In this paper, we briefly examine three areas in which compile-time determination of the data-format correspondence is useful: optimization, program validation, and automatic test data ~jeneration. A formalism for stating the problem is given, and a solution is discussed in terms of formal language theory. Using this formalism, 3n algorithm for determining the correspondence is given, and its appli-cation is illustrated by examples in both PL/I and FORTRAN.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 13% of the total text.

Page 1 of 11

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

COMPILE-TIME ANALYSIS OF DATA :FIST-FORMAT LIST CORRESPONDENCES

Paul Abrahams and Lori Clarke ' aFebruary 1979 ~1 Report No. 010

Compile-Time Analysis of Data List-Format List

Correspondences

Paul Abrahams* Computer Science Department New York University

and

Lori Clarke** Computer and Information Science Department University of Massachusetts *This research was supported in part by the U.S. Department of Energy under contract EY-76-C-03- 3077, and in part by Control Data Corporation under contract C08AA.

**This research was supported in part by AFOSR under contract AFOSR-77-:327, and in part by the National Science Foundation under grant MCS77-021.01.

ABSTRACT

Formatted input-output is available in a number of Programming languages. In the most general case, the correspondence between data items and format items cannot be determined during compilation, and so it is determined dynamically during execution. However, in most pairs of data and format lists that occur in practice, determination of the correspondence is in fact possible during compilation. Although some commercial compilers make this determination, there is little published literature on the subject. In this paper, we briefly examine three areas in which compile-time determination of the data-format correspondence is useful: optimization, program validation, and automatic test data ~jeneration. A formalism for stating the problem is given, and a solution is discussed in terms of formal language theory. Using this formalism, 3n algorithm for determining the correspondence is given, and its appli-cation is illustrated by examples in both PL/I and FORTRAN.

Keywords and key phrases: formats, compilers, program optimization, program validation, test data generation, input-output, static program analysis. i

1. Introduction

Formatted input-output play:; an important role in FORTRAN and PL/I, and is also provided in Algol 68 and in certain Algol extensions. A formatted input-output operation is specified by providing a data list and a format list. The data list specifies the items to be read or written, while the format list specifies how the items are represented on :he input or output medium. In most cases that occur in practice, it is possible to determine during compilation how data items are naire< with format items. That isn'ttoo surprising, since the programmer should have anticipated the correspondence when the data list and format list were composed. Consolidating the two lists into one list of pairs eliminates the need for expensive execution-time linkage mechanisms,

New York University Page 1 Dec 31, 1979

Page 2 of 11

COMPILE-TIME ANALYSIS OF DATA :FIST-FORMAT LIST CORRESPONDENCES

and moreover makes it possible ,to derive information useful in program validation and in automatic test data generation. In this paper, we present an al7orithtn for converting the two lists into a single :List of pairs. Altho...