February 1970 - Vol. 13 No. 2

A parsing algorithm which seems to be the most efficient general context-free algorithm known is described. It is similar to both Knuth's LR(k) algorithm and the familiar top-down algorithm. It has a time bound proportional to n3 (where n is the length of the string being parsed) in general; it has an n2 bound for unambiguous grammars; and it runs in linear time on a large class of grammars, which seems to include most practical context-free programming language grammars. In an empirical comparison it appears to be superior to the top-down and bottom-up algorithms studied by Griffiths and Petrick.

Some of the problems of simulating discrete event systems, particularly computer systems, on a conventional digital computer are dealt with. The systems are assumed to be described as a network of interconnected sequential processes. Briefly reviewed are the common techniques used to handle such simulations when simultaneous events do not occur, can be ignored, or can be handled by simple priority rules. Following this, the problem of dealing with simultaneous events in separate processes is introduced. An abstraction of this problem is developed which admits solution for a majority of commonly encountered problems. The technique will either find a method of simulating the parallel events or report that none can be found. In some of the latter cases it is shown to be possible to find a solution by extending the information available to the solution technique, but in many cases the technique becomes computationally unfeasible when the additional information is provided.

The principles of address calculation and merging are combined to yield an efficient sorting technique. Detailed flowcharts of the most important program steps are included. The characteristics of the proposed sort are discussed.

Secondary clustering as a cause of hash code inefficiency is discussed, and a new hashing method based on its eliminiation is presented. Comparisons with previous methods are made both analytically and empirically.

Several years of experience have led to the belief that the creative design and evaluation of management information systems requires a thorough understanding of the related computer technology. Concepts such as paging and priority interrupt systems can best be explained at the machine language level. Any machine used for exposition should fulfill several criteria. It should: (1) raise as few spurious issues as possible; (2) allow, without undue effort, the solution of interesting problems; (3) be capable of exposing all outstanding issues of significance, within the chosen machine; (4) be useful for pursuing issues in great depth when appropriate; (5) not be committed to the equipment provided by any manufacturer; (6) be able to provide the student with diagnostic aids to a great depth; (7) allow the student ready access to the machine; (8) be capable of extension to expose new issues as they come along. We have constructed a simulated machine and its associated software which meets these criteria. This system, called the PRISM system, is documented by a primer and a reference manual.

An interactive computer system operational on a graphical computer terminal is described. This system was designed to demonstrate a method of programming by computer interpretation of a flowchart. The user draws a description of a sampled-data system and specifies an original input signal on a display oscilloscope. This graphical description is transmitted to a large scale computer. The design is simulated, and a graphic representation of the processed signal is returned to the scope. A successful design may require numerous modifications of the original design. A graphical interactive system provides an environment to perform this iterative process efficiently and effectively.