1,205 papers · page 60 of 61
Described is a method for syntactic error recovery that is compatible with deterministic parsing methods and that is able to recover from many errors more quickly than do other schemes because it performs global context recovery. The method relies on fiducial symbols, which are t…
The cost (expected number of accesses per retrieval) of hashing functions is examined without the assumption that it is equally probable for all keys to be present in the table. It is shown that the obvious strategy—trying to balance the sums of probabilities of the keys mapped t…
A method is presented for parsing syntactic constructs that are permitted to appear independently anywhere in a program. Some examples include comments, macros, and constructs for conditional compilation. Each such construct is defined by its own grammar and parsed by a separate …
A class of parallel processors potentially involving thousands of individual processing elements is described. The architecture is based on the perfect shuffle connection and has two favorable characteristics: (1) Each processor communicates with a fixed number of other processor…
The portable programming language (PPL) is one of a number of recently designed programming languages that enable the user to define new types by giving their representations and operations in terms of those of previously available types. Such provisions for the construction of o…
A simple dynamic allocation algorithm is described for queuing variable length messages in memory. The algorithm makes use of the ability of many operating system to increase and decrease available memory as required. Some results describing its efficiency are presented.
List structures provide a general mechanism for representing easily changed structured data, but can introduce inefficiencies in the use of space when fields of uniform size are used to contain pointers to data and to link the structure. Empirically determined regularity can be e…
We describe a means of presenting hierarchically organized formal definitions of programming languages using the denotational approach of D. Scott and C. Strachey. As an example of our approach, we give the semantics of PL/CS, an instructional variant of PL/I. We also discuss the…
“Pure” SETL is a language of very high level allowing algorithms to be programmed rapidly and succintly. SETL's representation sublanguage adds a system of declarations which allow the user of the language to control the data structures that will be used to implement an algorithm…
An incremental parser is a device which is able to perform syntax analysis in an incremental way, avoiding complete reparsing of a program after each modification. The incremental parser presented extends the conventional LR parsing algorithm and its performance is compared with …
The “intermittent assertion” method for proving programs correct is explained and compared with the conventional method. Simple conventional proofs of iterative algorithms that compute recursively defined functions, including Ackermann's function, are given.
Although operators, which apply to functions to produce functions, prove very useful in mathematics, they are absent from most programming languages. This paper illustrates their simplicity and power in terms of the operators of APL, and examines related constructs in other progr…
The problem of semantic evaluation in a compiler-generating system can be addressed by specifying language semantics in an attribute grammar [19], a context-free grammar augmented with “attributes” for the nonterminals and “semantic functions” to compute the attributes. A determi…
In his recent paper, “Communicating Sequential Processes” ( Comm. ACM 21, 8 (Aug. 1978), 666-677), C.A.R. Hoare outlines a programming language notation for interprocess communication in which processes are synchronized by the messages they exchange. The notation carries with it …
A new, nonassertional approach to proving multiprocess program correctness is described by proving the correctness of a new algorithm to solve the mutual exclusion problem. The algorithm is an improved version of the bakery algorithm. It is specified and proved correct without be…
A fast algorithm for finding dominators in a flowgraph is presented. The algorithm uses depth-first search and an efficient method of computing functions defined on paths in trees. A simple implementation of the algorithm runs in O ( m log n ) time, where m is the number of edges…
Backtracking is a powerful conceptual and practical programming language control structure. However, its application in general has been limited to global control over recursive programs. In this paper we explore the coherence and utility of applying backtracking in a more genera…
A practical method is presented for automating in a uniform way the verification of Pascal programs that operate on the standard Pascal data structures Array, Record, and Pointer. New assertion language primitives are introduced for describing computational effects of operations …
A method for combining decision procedures for several theories into a single decision procedure for their combination is described, and a simplifier based on this method is discussed. The simplifier finds a normal form for any expression formed from individual variables, the usu…
The scientific community has consistently demanded from computing machines an increase in the number of instructions executed per second. The latest increase has been achieved by duplication of arithmetic units for an array processor and the pipelining of functional units for vec…