Ingerman generalised BNF(ID:8012/)

Extensions to BNF to make a true compiler generator

Peter Ingerman, University of Pennsylvania 1959-1963

Note that stacks - called cellar-principle lists in Rutishauser etc are here called "Cafeteria-style last-in-first-out lists". Is this the first use of the terms?

Places
People:
Related languages
BNF => Ingerman generalised BNF   Extension of
References:
  • Ingerman, P. Z. "A new algorithm for algebraic translation" view details Extract: Rationale and description of system
    A new, machine-independent technique for producing a set of control-. commamd-object triplets from a "normal" algebraic expression has been developed at the University of Pennsylvania Computer Center. Input to which the technique is applied consists of slightly modified (edited) algebraic expressions. Output after application of the technique takes the form of the triplets, which are considered by some authorities to be mere basic than the three-address intermediate forms found in some  compilers for commercial computers.
    Each triplet consists of (1) the designation of an object, (2) the command which is to apply to the object and (3) the control point through which the command is exercised. Because this triple level of information appears in a brief form, several advantages accrue. First, many common subexpressions may be eliminated, techuiques such as the "Russian" method may be used to minimize temporary storage needs, and expressions which are permutations of other expressions may be evaluated unambiguously. Second, transitions to specific machine codes may be accomplished easily. In fact, the triplets themselves could serve as the micro-program for a specific machine.
    The triplet list which results from application of the technique may best be described as a step-by-step analysis of what must be done to evaluate the original algebraic expression. The technique which produces the triplets embodies several important features.
    (1) Only one backward scan of the original expression is required during the entire transformation from algebraic notation to triplet notation.
    (2) No redundant characters need be inserted during production.
    (3) "Cafeteria~style" last-in-first-out lists are employed throughout the procedures
    (4) Only necessary triplets are produced.
    This technique is simpler in concept than any of the expression-scanning techniques described in the literature, and it is readily mechanized

          in SESSION: Automatic programming: algorithm translators view details
  • Ingerman, Peter Zilahy "A translation technique for languages whose syntax is expressible in extended Backus Normal Form" view details
          in Symbolic Languages in Data Processing, in the Proceedings of the Symposium organized and edited by the International Computation Centre, Rome, Italy, March 26­31, 1962, Gordon and Beech Science Publishers, 1962. view details
  • Ingerman, Peter Zilahy: "A syntax-oriented compiler for languages whose syntax is expressible in Backus Normal Form and some proposed extensions thereto" Master's Thesis. Philadelphia, Pa. Moore School of Electrical Engineering, University of Pennsylvania 1963. view details
          in Symbolic Languages in Data Processing, in the Proceedings of the Symposium organized and edited by the International Computation Centre, Rome, Italy, March 26­31, 1962, Gordon and Beech Science Publishers, 1962. view details