Metacompiler
Encyclopedia
Metacompilers are a subset of a specialized class of compiler writing tools
called compiler-compiler
s.
The feature that sets a metacompiler apart from a standard compiler-compiler
is that a metacompiler is written in its own language and translates itself.
Metacompilers are not only useful for generating parsers and
code generators, they are also useful for generating a
wide range of other software engineering and analysis tools.
Besides being useful for parsing domain-specific languages,
a metacompiler is itself a prime example of a domain-specific language,
designed for the domain of compiler writing.
A metacompiler is defined by a set of grammar
productions
defining itself, written in its
own specialized language. The metacompiler translates this grammar definition
into the executable form of itself. Usually the grammar reduction rules are
intermixed with semantic translation rules. Defining itself and translating
itself this way constitutes the meta-step that sets a metacompiler apart
from other compiler-compilers.
Since the metacompiler defines and translates itself, the question arises as
to how it is initially created (a chicken and egg problem). This is solved in
one of two ways: by cross-compiling or by
bootstrapping
. Cross-compiling involves
translating the new metacompiler using some other compiler or metacompiler
running on some other platform. This is similar to how you make more
sourdough starter.
Bootstrapping, the other method, is an elegant (and usually mind-bending)
process whereby the metacompiler is defined in progressively sophisticated
stages and "bootstraps" itself. The first version of the metacompiler
translation is executed by hand. That is, the programmer pretends to be the
metacompiler, parsing its rules and generating the code just as the
metacompiler would do if it existed, which it doesn't, at least not at
that first stage. Once the initial metacompiler is up and running, in a
simple embryonic form, the full-strength metacompiler is created by
successively defining and translating more sophisticated versions of itself.
That is, at each succeeding stage, version n of the metacompiler is used to
generate its successor, version n+1.
A runtime module consisting of support functions required for the translation
process usually rounds out the full metacompiler package. This would include
input/output
, symbol table
, and
string processing functions.
the build-up of the computer industry. Initial metacompilers included
Meta-II
and its descendent
TreeMeta
.
A MetaII Tutorial provides an online way to learn about MetaII.
Information about later descendents of these metacompilers is not generally
available. 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.
The ideas about grammars, self-generation and extensions are widely used by Program transformation
systems.
called compiler-compiler
Compiler-compiler
A compiler-compiler or compiler generator is a tool that creates a parser, interpreter, or compiler from some form of formal description of a language and machine...
s.
The feature that sets a metacompiler apart from a standard compiler-compiler
is that a metacompiler is written in its own language and translates itself.
Metacompilers are not only useful for generating parsers and
code generators, they are also useful for generating a
wide range of other software engineering and analysis tools.
Besides being useful for parsing domain-specific languages,
a metacompiler is itself a prime example of a domain-specific language,
designed for the domain of compiler writing.
A metacompiler is defined by a set of grammar
Formal grammar
A formal grammar is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax...
productions
Production (computer science)
A production or production rule in computer science is a rewrite rule specifying a symbol substitution that can be recursively performed to generate new symbol sequences. A finite set of productions P is the main component in the specification of a formal grammar...
defining itself, written in its
own specialized language. The metacompiler translates this grammar definition
into the executable form of itself. Usually the grammar reduction rules are
intermixed with semantic translation rules. Defining itself and translating
itself this way constitutes the meta-step that sets a metacompiler apart
from other compiler-compilers.
Since the metacompiler defines and translates itself, the question arises as
to how it is initially created (a chicken and egg problem). This is solved in
one of two ways: by cross-compiling or by
bootstrapping
Bootstrapping (compilers)
In computer science, bootstrapping is the process of writing a compiler in the target programming language which it is intended to compile...
. Cross-compiling involves
translating the new metacompiler using some other compiler or metacompiler
running on some other platform. This is similar to how you make more
sourdough starter.
Bootstrapping, the other method, is an elegant (and usually mind-bending)
process whereby the metacompiler is defined in progressively sophisticated
stages and "bootstraps" itself. The first version of the metacompiler
translation is executed by hand. That is, the programmer pretends to be the
metacompiler, parsing its rules and generating the code just as the
metacompiler would do if it existed, which it doesn't, at least not at
that first stage. Once the initial metacompiler is up and running, in a
simple embryonic form, the full-strength metacompiler is created by
successively defining and translating more sophisticated versions of itself.
That is, at each succeeding stage, version n of the metacompiler is used to
generate its successor, version n+1.
A runtime module consisting of support functions required for the translation
process usually rounds out the full metacompiler package. This would include
input/output
Input/output
In computing, input/output, or I/O, refers to the communication between an information processing system , and the outside world, possibly a human, or another information processing system. Inputs are the signals or data received by the system, and outputs are the signals or data sent from it...
, symbol table
Symbol table
In computer science, a symbol table is a data structure used by a language translator such as a compiler or interpreter, where each identifier in a program's source code is associated with information relating to its declaration or appearance in the source, such as its type, scope level and...
, and
string processing functions.
Historical
Metacompilers have played a significant role in both computer science andthe build-up of the computer industry. Initial metacompilers included
Meta-II
META II
META II is a compiler writing language first released in 1962 by D. V. Schorre. It consists of syntax equations resembling Backus normal form and into which instructions to output assembly language commands are inserted. Compilers have been written in this language for VALGOL I and VALGOL II...
and its descendent
TreeMeta
TREE-META
The TREE-META Translator Writing System is a Compiler-compiler system for context-free languages originally developed in the 1960s. Parsing statements of the metalanguage resemble Backus-Naur Form with embedded tree-building directives...
.
A MetaII Tutorial provides an online way to learn about MetaII.
Information about later descendents of these metacompilers is not generally
available. 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.
The ideas about grammars, self-generation and extensions are widely used by Program transformation
Program transformation
A program transformation is any operation that takes a computer program and generates another program. In many cases the transformed program is required to be semantically equivalent to the original, relative to a particular formal semantics and in fewer cases the transformations result in programs...
systems.
See also
- Compiler-compilerCompiler-compilerA compiler-compiler or compiler generator is a tool that creates a parser, interpreter, or compiler from some form of formal description of a language and machine...
- Domain-specific language
- Domain analysisDomain analysisIn software engineering, domain analysis, or product line analysis, is the process of analyzing related software systems in a domain to find their common and variable parts. It is a model of wider business context for the system. The term was coined in the early 1980s by James Neighbors. Domain...
- Program transformationProgram transformationA program transformation is any operation that takes a computer program and generates another program. In many cases the transformed program is required to be semantically equivalent to the original, relative to a particular formal semantics and in fewer cases the transformations result in programs...