Search

Affix grammars are two-level grammars which are similar to van Wijngaarden's two-level grammars used in the definition of Algol 68. Affix grammars are shown by Koster to be equal in power to van Wijngaarden grammars. They are much more suited to parsing than are the latter, however. Koster, the inventor of affix grammars, suggests a top-down scheme for parsing them, based on recursive procedures. This paper presents a bottom-up scheme for parsing them, based on an extension of Floyd Production Language (FPL). Included is an algorithm, similar to that of DeRemer's, for converting a large class of affix grammars into FPL. The paper concludes by discussing briefly the applicabilities of the conversion algorithm and affix grammars in general, and some possible extensions to Koster's definition of affix grammars. [ABSTRACT FROM AUTHOR]

A comprehensive system for transformational grammar has been designed and implemented on the IBM 360/67 computer. The system deals with the transformational model of syntax, along the lines of Chomsky's Aspects of the Theory of Syntax. The major innovations include a full, formal description of the syntax of a transformational grammar, a directed random phrase structure generator, a lexical insertion algorithm, an extended definition of analysis, and simple problem-oriented programming language in which the algorithm for application of transformations can be expressed. In this paper we present the system as a whole, first discussing the general attitudes underlying the development of the system, then outlining the system and discussing its more important special features. References are given to papers which consider some particular aspect of the system in detail. [ABSTRACT FROM AUTHOR]

The use of the Kleene regular expression notation for describing algebraic language syntax, in particular of ALGOL is described in this paper. A FORTRAN II computer program for carrying out the elimination algorithm of Gorn, similar to Gaussian elimination for linear systems of algebraic equations, is described. This was applied to numerous smaller languages, including some sublanguages of ALGOL. A hand calculation result of the application of the algorithm to all of ALGOL is given, thus expressing the Revised ALGOL 1960 syntax in completely nonrecursive terms, as far as its context-free portion is concerned. This description in many ways is far more intuitively understood than the previous recursive description, it is suggested. The paper also includes results of the machine program, which does not include a simplification algorithm. [ABSTRACT FROM AUTHOR]

For the segmentation of a program it is useful to have a reasonable estimation of the values of Sij, where Sij is the mean value of the number of jumps from the ith instruction on to the ith instruction in the run time. In the cases where the Sij, are estimated directly, the structure of the whole program must be generally taken into account; therefore it is very difficult for the programmer and/or the translator to obtain a good estimation of the Sij. It is easier to estimate not Sij, but the quantities pij = Sij·ci,/∑jN=1 Sij, where c, is an arbitrary positive constant for each i. Although the pij are, for each i, proportional to Sij, the estimation of pij is easier, because we must estimate only the "probabilities" of events where instruction lj, is executed after instruction li. This estimation can often be done without considering the structure of the whole program. In the first part of the paper, using the theory of the Markov chains, an algorithm for the computation of the Sij from the p , is found, and some ways of obtaining estimates of the pij are given. In the second part a variant of this algorithm is derived, avoiding the necessity of computation involving large matrices. [ABSTRACT FROM AUTHOR]

A method for returning registers to the free list is an essential part of any list processing system. In this paper, past solutions of the recovery problem are reviewed and compared. A new algorithm is presented which offers significant advantages of speed and storage utilization. The routine for implementing this algorithm can be written in the list language with which it is to be used, thus insuring a degree of machine independence. Finally, the application of the algorithm to a number of different list structures appearing in the literature is indicated. [ABSTRACT FROM AUTHOR]

This paper deals with algorithms concerning arithmetic expressions used in a FORTRAN IV compiler for a HITAC.5020 computer having n accumulators. The algorithms generate an object code which minimizes the frequency of storing and recovering the partial results of the arithmetic expressions in cases where there are several accumulators. [ABSTRACT FROM AUTHOR]

The article focuses on a paper indicating the error of algorithmic language ALGOL 60 pointed up by the Algorithm 355 construct in the October 1969 issue of the periodical "Communications of the Automation for Computing Machinery." The procedure statement "p" occurs in the body of this procedure, showing "p" to be a procedure without parameters. As originally submitted, the algorithm contained several procedure statements in which p was replaced by a procedure statement. It is possible that the authors of ALGOL 60 intended to permit this but they did not do so. The author's original form may have been more in the sprit of the ALGOL 60 report but the published form confirms to the syntax of ALGOL 60 as described in the report.