History of compiler construction
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. Thus, compilers are very important to programmers. Improvements to a compiler may lead to a large number of improved 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 sematics and a back-end generating machine code).
Contents
- 1 First compilers
- 2 Self-hosting compilers
- 3 Context-free grammars and parsers
- 4 Grammar description languages
- 5 Parser generators
- 6 Metacompilers
- 7 Cross compilation
- 8 Optimizing compilers
- 9 Diagnostics
- 10 Just in Time compilation
- 11 Intermediate representation
- 12 Code Generation
- 13 Notable compilers
- 14 See also
- 15 References
- 16 Further reading
- 17 External links
First compilers[edit]
Software for early computers was primarily written in assembly language. 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.
The first theoretical compiler was written by Corrado Böhm, in 1951, for his PhD thesis. The first implemented compiler was written by Grace Hopper, who also coined the term "compiler"[1][2], referring to her A-0 system which functioned as a loader or linker, not the modern notion of a compiler. 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.[3]
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.[4] 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.[2]
Self-hosting compilers[edit]
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 or compiled by a compiler written in another language, or compiled by running the compiler 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 dated 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[citation needed].
NELIAC[edit]
This section does not cite any sources. (January 2019) (Learn how and when to remove this template message) |
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.
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.[5] 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.[6]
- 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)[6]
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 commonly confused with metacompilation and metacompilers.[citation needed] 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.[7]
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]
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).[8]
Korenjak (1969) was the first to show parsers for programming languages could be produced using these techniques.[9] Frank DeRemer devised the more practical Simple LR (SLR) and Look-ahead LR (LALR) techniques, published in his PhD dissertation at MIT in 1969.[10][11] 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[12] 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.[12] The technique was later expounded upon by G.H. Roberts[13] in 1988 as well as in an article by Leermakers, Augusteijn, Kruseman Aretz[14] in 1992 in the journal Theoretical Computer Science.
LL parsing[edit]
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 CACM in separate papers by A.A. Grau and Edgar T. "Ned" Irons. [15] [16] Richard Waychoff and colleagues also implemented recursive descent in the Burroughs ALGOL compiler in March 1961,[17] the two groups used different approaches but were in at least informal contact.[18]
The idea of LL(1) grammars was introduced by Lewis and Stearns (1968).[19][20]
Recursive descent was popularised by Niklaus Wirth with PL/0, an educational programming language used to teach compiler construction in the 1970s.[21]
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[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.[22]
Grammar description languages[edit]
John Backus proposed "metalinguistic formulas"[23][24] 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,[25] 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]
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. It is almost certain that the "Compiler Compiler" name has entered common use due to Yacc rather than Brooker's work being remembered.[citation needed]
In the early 1960s, Robert McClure at Texas Instruments invented a compiler-compiler called TMG, the name taken from "transmogrification".[26][27][28][29] 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.[30] 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, Doug McIlroy created the new system's first higher-level language: an implementation of McClure's TMG.[31] 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.[32][33]
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.[34] 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.[35] 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.
Metacompilers[edit]
Metacompilers differ from parser generators, taking as input a program written in a metalanguage. Their input consists grammar analyzing formula and code production transforms that output executable 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)s. 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.[36]
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.[2]
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.[37]
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,[38] introduced the use of graph data structures to encode program content for optimization.[39] Her 1970 papers, Control Flow Analysis[40] and A Basis for Program Optimization[41] established intervals as the context for efficient and effective data flow analysis and optimization. Her 1971 paper with Cocke, A Catalogue of Optimizing Transformations,[42] 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.[43][44] Her 1976 paper with Cocke describes one of the two main analysis strategies used in optimizing compilers today.[45]
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.[46] 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.[47]
Peephole Optimization[edit]
Peephole optimization is a very simple but effective optimization technique. It was invented by William M. McKeeman and published in 1965 in CACM.[48] 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.[49][50]
Modern compilers typically provide optimization options, so programmers can 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.[51]
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]
Just in time compilation (JIT) is the generation of executable code on-the-fly or as close as possible to its actual execution, to take advantage of run time metrics or other performance enhancing options.
Intermediate representation[edit]
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.[52] 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]
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]
- Amsterdam Compiler Kit by Andrew Tanenbaum and Ceriel Jacobs
- Berkeley Pascal, created by Ken Thompson in 1975. Bill Joy and others at University of California, Berkeley added improvements
- GNU Compiler Collection, formerly the GNU C Compiler. First created by Richard Stallman in 1987, GCC is the major compiler used to build 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.
See also[edit]
- History of programming languages
- Lex (and Flex lexical analyser), the token parser commonly used in conjunction with yacc (and Bison).
- BNF, a metasyntax used to express context-free grammar: that is, a formal way to describe formal languages.
- Self-interpreter, an interpreter written in a language it can interpret.
References[edit]
- ^ 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.)"
- ^ a b c [1] The World's First COBOL Compilers Archived 13 October 2011 at the Wayback Machine
- ^ Backus et al. "The FORTRAN automatic coding system", Proc. AFIPS 1957 Western Joint Computer Conf., Spartan Books, Baltimore 188–198
- ^ [2] Rosen, Saul. ALTAC, FORTRAN, and compatibility. Proceedings of the 1961 16th ACM national meeting
- ^ T. Hart and M. Levin "The New Compiler", AIM-39 CSAIL Digital Archive – Artificial Intelligence Laboratory Series
- ^ a b Tim Hart; Mike Levin. "AI Memo 39-The new compiler" (PDF). Retrieved 2008-05-23.
- ^ Chomsky, Noam (Sep 1956). "Three models for the description of language" (PDF). Information Theory, IEEE Transactions. 2 (3): 113–124. doi:10.1109/TIT.1956.1056813. Retrieved 2007-06-18.
- ^ Knuth, Donald. "On the Translation of Languages from Left to Right" (PDF). Retrieved 29 May 2011.
- ^ Korenjak, A. “A Practical Method for Constructing LR(k) Processors,” Communications of the ACM, Vol. 12, No. 11, 1969
- ^ DeRemer, F. Practical Translators for LR(k) Languages. PhD dissertation, MIT, 1969.
- ^ DeRemer, F. “Simple LR(k) Grammars,” Communications of the ACM, Vol. 14, No. 7, 1971.
- ^ a b Thomas J Pennello (1986). "Very fast LR parsing". ACM SIGPLAN Notices. 21 (7).
- ^ G.H. Roberts (1988). "Recursive ascent: an LR analog to recursive descent".
- ^ Leermakers, Augusteijn, Kruseman Aretz (1992). "A functional LR parser".CS1 maint: Multiple names: authors list (link)
- ^ A.A. Grau, "Recursive processes and ALGOL translation", Commun. ACM, 4, No. 1, pp. 10–15. Jan. 1961
- ^ Edgar T. Irons, "A syntax-directed compiler for ALGOL 60", Commun. ACM, 4, No. 1, Jan. 1961, pp. 51–55.
- ^ "Stories of the B5000 and People Who Were There" (PDF).
- ^ "The Burroughs B5000 Conference, Charles Babbage Institute". hdl:11299/107105.
- ^ P. M. Lewis, R. E. Stearns, "Syntax directed transduction," focs, pp.21–35, 7th Annual Symposium on Switching and Automata Theory (SWAT 1966), 1966
- ^ Lewis, P. and Stearns, R. “Syntax-Directed Transduction,” Journal of the ACM, Vol. 15, No. 3, 1968.
- ^ "The PL/0 compiler/interpreter".
- ^ J. Earley, "An efficient context-free parsing algorithm", Communications of the Association for Computing Machinery, 13:2:94-102, 1970.
- ^ 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.
- ^ Farrell, James A. (August 1995). "Extended Backus Naur Form". Compiler Basics. Retrieved 11 May 2011.
- ^ Donald E. Knuth, "Backus Normal Form vs. Backus Naur Form", Commun. ACM, 7(12):735–736, 1964.
- ^ "TMG Meta Compiler". reocities.com.
- ^ "Archived copy". Archived from the original on 21 September 2007. Retrieved 30 June 2011.CS1 maint: Archived copy as title (link)
- ^ "Programming languages for non-numeric processing—1". acm.org.
- ^ R. M. McClure, TMG—A Syntax Directed Compiler Proc. 20th ACM National Conf. (1965), pp. 262–274.
- ^ "Multics PL/I". multicians.org.
- ^ "Archived copy". Archived from the original on 10 January 2015. Retrieved 3 August 2011.CS1 maint: Archived copy as title (link) Dennis M. Ritchie. The Development of the C Language
- ^ McKeeman, William Marshall; Horning, James J.; and Wortman, David B., A Compiler Generator (1971), ISBN 978-0-13-155077-3.
- ^ Computer Science Department, University of Toronto, "The XPL Programming Language"
- ^ Johnson, S.C., “Yacc – Yet Another Compiler Compiler”, Computing Science Technical Report 32, AT&T Bell Labs, 1975
- ^ Hamilton, Naomi. "The A-Z of Programming Languages: YACC". TechWorld.
- ^ "META II a syntax-oriented compiler writing language". acm.org.
- ^ "Comp.compilers: Re: History and evolution of compilers". iecc.com.
- ^ F.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.
- ^ Frances E. Allen and John Cocke. Graph theoretic constructs for program control flow analysis. Technical Report IBM Res. Rep. RC 3923, IBM T.J. Watson Research Center, Yorktown Heights, NY, 1972.
- ^ Frances E. Allen. Control flow analysis. ACM SIGPLAN Notices, 5(7):1–19, July 1970.
- ^ Frances E. Allen. A basis for program optimization. In Proc. IFIP Congress 71, pages 385–390. North-Holland, 1972.
- ^ 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.
- ^ Frances E. Allen. Interprocedural data flow analysis. In Proc. IFIP Congress 74, pages 398–402. North-Holland, 1974.
- ^ 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.
- ^ Frances E. Allen and John Cocke. A program data flow analysis procedure. Communications of the ACM, 19(3):137–147, March 1976.
- ^ Vivek Sarkar. The PTRAN Parallel Programming System. In Parallel Functional Programming Languages and Compilers, edited by B. Szymanski, ACM Press Frontier Series, pages 309–391, 1991.
- ^ John Cocke and Jacob T. Schwartz, Programming Languages and their Compilers. Courant Institute of Mathematical Sciences, New York University, April 1970.
- ^ McKeeman, W.M. Peephole optimization. Commun. ACM 8, 7 (July 1965), 443–444
- ^ http://www.bitsavers.org/pdf/ibm/360/A22_6825-1_360instrTiming.pdf
- ^ "Software engineering for the Cobol environment". acm.org.
- ^ CACM March 1973 pp 169–179.
- ^ 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.
Further reading[edit]
- Backus, John, et al., "The FORTRAN Automatic Coding System", Proceedings of the Western Joint Computer Conference, Los Angeles, California, February 1957. Describes the design and implementation of the first FORTRAN compiler by the IBM team.
- Knuth, D. E., RUNCIBLE-algebraic translation on a limited computer, Communications of the ACM, Vol. 2, p. 18, (Nov. 1959).
- Irons, Edgar T., A syntax directed compiler for ALGOL 60, Communications of the ACM, Vol. 4, p. 51. (Jan. 1961)
- Dijkstra, Edsger W. (1961). "ALGOL 60 Translation: An ALGOL 60 Translator for the X1 and Making a Translator for ALGOL 60 (PDF) (Technical report). Amsterdam: Mathematisch Centrum. 35.
- Conway, Melvin E., Design of a separable transition-diagram compiler, Communications of the ACM, Volume 6, Issue 7 (July 1963)
- Floyd, R. W., Syntactic analysis and operator precedence, Journal of the ACM, Vol. 10, p. 316. (July 1963).
- Cheatham, T. E., and Sattley, K., Syntax directed compilation, SJCC p. 31. (1964).
- Randell, Brian; Russell, Lawford John, ALGOL 60 Implementation: The Translation and Use of ALGOL 60 Programs on a Computer, Academic Press, 1964
- Knuth, D. E. (July 1965). "On the translation of languages from left to right" (PDF). Information and Control. 8 (6): 607–639. doi:10.1016/S0019-9958(65)90426-2. Retrieved 29 May 2011.
- Cocke, John; Schwartz, Jacob T., Programming Languages and their Compilers: Preliminary Notes, Courant Institute of Mathematical Sciences technical report, New York University, 1969.
- Bauer, Friedrich L.; Eickel, Jürgen (Eds.), Compiler Construction, An Advanced Course, 2nd ed. Lecture Notes in Computer Science 21, Springer 1976, ISBN 3-540-07542-9
- Gries, David, Compiler Construction for Digital Computers, New York : Wiley, 1971. ISBN 0-471-32776-X
External links[edit]
- Compiler Construction before 1980 — Annotated literature list by Dick Grune
- "A HISTORY OF WRITING COMPILERS" (PDF). Computers and Automation. XI (12): 8–10, 12, 14, 24–25. Dec 1962.