History of compiler construction

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.

Compilers are large and complex programs, but systematic analysis and research by computer scientists has led to a clearer understanding of compiler construction and a large body of theory has been developed around them. Research into compiler construction has led to tools that make it much easier to create compilers, so that today computer science students can create their own small language and develop a simple compiler for it in a few weeks.

First compilers

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 compiler was written by Grace Hopper, in 1952, for the A-0 System language. The term compiler was coined by Hopper.[1][2] The A-0 functioned more as a loader or linker than the modern notion of a compiler. The first autocode and its compiler were developed by Alick Glennie in 1952 for the Mark 1 computer at the University of Manchester and is considered by some to be the first compiled programming language. The FORTRAN team led by John W. Backus at IBM is generally credited as having introduced the first complete compiler, in 1957. The first FORTRAN compiler 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]

The COBOL compiler for the UNIVAC II was probably the first to be written in a high-level language, namely FLOW-MATIC, by a team led by Grace Hopper.

Self-hosting compilers

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 or compiled by a compiler written in another language, or compiled by running the compiler in an interpreter.

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

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

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

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

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

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

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

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. It is almost certain that the "Compiler Compiler" name has entered common use due to Yacc rather than Brooker's work being remembered.

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

XPL is a dialect of the PL/I programming language, developed in 1967, used for the development of compilers for computer languages. It was designed and implemented by a team with William 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]

It is the name of both the programming language and the LALR parser generator system (or TWS: translator writing system) based on the language.

XPL featured a relatively simple bottom-up compiler system dubbed MSP (mixed strategy precedence) by its authors. It was bootstrapped through Burroughs Algol onto the IBM System/360 computer. Subsequent implementations of XPL featured an SLR(1) parser.

Yacc

