The theory of parsing, translation, and compiling

ABSTRACT

From volume 1 Preface (See Front Matter for full Preface) This book is intended for a one or two semester course in compiling theory at the senior or graduate level. It is a theoretically oriented treatment of a practical subject. Our motivation for making it so is threefold. (1) In an area as rapidly changing as Computer Science, sound pedagogy demands that courses emphasize ideas, rather than implementation details. It is our hope that the algorithms and concepts presented in this book will survive the next generation of computers and programming languages, and that at least some of them will be applicable to fields other than compiler writing. (2) Compiler writing has progressed to the point where many portions of a compiler can be isolated and subjected to design optimization. It is important that appropriate mathematical tools be available to the person attempting this optimization. (3) Some of the most useful and most efficient compiler algorithms, e.g. LR(k) parsing, require a good deal of mathematical background for full understanding. We expect, therefore, that a good theoretical background will become essential for the compiler designer. While we have not omitted difficult theorems that are relevant to compiling, we have tried to make the book as readable as possible. Numerous examples are given, each based on a small grammar, rather than on the large grammars encountered in practice. It is hoped that these examples are sufficient to illustrate the basic ideas, even in cases where the theoretical developments are difficult to follow in isolation. From volume 2 Preface (See Front Matter for full Preface) Compiler design is one of the first major areas of systems programming for which a strong theoretical foundation is becoming available. Volume I of The Theory of Parsing, Translation, and Compiling developed the relevant parts of mathematics and language theory for this foundation and developed the principal methods of fast syntactic analysis. Volume II is a continuation of Volume I, but except for Chapters 7 and 8 it is oriented towards the nonsyntactic aspects of compiler design. The treatment of the material in Volume II is much the same as in Volume I, although proofs have become a little more sketchy. We have tried to make the discussion as readable as possible by providing numerous examples, each illustrating one or two concepts. Since the text emphasizes concepts rather than language or machine details, a programming laboratory should accompany a course based on this book, so that a student can develop some facility in applying the concepts discussed to practical problems. The programming exercises appearing at the ends of sections can be used as recommended projects in such a laboratory. Part of the laboratory course should discuss the code to be generated for such programming language constructs as recursion, parameter passing, subroutine linkages, array references, loops, and so forth.

REFERENCES

