Introduction to Gamma

Author: Denis Kuniß

Gamma is compiler generator. It generates compilers from formal specifications. The concept of parser genrators are quite well known, they generate parser from grammar specifications. Gamma is more than that.It generates whole compilers from an extended grammar specifications.

Compilers basically realize complex partial functions: they map elements of a well-defined subset of all buildable strings into other strings; the definition and value domain of a compiler understood as a function are formal languages. The implementation of a compiler essentially assigns each sentence of the source language a sentences of the target language. Specifying a compiler’s input/output mapping can, however, not be done by listing all (input,output) pairs, as the number of sentences in a formal language is potentially infinite. However, the sentences of many languages can be structured in such a way that a finite structure of all sentences of a language can be derived from. These structures, called grammars, could now, since they are finite, be used constructively for giving the input/output mapping in a compiler.

Unfortunately this mapping is not comprehensible in "handwritten" compilers. Thus, however, the actual function of a compiler is not transparent. Also the best and most exact manual of a compiler does not describe its function completely. The only complete description of the functionality of a compiler is its code. But who wants to be expected to read the source code of a compiler for verification, especially the actual translation structure is overlayed by programming styles, inadequacies of the used programming language or optimizations, if the source code is available at all. It would be desirable to have a formalism in which structures of the source and target language could be written down side by side in a simple, clear form and from which a compiler can be automatically generated.

Attribute grammars (AGs), introduced by Knuth, provide a formalism that can be used not only for the description of programming languages, but also as basis for the automatic generation of compilers. Being an open calculus, however, this formalism requires the use of a further specification or programming language for the description of the context conditions and the semantics of a language. This complicates the understanding of the compiler and obscures its actual functionality, as in a "handwritten" compiler.

Extended affix grammars (EAGs), introduced by Watt, represent a closed calculus and compensate this disadvantage [Watt]. Syntax and semantics of a programming language are described in a formalism which omits all non-relevant information - concerning optimizations, the implementation language used and other points. The mapping from source to target language is explicit and describes the transformation function to be realized by the compiler unambiguously and in simple form.

The principal suitability of this calculus for the automatic creation of translators was already demonstrated by the compiler generator Eta [Schröer], which was developed in 1984, and since then had been used with many extensions in the context of courses. The choice of languages for implementation on a mainframe computer as well as the sheer size of the system made maintenance or porting almost impossible.

With Epsilon, a small experimental system with greater flexibility and controllability was designed and implemented in 1997 from scratch in Oberon-2 [DeWeKaKr] allowing to generate compilers from a uniform, formal specification.

In 2019 Epsilon was revived by migrating its implementation to the language D and published at GitHub. It was accompanied by an Xtext based Eclipse plugin and VS code extension for comfortable editing.

Since 2020 the project evolves under a new name on GitHub - Gamma.