State transition language(ID:7589/)

State transition definition language proposed by Conway, Spiel and Speroni at CASE in 1962/3 to define compilers
References:
  • Conway, Melvin E. "Design of a separable transition-diagram compiler" view details Abstract: A COBOL compiler design is presented which is compact
    enough to permit rapid, one-pass compilation of a large subset
    of COBOL on a moderately large computer. Versions of
    the same compiler for smaller machines require only two working
    tapes plus a compiler tape. The methods given are largely
    applicable to the construction of ALGOL compilers.
          in [ACM] CACM 6(07) July 1963 view details
  • Conway, Melvin E. and Speroni, Joseph "Arithmetizing declarations: an application to COBOL" view details Abstract: The compiling technique of discovering the syntactical structure of a well-formed formula of a language by using a "syntax-directed" analysis [i], as opposed to incorporating the analysis in machine code, is equivalent in idea to performing a calculation with an interpretive system instead of coding it directly in machine language. The direct method is potentially the faster because interpretation is not required, but in many eases the interpretive method requires significantly less storage and is therefore chosen
    by necessity. Certain methods not available to the purist render the speed difference between the interpretive and direct methods imperceptible; with the availability of these methods the use of syntax-directed techniques becomes the only rational choice. Such techniques have been used at the Case Institute of Technology in the design of a two-pass COBOL translator whose anticipated processing speed (measured in terms of the number of average machine instructions required to translate completely one input character) is comparable to that of the fastest algebraic translators in existence.

    This paper discusses a problem in the design of every COBOL processor: gleaning information from the item description entries of the Data Division. It will be seen that the solution presented here is an "interpretive" rather than a "direct" one, in the sense that the specification to the processor of predefined interrelationships among elements of the source language is expressed not in machine
    code but in some nonmachine language which is interpreted during compilation.
    The entries of COBOL item descriptions contain clauses like "USAGE IS COMPUTATIONAL" which ascribe properties to the item in question; in this case the item is declared to occur predominantly in arithmetic calculations the item is numeric by implication and therefore the clause named renders the clause "CLASS IS NUMERIC" superfluous. At the same time it would render the clause "CLASS IS ALPHABETIC" contradictory The goal sought here is to devise an arithmetic procedure which 1) makes clear all of the properties declared, both explicitly and implicitly, and 2) discovers any inconsistencies among these properties. Those who take seriously the application of these goals to COBOL know that the problem is not simple. There is hope that the methods presented here have more general utility in semantic analysis, e.g., resolution of meaning in mechanical translation and the forinalization of the fringe area between syntax and semantics of formal languages.
          in [ACM] CACM 6(01) (January 1963) view details
  • Leavenworth, B. review of Conway (STL) view details Abstract: This paper is a clearly written exposition of some interesting ideas used in the construction of a COBOL compiler. The most interesting concept is that of coroutines which can be used to segment a one-pass compiler into various configurations. By essentially changing the read and write linkages of these routines, they can be executed either alternately or serially, provided that the compiler has been designed to have a separable property. Another technique is the use of transition tables by a recursive control program called a diagrammer. As the author concedes, the diagrams are constructed "by a process which is neither straightforward nor easy to describe," since they must satisfy the "no-backup condition." This condition requires that all like prefixes in the productions of the language be factored out.

    The remainder of the paper describes the generation of reverse Polish intermediate language by the diagrammer, the treatment of date name qualification, and the generation of object code (forward references have to be fixed up by a onepass translator at load time).

    The author questions the practice of using compilers to write compilers, and suggests that the front end of any fast compiler will be written with an assembler (the speed of the NELIAC compilers would seem to refute this) because of the fact that most of the time is spent on lexical analysis (compression of names and operators to internal representation). While this proposition may be true for COBOL, it does not necessarily follow for ALGOL type languages.
          in ACM Computing Reviews 5(01) January-February 1964 view details