History of compiler construction

Self-hosting compilers

Like any other software, there are benefits from implementing a compiler in a high-level language. In particular, a compiler can be self-hosted – that is, written in the programming language it compiles. Building a self-hosting compiler is a bootstrapping problem, i.e. the first such compiler for a language must be either hand written machine code, compiled by a compiler written in another language, or compiled by running the compiler's source on itself in an interpreter.

Corrado Böhm PhD dissertation

Corrado Böhm developed a language, a machine, and a translation method for compiling that language on the machine in his PhD dissertation submitted in 1951. He not only described a complete compiler, but also defined for the first time that compiler in its own language. The language was interesting in itself, because every statement (including input statements, output statements and control statements) was a special case of an assignment statement.

NELIAC

The Navy Electronics Laboratory International ALGOL Compiler or NELIAC was a dialect and compiler implementation of the ALGOL 58 programming language developed by the Navy Electronics Laboratory in 1958.

NELIAC was the brainchild of Harry Huskey – then Chairman of the ACM and a well-known computer scientist (and later academic supervisor of Niklaus Wirth) – and supported by Maury Halstead, the head of the computational center at NEL. The earliest version was implemented on the prototype USQ-17 computer (called the Countess) at the laboratory. It was the world's first self-compiling compiler – the compiler was first coded in simplified form in assembly language (the bootstrap), then re-written in its own language and compiled by the bootstrap, and finally re-compiled by itself, making the bootstrap obsolete.

Lisp

Another early self-hosting compiler was written for Lisp by Tim Hart and Mike Levin at MIT in 1962. They wrote a Lisp compiler in Lisp, testing it inside an existing Lisp interpreter. Once they had improved the compiler to the point where it could compile its own source code, it was self-hosting.

The compiler as it exists on the standard compiler tape is a machine language program that was obtained by having the S-expression definition of the compiler work on itself through the interpreter.

— AI Memo 39

This technique is only possible when an interpreter already exists for the very same language that is to be compiled. It borrows directly from the notion of running a program on itself as input, which is also used in various proofs in theoretical computer science, such as the proof that the halting problem is undecidable.

Forth

Forth is an example of a self-hosting compiler. The self compilation and cross compilation features of Forth are synonymous with metacompilation and metacompilers. Like Lisp, Forth is an extensible programming language. It is the extensible programming language features of Forth and Lisp that enable them to generate new versions of themselves or port themselves to new environments.

Context-free grammars and parsers

A parser is an important component of a compiler. It parses the source code of a computer programming language to create some form of internal representation. Programming languages tend to be specified in terms of a context-free grammar because fast and efficient parsers can be written for them. Parsers can be written by hand or generated by a parser generator. A context-free grammar provides a simple and precise mechanism for describing how programming language constructs are built from smaller blocks. The formalism of context-free grammars was developed in the mid-1950s by Noam Chomsky.

Block structure was introduced into computer programming languages by the ALGOL project (1957–1960), which, as a consequence, also featured a context-free grammar to describe the resulting ALGOL syntax.

Context-free grammars are simple enough to allow the construction of efficient parsing algorithms which, for a given string, determine whether and how it can be generated from the grammar. If a programming language designer is willing to work within some limited subsets of context-free grammars, more efficient parsers are possible.

LR parsing

The LR parser (left to right) was invented by Donald Knuth in 1965 in a paper, "On the Translation of Languages from Left to Right". An LR parser is a parser that reads input from Left to right (as it would appear if visually displayed) and produces a Rightmost derivation. The term LR(k) parser is also used, where k refers to the number of unconsumed lookahead input symbols that are used in making parsing decisions.

Knuth proved that LR(k) grammars can be parsed with an execution time essentially proportional to the length of the program, and that every LR(k) grammar for k > 1 can be mechanically transformed into an LR(1) grammar for the same language. In other words, it is only necessary to have one symbol lookahead to parse any deterministic context-free grammar (DCFG).

