Content deleted Content added
Citation bot (talk | contribs) Removed URL that duplicated identifier. | Use this bot. Report bugs. | #UCB_CommandLine |
m →Variants: HTTP to HTTPS for SourceForge |
||
| (One intermediate revision by one other user not shown) | |||
Line 4:
{{Use dmy dates|date=January 2020|cs1-dates=y}}
In [[computer science]], a '''compiler-compiler''' or '''compiler generator''' is a [[programming tool]] that creates a [[Parsing#Computer_languages|parser]], [[interpreter (computer software)|interpreter]], or [[compiler]] from some form of formal description of a [[programming language]] and machine.
The most common type of compiler-compiler is called a '''parser generator'''.<ref>{{cite book |title=Compilers : principles, techniques, & tools |date=2007 |others=Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman, Alfred V. Aho |isbn=978-0-321-48681-3 |edition=Second |___location=Boston |page=287 |oclc=70775643}}</ref> It handles only [[syntactic analysis]].
Line 21:
One of the earliest (1964), surprisingly powerful, versions of compiler-compilers is [[META II]], which accepted an analytical grammar with output facilities [[Code generation (compiler)|that produce stack machine]] code, and is able to compile its own source code and other languages.
Among the earliest programs of the original [[Unix]] versions being built at [[Bell Labs]] was the two-part [[lex (software)|lex]] and [[yacc]] system, which was normally used to output [[C programming language]] code, but had a flexible output system that could be used for everything from programming languages to [[text file]] conversion. Their modern [[GNU Project|GNU]] versions are [[Flex (lexical analyser generator)|flex]] and [[GNU Bison|bison]].
Some experimental compiler-compilers take as input a formal description of programming language semantics, typically using [[denotational semantics]]. This approach is often called 'semantics-based compiling', and was pioneered by [[Peter Mosses]]' Semantic Implementation System (SIS) in 1978.<ref>Peter Mosses, "SIS: A Compiler-Generator System Using Denotational Semantics," Report 78-4-3, Dept. of Computer Science, University of Aarhus, Denmark, June 1978</ref> However, both the generated compiler and the code it produced were inefficient in time and space. No production compilers are currently built in this way, but research continues.
Line 27:
The Production Quality Compiler-Compiler ([[PQCC]]) project at [[Carnegie Mellon University]] does not formalize semantics, but does have a semi-formal framework for machine description.
Compiler-compilers exist in many flavors, including bottom-up rewrite machine generators (see [
===Metacompilers===
Line 60:
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"/>
| |||