Editing Compiler-compiler (section)

==History==
Design of the original compiler-compiler was started by [[Tony Brooker]] and Derrick Morris in 1959, with initial testing beginning in March 1962.<ref>{{Cite web |last=Lavington |first=Simon |date=April 2016 |title=Tony Brooker and the Atlas Compiler Compiler |url=http://curation.cs.manchester.ac.uk/atlas/elearn.cs.man.ac.uk/_atlas/docs/Tony%20Brooker%20and%20the%20Atlas%20Compiler%20Compiler.pdf |url-status=live |access-date=2023-09-29 |archive-date=2023-03-26  |archive-url=https://web.archive.org/web/20230326214708/http://curation.cs.manchester.ac.uk/atlas/elearn.cs.man.ac.uk/_atlas/docs/Tony%20Brooker%20and%20the%20Atlas%20Compiler%20Compiler.pdf }}</ref> The Brooker Morris Compiler Compiler (BMCC) was used to create compilers for the new [[Atlas (computer)|Atlas]] computer at the [[University of Manchester]], for several languages: [[Mercury Autocode]], Extended Mercury Autocode, [[Atlas Autocode]], [[ALGOL 60]] and ASA [[Fortran]]. At roughly the same time, related work was being done by E. T. (Ned) Irons at Princeton, and Alick Glennie at the Atomic Weapons Research Establishment at Aldermaston whose "Syntax Machine" paper (declassified in 1977) inspired the META series of translator writing systems mentioned below.

The early history of metacompilers is closely tied with the history of SIG/PLAN Working group 1 on Syntax Driven Compilers. The group was started primarily through the effort of Howard Metcalfe in the Los Angeles area.<ref name="Metcalfe1"/> In the fall of 1962, Howard Metcalfe designed two compiler-writing interpreters. One used a bottom-to-top analysis technique based on a method described by Ledley and Wilson.<ref name="Ledleyl"/> The other used a top-to-bottom approach based on work by Glennie to generate random English sentences from a context-free grammar.<ref name="Glenniel"/>

At the same time, Val Schorre described two "meta machines", one generative and one analytic. The generative machine was implemented and produced random algebraic expressions. Meta I the first metacompiler was implemented by Schorre on an IBM 1401 at UCLA in January 1963. His original interpreters and metamachines were written directly in a pseudo-machine language. [[META II]], however, was written in a higher-level metalanguage able to describe its own compilation into the pseudo-machine language.<ref name="METAII"/><ref name="SMALGOL"/><ref name="META1"/>

Lee Schmidt at Bolt, Beranek, and Newman wrote a metacompiler in March 1963 that utilized a CRT display on the time-sharing PDP-l.<ref name="Schmidt1"/> This compiler produced actual machine code rather than interpretive code and was partially bootstrapped from Meta I.{{citation needed|date=May 2020}}

Schorre bootstrapped Meta II from Meta I during the spring of 1963. The paper on the refined metacompiler system presented at the 1964 Philadelphia ACM conference is the first paper on a metacompiler available as a general reference. The syntax and implementation technique of Schorre's system laid the foundation for most of the systems that followed. The system was implemented on a small 1401, and was used to implement a small [[ALGOL]]-like language.{{citation needed|date=May 2020}}

Many similar systems immediately followed.{{citation needed|date=May 2020}}

Roger Rutman of [[Aptiv|AC Delco]]<!-- Not the same firm as current brand ACDelco. --> developed and implemented LOGIK, a language for logical design simulation, on the IBM 7090 in January 1964.<ref name="Rutman1"/> This compiler used an algorithm that produced efficient code for Boolean expressions.{{citation needed|date=May 2020}}

Another paper in the 1964 ACM proceedings describes [http://dl.acm.org/citation.cfm?id=808898 Meta III], developed by [http://www.peacham.com/ Schneider] and Johnson at UCLA for the IBM 7090.<ref name="Schneiderl"/> Meta III represents an attempt to produce efficient machine code, for a large class of languages. Meta III was implemented completely in assembly language. Two compilers were written in Meta III, CODOL, a compiler-writing demonstration compiler, and PUREGOL, a dialect of ALGOL 60. (It was pure gall to call it ALGOL).

Late in 1964, Lee Schmidt bootstrapped the metacompiler EQGEN, from the PDP-l to the Beckman 420. EQGEN was a logic equation generating language.

In 1964, System Development Corporation began a major effort in the development of metacompilers. This effort includes powerful metacompilers, Bookl, and Book2 written in [[Lisp (programming language)|Lisp]] which have extensive tree-searching and backup ability. An outgrowth of one of the [[AN/FSQ-32|Q-32]] systems at SDC is Meta 5.<ref name=Oppenheim/> The Meta 5 system incorporates backup of the input stream and enough other facilities to parse any context-sensitive language. This system was successfully released to a wide number of users and had many string-manipulation applications other than compiling. It has many elaborate push-down stacks, attribute setting and testing facilities, and output mechanisms. That Meta 5 successfully translates [[JOVIAL]] programs to [[PL/I]] programs demonstrates its power and flexibility.

Robert McClure at [[Texas Instruments]] invented a compiler-compiler called [[TMG (language)|TMG]] (presented in 1965). TMG was used to create early compilers for programming languages like [[B (programming language)|B]], [[PL/I]] and [[ALTRAN]]. Together with metacompiler of Val Schorre, it was an early inspiration for the last chapter of [[Donald Knuth]]'s ''[[The Art of Computer Programming]]''.<ref>{{cite conference |conference=International Conference on Attribute Grammars and Their Applications| first=Donald |last=Knuth |title=The genesis of attribute grammars |url=https://www.dcs.warwick.ac.uk/~sk/cs325/gag.pdf |location=New York |book-title=Proceedings of the International Conference on Attribute Grammars and Their Applications (Paris, France) |volume=461 |pages=1–12 |editor=P. Deransart |editor2=M. Jourdan |publisher=Springer-Verlag |year=1990 |doi=10.1007/3-540-53101-7_1 |isbn=978-3-540-53101-2 |citeseerx=10.1.1.105.5365 |series=Lecture Notes in Computer Science |access-date=2020-02-06  |archive-date=2020-11-23  |archive-url=https://web.archive.org/web/20201123154647/https://www.dcs.warwick.ac.uk/~sk/cs325/gag.pdf |url-status=live }}</ref>

The LOT system was developed during 1966 at Stanford Research Institute and was modeled very closely after Meta II.<ref name="Kirkleyl"/> It had new special-purpose constructs allowing it to generate a compiler which could in turn, compile a subset of PL/I. This system had extensive statistic-gathering facilities and was used to study the characteristics of top-down analysis.

SIMPLE is a specialized translator system designed to aid the writing of pre-processors for PL/I, SIMPLE, written in PL/I, is composed of three components: An executive, a syntax analyzer and a semantic constructor.<ref name="George"/>

The [[TREE-META]] compiler was developed at Stanford Research Institute in Menlo Park, California. April 1968. The early metacompiler history is well documented in the [http://bitsavers.informatik.uni-stuttgart.de/pdf/sri/arc/rulifson/A_Tree_Meta_For_The_XDS_940_Appendix_D_Apr68.pdf TREE META manual.] TREE META paralleled some of the SDC developments. Unlike earlier metacompilers it separated the semantics processing from the syntax processing. The syntax rules contained [[Tree (data structure)|tree]] building operations that combined recognized language elements with tree nodes. The tree structure representation of the input was then processed by a simple form of unparse rules. The unparse rules used node recognition and attribute testing that when matched resulted in the associated action being performed. In addition like tree element could also be tested in an unparse rule. Unparse rules were also a recursive language being able to call unparse rules passing elements of thee tree before the action of the unparse rule was performed.

The concept of the metamachine originally put forth by Glennie is so simple that three hardware versions have been designed and one actually implemented. The latter at Washington University in St. Louis. This machine was built from macro-modular components and has for instructions the codes described by Schorre.

CWIC (Compiler for Writing and Implementing Compilers) is the last known Schorre metacompiler. It was developed at Systems Development Corporation by Erwin Book, Dewey Val Schorre and Steven J. Sherman With the full power of (lisp 2) a list processing language optimizing algorithms could operate on syntax generated lists and trees before code generation. CWIC also had a symbol table built into the language.

With the resurgence of domain-specific languages and the need for parser generators which are easy to use, easy to understand, and easy to maintain, metacompilers are becoming a valuable tool for advanced software engineering projects.

Other examples of parser generators in the yacc vein are [[ANTLR]], [[Coco/R]],<ref name="Rechenberg-Mössenböck_1985"/> CUP,{{Citation needed|date=March 2012}} [[GNU Bison]], Eli,<ref>{{cite journal|doi=10.1145/129630.129637 |title=Eli: A complete, flexible compiler construction system |year=1992 |last1=Gray |first1=Robert W. |last2=Levi |first2=Steven P. |last3=Heuring |first3=Vincent P. |last4=Sloane |first4=Anthony M. |last5=Waite |first5=William M. |journal=Communications of the ACM |volume=35 |issue=2 |pages=121–130 |s2cid=5121773 |doi-access=free }}</ref> FSL,{{Citation needed|date=March 2012}} [[SableCC]], SID (Syntax Improving Device),<ref>{{cite journal|doi=10.1093/comjnl/11.1.31 |doi-access=free |title=A syntax improving program |year=1968 |last1=Foster |first1=J. M. |journal=The Computer Journal |volume=11 |pages=31–34 }}</ref> and [[JavaCC]]. While useful, pure parser generators only address the parsing part of the problem of building a compiler. Tools with broader scope, such as [[PQCC]], [[Coco/R]] and [[DMS Software Reengineering Toolkit]] provide considerable support for more difficult post-parsing activities such as semantic analysis, code optimization and generation.