Korenjak (1969) was the first to show parsers for programming languages could be produced using these techniques. Frank DeRemer devised the more practical Simple LR (SLR) and Look-ahead LR (LALR) techniques, published in his PhD dissertation at MIT in 1969. This was an important breakthrough, because LR(k) translators, as defined by Donald Knuth, were much too large for implementation on computer systems in the 1960s and 1970s.

In practice, LALR offers a good solution; the added power of LALR(1) parsers over SLR(1) parsers (that is, LALR(1) can parse more complex grammars than SLR(1)) is useful, and, though LALR(1) is not comparable with LL(1)(See below) (LALR(1) cannot parse all LL(1) grammars), most LL(1) grammars encountered in practice can be parsed by LALR(1). LR(1) grammars are more powerful again than LALR(1); however, an LR(1) grammar requires a canonical LR parser which would be extremely large in size and is not considered practical. The syntax of many programming languages are defined by grammars that can be parsed with an LALR(1) parser, and for this reason LALR parsers are often used by compilers to perform syntax analysis of source code.

A recursive ascent parser implements an LALR parser using mutually-recursive functions rather than tables. Thus, the parser is directly encoded in the host language similar to recursive descent. Direct encoding usually yields a parser which is faster than its table-driven equivalent for the same reason that compilation is faster than interpretation. It is also (in principle) possible to hand edit a recursive ascent parser, whereas a tabular implementation is nigh unreadable to the average human.

Recursive ascent was first described by Thomas Pennello in his article "Very fast LR parsing" in 1986. The technique was later expounded upon by G.H. Roberts in 1988 as well as in an article by Leermakers, Augusteijn, Kruseman Aretz in 1992 in the journal Theoretical Computer Science.

LL parsing

An LL parser parses the input from Left to right, and constructs a Leftmost derivation of the sentence (hence LL, as opposed to LR). The class of grammars which are parsable in this way is known as the LL grammars. LL grammars are an even more restricted class of context-free grammars than LR grammars. Nevertheless, they are of great interest to compiler writers, because such a parser is simple and efficient to implement.

LL(k) grammars can be parsed by a recursive descent parser which is usually coded by hand, although a notation such as META II might alternatively be used.

The design of ALGOL sparked investigation of recursive descent, since the ALGOL language itself is recursive. The concept of recursive descent parsing was discussed in the January 1961 issue of Communications of the ACM in separate papers by A.A. Grau and Edgar T. "Ned" Irons. Richard Waychoff and colleagues also implemented recursive descent in the Burroughs ALGOL compiler in March 1961, the two groups used different approaches but were in at least informal contact.

The idea of LL(1) grammars was introduced by Lewis and Stearns (1968).

Recursive descent was popularised by Niklaus Wirth with PL/0, an educational programming language used to teach compiler construction in the 1970s.

LR parsing can handle a larger range of languages than LL parsing, and is also better at error reporting, i.e. it detects syntactic errors when the input does not conform to the grammar as soon as possible.

Earley parser

In 1970, Jay Earley invented what came to be known as the Earley parser. Earley parsers are appealing because they can parse all context-free languages reasonably efficiently.

Grammar description languages

John Backus proposed "metalinguistic formulas" to describe the syntax of the new programming language IAL, known today as ALGOL 58 (1959). Backus's work was based on the Post canonical system devised by Emil Post.

Further development of ALGOL led to ALGOL 60; in its report (1963), Peter Naur named Backus's notation Backus normal form (BNF), and simplified it to minimize the character set used. However, Donald Knuth argued that BNF should rather be read as Backus–Naur form, and that has become the commonly accepted usage.

Niklaus Wirth defined extended Backus–Naur form (EBNF), a refined version of BNF, in the early 1970s for PL/0. Augmented Backus–Naur form (ABNF) is another variant. Both EBNF and ABNF are widely used to specify the grammar of programming languages, as the inputs to parser generators, and in other fields such as defining communication protocols.

Parser generators