Yacc is a parser generator (loosely, compiler-compiler), not to be confused with lex, which is a lexical analyzer frequently used as a first stage by Yacc. Yacc was developed by Stephen C. Johnson at AT&T for the Unix operating system.[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

Main article: metacompiler

Metacompilers differ from parser generators. They take a program in a metaprogramming language, and have grammar analyzing rules and code production transforms that output executable code. They can be programmed in their own metalanguages enabling them to compile themselves, making them self-hosting extensible language compilers.

Many metacompilers build on the work of Val Schorre. His META II, first released in 1962, was the first documented metacompiler. META II accepted grammars and code generation rules, and was able to compile itself and other languages. It also translated to one of the earliest instances of a virtual machine.[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. A grammar now produced an abstract syntax tree that the unparse rules operated on. The unparse tree pattern matching provided peephole optimization ability. Abstract syntax tree generation is programmed in the grammar analysis.

CWIC, described in a 1970 ACM publication is a third generation Schorre metacompiler that added lexical rules and backtracking operators to the grammar analysis. LISP 2 was married with the unparse rules of TREEMETA. 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 IBM System/360 machine code.

Later generations are not publicly documented. One important feature would be the abstraction of the target processor instruction set, generating to a pseudo instruction set that could be separately defined or mapped to a real machine's instructions.

Cross compilation

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

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

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

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

Capex COBOL Optimizer

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

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

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

PL/C

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

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

Main article: Intermediate language

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

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

Register Allocation

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

Notable compilers

This list is incomplete; you can help by expanding it.

See also

References

  1. ↑ 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.)"
  2. 1 2 3 The World's First COBOL Compilers Archived 13 October 2011 at the Wayback Machine.
  3. ↑ Backus et al. "The FORTRAN automatic coding system", Proc. AFIPS 1957 Western Joint Computer Conf., Spartan Books, Baltimore 188–198
  4. ↑ Rosen, Saul. ALTAC, FORTRAN, and compatibility. Proceedings of the 1961 16th ACM national meeting
  5. ↑ T. Hart and M. Levin "The New Compiler", AIM-39 CSAIL Digital Archive – Artificial Intelligence Laboratory Series
  6. 1 2 Tim Hart; Mike Levin. "AI Memo 39-The new compiler" (PDF). Retrieved 2008-05-23.
  7. ↑ 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.
  8. ↑ Knuth, Donald. "On the Translation of Languages from Left to Right" (PDF). Retrieved 29 May 2011.
  9. ↑ Korenjak, A. “A Practical Method for Constructing LR(k) Processors,” Communications of the ACM, Vol. 12, No. 11, 1969
  10. ↑ DeRemer, F. Practical Translators for LR(k) Languages. PhD dissertation, MIT, 1969.
  11. ↑ DeRemer, F. “Simple LR(k) Grammars,” Communications of the ACM, Vol. 14, No. 7, 1971.
  12. 1 2 Thomas J Pennello (1986). "Very fast LR parsing". ACM SIGPLAN Notices. 21 (7).
  13. ↑ G.H. Roberts (1988). "Recursive ascent: an LR analog to recursive descent".
  14. ↑ Leermakers, Augusteijn, Kruseman Aretz (1992). "A functional LR parser".
  15. ↑ A.A. Grau, "Recursive processes and ALGOL translation", Commun. ACM, 4, No. 1, pp. 10–15. Jan. 1961
  16. ↑ Edgar T. Irons, "A syntax-directed compiler for ALGOL 60", Commun. ACM, 4, No. 1, Jan. 1961, pp. 51–55.
  17. ↑ "Stories of the B5000 and People Who Were There" (PDF).
  18. ↑ "The Burroughs B5000 Conference, Charles Babbage Institute".
  19. ↑ P. M. Lewis, R. E. Stearns, "Syntax directed transduction," focs, pp.21–35, 7th Annual Symposium on Switching and Automata Theory (SWAT 1966), 1966
  20. ↑ Lewis, P. and Stearns, R. “Syntax-Directed Transduction,” Journal of the ACM, Vol. 15, No. 3, 1968.
  21. ↑ "The PL/0 compiler/interpreter".
  22. ↑ J. Earley, "An efficient context-free parsing algorithm", Communications of the Association for Computing Machinery, 13:2:94-102, 1970.
  23. ↑ Backus, J. W. (1959). "Proceedings of the International Conference on Information Processing". UNESCO: 125–132. |contribution= ignored (help)
  24. ↑ Farrell, James A. (August 1995). "Extended Backus Naur Form". Retrieved 11 May 2011. |contribution= ignored (help)
  25. ↑ Donald E. Knuth, "Backus Normal Form vs. Backus Naur Form", Commun. ACM, 7(12):735–736, 1964.
  26. ↑ "TMG Meta Compiler". reocities.com.
  27. ↑ http://hopl.murdoch.edu.au/showlanguage.prx?exp=242
  28. ↑ "Programming languages for non-numeric processing—1". acm.org.
  29. ↑ R. M. McClure, TMG—A Syntax Directed Compiler Proc. 20th ACM National Conf. (1965), pp. 262–274.
  30. ↑ "Multics PL/I". multicians.org.
  31. ↑ Dennis M. Ritchie. The Development of the C Language
  32. ↑ McKeeman, William Marshall; Horning, James J.; and Wortman, David B., A Compiler Generator (1971), ISBN 978-0-13-155077-3.
  33. ↑ Computer Science Department, University of Toronto, "The XPL Programming Language"
  34. ↑ Johnson, S.C., “Yacc – Yet Another Compiler Compiler”, Computing Science Technical Report 32, AT&T Bell Labs, 1975
  35. ↑ Hamilton, Naomi. "The A-Z of Programming Languages: YACC". TechWorld.
  36. ↑ "META II a syntax-oriented compiler writing language". acm.org.
  37. ↑ "Comp.compilers: Re: History and evolution of compilers". iecc.com.
  38. ↑ 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.
  39. ↑ 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.
  40. ↑ Frances E. Allen. Control flow analysis. ACM SIGPLAN Notices, 5(7):1–19, July 1970.
  41. ↑ Frances E. Allen. A basis for program optimization. In Proc. IFIP Congress 71, pages 385–390. North-Holland, 1972.
  42. ↑ 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.
  43. ↑ Frances E. Allen. Interprocedural data flow analysis. In Proc. IFIP Congress 74, pages 398–402. North-Holland, 1974.
  44. ↑ 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.
  45. ↑ Frances E. Allen and John Cocke. A program data flow analysis procedure. Communications of the ACM, 19(3):137–147, March 1976.
  46. ↑ 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.
  47. ↑ John Cocke and Jacob T. Schwartz, Programming Languages and their Compilers. Courant Institute of Mathematical Sciences, New York University, April 1970.
  48. ↑ McKeeman, W.M. Peephole optimization. Commun. ACM 8, 7 (July 1965), 443–444
  49. ↑ http://www.bitsavers.org/pdf/ibm/360/A22_6825-1_360instrTiming.pdf
  50. ↑ "Software engineering for the Cobol environment". acm.org.
  51. ↑ CACM March 1973 pp 169–179.
  52. ↑ 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. doi:10.1145/115372.115320.

Further reading

This article is issued from Wikipedia - version of the 11/13/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.