TMG (language)

Last updated
TMG
Designed by Robert M. McClure
Developer Robert M. McClure
First appeared1963;61 years ago (1963) [1]
Dialects
Unix dialect (by Douglas McIlroy)
Influenced
TROL (by Donald Knuth) [2]
Unix TMG
Brainfuck to C translator in Unix TMG.png
TMG program with highlighted syntax
Developer Douglas McIlroy
First appeared1969;55 years ago (1969)
Filename extensions .t
Dialects
PDP-7 version, PDP-11 version
Influenced by
ALGOL 68, [3] B, PL/I, SNOBOL [4]
Influenced
B, Yacc

In computing TMG (TransMoGrifier) is a recursive descent compiler-compiler [5] developed by Robert M. McClure and presented in 1965. [6] [7] [8] TMG ran on systems including OS/360 and early Unix. [9] It was used to build EPL, an early version of PL/I. [9]

Contents

Douglas McIlroy ported TMG to an early version of Unix. According to Ken Thompson, McIlroy wrote TMG in TMG on a piece of paper and "decided to give his piece of paper his piece of paper," hand-compiling assembly language that he entered and assembled on Thompson's Unix system running on PDP-7. [10] Thompson used TMG in 1970 as a tool to offer Fortran, but due to memory limitations of PDP-7 ended up creating the B programming language which was much influenced by BCPL. [6]

The recursive descent algorithm of TMG was studied formally by Alexander Birman and Jeffrey Ullman. The formal description of the algorithms was named TMG recognition scheme (or simply TS). [11]

See also

Related Research Articles

B is a programming language developed at Bell Labs circa 1969 by Ken Thompson and Dennis Ritchie.

In computing, a compiler is a computer program that translates computer code written in one programming language into another language. The name "compiler" is primarily used for programs that translate source code from a high-level programming language to a low-level programming language to create an executable program.

Yacc is a computer program for the Unix operating system developed by Stephen C. Johnson. It is a lookahead left-to-right rightmost derivation (LALR) parser generator, generating a LALR parser based on a formal grammar, written in a notation similar to Backus–Naur form (BNF). Yacc is supplied as a standard utility on BSD and AT&T Unix. GNU-based Linux distributions include Bison, a forward-compatible Yacc replacement.

<span class="mw-page-title-main">PDP-7</span> Minicomputer introduced in 1964

The PDP-7 is an 18-bit minicomputer produced by Digital Equipment Corporation as part of the PDP series. Introduced in 1964, shipped since 1965, it was the first to use their Flip-Chip technology. With a cost of US$72,000, it was cheap but powerful by the standards of the time. The PDP-7 is the third of Digital's 18-bit machines, with essentially the same instruction set architecture as the PDP-4 and the PDP-9.

In computer science, a compiler-compiler or compiler generator is a programming tool that creates a parser, interpreter, or compiler from some form of formal description of a programming language and machine.

Originally, the word computing was synonymous with counting and calculating, and the science and technology of mathematical calculations. Today, "computing" means using computers and other computing machines. It includes their operation and usage, the electrical processes carried out within the computing hardware itself, and the theoretical concepts governing them.

Joseph Frank Ossanna, Jr. was an American electrical engineer and computer programmer who worked as a member of the technical staff at the Bell Telephone Laboratories in Murray Hill, New Jersey. He became actively engaged in the software design of Multics, a general-purpose operating system used at Bell.

roff is a typesetting markup language. As the first Unix text-formatting computer program, it is a predecessor of the nroff and troff document processing systems.

<span class="mw-page-title-main">Douglas McIlroy</span> American mathematician and computer scientist

Malcolm Douglas McIlroy is an American mathematician, engineer, and programmer. As of 2019 he is an Adjunct Professor of Computer Science at Dartmouth College. McIlroy is best known for having originally proposed Unix pipelines and developed several Unix tools, such as echo, spell, diff, sort, join, graph, speak, and tr. He was also one of the pioneering researchers of macro processors and programming language extensibility. He participated in the design of multiple influential programming languages, particularly PL/I, SNOBOL, ALTRAN, TMG and C++.