A parser generator generates the lexical-analyzer portion of a compiler. It is a program that takes a description of a formal grammar of a specific programming language and produces a parser for that language. That parser can be used in a compiler for that specific language. The parser detects and identifies the reserved words and symbols of the specific language from a stream of text and returns these as tokens to the code which implements the syntactic validation and translation into object code. This second part of the compiler can also be created by a compiler-compiler using a formal rules-of-precedence syntax-description as input.

The first compiler-compiler to use that name was written by Tony Brooker in 1960 and was used to create compilers for the Atlas computer at the University of Manchester, including the Atlas Autocode compiler. However it was rather different from modern compiler-compilers, and today would probably be described as being somewhere between a highly customisable generic compiler and an extensible-syntax language. The name "compiler-compiler" was far more appropriate for Brooker's system than it is for most modern compiler-compilers, which are more accurately described as parser generators.

In the early 1960s, Robert McClure at Texas Instruments invented a compiler-compiler called TMG, the name taken from "transmogrification". In the following years TMG was ported to several UNIVAC and IBM mainframe computers.

The Multics project, a joint venture between MIT and Bell Labs, was one of the first to develop an operating system in a high-level language. PL/I was chosen as the language, but an external supplier could not supply a working compiler. The Multics team developed their own subset dialect of PL/I known as Early PL/I (EPL) as their implementation language in 1964. TMG was ported to GE-600 series and used to develop EPL by Douglas McIlroy, Robert Morris, and others.

Not long after Ken Thompson wrote the first version of Unix for the PDP-7 in 1969, Douglas McIlroy created the new system's first higher-level language: an implementation of McClure's TMG. TMG was also the compiler definition tool used by Ken Thompson to write the compiler for the B language on his PDP-7 in 1970. B was the immediate ancestor of C.

An early LALR parser generator was called "TWS", created by Frank DeRemer and Tom Pennello.

XPL

XPL is a dialect of the PL/I programming language, used for the development of compilers for computer languages. It was designed and implemented in 1967 by a team with William M. McKeeman, James J. Horning, and David B. Wortman at Stanford University and the University of California, Santa Cruz. It was first announced at the 1968 Fall Joint Computer Conference in San Francisco.

XPL featured a relatively simple translator writing system dubbed ANALYZER, based upon a bottom-up compiler precedence parsing technique called MSP (mixed strategy precedence). XPL was bootstrapped through Burroughs Algol onto the IBM System/360 computer. (Some subsequent versions of XPL used on University of Toronto internal projects utilized an SLR(1) parser, but those implementations have never been distributed).

Yacc

Yacc is a parser generator (loosely, compiler-compiler), not to be confused with lex, which is a lexical analyzer frequently used as a first stage by Yacc. Yacc was developed by Stephen C. Johnson at AT&T for the Unix operating system. The name is an acronym for "Yet Another Compiler-Compiler." It generates an LALR(1) compiler based on a grammar written in a notation similar to Backus–Naur form.

Johnson worked on Yacc in the early 1970s at Bell Labs. He was familiar with TMG and its influence can be seen in Yacc and the design of the C programming language. Because Yacc was the default compiler generator on most Unix systems, it was widely distributed and used. Derivatives such as GNU Bison are still in use.

The compiler generated by Yacc requires a lexical analyzer. Lexical analyzer generators, such as lex or flex are widely available. The IEEE POSIX P1003.2 standard defines the functionality and requirements for both Lex and Yacc.

Coco/R

Coco/R is a parser generator that generates LL(1) parsers in Modula-2 (with plug-ins for other languages) from input grammars written in a variant of EBNF. It was developed by Hanspeter Mössenböck at the Swiss Federal Institute of Technology in Zurich (ETHZ) in 1985.

ANTLR

ANTLR is a parser generator that generates LL(*) parsers in Java from input grammars written in a variant of EBNF. It was developed by Terence Parr at the University of San Francisco in the early 1990s as a successor of an earlier generator called PCCTS.

Metacompilers

Metacompilers differ from parser generators, taking as input a program written in a metalanguage. Their input consists of grammar analyzing formula combined with embedded transform operations that construct abstract syntax trees, or simply output reformatted text strings that may be stack machine code.

