History of compiler construction

The Production Quality Compiler-Compiler, in the late 1970s, 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).

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

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.

[8][9] 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.

[10] 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.

A context-free grammar provides a simple and precise mechanism for describing how programming language constructs are built from smaller blocks.

If a programming language designer is willing to work within some limited subsets of context-free grammars, more efficient parsers are possible.

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.

It is also (in principle) possible to hand edit a recursive ascent parser, whereas a tabular implementation is nigh unreadable to the average human.

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 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.

[26][27] Richard Waychoff and colleagues also implemented recursive descent in the Burroughs ALGOL compiler in March 1961,[28] the two groups used different approaches but were in at least informal contact.

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

[33] John Backus proposed "metalinguistic formulas"[34][35] to describe the syntax of the new programming language IAL, known today as ALGOL 58 (1959).

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.

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 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.

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.

B was the immediate ancestor of C. An early LALR parser generator was called "TWS", created by Frank DeRemer and Tom Pennello.

(Some subsequent versions of XPL used on University of Toronto internal projects utilized an SLR(1) parser, but those implementations have never been distributed).

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.

Their input consists 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.

It extended the capabilities of META II, adding unparse rules separating code production from the grammar analysis.

CWIC, described in a 1970 ACM publication is a third generation Schorre metacompiler that added lexing rules and backtracking operators to the grammar analysis.

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.

[56] Allen developed and implemented her methods as part of compilers for the IBM 7030 Stretch-Harvest and the experimental Advanced Computing System.

Programming Languages and their Compilers by John Cocke and Jacob T. Schwartz, published early in 1970, devoted more than 200 pages to optimization algorithms.

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.

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.