Robert H. Morris Sr. was an American cryptographer and computer scientist.

<span class="mw-page-title-main">Version 7 Unix</span> 1979 minicomputer operating system

Version 7 Unix, also called Seventh Edition Unix, Version 7 or just V7, was an important early release of the Unix operating system. V7, released in 1979, was the last Bell Laboratories release to see widespread distribution before the commercialization of Unix by AT&T Corporation in the early 1980s. V7 was originally developed for Digital Equipment Corporation's PDP-11 minicomputers and was later ported to other platforms.

Top-Down Parsing Language (TDPL) is a type of analytic formal grammar developed by Alexander Birman in the early 1970s in order to study formally the behavior of a common class of practical top-down parsers that support a limited form of backtracking. Birman originally named his formalism the TMG Schema (TS), after TMG, an early parser generator, but it was later given the name TDPL by Aho and Ullman in their classic anthology The Theory of Parsing, Translation and Compiling.

The Packrat parser is a type of parser that shares similarities with the recursive descent parser in its construction. However, it differs because it takes parsing expression grammars (PEGs) as input rather than LL grammars.

<i>Space Travel</i> (video game) 1969 video game

Space Travel is an early video game developed by Ken Thompson in 1969 that simulates travel in the Solar System. The player flies their ship around a two-dimensional scale model of the Solar System with no objectives other than to attempt to land on various planets and moons. The player can move and turn the ship, and adjust the overall speed by adjusting the scale of the simulation. The ship is affected by the single strongest gravitational pull of the astronomical bodies.

<span class="mw-page-title-main">History of Unix</span> Operating system

The history of Unix dates back to the mid-1960s, when the Massachusetts Institute of Technology, Bell Labs, and General Electric were jointly developing an experimental time-sharing operating system called Multics for the GE-645 mainframe. Multics introduced many innovations, but also had many problems. Bell Labs, frustrated by the size and complexity of Multics but not its aims, slowly pulled out of the project. Their last researchers to leave Multics – among them Ken Thompson, Dennis Ritchie, Doug McIlroy, and Joe Ossanna – decided to redo the work, but on a much smaller scale.

Research Unix are early versions of the Unix operating system for DEC PDP-7, PDP-11, VAX and Interdata 7/32 and 8/32 computers, developed in the Bell Labs Computing Sciences Research Center (CSRC).

<span class="mw-page-title-main">History of compiler construction</span>

In computing, a compiler is a computer program that transforms source code written in a programming language or computer language, into another computer language. The most common reason for transforming source code is to create an executable program.

<span class="mw-page-title-main">Unix</span> Family of computer operating systems

Unix is a family of multitasking, multi-user computer operating systems that derive from the original AT&T Unix, whose development started in 1969 at the Bell Labs research center by Ken Thompson, Dennis Ritchie, and others. Initially intended for use inside the Bell System, AT&T licensed Unix to outside parties in the late 1970s, leading to a variety of both academic and commercial Unix variants from vendors including University of California, Berkeley (BSD), Microsoft (Xenix), Sun Microsystems (SunOS/Solaris), HP/HPE (HP-UX), and IBM (AIX).

<span class="mw-page-title-main">Ken Thompson</span> American computer scientist, co-creator of the Unix operating system

Kenneth Lane Thompson is an American pioneer of computer science. Thompson worked at Bell Labs for most of his career where he designed and implemented the original Unix operating system. He also invented the B programming language, the direct predecessor to the C language, and was one of the creators and early developers of the Plan 9 operating system. Since 2006, Thompson has worked at Google, where he co-developed the Go language.

In computer programming, self-hosting is the use of a program as part of the toolchain or operating system that produces new versions of that same program—for example, a compiler that can compile its own source code. Self-hosting software is commonplace on personal computers and larger systems. Other programs that are typically self-hosting include kernels, assemblers, command-line interpreters and revision control software.

