Jump to content

History of compiler construction

From Wikipedia, the free encyclopedia
(Redirected from History of compiler writing)

History of computing
Hardware
Software
Computer science
Modern concepts
By country
Timeline of computing
Glossary of computer science

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.

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

First compilers

[edit]

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, it took a while for compilers 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 Plankalkül ("plan calculus"), the first high-level language for a computer, for which he envisioned a Planfertigungsgerät ("plan assembly device"), which would automatically translate the mathematical formulation of a program into machine-readable punched film stock.[1] 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.[2] His ideas were later refined by Friedrich L. Bauer and Klaus Samelson.[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 implemented compiler was written by Grace Hopper, who also coined the term "compiler",[6][7] 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.[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.

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.[11] 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.[7][12]

Self-hosting compilers

[edit]
Not to be confused with Compiler-compiler.

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

[edit]

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.[4][5] 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

[edit]

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

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

[edit]

Another early self-hosting compiler was written for Lisp by Tim Hart and Mike Levin at MIT in 1962.[14] 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.[15]

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[15]

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

[edit]

Forth is an example of a self-hosting compiler. The self compilation and cross compilation features of Forth are synonymous with metacompilation and metacompilers.[16][17] 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

[edit]

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

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

[edit]
Main article: LR parser

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).[19]

Korenjak (1969) was the first to show parsers for programming languages could be produced using these techniques.[20] Frank DeRemer devised the more practical Simple LR (SLR) and Look-ahead LR (LALR) techniques, published in his PhD dissertation at MIT in 1969.[21][22] 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[23] 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.[23] The technique was later expounded upon by G.H. Roberts[24] in 1988 as well as in an article by Leermakers, Augusteijn, Kruseman Aretz[25] in 1992 in the journal Theoretical Computer Science.

LL parsing

[edit]
Main article: LL parser

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

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

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

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

Earley parser

[edit]

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

Grammar description languages

[edit]

John Backus proposed "metalinguistic formulas"[34][35] 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,[36] 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

[edit]
For a more complete list, which also includes LL, SLR, GLR and LR parser generators, see Comparison of parser generators

A parser generator generates the lexical-analyser 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".[37][38][39][40] 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.[41] 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.[42] 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

[edit]

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.[43][44]

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

[edit]

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.[45] 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.[46] 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

[edit]

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

[edit]

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

[edit]
Main article: metacompiler

Metacompilers differ from parser generators, taking as input a program written in a metalanguage. 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.

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 imbedded 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.[47]

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 married with the unparse rules of TREEMETA 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 compiles 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

[edit]

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

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

[edit]

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

Later compilers, like IBM's Fortran IV compiler, placed more priority on good diagnostics and executing more quickly, 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,[49] introduced the use of graph data structures to encode program content for optimization.[50] Her 1970 papers, Control Flow Analysis[51] and A Basis for Program Optimization[52] established intervals as the context for efficient and effective data flow analysis and optimization. Her 1971 paper with Cocke, A Catalogue of Optimizing Transformations,[53] 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.[54][55] Her 1976 paper with Cocke describes one of the two main analysis strategies used in optimizing compilers today.[56]

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.[57] 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.[58]

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

Peephole optimization

[edit]

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

Capex COBOL optimizer

[edit]

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 5 times as fast as a CLC instruction for single byte comparisons.[62][63]

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

Diagnostics

[edit]

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

[edit]

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

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

[edit]
Main article: 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

[edit]
Main article: 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.[65] 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

[edit]
Main article: Code generation (compiler)

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

Register allocation

[edit]

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

Notable compilers

[edit]
See also: ALGOL 60: ALGOL 60 implementations timeline and List of compilers

See also

[edit]

References

[edit]
  1. ^ Hellige, Hans Dieter (2004). Geschichten der Informatik - Visionen, Paradigmen, Leitmotive (in German) (1 ed.). Berlin, Germany: Springer. pp. 45, 104, 105. ISBN 3-540-00217-0.
  2. ^ Rutishauser, Heinz (1951). "Über automatische Rechenplanfertigung bei programmgesteuerten Rechenanlagen". Zeitschrift für Angewandte Mathematik und Mechanik (in German). 31: 255. doi:10.1002/zamm.19510310820.
  3. ^ Fothe, Michael; Wilke, Thomas, eds. (2015) [2014-11-14]. Written at Jena, Germany. Keller, Stack und automatisches Gedächtnis – eine Struktur mit Potenzial [Cellar, stack and automatic memory - a structure with potential] (PDF) (Tagungsband zum Kolloquium 14. November 2014 in Jena). GI Series: Lecture Notes in Informatics (LNI) – Thematics (in German). Vol. T-7. Bonn, Germany: Gesellschaft für Informatik (GI) / Köllen Druck + Verlag GmbH. pp. 20–21. ISBN 978-3-88579-426-4. ISSN 1614-3213. Archived (PDF) from the original on 12 April 2020. Retrieved 12 April 2020. [1] (77 pages)
  4. ^ a b Böhm, Corrado (1954). Calculatrices digitales: Du déchiffrage de formules logicomathématiques par la machine même dans la conception du programme (PDF) (PhD) (in French). Zurich: ETH Zurich. Retrieved 27 September 2022.
  5. ^ a b Böhm, Corrado (1954). Digital Computers: On encoding logical-mathematical formulas using the machine itself during program conception (PDF) (PhD). Zurich: ETH Zurich. Retrieved 27 September 2022.
  6. ^ 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 [1953] in general use, although it had in fact been introduced by Grace Hopper.)"
  7. ^ a b c [2] The World's First COBOL Compilers Archived 13 October 2011 at the Wayback Machine
  8. ^ Knuth, Donald E.; Pardo, Luis Trabb. "Early development of programming languages". Encyclopedia of Computer Science and Technology. 7: 419–493.
  9. ^ Bentley, Peter J. (2012). Digitized: The Science of Computers and how it Shapes Our World. Oxford University Press. p. 87. ISBN 978-0-19-969379-5. Archived from the original on 29 August 2016.
  10. ^ Backus et al. "The FORTRAN automatic coding system", Proc. AFIPS 1957 Western Joint Computer Conf., Spartan Books, Baltimore 188–198
  11. ^ [3] Rosen, Saul. ALTAC, FORTRAN, and compatibility. Proceedings of the 1961 16th ACM national meeting
  12. ^ Norman, Jeremy. "Grace Hopper and Colleagues Introduce COBOL". HistoryOfInformation.com. Jeremy Norman. Retrieved 14 December 2022.
  13. ^ "Algol 58 implementations and dialects — Software Preservation Group".
  14. ^ T. Hart and M. Levin "The New Compiler", AIM-39 CSAIL Digital Archive – Artificial Intelligence Laboratory Series
  15. ^ a b Hart, Tim; Levin, Mike. "AI Memo 39-The new compiler" (PDF). Archived from the original (PDF) on 13 December 2020. Retrieved 23 May 2008.
  16. ^ "Introduction to metacompilation in FORTH". 24 March 2021.
  17. ^ Howe, Richard James. "A Meta-compiler, an implementation of eForth, and a tutorial on both". GitHub. Retrieved 27 September 2022.
  18. ^ Chomsky, Noam (September 1956). "Three models for the description of language". IEEE Transactions on Information Theory. 2 (3): 113–124. doi:10.1109/TIT.1956.1056813. S2CID 19519474.
  19. ^ Knuth, Donald. "On the Translation of Languages from Left to Right" (PDF). Archived from the original (PDF) on 15 March 2012. Retrieved 29 May 2011.
  20. ^ Korenjak, A. "A Practical Method for Constructing LR(k) Processors", Communications of the ACM, Vol. 12, No. 11, 1969
  21. ^ DeRemer, F. Practical Translators for LR(k) Languages. PhD dissertation, MIT, 1969.
  22. ^ DeRemer, F. "Simple LR(k) Grammars", Communications of the ACM, Vol. 14, No. 7, 1971.
  23. ^ a b Thomas J Pennello (1986). "Very fast LR parsing". ACM SIGPLAN Notices. Vol. 21, no. 7.
  24. ^ G.H. Roberts (1988). "Recursive ascent: an LR analog to recursive descent". ACM SIGPLAN Notices. 23 (8): 23–29. doi:10.1145/47907.47909. S2CID 12740771.
  25. ^ René Leermakers; Lex Augusteijn; Frans E.J. Kruseman Aretz (1992). "A functional LR parser". Theoretical Computer Science. 104 (2): 313–323. doi:10.1016/0304-3975(92)90128-3.
  26. ^ A.A. Grau, "Recursive processes and ALGOL translation", Communications of the ACM, 4, No. 1, pp. 10–15. Jan. 1961
  27. ^ Edgar T. Irons, "A syntax-directed compiler for ALGOL 60", Communications of the ACM, 4, No. 1, Jan. 1961, pp. 51–55.
  28. ^ "Stories of the B5000 and People Who Were There" (PDF). Archived from the original (PDF) on 1 March 2021. Retrieved 1 August 2016.
  29. ^ Waychoff, Richard; Turner, Lloyd; Rosin, Robert F.; Pearson, Ralph W.; Oliphint, G. Clark; MacKenzie, F. Brad; MacDonald, Ray W.; MacDonald, Duncan N.; Lonergan, William D.; Kreuder, Norman L.; King, Paul D.; Hootman, Joseph T.; Hauck, Erwin A.; Hale, John E.; Galler, Bernard A.; Ford, James; Eppert, Ray R.; Dent, Benjamin A.; Dahm, David M.; Creech, Bobby A.; Collins, George A.; Berce, Henri; Barton, Robert S. (6 September 1985). "Burroughs B 5000 Conference". University of Minnesota. hdl:11299/107105.
  30. ^ P. M. Lewis, R. E. Stearns, "Syntax directed transduction," focs, pp.21–35, 7th Annual Symposium on Switching and Automata Theory (SWAT 1966), 1966
  31. ^ Lewis, P. and Stearns, R. "Syntax-Directed Transduction", Journal of the ACM, Vol. 15, No. 3, 1968.
  32. ^ "The PL/0 compiler/interpreter". Archived from the original on 8 December 2008. Retrieved 7 July 2011.
  33. ^ J. Earley, "An efficient context-free parsing algorithm", Communications of the Association for Computing Machinery, 13:2:94-102, 1970.
  34. ^ Backus, J. W. (1959). "The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMM Conference". Proceedings of the International Conference on Information Processing: 125–132.
  35. ^ Farrell, James A. (August 1995). "Extended Backus Naur Form". Compiler Basics. Retrieved 11 May 2011.
  36. ^ Donald E. Knuth, "Backus Normal Form vs. Backus Naur Form", Communications of the ACM, 7(12):735–736, 1964.
  37. ^ "TMG Meta Compiler". reocities.com. Archived from the original on 4 March 2016. Retrieved 30 June 2011.
  38. ^ "The Encyclopedia of Computer Languages". Archived from the original on 21 September 2007. Retrieved 30 June 2011.
  39. ^ McClure, R. M. (1965). "Programming languages for non-numeric processing---1: TMG---a syntax directed compiler". Proceedings of the 1965 20th national conference. pp. 262–274. doi:10.1145/800197.806050. ISBN 978-1-4503-7495-8. S2CID 44606611. {{cite book}}: |work= ignored (help)
  40. ^ R. M. McClure, TMG—A Syntax Directed Compiler Proc. 20th ACM National Conf. (1965), pp. 262–274.
  41. ^ "Multics PL/I". multicians.org.
  42. ^ "Chistory". Archived from the original on 10 January 2015. Retrieved 3 August 2011. Dennis M. Ritchie. The Development of the C Language
  43. ^ McKeeman, William Marshall; Horning, James J.; and Wortman, David B., A Compiler Generator (1971), ISBN 978-0-13-155077-3.
  44. ^ Computer Science Department, University of Toronto, "The XPL Programming Language"
  45. ^ Johnson, S.C., "Yacc – Yet Another Compiler-Compiler", Computing Science Technical Report 32, AT&T Bell Labs, 1975
  46. ^ Hamilton, Naomi (5 October 2023). "The A-Z of Programming Languages: YACC". TechWorld.
  47. ^ Schorre, D. V. (1964). "META II a syntax-oriented compiler writing language". Proceedings of the 1964 19th ACM national conference. pp. 41.301–41.3011. doi:10.1145/800257.808896. ISBN 978-1-4503-7918-2. S2CID 43144779. {{cite book}}: |work= ignored (help)
  48. ^ "Comp.compilers: Re: History and evolution of compilers". iecc.com.
  49. ^ Frances E. Allen, "Program optimization" In Mark I. Halpern and Christopher J. Shaw, editors, Annual Review in Automatic Programming, volume 5, pages 239–307. Pergamon Press, New York, 1969.
  50. ^ Allen, Frances E.; Cocke, John (11 July 1972). Graph-Theoretic Constructs for Program Control Flow Analysis (RC 3923) (PDF). Yorktown Heights, NY: IBM Thomas J. Watson Research Center. Retrieved 6 May 2021.
  51. ^ Frances E. Allen. "Control flow analysis". ACM SIGPLAN Notices, 5(7):1–19, July 1970.
  52. ^ Frances E. Allen. "A basis for program optimization". In Proc. IFIP Congress 71, pages 385–390. North-Holland, 1972.
  53. ^ Frances E. Allen and John Cocke. "A catalogue of optimizing transformations." In R. Rustin, editor, Design and Optimization of Compilers, pages 1–30. Prentice-Hall, 1971.
  54. ^ Frances E. Allen. "Interprocedural data flow analysis". In Proc. IFIP Congress 74, pages 398–402. North-Holland, 1974.
  55. ^ Frances E. Allen. "A method for determining program data relationships". In Andrei Ershov and Valery A. Nepomniaschy, editors, Proc. International Symposium on Theoretical Programming, Novosibirsk, USSR, August 1972, volume 5 of Lecture Notes in Computer Science, pages 299–308. Springer-Verlag, 1974.
  56. ^ Frances E. Allen and John Cocke. "A program data flow analysis procedure", Communications of the ACM, 19(3):137–147, March 1976.
  57. ^ Sarkar, Vivek (1991). "PTRAN—the IBM parallel translation system". Parallel functional languages and compilers. New York, NY: Association for Computing Machinery. pp. 309–391. doi:10.1145/107214.129260. ISBN 0-201-52243-8. Retrieved 6 May 2021.
  58. ^ John Cocke and Jacob T. Schwartz, Programming Languages and their Compilers. Courant Institute of Mathematical Sciences, New York University, April 1970.
  59. ^ Kildall, Gary Arlen (May 1972). Global expression optimization during compilation (Ph.D. dissertation). Seattle, Washington, USA: University of Washington, Computer Science Group. Thesis No. 20506, Technical Report No. 72-06-02.
  60. ^ Kildall, Gary Arlen (1 October 1973). "A Unified Approach to Global Program Optimization" (PDF). Proceedings of the 1st Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL). Boston, Massachusetts, USA: 194–206. doi:10.1145/512927.512945. hdl:10945/42162. S2CID 10219496. Retrieved 2 May 2023.
  61. ^ McKeeman, W.M. "Peephole optimization". Communications of the ACM 8, 7 (July 1965), 443–444
  62. ^ System/360 Instruction Timing Information (PDF). IBM Systems Reference Library. May 1964. Retrieved 6 May 2021.
  63. ^ Evans, Michael (1982). "Software engineering for the Cobol environment". Communications of the ACM. 25 (12): 874–882. doi:10.1145/358728.358732. S2CID 17268690.
  64. ^ CACM March 1973 pp 169–179.
  65. ^ Cytron, Ron; Ferrante, Jeanne; Rosen, Barry K.; Wegman, Mark N.; Zadeck, F. Kenneth (1991). "Efficiently Computing Static Single Assignment Form and the Control Dependence Graph" (PDF). ACM Transactions on Programming Languages and Systems. 13 (4): 451–490. CiteSeerX 10.1.1.100.6361. doi:10.1145/115372.115320. S2CID 13243943.

Further reading

[edit]
[edit]
Retrieved from "https://en.wikipedia.org/w/index.php?title=History_of_compiler_construction&oldid=1258728225"