Many can be programmed in their own metalanguage enabling them to compile themselves, making them self-hosting extensible language compilers.

Many metacompilers build on the work of Dewey Val Schorre. His META II compiler, first released in 1964, was the first documented metacompiler. Able to define its own language and others, META II accepted syntax formula having embedded output (code production). It also translated to one of the earliest instances of a virtual machine. Lexical analysis was performed by built token recognizing functions: .ID, .STRING, and .NUMBER. Quoted strings in syntax formula recognize lexemes that are not kept.

TREE-META, a second generation Schorre metacompiler, appeared around 1968. It extended the capabilities of META II, adding unparse rules separating code production from the grammar analysis. Tree transform operations in the syntax formula produce abstract syntax trees that the unparse rules operate on. The unparse tree pattern matching provided peephole optimization ability.

CWIC, described in a 1970 ACM publication is a third generation Schorre metacompiler that added lexing rules and backtracking operators to the grammar analysis. LISP 2 was combined with the unparse rules of TREE-META in the CWIC generator language. With LISP 2 processing, CWIC can generate fully optimized code. CWIC also provided binary code generation into named code sections. Single and multipass compilers could be implemented using CWIC.

CWIC compiled to 8-bit byte-addressable machine code instructions primarily designed to produce IBM System/360 code.

Later generations are not publicly documented. One important feature would be the abstraction of the target processor instruction set, generating to a pseudo machine instruction set, macros, that could be separately defined or mapped to a real machine's instructions. Optimizations applying to sequential instructions could then be applied to the pseudo instruction before their expansion to target machine code.

Cross compilation

A cross compiler runs in one environment but produces object code for another. Cross compilers are used for embedded development, where the target computer has limited capabilities.

An early example of cross compilation was AIMICO, where a FLOW-MATIC program on a UNIVAC II was used to generate assembly language for the IBM 705, which was then assembled on the IBM computer.

The ALGOL 68C compiler generated ZCODE output, that could then be either compiled into the local machine code by a ZCODE translator or run interpreted. ZCODE is a register-based intermediate language. This ability to interpret or compile ZCODE encouraged the porting of ALGOL 68C to numerous different computer platforms.

Optimizing compilers

Compiler optimization is the process of improving the quality of object code without changing the results it produces.

The developers of the first FORTRAN compiler aimed to generate code that was better than the average hand-coded assembler, so that customers would actually use their product. In one of the first real compilers, they often succeeded.

Later compilers, like IBM's Fortran IV compiler, placed more priority on good diagnostics and faster execution, at the expense of object code optimization. It wasn't until the IBM System/360 series that IBM provided two separate compilers—a fast-executing code checker, and a slower, optimizing one.

Frances E. Allen, working alone and jointly with John Cocke, introduced many of the concepts for optimization. Allen's 1966 paper, Program Optimization, introduced the use of graph data structures to encode program content for optimization. Her 1970 papers, Control Flow Analysis and A Basis for Program Optimization established intervals as the context for efficient and effective data flow analysis and optimization. Her 1971 paper with Cocke, A Catalogue of Optimizing Transformations, provided the first description and systematization of optimizing transformations. Her 1973 and 1974 papers on interprocedural data flow analysis extended the analysis to whole programs. Her 1976 paper with Cocke describes one of the two main analysis strategies used in optimizing compilers today.

Allen developed and implemented her methods as part of compilers for the IBM 7030 Stretch-Harvest and the experimental Advanced Computing System. This work established the feasibility and structure of modern machine- and language-independent optimizers. She went on to establish and lead the PTRAN project on the automatic parallel execution of FORTRAN programs. Her PTRAN team developed new parallelism detection schemes and created the concept of the program dependence graph, the primary structuring method used by most parallelizing compilers.

Programming Languages and their Compilers by John Cocke and Jacob T. Schwartz, published early in 1970, devoted more than 200 pages to optimization algorithms. It included many of the now familiar techniques such as redundant code elimination and strength reduction.