• 1: Church, A. [1956] Introduction to Mathematical Logic. Princeton University Press, Princeton, N.J.
• 2: Halmos, P. R. [1963] Lectures on Boolean Algebras. Van Nostrand Reinhold, New York.
• 3: Mendelson, E. [1968] Introduction to Mathematical Logic. Van Nostrand Reinhold, New York.
• 1: Borodin, A. [1970] Computational complexity---a survey. Proc. Fourth Annual Princeton Conference on Information Sciences and Systems, pp. 257--262. Also see Aho [1973].
• 2: Davis, M. [1958] Computability and Unsolvability. McGraw-Hill, New York.
• 3: Davis, M. (ed.) [1965] The Undecidable. Basic papers in undecidable propositions, unsolvable problems and computable functions. Raven Press, New York.
• 4: Hartmanis, J., and J. E. Hopcroft [1970] An overview of the theory of computational complexity. J. ACM 18:3, 444--475.
• 5: Hopcroft, J. E., and J. D. Ullman [1969] Formal Languages and Their Relation to automata. Addison-Wesley, Reading, Mass.
• 6: Irland, M. I., and P. C. Fischer [1970] A bibliography on computational complexity. CSRR 2028. Department of Applied Analysis and Computer Science, University of Waterloo, Ontario.
• 7: Kleene, S. C. [1952] Introduction to Metamathematics. Van Nostrand Reinhold, New York.
• 8: Knuth, D. E. [1965] On the translation of languages from left to right. Information and Control 8:6, 607--639.
• 9: Minsky, M. [1967] Computation: Finite and Infinite Machines. Prentice-Hall, Englewoods Cliffs, N.J.
• 10: Post, E. L. [1947] Recursive unsolvability of a problem of Thue. J. Symbolic Logic, 12, 1--11. Reprinted in Davis [1965], pp. 292--303.
• 11: Rogers, H., Jr. [1967] Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York.
• 12: Turing, A. M. [1936] On computable numbers, with an application to the Entscheidungsproblem. Proc. London Mathematical Soc. Ser. 2, 42, 230--265. Corrections, Ibid., 43 (1937), 544--546.
• 1: Berge, C. [1958] The Theory of Graphs and Its Applications. Wiley, New York.
• 2: Floyd, R. W. [1962a] Algorithm 97: shortest path. Comm. ACM 5:6, 345.
• 3: Harary, E. [1969] Graph Theory. Addison-Wesley, Reading, Mass.
• 4: Knuth, D. E. [1968a] The Art of Computer Programming, Vol. 1: Fundamental Algorithms. Addison-Wesley, Reading, Mass.
• 5: Munro, I. [1971] Efficient determination of the transitive closure of a directed graph. Information Processing Letters 1:2, 56--58.
• 6: Ore, O. [1962] Theory of Graphs. American Mathematical Society Colloquium Publications, Vol. 38, Providence.
• 7: Strassen, V. [1969] Gaussian elimination is not optimal. Numerische Mathematik 13, 354--356.
• 1: Cheatham, T. E. [1966] The introduction of definitional facilities into higher level programming languages. Proc. AFIPS Fall Joint Computer Conference. Vol. 30. Spartan, New York, pp. 623--637.
• 2: Chomsky, N. [1959a] On certain formal properties of grammars. Information and Control 2:2, 137--167.
• 3: Chomsky, N. [1963] Formal properties of grammars. In Handbook of Mathematical Psychology, Vol. 2, R. D. Luce, R. R. Bush, and E. Galanter (eds.). Wiley, New York, pp. 323--418.
• 4: Christensen, C., and J. C. Shaw (eds.) [1969] Proc. of the extensible languages symposium. ACM SIGPLAN Notices 4:8.
• 5: Engeler, E. (ed.) [1971] Symposium on Semantics of Algorithmic Languages. Lecture Notes in Mathematics. Springer, Berlin.
• 6: Galler, B. A., and A. J. Perlis [1967] A proposal for definitions in ALGOL. Comm. ACM 10:4, 204--219.
• 7: Leavenworth, B. M. [1966] Syntax macros and extended translation. Comm. ACM 9:11, 790--793.
• 8: Lucas, P., and K. Walk [1969] On the formal description of PL/I. Annual Review in Automatic Programming, Vol. 6, No. 3. Pergamon, Elmsford, N.Y., pp. 105--182.
• 9: McIlroy, M. D. [1960] Macro instruction extensions of compiler languages. Comm. ACM 3:4, 414--220.
• 10: Naur, P. (ed.) [1963] Revised report on the algorithmic language ALGOL 60. Comm. ACM 6:1, 1--17.
• 11: Sammet, J. E. [1969] Programming Languages: History and Fundamentals. Prentice-Hall, Englewood Cliffs, N.J.
• 12: Steel, T. B. (ed.) [1966] Formal Language Description Languages for Computer Programming. North-Holland, Amsterdam.
• 13: Van Wijngaarden, A. (ed.) [1969] Report on the algorithmic language ALGOL 68. Numerische Mathematik 14, 79--218.
• 14: Wegbreit, B. [1970] Studies in extensible programming languages. Ph. D. Thesis, Harvard University, Cambridge, Mass.
• 1: Backus, J. W., et al. [1957] The FORTRAN Automatic Coding System. Proc. Western Joint Computer Conference, Vol. 11, pp. 188--198.
• 2: Brooker, R. A., and D. Morris [1963] The compiler-compiler. Annual Review in Automatic Programming, Vol. 3. Pergamon, Elmsford, N.Y., pp. 229--275.
• 3: Cheatham, T. E., [1965] The TGS-II translator-generator system. Proc. IFIP Congress 65. Spartan, New York, pp. 592--593.
• 4: Cheatham, T. E., and T. Standish [1970] Optimization aspects of compiler-compilers. ACM SIGPLAN Notices 5: 10, 10--17.
• 5: Cocke, J., and J. T. Schwartz [1970] Programming Languages and Their Compilers (2nd ed.). Courant Institute of Mathematical Sciences, New York University, New York.
• 6: Conway, R. W., and W. L. Maxwell [1963] CORC: the Cornell computing language. Comm. ACM 6:6, 317--321.
• 7: Conway, R. W., and W. L. Maxwell [1968] CUPL---an approach to introductory computing instruction. Technical Report No. 68-4. Department of Computer Science, Cornell University, Ithaca, N.Y.
• 8: Conway, R. W., et al. [1970] PL/C. A high performance subset of PL/I. Technical Report 70-55. Department of Computer Science, Cornell University, Ithaca, N.Y.
• 9: Dewar, R. B. K., R. R. Hochsprung, and W. S. Worley [1969] The IITRAN programming language. Comm. ACM 12: 10, 569--575.
• 10: Elspas, B., M. W. Green, and K. N. Levitt [1971] Software reliability. Computer 1, 21--27.
• 11: Feldman, J. A. [1966] A formal semantics for computer languages and its application in a compiler-compiler. Comm. ACM 9:1, 3--9.
• 12: Feldman, J. A., and D. Gries [1968] Translator writing systems. Comm. ACM 11:2, 77--113.
• 13: Floyd, R. W. [1967a] Assigning meanings to programs. In Schwartz [1967], pp. 19--32.
• 14: Freeman, D. N. [1964] Error correction in CORC, the Cornell computing language. Proc. AFIPS Fall Joint Computer Conference, Vol. 26. Spartan, New York, pp. 15--34.
• 15: Gries, D. [1971] Compiler Construction for Digital Computers. Wiley, New York.
• 16: Hopgood, F. R. A. [1969] Compiling Techniques. American Elsevier, New York.
• 17: Ingerman, P. Z. [1966] A Syntax Oriented Translator. Academic Press, New York.
• 18: Irons, E. T. [1963b] The structure and use of the syntax directed compiler. Annual Review in Automatic Programming, Vol. 3. Pergamon, Elmsford, N.Y., pp. 207--227.
• 19: Lee, J. A. N. [1967] Anatomy of a Compiler. Van Nostrand Reinhold, New York.
• 20: McCarthy, J. [1963] A basis for the mathematical theory of computation. In Braffort and Hirschberg [1963], pp. 33--71.
• 21: McCarthy, J., and J. A. Painter [1967] Correctness of a compiler for arithmetic expressions. In Schwartz [1967], pp. 33--41.
• 22: McClure, R. M. [1965] TMG---a syntax directed compiler. Proc. ACM National Conference, Vol. 20, pp. 262--274.
• 23: McKeeman, W. M., J. J. Horning, and D. B. Wortman [1970] A Compiler Generator. Prentice-Hall, Englewood Cliffs, N.J.
• 24: Morgan, H. L. [1970] Spelling correction in systems programs. Comm. ACM 13:2, 90--93.
• 25: Moulton, P. G., and M. E. Muller [1967] A compiler emphasizing diagnostics. Comm. ACM 10:1, 45--52.
• 26: Painter, J. A. [1970] Effectiveness of an optimizing compiler for arithmetic expressions. ACM SIGPLAN Notices 5:7, 101--126.
• 27: Randell, B., and L. J. Russell [1964] ALGOL 60 Implementation. Academic Press, New York.
• 28: Reynolds, J. C. [1965] An introduction to the COGENT programming system. Proc. ACM National Conference, Vol. 20, p. 422.
• 29: Rosen S. (ed.) [1967a] Programming Systems and Languages. McGraw-Hill, New York.
• 30: Rosen, S. [1967b] A compiler-building system developed by Brooker and Morris. In Rosen [1967a], pp. 306--331.
• 31: Schorre, D. V. [1964] META II, a syntax oriented compiler writing language, Proc. ACM National Conference, Vol. 19, pp. D1.3--1D1.3--11.
• 32: Warshall, S., and R. M. Shapiro [1964] A general purpose table driven compiler. Proc. AFIPS Spring Joint Computer Conference, Vol. 25. Spartan, New York, pp. 59--65.
• 1: Bar-Hillel, Y. [1964] Language and Information. Addison-Wesley, Reading, Mass.
• 2: Bobrow, D. G. [1963] Syntactic analysis of English by computer---a survey. Proc. AFIPS Fall Joint Computer Conference, Vol. 24. Spartan, New York, pp. 365--387.
• 3: Chomsky, N. [1965] Aspects of the Theory of Syntax. M.I.T. Press, Cambridge, Mass.
• 4: Miller, W. F., and A. C. Shaw [1968] Linguistic methods in picture processing---a survey. Proc. AFIPS Fall Joint Computer Conference, Vol. 33. The Thompson Book Co., Washington, D.C., pp. 279--290.
• 5: Montanari, U. G. [1970] Separable graphs, planar graphs and web grammars. Information and Control 16:3, 243--267.
• 6: Pavlidis, T. [1972] Linear and context-free graph grammars. J. ACM 19:1, 11--23.
• 7: Pfaltz, J. L., and A. Rosenfeld [1969] Web grammars. Proc. International Joint Conference on Artificial Intelligence, Washington, D. C., pp. 609--619.
• 8: Shaw, A. C. [1970] Parsing of graph-representable pictures. J. ACM 17:3, 453--481.
• 1: Aho, A. V. [1968] Indexed grammars---an extension of context-free grammars. J. ACM 15:4, 647--671.
• 2: Bar-Hillel, Y. [1964] Language and Information. Addison-Wesley, Reading, Mass.
• 3: Book, R. V. [1970] Problems in formal language theory. Proc. Fourth Annual Princeton Conference on Information Sciences and Systems, pp. 253--256. Also see Aho [1973].
• 4: Chomsky, N. [1956] Three models for the description of language. IEEE Trans. on Information Theory 2:3, 113--124.
• 5: Chomsky, N. [1957] Syntactic Structures. Mouton and Co., The Hague.
• 6: Chomsky, N. [1959a] On certain formal properties of grammars. Information and Control 2:2, 137--167.
• 7: Chomsky, N. [1959b] A note on phrase structure grammars. Information and Control 2: 4, 393--395.
• 8: Chomsky, N. [1963] Formal properties of grammars. In Handbook of Mathematical Psychology, Vol. 2, R. D. Luce, R. R. Bush, and E. Galanter (eds.). Wiley, New York, pp. 323--418.
• 9: Ginsburg, S. [1966] The Mathematical Theory of Context-Free Languages. McGraw-Hill, New York.
• 10: Ginsburg, S., and S. A. Greibach [1969] Abstract families of languages. Memoir American Math. Soc. No. 87, 1--32.
• 11: Greibach S. A., and J. E. Hopcroft [1969] Scattered context grammars. J. Computer and System Sciences 3:3, 233--247.
• 12: Haines, L. H. [1970] Representation theorems for context-sensitive languages. Department of Electrical Engineering and Computer Sciences, University of California, Berkeley.
• 13: Hopcroft, J. E., and J. D. Ullman [1967] An approach to a unified theory of automata. Bell System Tech. J. 46:8, 1763--1829.
• 14: Hopcroft, J. E., and J. D. Ullman [1969] Formal Languages and Their Relation to automata. Addison-Wesley, Reading, Mass.
• 15: McCulloch, W. S., and W. Pitts [1943] A logical calculus of the ideas immanent in nervous activity. Bulletin of Math. Biophysics 5, 115--133.
• 16: Moore, E. F. [1956] Gedanken experiments on sequential machines. In Shannon and McCarthy [1956], pp. 129--153.
• 17: Rabin, M. O., and D. Scott [1959] Finite automata and their decision problems. IBM J. Research and Development 3, 114--125. Reprinted in Moore [1964], pp. 63--91.
• 18: Rosenkrantz, D. J. [1968] Programmed grammars and classes of formal languages. J. ACM 16:1, 107--131.
• 1: Brzozowski, J. A. [1962] A survey of regular expressions and their applications. IRE Trans. on Electronic Computers 11:3, 324--335.
• 2: Chomsky, N., and G. A. Miller [1958] Finite state languages. Information and Control 1:2, 91--112.
• 3: Kleene, S. C. [1956] Representation of events in nerve nets. In Shannon and McCarthy [1956], pp. 3--40.
• 4: McNaughton, R., and H. Yamada [1960] Regular expressions and state graphs for automata. IRE Trans. on Electronic Computers 9: 1, 39--47. Reprinted in Moore [1964], pp. 157--174.
• 5: Rabin, M. O., and D. Scott [1959] Finite automata and their decision problems. IBM J. Research and Development 3, 114--125. Reprinted in Moore [1964], pp. 63--91.
• 6: Salomaa, A. [1966] Two complete axiom systems for the algebra of regular events. J. ACM 13:1, 158--169.
• 7: Shepherdson, J. C. [1959] The reduction of two-way automata to one-way automata. IBM J. Research 3, 198--200. Reprinted in Moore [1964], pp. 92--97.
• 1: Arbib, M. A. [1969] Theories of Abstract Automata. Prentice-Hall, Englewood Cliffs, N.J.
• 2: Booth, T. L. [1967] Sequential Machines and Automata Theory. Wiley, New York.
• 3: Brzozowski, J. A. [1964] Derivatives of regular expressions. J. ACM 11:4, 481--494.
• 4: Gill, A. [1962] Introduction to the Theory of Finite State Machines. McGraw-Hill, New York.
• 5: Ginsburg, S. [1962] An Introduction to Mathematical Machine Theory. Addison-Wesley, Reading, Mass.
• 6: Ginzburg, A. [1968] Algebraic Theory of Automata. Academic Press, New York.
• 7: Harrison, M. A. [1965] Introduction to Switching and Automata Theory. McGraw-Hill, New York.
• 8: Hopcroft, J. E. [1971] An n log n algorithm for minimizing states in a finite automaton. CS71-190. Computer Science Department, Stanford University, Stanford, Cal. Also in Theory of Machines and Computations, Z. Kohavi and A. Paz (eds). Academic Press, New York, pp. 189--196.
• 9: Huffman, D. A. [1954] The synthesis of sequential switching circuits. J. Franklin Institute 257, 3--4, 161, 190, and 275--303.
• 10: Kameda, T., and P. Weiner [1968] On the reduction of nondeterministic automata. Proc. Second Annual Princeton Conference on Information Sciences and Systems, pp. 348--352.
• 11: Kosaraju, S. R. [1970] Finite state automata with markers. Proc. Fourth Annual Princeton Conference on Information Sciences and Systems, p. 380.
• 12: Minsky, M. [1967] Computation: Finite and Infinite Machines. Prentice-Hall, Englewoods Cliffs, N.J.
• 13: Moore, E. F. [1956] Gedanken experiments on sequential machines. In Shannon and McCarthy [1956], pp. 129--153.
• 14: Prather, R. E. [1969] Minimal solutions of Paull-Unger problems. Math. System Theory 3:1, 76--85.
• 15: Rabin, M. O., and D. Scott [1959] Finite automata and their decision problems. IBM J. Research and Development 3, 114--125. Reprinted in Moore [1964], pp. 63--91.
• 16: Salomaa, A. [1969a] Theory of Automata. Pergamon, Elmsford, N.Y.
• 17: Thompson, K. [1968] Regular expression search algorithm. Comm. ACM 11:6, 419--422.
• 1: Chomsky, N. [1959a] On certain formal properties of grammars. Information and Control 2:2, 137--167.
• 2: Chomsky, N. [1963] Formal properties of grammars. In Handbook of Mathematical Psychology, Vol. 2, R. D. Luce, R. R. Bush, and E. Galanter (eds.). Wiley, New York, pp. 323--418.
• 3: Chomsky, N., and M. P. Schutzenberger [1963] The algebraic theory of context-free languages. In Braffort and Hirschberg [1963], pp. 118--161.
• 4: Evey, R. J. [1963] Applications of pushdown-store machines. Proc. AFIPS Fall Joint Computer Conference, Vol. 24. Spartan, New York, pp. 215--227.
• 5: Floyd, R. W. [1963] Syntactic analysis and operator precedence. J. ACM 10:3, 316--333.
• 6: Ginsburg, S., and H. G. Rice [1962] Two families of languages related to ALGOL. J. ACM 9:3, 350--371.
• 7: Greibach, S. A. [1965] A new normal form theorem for context-free phrase structure grammars. J. ACM 12:1, 42--52.
• 8: Rosenkrantz, D. J. [1967] Matrix equations and normal forms for context-free grammars. J. ACM 14: 3, 501--507.
• 1: Aho, A. V., J. E. Hopcroft, and J. D. Ullman [1968] Time and tape complexity of pushdown automaton languages. Information and Control 13:3, 186--206.
• 2: Chomsky, N. [1962] Context-free grammars and pushdown storage. Quarterly Progress Report No. 65. Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, Mass.
• 3: Cook, S. A. [1971] Linear time simulation of deterministic two-way pushdown automata. Proc. IFIP Congress 71, TA-2. North-Holland, Amsterdam. pp. 174--179.
• 4: Evey, R. J. [1963] Applications of pushdown-store machines. Proc. AFIPS Fall Joint Computer Conference, Vol. 24. Spartan, New York, pp. 215--227.
• 5: Gray, J. N., M. A. Harrison, and O. Ibarra [1967] Two way pushdown automata. Information and Control 11:1, 30--70.
• 6: Hartmanis, J., P. M. Lewis, II, and R. E. Stearns [1965] Classifications of computations by time and memory requirements. Proc. IFIP Congress 65. Spartan, New York, pp. 31--35.
• 7: Oettinger, A. [1961] Automatic syntactic analysis and the pushdown store. In Structure of Language and its Mathematical Concepts, Proc. 12th Symposium on Applied Mathematics. American Mathematical Society, Providence, pp. 104--129.
• 8: Schutzenberger, M. P. [1963] On context-free languages and pushdown automata. Information and Control 6:3, 246--264.
• 1: Bar-Hillel Y., M. Perles, and E. Shamir [1961] On formal properties of simple phrase structure grammars. Z. Phonetik, Sprachwissenschaft und Kommunikationsforschung 14, 143--172. Also in Bar-Hillel [1964], pp. 116--150.
• 2: Blattner, M. [1972] The unsolvability of the equality problem for sentential forms of context-free languages. Unpublished Memorandum, UCLA, Los Angeles, Calif. To appear in JCSS.
• 3: Book, R. V. [1970] Problems in formal language theory. Proc. Fourth Annual Princeton Conference on Information Sciences and Systems, pp. 253--256. Also see Aho [1973].
• 4: Cantor, D. G. [1962] On the ambiguity problem of Backus systems. J. ACM 9:4, 477--479.
• 5: Chomsky, N. [1959a] On certain formal properties of grammars. Information and Control 2:2, 137--167.
• 6: Chomsky, N., and M. P. Schutzenberger [1963] The algebraic theory of context-free languages. In Braffort and Hirschberg [1963], pp. 118--161.
• 7: Floyd, R. W. [1962a] Algorithm 97: shortest path. Comm. ACM 5:6, 345.
• 8: Ginsburg, S. [1966] The Mathematical Theory of Context-Free Languages. McGraw-Hill, New York.
• 9: Ginsburg, S., and S. A. Greibach [1966] Deterministic context-free languages. Information and Control 9:6, 620--648.
• 10: Gross, M., and A. Lentin [1970] Introduction to Formal Grammars. Springer-Verlag, New York.
• 11: Hopcroft, J. E., and J. D. Ullman [1969] Formal Languages and Their Relation to automata. Addison-Wesley, Reading, Mass.
• 12: Ogden, W. [1968] A helpful result for proving inherent ambiguity. Mathematical Systems Theory 2:3, 191--194.
• 13: Parikh, R. J. [1966] On context-free languages. J. ACM 13:4, 570--581.
• 14: Salomaa, A. [1969b] On the index of a context-free grammar and language. Information and Control 14:5, 474--477.
• 15: Stearns, R. E. [1967] A regularity test for pushdown machines. Information and Control 11: 3, 323--340.
• 1: Barnett, M. P., and R. P. Futrelle [1962] Syntactic analysis by digital computer. Comm. ACM 5: 10, 515--526.
• 2: Ginsburg, S. [1962] An Introduction to Mathematical Machine Theory. Addison-Wesley, Reading, Mass.
• 3: Griffiths, T. V. [1968] The unsolvability of the equivalence problem for A-free nondeterministic generalized machines. J. ACM 15:3, 409--413.
• 4: Irons, E. T. [1961] A syntax directed compiler for ALGOL 60. Comm. ACM 4:1, 51--55.
• 5: Lewis, P. M., II, and R. E. Stearns [1968] Syntax directed transduction. J. ACM 15:3, 464--488.
• 1: Aho, A. V., and J. D. Ullman [1969a] Syntax directed translation and the pushdown assembler. J. Computer and System Sciences 3:1, 37--56.
• 2: Aho, A. V., and J. D. Ullman [1969b] Properties of syntax directed translations. J. Computer and System Sciences 3:3, 319--334.
• 1: Freeman, D. N. [1964] Error correction in CORC, the Cornell computing language. Proc. AFIPS Fall Joint Computer Conference, Vol. 26. Spartan, New York, pp. 15--34.
• 2: Johnson, W. L., J. H. Porter, S. I. Ackley, and D. T. Ross [1968] Automatic generation of efficient lexical processors using finite state techniques. Comm. ACM 11:12, 805--813.
• 3: Morgan, H. L. [1970] Spelling correction in systems programs. Comm. ACM 13:2, 90--93.
• 4: Thompson, K. [1968] Regular expression search algorithm. Comm. ACM 11:6, 419--422.
• 1: Cheatham, T. E. [1967] The Theory and Construction of Compilers (2nd ed.). Computer Associates, Inc., Wakefield, Mass.
• 2: Gray, J. N. [1969] Precedence parsers for programming languages. Ph. D. Thesis, Department of Computer Science, University of California, Berkeley.
• 3: Gray, J. N., and M. A. Harrison [1969] Single pass precedence analysis. IEEE Conference Record of 10th Annual Symposium on Switching and Automata Theory, pp. 106--117.
• 4: Reynolds, J. C., and R. Haskell [1970] Grammatical coverings. Unpublished memorandum, Syracuse University.
• 1: Cheatham, T. E., and K. Sattley [1964] Syntax directed compiling. Proc. AFIPS Spring Joint Computer Conference, Vol. 25. Spartan, New York, pp. 31--57.
• 2: Cohen, D. J., and C. C. Gotlieb [1970] A list structure form of grammars for syntactic analysis. Computing Surveys 2: 1, 65--82.
• 3: Floyd, R. W. [1964b] The syntax of programming languages---a survey. IEEE Trans. on Electronic Computers EC-13: 4, 346--353.
• 4: Floyd, R. W. [1967b] Nondeterministic algorithms. J. ACM 14:4, 636--644.
• 5: Griffiths, T. V., and S. R. Petrick [1965] On the relative efficiencies of context-free grammar recognizers. Comm. ACM 8:5, 289--300.
• 6: Hext, J. B., and P. S. Roberts [1970] Syntax analysis by Domolki's algorithm. Computer J. 13:3, 263--271.
• 7: Irons, E. T. [1961] A syntax directed compiler for ALGOL 60. Comm. ACM 4:1, 51--55.
• 8: Kuno, S., and A. G. Oettinger [1962] Multiple-path syntactic analyzer. Information Processing 62 (IFIP Congress), Popplewell (ed.). North-Holland, Amsterdam, pp. 306--311.
• 9: Reynolds, J. C. [1965] An introduction to the COGENT programming system. Proc. ACM National Conference, Vol. 20, p. 422.
• 10: Rosen, S. [1967b] A compiler-building system developed by Brooker and Morris. In Rosen [1967a], pp. 306--331.
• 11: Schorre, D. V. [1964] META II, a syntax oriented compiler writing language, Proc. ACM National Conference, Vol. 19, pp. D1.3--1D1.3--11.
• 12: Unger, S. H. [1968] A global parser for context-free phrase structure grammars. Comm. ACM 11:4, 240--246, and 11:6, 427.
• 1: Earley, J. [1968] An efficient context-free parsing algorithm. Ph. D. Thesis, Carnegie-Mellon University, Pittsburgh. Also see Comm. ACM (February, 1970) 13:2, 94--102.
• 2: Hays, D. G. [1967] Introduction to Computational Linguistics. American Elsevier, New York.
• 3: Kasami, T. [1965] An efficient recognition and syntax analysis algorithm for context-free languages. Scientific Report AFCRL-65-758. Air Force Cambridge Research Laboratory, Bedford, Mass.
• 4: Kasami, T., and K. Torii [1969] A syntax analysis procedure for unambiguous context-free grammars. J. ACM 16:3, 423--431.
• 5: Younger, D. H. [1967] Recognition and parsing of context-free languages in time n³. Information and Control 10:2, 189--208.
• 1: Culik, K., II [1968] Contribution to deterministic top-down analysis of context-free languages. Kybernetika 4:5, 422--431.
• 2: Knuth, D. E. [1967] Top-down syntax analysis. Lecture Notes. International Summer School on Computer Programming, Copenhagen. Also in Acta Informatica 1:2, (1971), 79--110.
• 3: Korenjak, A. J., and J. E. Hopcroft [1966] Simple deterministic languages. IEEE Conference Record of 7th Annual Symposium on Switching and Automata Theory, pp. 36--46.
• 4: Kurki-Suonio, R. [1969] Notes on top-down languages. BIT 9, 225--238.
• 5: Lewis, P. M., II, and D. J. Rosenkrantz [1971] An ALGOL compiler designed using automata theory. Proc. Symposium on Computers and Automata, Microwave Research Institute Symposia Series, Vol. 21. Polytechnic Institute of Brooklyn., New York., pp. 75--88.
• 6: Lewis, P. M., II, and R. E. Stearns [1968] Syntax directed transduction. J. ACM 15:3, 464--488.
• 7: Rosenkrantz, D. J., and P. M. Lewis, II [1970] Deterministic left corner parsing. IEEE Conference Record of 11th Annual Symposium on Switching and Automata Theory, pp. 139--152.
• 8: Rosenkrantz, D. J., and R. E. Stearns [1970] Properties of deterministic top-down grammars. Information and Control 17:3, 226--256.
• 9: Wood, D. [1970] Bibliography 23: Formal language theory and automata theory. Computing Reviews 11:7, 417--430.
• 1: Aho, A. V., and J. D. Ullman [1971] Translations on a context-free grammar. Information and Control 19:5, 439--475.
• 2: DeRemer, F. L. [1969] Practical translators for LR(k) languages. Ph. D. Thesis, Massachusetts Institute of Technology, Cambridge, Mass.
• 3: Hopcroft, J. E., and J. D. Ullman [1969] Formal Languages and Their Relation to automata. Addison-Wesley, Reading, Mass.
• 4: Knuth, D. E. [1965] On the translation of languages from left to right. Information and Control 8:6, 607--639.
• 5: Korenjak, A. J. [1969] A practical method for constructing LR(k) processors. Comm. ACM 12:11, 613--623.
• 6: Walters, D. A. [1970] Deterministic context-sensitive languages. Information and Control 17:1, 14--61.
• 1: Aho, A. V., J. E. Hopcroft, and J. D. Ullman [1968] Time and tape complexity of pushdown automaton languages. Information and Control 13:3, 186--206.
• 2: Bauer, H., S. Becker, and S. Graham [1968] ALGOL W implementation. CS98, Computer Science Department, Stanford University, Stanford, Cal.
• 3: Fischer, M. J. [1972] Efficiency of equivalence algorithms. Memo No. 256, Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, Mass.
• 4: Floyd, R. W. [1961] A descriptive language for symbol manipulation. J. ACM 8:4, 579--584.
• 5: Graham, S. L. [1970] Extended precedence languages, bounded right context languages and deterministic languages. IEEE Conference Record of 11th Annual Symposium on Switching and Automata Theory, pp. 175--180.
• 6: Gray, J. N. [1969] Precedence parsers for programming languages. Ph. D. Thesis, Department of Computer Science, University of California, Berkeley.
• 7: Ichbiah, J. D., and S. P. Morse [1970] A technique for generating almost optimal Floyd-Evans productions for precedence grammars. Comm. ACM 13:8, 501--508.
• 8: Leinius, R. P. [1970] Error detection and recovery for syntax directed compiler systems. Ph. D. Thesis, University of Wisconsin, Madison.
• 9: McKeeman, W. M. [1966] An approach to computer language design. CS48. Computer Science Department, Stanford University, Stanford, Cal.
• 10: Pair, C. [1964] Trees, pushdown stores and compilation. RFTI---Chiffres 7:3, 199--216.
• 11: Wirth, N. [1968] PL 360---a programming language for the 360 computers. J. ACM 15:1, 37--34.
• 12: Wirth, N., and H. Weber [1966] EULER---a generalization of ALGOL and its formal definition, Parts 1 and 2. Comm. ACM 9: 1--2, 13--23, and 89--99.
• 1: Eickel, J., M. Paul, F. L. Bauer, and K. Samelson [1963] A syntax-controlled generator of formal language processors. Comm. ACM 6:8, 451--455.
• 2: Evans, A., Jr. [1964] An ALGOL 60 compiler. Annual Review in Automatic Programming, Vol. 4. Pergamon, Elmsford, N.Y., pp. 87--124.
• 3: Feldman, J. A. [1966] A formal semantics for computer languages and its application in a compiler-compiler. Comm. ACM 9:1, 3--9.
• 4: Floyd, R. W. [1961] A descriptive language for symbol manipulation. J. ACM 8:4, 579--584.
• 5: Floyd, R. W. [1963] Syntactic analysis and operator precedence. J. ACM 10:3, 316--333.
• 6: Floyd, R. W. [1964a] Bounded context syntactic analysis. Comm. ACM 7:2, 62--67.
• 7: Floyd, R. W. [1964b] The syntax of programming languages---a survey. IEEE Trans. on Electronic Computers EC-13: 4, 346--353.
• 8: Graham, R. M. [1964] Bounded context translation. Proc. AFIPS Spring Joint Computer Conference, Vol. 25. Spartan, New York, pp. 17--29.
• 9: Gray, J. N., and M. A. Harrison [1969] Single pass precedence analysis. IEEE Conference Record of 10th Annual Symposium on Switching and Automata Theory, pp. 106--117.
• 10: Hopgood, F. R. A. [1969] Compiling Techniques. American Elsevier, New York.
• 11: Irons, E. T. [1964] Structural connections in formal languages. Comm. ACM 7:2, 62--67.
• 12: Loeckx, J. [1970] An algorithm for the construction of bounded-context parsers. Comm. ACM 13:5, 297--307.
• 13: McKeeman, W. M., J. J. Horning, and D. B. Wortman [1970] A Compiler Generator. Prentice-Hall, Englewood Cliffs, N.J.
• 14: Paul, M. [1962] A general processor for certain formal languages. Proc. ICC Symposium on Symbolic Language Data Processing. Gordon & Breach, New York, pp. 65--74.
• 15: Wise, D. S. [1971] Domolki's algorithm applied to generalized overlap resolvable grammars. Proc. Third Annual ACM Symposium on Theory of Computing, pp. 171--184.
• 1: Birman, A., and J. D. Ullman [1970] Parsing algorithms with backtrack. IEEE Conference Record of 11th Annual Symposium on Switching and Automata Theory, pp. 153--174.
• 2: Knuth, D. E. [1967] Top-down syntax analysis. Lecture Notes. International Summer School on Computer Programming, Copenhagen. Also in Acta Informatica 1:2, (1971), 79--110.
• 3: McClure, R. M. [1965] TMG---a syntax directed compiler. Proc. ACM National Conference, Vol. 20, pp. 262--274.
• 4: Schorre, D. V. [1964] META II, a syntax oriented compiler writing language, Proc. ACM National Conference, Vol. 19, pp. D1.3--1D1.3--11.
• 1: Cohen, R. S., and K. Culik, II [1971] LR-regular grammars---an extension of LR(k) grammars. IEEE Conference Record of 12th Annual Symposium on Switching and Automata Theory, pp. 153--165.
• 2: Colmerauer, A. [1970] Total precedence relations. J. ACM 17:1, 14--30.
• 3: Gray, J. N., and M. A. Harrison [1969] Single pass precedence analysis. IEEE Conference Record of 10th Annual Symposium on Switching and Automata Theory, pp. 106--117.
• 1: Aho, A. V., and J. D. Ullman [1972a] Linear precedence functions for weak precedence grammars. International J. Computer Mathematics, Section A, 3, 149--155.
• 2: Aho, A. V., and J. D. Ullman [1972b] Error detection in precedence parsers. Mathematical Systems Theory, 7:2 (February 1973), 97--113.
• 3: Bell, J. R. [1969] A new method for determining linear precedence functions for precedence grammars. Comm. ACM 12:10, 316--333.
• 4: Floyd, R. W. [1963] Syntactic analysis and operator precedence. J. ACM 10:3, 316--333.
• 5: Martin, D. F. [1972] A Boolean matrix method for the computation of linear precedence functions. Comm. ACM 15:6, 448--454.
• 6: Wirth, N. [1965] Algorithm 265: Find precedence functions. Comm. ACM 8:10, 604--605.
• 7: Wirth, N., and H. Weber [1966] EULER---a generalization of ALGOL and its formal definition, Parts 1 and 2. Comm. ACM 9: 1--2, 13--23, and 89--99.
• 1: Beals, A. J. [1969] The generation of a deterministic parsing algorithm. Report No. 304, Department of Computer Science, University of Illinois, Urbana.
• 2: Beals, A. J., J. E. LaFrance, and R. S. Northcote [1969] The automatic generation of Floyd production syntactic analyzers. Report No. 350. Department of Computer Science, University of Illinois, Urbana.
• 3: Cheatham, T. E. [1967] The Theory and Construction of Compilers (2nd ed.). Computer Associates, Inc., Wakefield, Mass.
• 4: DeRemer, F. L. [1968] On the generation of parsers for BNF grammars: an algorithm. Report No. 276. Department of Computer Science, University of Illinois, Urbana.
• 5: Earley, J. [1966] Generating a recognizer for a BNF grammar. Computation Center Report, Carnegie-Mellon University, Pittsburgh.
• 6: Haynes, H. R., and L. J. Schutte [1970] Compilation of optimized syntactic recognizers from Floyd-Evans productions. ACM SIGPLAN Notices 5:7, 38--51.
• 7: Ichbiah, J. D., and S. P. Morse [1970] A technique for generating almost optimal Floyd-Evans productions for precedence grammars. Comm. ACM 13:8, 501--508.
• 8: LaFrance, J. [1970] Optimization of error recovery in syntax directed parsing algorithms. ACM SIGPLAN Notices 5:12, 2--17.
• 1: Aho, A. V., and J. D. Ullman [1972c] Optimization of LR(k) parsers. J. Computer and System Sciences, 6:6, 573--602.
• 2: Aho, A. V., and J. D. Ullman [1972d] A technique for speeding up LR(k) parsers. Proc. Fourth Annual ACM Symposium on Theory of Computing, pp. 251--263.
• 3: Lewis, P. M., II, and D. J. Rosenkrantz [1971] An ALGOL compiler designed using automata theory. Proc. Symposium on Computers and Automata, Microwave Research Institute Symposia Series, Vol. 21. Polytechnic Institute of Brooklyn., New York., pp. 75--88.
• 4: Pager, D. [1970] A solution to an open problem by Knuth. Information and Control 17:5, 462--473.
• 1: Aho, A. V., and J. D. Ullman [1972d] A technique for speeding up LR(k) parsers. Proc. Fourth Annual ACM Symposium on Theory of Computing, pp. 251--263.
• 2: DeRemer, F. L. [1969] Practical translators for LR(k) languages. Ph. D. Thesis, Massachusetts Institute of Technology, Cambridge, Mass.
• 3: DeRemer, F. L. [1971] Simple LR(k) grammars. Comm. ACM 14:7, 453--460.
• 4: Earley, J. [1968] An efficient context-free parsing algorithm. Ph. D. Thesis, Carnegie-Mellon University, Pittsburgh. Also see Comm. ACM (February, 1970) 13:2, 94--102.
• 5: Korenjak, A. J. [1969] A practical method for constructing LR(k) processors. Comm. ACM 12:11, 613--623.
• 6: Leinius, R. P. [1970] Error detection and recovery for syntax directed compiler systems. Ph. D. Thesis, University of Wisconsin, Madison.
• 1: Aho, A. V., S. C. Johnson, and J. D. Ullman [1972] Deterministic parsing of ambiguous grammars. Unpublished manuscript, Bell Laboratories, Murray Hill, N.J.
• 2: DeRemer, F. L. [1969] Practical translators for LR(k) languages. Ph. D. Thesis, Massachusetts Institute of Technology, Cambridge, Mass.
• 1: Knuth, D. E. [1967] Top-down syntax analysis. Lecture Notes. International Summer School on Computer Programming, Copenhagen. Also in Acta Informatica 1:2, (1971), 79--110.
• 2: Korenjak, A. J., and J. E. Hopcroft [1966] Simple deterministic languages. IEEE Conference Record of 7th Annual Symposium on Switching and Automata Theory, pp. 36--46.
• 3: Kurki-Suonio, R. [1969] Notes on top-down languages. BIT 9, 225--238.
• 4: McNaughton, R. [1967] Parenthesis grammars. J. ACM 14:3, 490--500.
• 5: Paull, M. C., and S. H. Unger [1968a] Structural equivalence of context-free grammars. J. Computer and System Sciences 2:1, 427--463.
• 6: Rosenkrantz, D. J., and R. E. Stearns [1970] Properties of deterministic top-down grammars. Information and Control 17:3, 226--256.
• 1: Aho, A. V., P. J. Denning, and J. D. Ullman [1972] Weak and mixed strategy precedence parsing. J. ACM 19:2, 225--243.
• 2: Graham, S. L. [1970] Extended precedence languages, bounded right context languages and deterministic languages. IEEE Conference Record of 11th Annual Symposium on Switching and Automata Theory, pp. 175--180.
• 3: Gray, J. N., and M. A. Harrison [1969] Single pass precedence analysis. IEEE Conference Record of 10th Annual Symposium on Switching and Automata Theory, pp. 106--117.
• 4: Knuth, D. E. [1965] On the translation of languages from left to right. Information and Control 8:6, 607--639.
• 1: Fischer, M. J. [1969] Some properties of precedence languages. Proc. ACM Symposium on Theory of Computing, pp. 181--190.
• 1: Backus, J. W., et al. [1957] The FORTRAN Automatic Coding System. Proc. Western Joint Computer Conference, Vol. 11, pp. 188--198.
• 2: Elson, M., and S. T. Rake [1970] Code-generation technique for large-language compilers. IBM Systems J. 9:3, 166--188.
• 3: Grau, A. A., U. Hill, and H. Langmaack [1967] Translation of ALGOL 60. Springer-Verlag, New York.
• 4: IBM [1969] System 360 Operating System PL/I (F) Compiler Program Logic Manual. Publ. No. Y286800, IBM, Hursley, Winchester, England.
• 5: Knuth, D. E. [1968a] The Art of Computer Programming, Vol. 1: Fundamental Algorithms. Addison-Wesley, Reading, Mass.
• 6: Randell, B., and L. J. Russell [1964] ALGOL 60 Implementation. Academic Press, New York.
• 7: Wilcox, T. R. [1971] Generating machine code for high-level programming languages. Technical Report 71--103. Department of Computer Science, Cornell University, Ithaca, N.Y.
• 1: Aho, A. V., and J. D. Ullman [1969a] Syntax directed translation and the pushdown assembler. J. Computer and System Sciences 3:1, 37--56.
• 2: Aho, A. V., and J. D. Ullman [1972g] LR(k) syntax directed translation. Unpublished manuscript, Bell Laboratories, Murray Hill, N.J.
• 3: Lewis, P. M., II, and R. E. Stearns [1968] Syntax directed transduction. J. ACM 15:3, 464--488.
• 4: McClure, R. M. [1965] TMG---a syntax directed compiler. Proc. ACM National Conference, Vol. 20, pp. 262--274.
• 5: McIlroy, M. D. [1972] A manual for the TMG compiler writing language. Unpublished memorandum, Bell Laboratories, Murray Hill, N.J.
• 6: Schorre, D. V. [1964] META II, a syntax oriented compiler writing language, Proc. ACM National Conference, Vol. 19, pp. D1.3--1D1.3--11.
• 1: Aho, A. V., and J. D. Ullman [1971] Translations on a context-free grammar. Information and Control 19:5, 439--475.
• 2: Knuth, D. E. [1968b] Semantics of context-free languages. Math. Systems Theory 2:2, 127--146. Also see Math. Systems Theory 5: 1, 95--95.
• 3: Bruno, J. L., and W. A. Burkhard [1970] A circularity test for interpreted grammars. Technical Report 88. Computer Sciences Laboratory, Department of Electrical Engineering, Princeton University, Princeton, N.J.
• 1: Bell, J. R. [1970] The quadratic quotient method: a hash code eliminating secondary clustering. Comm. ACM 13:2, 107--109.
• 2: Knuth, D. E. [1973] The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison-Wesley, Reading, Mass.
• 3: Maurer, W. D. [1968] An improved hash code for scatter storage. Comm. ACM 11:1, 35--38.
• 4: Morris, Robert [1968] Scatter storage techniques. Comm. ACM 11:1, 35--44.
• 5: Peterson, W. W. [1957] Addressing for random access storage. IBM J. Research and Development 1:2, 130--146.
• 6: Radke, C. E. [1970] The use of quadratic residue search. Comm. ACM 13:2, 103--109.
• 7: Ullman, J. D. [1972a] A note on hashing functions. J. ACM 19:3, 569--575.
• 8: Ullman, J. D. [1972b] Fast Algorithms for the Elimination of Common Subexpressions. Technical Report TR-106, Dept. of Electrical Engineering, Princeton University, Princeton, N.J.
• 1: Fischer, M. J. [1972] Efficiency of equivalence algorithms. Memo No. 256, Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, Mass.
• 2: Hopcroft, J. E., and J. D. Ullman [1972a] Set merging algorithms. Unpublished memorandum. Department of Computer Science, Cornell University, Ithaca, N.Y.
• 3: Stearns, R. E., and P. M. Lewis, II [1969] Property grammars and table machines. Information and Control 14:6, 524--549.
• 4: Stearns, R. E., and D. J. Rosenkrantz [1969] Table machine simulation. IEEE Conference Record of 10th Annual Symposium on Switching and Automata Theory, pp. 118--128.
• 1: Aho, A. V., and J. D. Ullman [1972e] Optimization of straight line code. SIAM J. on Computing 1:1, 1--19.
• 2: Aho, A. V., and J. D. Ullman [1972f] Equivalence of programs with structured variables. J. Computer and System Sciences 6:2, 125--137.
• 3: Aho, A. V., R. Sethi, and J. D. Ullman [1972] Code optimization and finite Church--Rosser systems. In Design and Optimization of Compilers (R. Rustin, ed.). Prentice-Hall, Englewood Cliffs, N.J., pp. 89--106.
• 4: Bracha, N. [1972] Transformations on loop-free program schemata. Report No. UIUCDCS-R-72-516, Department of Computer Science, University of Illinois, Urbana
• 5: Breuer, M. A. [1969] Generation of optimal code for expressions via factorization. Comm. ACM 12:6, 333--340.
• 6: Caviness, B. F. [1970] On canonical forms and simplification. J. ACM 17:2, 385--396.
• 7: De Bakker, J. W. [1971] Axiom systems for simple assignment statements. In Engeler [1971], pp. 1--22.
• 8: Floyd, R. W. [1961a] An algorithm for coding efficient arithmetic operations. Comm. ACM 4:1, 42--51.
• 9: Igarishi, S. [1968] On the equivalence of programs represented by Algol-like statements. Report of the Computer Centre, University of Tokyo 1, pp. 103--118.
• 10: Richardson, D. [1968] Some unsolvable problems involving elementary functions of a real variable. J. Symbolic Logic 33, 514--520.
• 1: Allard, R. W., K. A. Wolf, and R. A. Zemlin [1964] Some effects of the 6600 computer on language structures. Comm. ACM 7:2, 112--127.
• 2: Anderson, J. P. [1964] A note on some compiling algorithms. Comm. ACM 7:3, 149--150.
• 3: Baer, J. L., and D. P. Bovet [1968] Compilation of arithmetic expressions for parallel computations. Proc. IFIP Congress 68, B4--B10.
• 4: Beatty, J. C. [1972] An axiomatic approach to code optimization for expressions. J. ACM, 19: 4.
• 5: Belady, L. A. [1966] A study of replacement algorithms for a virtual storage computer. IBM Systems J. 5, 78--82.
• 6: Chen, S. [1972] On the Sethi-Ullman algorithm. Unpublished memorandum, Bell Laboratories, Holmdel, N.J.
• 7: Floyd, R. W. [1961a] An algorithm for coding efficient arithmetic operations. Comm. ACM 4:1, 42--51.
• 8: Frailey, D. J. [1970] Expression optimization using unary complement operators. ACM SIGPLAN Notices 5:7, 67--85.
• 9: Graham, R. L. [1972] Bounds on multiprocessing anomalies and related packing algorithms. Proc. AFIPS Spring Joint Computer Conference, Vol. 40 AFIPS Press, Montvale, N.J. pp. 205--217.
• 10: Hellerman, H. [1966] Parallel processing of algebraic expressions. IEEE Trans. on Electronic Computers EC-15:1, 82--91.
• 11: Horwitz, L. P., R. M. Karp, R. E. Miller, and S. Winograd [1966] Index register allocation. J. ACM 13:1, 43--61.
• 12: Kennedy, K. [1972] Index register allocation in straight line code and simple loops. In Design and Optimization of Compilers (R. Rustin, ed.). Prentice-Hall, Englewood Cliffs, N.J., pp. 51--64.
• 13: Meyers, W. J. [1965] Optimization of computer code. Unpublished memorandum. G. E. Research Center, Schenectady, N.Y.
• 14: Nakata, I. [1967] On compiling algorithms for arithmetic expressions. Comm. ACM 12:2, 81--84.
• 15: Redziejowski, R. R. [1969] On arithmetic expressions and trees. Comm. ACM 12:2, 81--84.
• 16: Sethi, R. [1972] Validating register allocations for straight line programs. Ph. D. Thesis, Department of Electrical Engineering, Princeton University.
• 17: Sethi, R., and J. D. Ullman [1970] The generation of optimal code for arithmetic expressions. J. ACM 17:4, 715--728.
• 18: Stone, H. S. [1967] One-pass compilation of arithmetic expressions for a parallel processor. Comm. ACM 10:4, 220--223.
• 1: Allen, F. E. [1969] Program optimization. Annual Review in Automatic Programming, Vol. 5., Pergamon, Elmsford, N.Y.
• 2: Allen, F. E., and J. Cocke [1972] A catalogue of optimizing transformations. In Design and Optimization of Compilers (R. Rustin, ed.). Prentice-Hall, Englewood Cliffs, N.J., pp. 1--30.
• 3: Busam, V. A., and D. E. Englund [1969] Optimization of expressions in Fortran. Comm. ACM 12:12, 666--674.
• 4: Clark, E. R. [1967] On the automatic simplification of source language programs. Comm. ACM 10:3, 160--164.
• 5: Gear, C. W. [1965] High speed compilation of efficient object code. Comm. ACM 8:8, 483--487.
• 6: Ianov, I. I. [1958] On the equivalence and transformation of program schemes. Translation in Comm. ACM 1:10, 8--11.
• 7: Kaplan, D. M. [1970] Proving things about programs. Proc. 4th Annual Princeton Conference on Information Sciences and Systems, pp. 244--251.
• 8: Lowry, E. S., and C. W. Medlock [1969] Object code optimization. Comm. ACM 12:1, 13--22.
• 9: Luckham, D. C., D. M. R. Park, and M. S. Paterson [1970] On formalized computer programs. J. Computer and System Sciences 4:3, 220--249.
• 10: Manna, Z. [1973] Program schemas. In Aho [1973].
• 11: Marill, M. [1962] Computational chains and the size of computer programs. IRE Trans. on Electronic Computers, EC-11:2, 173--180.
• 12: McKeeman, W. M. [1965] Peephole optimization. Comm. ACM 8: 7, 443--444.
• 13: Nievergelt, J. [1965] On the automatic simplification of computer programs. Comm. ACM 8:6, 366--370.
• 14: Prosser, R. T. [1959] Applications of Boolean matrices to the analysis of flow diagrams. Proc. Eastern J. Computer Conference, Spartan Books, N.Y., pp. 133--138.
• 1: Aho A. V., J. E. Hopcroft, and J. D. Ullman [1972] On finding lowest common ancestors in trees. Proc. Fifth Annual ACM Symposium on Theory of Computing, (May, 1973), 253--265.
• 2: Allen, F. E. [1970] Control flow analysis. ACM SIGPLAN Notices 5:7, 1--19.
• 3: Busam, V. A., and D. E. Englund [1969] Optimization of expressions in Fortran. Comm. ACM 12:12, 666--674.
• 4: Cocke, J. [1970] Global common subexpression elimination. ACM SIGPLAN Notices 5:7, 20--24.
• 5: Cocke, J., and J. T. Schwartz [1970] Programming Languages and Their Compilers (2nd ed.). Courant Institute of Mathematical Sciences, New York University, New York.
• 6: Hecht, M. S., and J. D. Ullman [1972a] Flow graph reducibility. SIAM J. on Computing 1:2, 188--202.
• 7: Hecht, M. S., and J. D. Ullman [1972b] Unpublished memorandum, Department of Electrical Engineering, Princeton University
• 8: Hopcroft, J. E., and J. D. Ullman [1972b] An n log n algorithm to detect reducible graphs Proc. Sixth Annual Princeton Conference on Information Sciences and Systems, pp. 119--122.
• 9: Kennedy, K. [1971] A global flow analysis algorithm. International J. Computer Mathematics 3:1, 5--16
• 10: Knuth, D. E. [1971] An empirical study of FORTRAN programs. Software-Practice and Experience 1:2, 105--134.
• 11: Lowry, E. S., and C. W. Medlock [1969] Object code optimization. Comm. ACM 12:1, 13--22.
• 12: Schaefer, M. [1973] A Mathematical Theory of Global Program Optimization Prentice-Hall, Englewood Cliffs, N.J., to appear.
• 13: Ullman, J. D. [1972b] Fast Algorithms for the Elimination of Common Subexpressions. Technical Report TR-106, Dept. of Electrical Engineering, Princeton University, Princeton, N.J.
• 1: Ans X.3.9 [1966] American National Standard FORTRAN. American National Standards Institute, New York.
• 2: Ansi Subcommittee X3J3 [1971] Clarification of FORTRAN standards---second report. Comm. ACM 14:10, 628--642.
• 3: Bagwell, J. T. [1970] Local optimizations. ACM SIGPLAN Notices 5:7, 52--66.
• 4: Braffort, P., and D. Hirschberg (eds.) [1963] Computer Programming and Formal Systems. North-Holland, Amsterdam.
• 5: Church, A. [1941] The Calculi of Lambda-Conversion. Annals of Mathematics Studies, Vol. 6. Princeton University Press, Princeton, N.J.
• 6: Conway, M. E. [1963] Design of a separable transition-diagram compiler. Comm. ACM 6:7, 396--408.
• 7: Cook, S. A., and S. D. Aanderaa [1969] On the minimum computation time of functions. Trans. American Math. Soc. 142, 291--314.
• 8: Floyd, R. W. [1962b] On ambiguity in phrase structure languages. Comm. ACM 5: 10, 526--534.
• 9: Garwick, J. V. [1964] GARGOYLE, a language for compiler writing. Comm. ACM 7:1, 16--20.
• 10: Garwick, J. V. [1968] GPL, a truly general purpose language. Comm. ACM 11:9, 634--638.
• 11: Gentleman, W. M. [1971] A portable coroutine system. Proc. IFIP Congress 71, TA-3. North-Holland, Amsterdam, pp. 94--98.
• 12: Glennie, A. [1960] On the syntax machine and the construction of a universal compiler. Technical Report No. 2. Computation Center, Carnegie-Mellon University, Pittsburg, Pa.
• 13: Griswold, R. E., J. F. Poage, and I. P. Polonsky [1971] The SNOBOL4 Programming Language (2nd ed.). Prentice-Hall, Englewood Cliffs, N.J.
• 14: Halmos, P. R. [1960] Naive Set Theory. Van Nostrand Reinhold, New York.
• 15: Hopkins, M. E. [1971] An optimizing compiler design. Proc. IFIP Congress, 71, TA-3. North-Holland, Amsterdam, pp. 69--73.
• 16: Huxtable, D. H. R. [1964] On writing an optimizing translator for ALGOL 60. In Introduction to System Programming, Academic Press, New York.
• 17: Irons, E. T. [1963a] An error correcting parse algorithm. Comm. ACM 6:11, 669--673.
• 18: Lalonde, W. R., E. S. Lee, and J. J. Horning [1971] An LALR(k) parser generator. Proc. IFIF Congress 71, TA-3. North-Holland, Amsterdam, pp. 153--157.
• 19: Markov, A. A. [1951] The theory of algorithms (in Russian). Trudi Mathematicheskova Instituta imeni V. A. Steklova 38, 176--189. (English translation, American Math. Soc. Trans. 2:15 (1960), 1--14.)
• 20: McIlroy, M. D. [1968] Coroutines. Unpublished manuscript, Bell Laboratories, Murray Hill, N.J.
• 21: Moore, E. F. [1964] Sequential Machines: Selected Papers. Addison-Wesley, Reading, Mass.
• 22: Paterson, M. S. [1968] Program schemata. Machine Intelligence, Vol. 3 (Michie, ed.). Edinburgh University Press, Edinburgh, pp. 19--31.
• 23: Paull, M. C., and S. H. Unger [1968b] Structural equivalence and LL-k grammars. IEEE Conference Record of Ninth Annual Symposium on Switching and Automata Theory, pp. 176--186.
• 24: Post, E. L. [1943] Formal reductions of the general combinatorial decision problem. American J. of Math. 65, 197--215.
• 25: Post, E. L. [1965] Absolutely unsolvable problems and relatively undecidable propositions---account of an anticipation. In Davis [1965], pp. 338--433.
• 26: Price, C. E. [1971] Table lookup techniques. ACM Computing Surveys, 3:2, 49--66.
• 27: Rabin, M. O. [1967] Mathematical theory of automata. In Schwartz [1967], pp. 173--175.
• 28: Samelson, K., and F. L. Bauer [1960] Sequential formula translation. Comm. ACM 3:2, 76--83.
• 29: Schwartz, J. T. (ed.) [1967] Mathematical Aspects of Computer Science. Proc. Symposia in Applied Mathematics, Vol. 19. American Mathematical Society, Providence.
• 30: Scott, D., and C. Strachey [1971] Towards a mathematical semantics for computer languages. Proc. Symposium on Computers and Automata, Microwave Research Institute Symposia Series, Vol. 21. Polytechnic Institute of Brooklyn, New York, pp. 19--46.
• 31: Shannon, C. E., and J. McCarthy (eds.) [1956] Automata Studies. Princeton University Press, Princeton, N.J.
• 32: Stearns, R. E. [1971] Deterministic top-down parsing. Proc. Fifth Annual Princeton Conference on Information Sciences and Systems, pp. 182--188.
• 33: Suppes, P. [1960] Axiomatic Set Theory. Van Nostrand Reinhold, New York.
• 34: Tarjan, R. [1972] Depth first search and linear graph algorithms. SIAM J. on Computing 1:2, 146--160.
• 35: Warshall, S. [1962] A theorem on Boolean matrices. J. ACM 9:1, 11--12.
• 36: Winograd, S. [1965] On the time required to perform addition. J. ACM 12:2, 277--285.
• 37: Winograd, S. [1967] On the time required to perform multiplication. J. ACM 14:4, 793--802.
• 38: Wood, D. [1969b] A note on top on top-down deterministic languages. BIT 9:4, 387--399.
• 39: Wozencraft, J. M., and A. Evans, Jr. [1969] Notes on Programming Languages. Department of Electrical Engineering, Massachusetts Institute of Technology, Cambridge, Mass.
• 40: Yershov, A. P. [1966] ALPHA---an automatic programming system of high efficiency. J. ACM 13:1, 17--24.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  A. General Literature
  A.2 REFERENCE

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Parsing

General Terms:
Design, Documentation