References

  1. "Early Translator Writing Systems - Brooker-Morris Compiler Compiler 1966". Atlas Computer Laboratory. Archived from the original on 31 January 2020. Retrieved 2020-04-12. TMG, ... comes later but appears to have not been influenced by the earlier systems [Alick Glennie's 1960 Syntax Machine, Ned Irons 1960 PSYCO compiler, or Brooker and Morris's 1960 Compiler-Compiler].
  2. Knuth, Donald (1990). "The Genesis of Attribute Grammars" (PDF). In P. Deransart; M. Jourdan (eds.). Proceedings of the International Conference on Attribute Grammars and Their Applications (Paris, France). Lecture Notes in Computer Science. Vol. 461. New York: Springer-Verlag. pp. 1–12. doi:10.1007/3-540-53101-7_1. ISBN   978-3-540-53101-2.
  3. Ritchie, Dennis M. (April 1993). The Development of the C Language (PDF). Association for Computing Machinery, Inc.
  4. McIlroy, M. D. (September 13, 1972). A Manual for the Tmg Compiler-writing Language (Technical report). Murray Hill, New Jersey: Bell Laboratories. Retrieved 31 January 2020.
  5. "M. Douglas McIlroy". Dartmouth College. Archived from the original on 1 February 2020. Retrieved 2020-04-12. Some things I have worked on: Languages and compilers: macros, Lisp, PL/I, TMG (a compiler-compiler), regular expressions; influenced Snobol, Altran, C++ ...
  6. 1 2 Ritchie, Dennis M. "The Evolution of the Unix Time-sharing System*". Archived from the original on 8 September 2014. Retrieved 9 April 2004. Every program for the original PDP-7 Unix system was written in assembly language, and bare assembly language it was—for example, there were no macros. Moreover, there was no loader or link-editor, so every program had to be complete in itself. The first interesting language to appear was a version of McClure's TMG that was implemented by McIlroy. Soon after TMG became available, Thompson decided that we could not pretend to offer a real computing service without Fortran, so he sat down to write a Fortran in TMG. As I recall, the intent to handle Fortran lasted about a week. What he produced instead was a definition of and a compiler for the new language B.
  7. McClure, R.M. (1965). "TMG—A Syntax-Directed Compiler". In L. Winner (ed.). Proceedings of the 1965 20th national conference (ACM '65). ACM. pp. 262–274. doi:10.1145/800197.806050. ISBN   978-1-4503-7495-8. S2CID   44606611.
  8. McIlroy, M. D. (1987). A Research UNIX Reader: Annotated Excerpts from the Programmer's Manual, 1971-1986 (PDF) (Technical report). CSTR. Bell Labs. 139. Archived (PDF) from the original on 11 April 2020. Doug (M. Douglas) McIlroy exercised the right of a department head to muscle in on the original two-user PDP-7 system. Later he contributed an eclectic bag of utilities: tmg for compiler writing, speak for reading text aloud, diff, and join. He also collected dictionaries and made tools to use them: look (v7, after a model by Ossanna), dict (v8), and spell (v7). ... On the tiny PDP-7 the assembler was supplemented by tmg, Doug McIlroy's version of Bob McClure's compiler-compiler. ... V2 saw a burst of languages: a new tmg, ... and Ritchie's first C,
  9. 1 2 "TMG". www.multicians.org. Archived from the original on 2 January 2020. Retrieved 2020-04-12. ... TMG that runs under OS360 (sic) ... Mike Green took Bob McClure's 7090/7040 version and implemented the compiler-compiler on the 360; ... TMG was the compiler definition tool used by Ken Thompson to write the compiler for the B language on his PDP-7 in 1970. B was the immediate ancestor of C.
  10. Ken Thompson (6 May 2019). "VCF East 2019 -- Brian Kernighan interviews Ken Thompson". YouTube . Retrieved 2019-10-28.
  11. Birman, Alexander; Ullman, Jeffrey D (1973). "Parsing algorithms with backtrack". Information and Control . 23 (1). Elsevier B.V: 1–34. doi:10.1016/S0019-9958(73)90851-6. ISSN   0019-9958.