In 1972, Gary A. Kildall introduced the theory of data-flow analysis used today in optimizing compilers (sometimes known as Kildall's method).

Peephole optimization

Peephole optimization is a simple but effective optimization technique. It was invented by William M. McKeeman and published in 1965 in CACM. It was used in the XPL compiler that McKeeman helped develop.

Capex COBOL optimizer

Capex Corporation developed the "COBOL Optimizer" in the mid-1970s for COBOL. This type of optimizer depended, in this case, upon knowledge of "weaknesses" in the standard IBM COBOL compiler, and actually replaced (or patched) sections of the object code with more efficient code. The replacement code might replace a linear table lookup with a binary search for example or sometimes simply replace a relatively "slow" instruction with a known faster one that was otherwise functionally equivalent within its context. This technique is now known as strength reduction. For example, on the IBM System/360 hardware, the CLI instruction was, depending on the particular model, between twice and five times as fast as a CLC instruction for single byte comparisons.

Modern compilers typically provide optimization options to allow programmers to choose whether or not to execute an optimization pass.

Diagnostics

When a compiler is given a syntactically incorrect program, a good, clear error message is helpful. From the perspective of the compiler writer, it is often difficult to achieve.

The WATFIV Fortran compiler was developed at the University of Waterloo, Canada in the late 1960s. It was designed to give better error messages than IBM's Fortran compilers of the time. In addition, WATFIV was far more usable, because it combined compiling, linking and execution into one step, whereas IBM's compilers had three separate components to run.

PL/C

PL/C was a computer programming language developed at Cornell University in the early 1970s. While PL/C was a subset of IBM's PL/I language, it was designed with the specific goal of being used for teaching programming. The two researchers and academic teachers who designed PL/C were Richard W. Conway and Thomas R. Wilcox. They submitted the famous article "Design and implementation of a diagnostic compiler for PL/I" published in the Communications of ACM in March 1973.

PL/C eliminated some of the more complex features of PL/I, and added extensive debugging and error recovery facilities. The PL/C compiler had the unusual capability of never failing to compile any program, through the use of extensive automatic correction of many syntax errors and by converting any remaining syntax errors to output statements.

Just-in-time compilation

Just-in-time (JIT) compilation is the generation of executable code on-the-fly or as close as possible to its actual execution, to take advantage of runtime metrics or other performance-enhancing options.

Intermediate representation

Most modern compilers have a lexer and parser that produce an intermediate representation of the program. The intermediate representation is a simple sequence of operations which can be used by an optimizer and a code generator which produces instructions in the machine language of the target processor. Because the code generator uses an intermediate representation, the same code generator can be used for many different high-level languages.

There are many possibilities for the intermediate representation. Three-address code, also known as a quadruple or quad is a common form, where there is an operator, two operands, and a result. Two-address code or triples have a stack to which results are written, in contrast to the explicit variables of three-address code.

Static Single Assignment (SSA) was developed by Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck, researchers at IBM in the 1980s. In SSA, a variable is given a value only once. A new variable is created rather than modifying an existing one. SSA simplifies optimization and code generation.

Code generation

A code generator generates machine language instructions for the target processor.

Register allocation

Sethi–Ullman algorithm or Sethi–Ullman numbering is a method to minimise the number of registers needed to hold variables.

Notable compilers

• Amsterdam Compiler Kit by Andrew Tanenbaum and Ceriel Jacobs
• Berkeley Pascal , written by Ken Thompson in 1975. Bill Joy and others at University of California, Berkeley added improvements
• GNU Compiler Collection, formerly the GNU C Compiler. Originally authored by Richard Stallman in 1987, GCC is a major modern compiler which is used to compile many free software projects, notably Linux.
• LLVM, formerly known as the Low Level Virtual Machine
• Small-C by Ron Cain and James E Hendrix
• Turbo Pascal, created by Anders Hejlsberg, first released in 1983.
• WATFOR, created at the University of Waterloo. One of the first popular educational compilers, although now largely obsolete.