February 1964 - Vol. 7 No. 2
Features
Bounded context syntactic analysis
Certain phase structure grammars define languages in which the phrasehood and structure of a substring of a sentence may be determined by consideration of only a bounded context of the substring. It is possible to determine, for any specified bound on the number of contextual characters considered, whether a given grammar is such a bounded context grammar. Such grammars are free from syntactic ambiguity. Syntactic analysis of sentences in a bounded context language may be performed by a standard process and requires a number of operations proportional to the length of sentence analyzed.
Bounded context grammars form models for most languages used in computer programming, and many methods of syntactic analysis, including analysis by operator precedence, are special cases of bounded context analysis.
“Structural connections” in formal languages
This paper defines the concept of “structural connection” in a mechanical language in an attempt to classify various formal languages according to the complexity of parsing structures on strings in the languages. Languages discussed vary in complexity from those with essentially no structure at all to languages which are self-defining. The relationship between some existing recognition techniques for several language classes is examined, as well as implications of language structure on the complexity of automatic recognizers.
One of the most primitive parts of a formula language is its specification of input-output actions within the framework of the language. While the specification is intrinsically more complex, say, than the evaluation of an arithmetic expression, most of the difficulties associated with input-output specification arise from the fact that the desired operations have not been properly defined using the framework of a programming language. Indeed, the complexity largely disappears when a programming language is constructed to specify input-output actions. The point to be made here is that the definition of an appropriate programming language makes more rational and simpler all three phases of the input-output programming cycle: (i) source program construction, (ii) object program construction, (iii) object program execution.
A general business-oriented language based on decision expressions
The structure of a digital computer programming language which covers a wide class of business and file processing applications is presented. Such a structure, based on identifying and incorporating into a compiler the aspects common to all processes of such class, permits writing extremely compact programs, even for comparatively complex applications, in terms of tables of control expressions which express only information characteristic of the particular application. Furthermore, local changes of a process (e.g. changes affecting only one of the output files involved) can be effected by local modifications in the program (e.g. modification of only one entry of the tables). This structure also allows for inexpensive preparation of loading-speed compilers which translate the source programs into efficient machine codes.
The approach adopted here departs from conventional mechanical language design philosophies. It stresses the structural analysis of the class of processes to be represented in the languages, as opposed to emphasizing formal (i.e., contents-independent) syntactical definitions. It relies exclusively on nonprocedural representation of processes as sets (tables) of relations between data and results (there are no control statements such as GO TO, etc.), instead of using procedure descriptions (which are one-to-one translations of flowcharts). Here an invariant pattern of procedure is identified as characteristic of the class of all batch file processes.
Some effects of the 6600 computer on language structures
The problem of compiling efficient 6600 codes prompted the development of an intermediate language reflecting the structure of the machine, that is more easily manipulated in improving object program efficiency. The subject of this paper is the intermediate language and methods of manipulating it.
Compilations of a series of arithmetic statements are discussed. It is assumed that all functions and exponentials have been removed from these statements, and replaced by simple variables. For purposes of simplicity the treatment of subscripts is ignored.
A simplified 6600 structure is presented to illustrate the compiling method. Several assumptions are made for purposes of simplification, although there are cases in which the assumptions are violated in the actual machine.
A programming package for some general modes of arithmetic
An interpretive programming package is described for computation with operands which may be real, complex, single or double precision, or real multiple precision. It also performs operations on matrices formed from these elements. A simple language structure is used to describe the computation.
On context and ambiguity in parsing
This note is by way of commentary on the notions of “bounded context” of Floyd [1] and “structural connections” of Irons [2], as these notions relate to as yet unpublished researches growing out of the development of the author's Algorithmic Theory of Language [3, 4]. In the closing paragraphs of [3], the author made comments concerning further developments of the theory which would include “context dependence” and “resolution of apparent syntactic ambiguities.” The work on parsing reported here was carried out in early September, 1962 (an earlier version in March, 1962), but has not been polished or reduced to final form because, for the purpose of the total theory, parsing should not be considered separately, and the complexities of the proper treatment of the “precedence string” (which relates to semantic structure as distinct from syntactic structure of parsing) have not yet been satisfactorily resolved.
The topics began with discussion of almost exclusively syntactic analysis and methods. Beginning with context-free phrase-structure languages, we considered limitations thereof to remove generative syntactic ambiguities (Floyd), and extensions thereto to introduce more context-dependence (Rose). As the conference proceeded we ran through a spectrum of considerations in which the expressions in the languages considered were examined less and less as meaningless objects (the formal, or purely syntactic approach, as in the paper by Steel) and required more and more meaningful interpretations. In other words, we became more and more involved with semantic considerations. It is clear, then, that applications of the study of mechanical languages to programming must involve semantic questions; ADD must mean something more than the concatenation of three (not two) characters. The papers beyond Session 1 were therefore discussing the mechanization of semantics, but in only one case did we hear about the formalization (and hence mechanization) of the specification of the semantics of a language (McCarthy).
