Tmg
- This article is not detailed enough and needs to be expanded. Please help us by adding some more information.
| Designed by | Robert M. McClure |
|---|---|
| Appeared in | 1963 |
| Computational class | Unknown |
| Reference implementation | [1] |
| Influenced | TROL, wikipedia:YACC |
[TMG] was a backtracking recursive descent compiler that could compile almost anything but was unbearably slow and, if it encountered a syntax error would backtrack back to the first character of the input file and say, in effect, "something's wrong in here somewhere". ~ S. C. Johnson
Tmg, also known as TMGL or Transmogrifier, is a language for expressing syntax-directed compilers. It is named after the tool TMG, originally developed by Robert M. McClure to develop PL/I and later reimplemented by Douglas McIlroy for UNIX.
History
McClure's original version of TMG was proprietary and intended for commercialization. In 1969, McIlroy hand-wrote a clean specification of Tmg in Tmg on paper, including syntax-directed compilation to the PDP-7. McIlroy then hand-wrote the self-application of that specification as PDP-7 assembler mnemonics on paper and typed it into Ken Thompson's editor. After fixing several bugs, McIlroy and Thompson had a working TMG on UNIX, and had therefore successfully performed Tmg's first metacompilation.
Thompson then attempted to implement FORTRAN in Tmg. This project was unsuccessful due to a lack of space on the PDP-7, but led to the development of B and eventually C.
Examples
As with all UNIX toolchains, there is a hello-world program:
program: parse(hello) ;
hello: = { <Hello, World!> * } ;
The following program (McIlroy, 1972) shows that Tmg is powerful enough to recognize non-context-free languages by recognizing the non-regular language `a{n}b{n}c{n}`.
f: proc(x) <a> f(( <b> x )) <c> | x ; program: parse(( f(()) )) ;
References
- TMG: a syntax-directed compiler, McClure 1965
- A Manual for the Tmg Compiler-writing Language, McIlroy 1972
- [2] Kernighan & Thompson 2019
- [3] a portable C version of TMG