Search

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]

An algorithm is described which accepts an arbitrary context-free grammar and constructs a bounded-context parser for it whenever such a parser exists. In the first part of the paper the definition of a context-free grammar and the working of a bounded-context parser are recalled. The notion of reduction class for a context-free gram- mar is then introduced and its connection with the structure of a bounded-context parser is indicated. Next, pushdown automata which generate the different reduction classes of a Context-free grammar ore defined. Finally, the algorithm is described; it essentially carries out an exhaustive study of all possible runs of the pushdown automata generating the reduction classes, In the second part, the utility of the algorithm is discussed in the light of the experience gained from its use in compiler design. The algorithm is claimed to be particularly useful in the simultaneous design of a language and a compiler for it. [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]

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.