In computing, a compiler is a computer program that transforms source code written in a programming language or computer language (the source language), into another computer language (the target language, often having a binary form known as object code or machine code). The most common reason for transforming source code is to create an executable program.

Any program written in a high-level programming language must be translated to object code before it can be executed, so all programmers using such a language use a compiler or an interpreter, sometimes even both. Improvements to a compiler may lead to a large number of improved features in executable programs.

In the late 1970s, the Production Quality Compiler-Compiler introduced the principles of compiler organization that are still widely used today (e.g., a front-end handling syntax and semantics and a back-end generating machine code).

First compilers

Software for early computers was primarily written in assembly language, and before that directly in machine code. It is usually more productive for a programmer to use a high-level language and programs written in a high-level language can be reused on different kinds of computers. Even so, compilers took a while to become established, because they generated code that did not perform as well as hand-written assembler, they were daunting development projects in their own right, and the very limited memory capacity of early computers created many technical problems for practical compiler implementations.

Between 1942 and 1945, Konrad Zuse developed ("plan calculus"), the first high-level language for a computer, for which he envisioned a ("plan assembly device"), which would automatically translate the mathematical formulation of a program into machine-readable punched film stock. However, the first actual compiler for the language was implemented only decades later.

Between 1949 and 1951, Heinz Rutishauser proposed Superplan, a high-level language and automatic translator. His ideas were later refined by Friedrich L. Bauer and Klaus Samelson.

The first practical compiler was written by Corrado Böhm in 1951 for his PhD thesis, one of the first computer science doctorates awarded anywhere in the world.

The first implemented compiler was written by Grace Hopper, who also coined the term "compiler",Maurice V. Wilkes. 1968. Computers Then and Now. Journal of the Association for Computing Machinery, 15(1):1–7, January. p. 3 (a comment in brackets added by editor), "(I do not think that the term compiler was then in general use, although it had in fact been introduced by Grace Hopper.)" The World's First COBOL Compilers referring to her A-0 system which functioned as a loader or linker, not the modern notion of a compiler. The first Autocode and compiler in the modern sense were developed by Alick Glennie in 1952 at the University of Manchester for the Mark 1 computer. The FORTRAN team led by John W. Backus at IBM introduced the first commercially available compiler in 1957, which took 18 person-years to create.

The first ALGOL 58 compiler was completed by the end of 1958 by Friedrich L. Bauer, Hermann Bottenbruch, Heinz Rutishauser, and Klaus Samelson for the Z22 computer. Bauer et al. had been working on compiler technology for the Sequentielle Formelübersetzung (i.e. sequential formula translation) in the previous years.

By 1960, an extended Fortran compiler, ALTAC, was available on the Philco 2000, so it is probable that a Fortran program was compiled for both IBM and Philco computer architectures in mid-1960. The first known demonstrated cross-platform high-level language was COBOL. In a demonstration in December 1960, a COBOL program was compiled and executed on both the UNIVAC II and the RCA 501.

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.T. Hart and M. Levin "The New Compiler", AIM-39 CSAIL Digital Archive – Artificial Intelligence Laboratory Series 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.

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.DeRemer, F. Practical Translators for LR(k) Languages. PhD dissertation, MIT, 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.