Content deleted Content added
m link to the relevant section |
m →Variants: HTTP to HTTPS for SourceForge |
||
| (4 intermediate revisions by 4 users 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
A formal description of a language is usually a [[formal grammar|grammar]] used as an input to a parser generator. It often resembles [[Backus–Naur form]] (BNF), [[extended Backus–Naur form]] (EBNF), or has its own syntax. Grammar files describe a [[Syntax (programming languages)|syntax]] of a generated compiler's target programming language and actions that should be taken against its specific constructs.
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 51:
This Forth use of the term metacompiler is disputed in mainstream computer science. See [[Forth (programming language)#Self-compilation and cross compilation|Forth (programming language)]] and [[History of compiler construction#Forth|History of compiler construction]]. The actual Forth process of compiling itself is a combination of a Forth being a [[History of compiler construction#Self-hosting compilers|self-hosting]] [[extensible programming]] language and sometimes [[History of compiler construction#Cross compilation|cross compilation]], long established terminology in computer science. Metacompilers are a general compiler writing system. Besides the Forth metacompiler concept being indistinguishable from self-hosting and extensible language. The actual process acts at a lower level defining a minimum subset of forth ''words'', that can be used to define additional forth words, A full Forth implementation can then be defined from the base set. This sounds like a bootstrap process. The problem is that almost every general purpose language compiler also fits the Forth metacompiler description.
: When (self-hosting compiler) X processes its own source code, resulting in an executable version of itself, X is a metacompiler.
Just replace X with any common language, C, C++, [[Java (programming language)|Java]], [[Pascal (programming language)|Pascal]], [[COBOL]], [[Fortran]], [[Ada (programming language)|Ada]], [[Modula-2]], etc. And X would be a metacompiler according to the Forth usage of metacompiler. A metacompiler operates at an abstraction level above the compiler it compiles. It only operates at the same (self-hosting compiler) level when compiling itself. One has to see the problem with this definition of metacompiler. It can be applied to most any language.
However, on examining the concept of programming in Forth, adding new words to the dictionary, extending the language in this way is metaprogramming. It is this metaprogramming in Forth that makes it a metacompiler.
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"/>
Line 193:
* [[GNU Bison]]
* [[Coco/R]], Coco-2<ref name="Rechenberg-Mössenböck_1985"/>
* Copper <ref>{{Cite web |title=Copper {{!}} Minnesota Extensible Language Tools Group |url=https://melt.cs.umn.edu/copper/ |access-date=2025-03-25 |website=melt.cs.umn.edu}}</ref>
* [[DMS Software Reengineering Toolkit]], a program transformation system with parser generators
* Epsilon Grammar Studio
Line 203 ⟶ 204:
* Syntax Improving Device (SID)
* [[SYNTAX]], an integrated toolset for compiler construction.
* tacc - The Alternative Compiler Compiler <ref>{{Cite web |url=http://legomatrix.com/tacc/tacc.htm |access-date=2025-03-25 |website=legomatrix.com}}</ref>
* [[TREE-META]]
* [[Yacc]]
| |||