Skip header Section
Skip Bibliometrics Section
The theory of parsing, translation, and compilingJanuary 1972
Skip Abstract Section
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.
Book Downloads
Skip Table Of Content Section
Chapters
- Ans X.3.9 [1966] American National Standard FORTRAN. American National Standards Institute, New York.Google Scholar
- Ansi Subcommittee X3J3 [1971] Clarification of FORTRAN standards---second report. Comm. ACM 14:10, 628--642.Google ScholarDigital Library
- Bagwell, J. T. [1970] Local optimizations. ACM SIGPLAN Notices 5:7, 52--66.Google ScholarDigital Library
- Braffort, P., and D. Hirschberg (eds.) [1963] Computer Programming and Formal Systems. North-Holland, Amsterdam.Google Scholar
- Church, A. [1941] The Calculi of Lambda-Conversion. Annals of Mathematics Studies, Vol. 6. Princeton University Press, Princeton, N.J.Google Scholar
- Conway, M. E. [1963] Design of a separable transition-diagram compiler. Comm. ACM 6:7, 396--408.Google ScholarDigital Library
- Cook, S. A., and S. D. Aanderaa [1969] On the minimum computation time of functions. Trans. American Math. Soc. 142, 291--314.Google ScholarCross Ref
- Floyd, R. W. [1962b] On ambiguity in phrase structure languages. Comm. ACM 5: 10, 526--534.Google ScholarDigital Library
- Garwick, J. V. [1964] GARGOYLE, a language for compiler writing. Comm. ACM 7:1, 16--20.Google ScholarDigital Library
- Garwick, J. V. [1968] GPL, a truly general purpose language. Comm. ACM 11:9, 634--638.Google ScholarDigital Library
- Gentleman, W. M. [1971] A portable coroutine system. Proc. IFIP Congress 71, TA-3. North-Holland, Amsterdam, pp. 94--98.Google Scholar
- 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.Google Scholar
- Griswold, R. E., J. F. Poage, and I. P. Polonsky [1971] The SNOBOL4 Programming Language (2nd ed.). Prentice-Hall, Englewood Cliffs, N.J.Google Scholar
- Halmos, P. R. [1960] Naive Set Theory. Van Nostrand Reinhold, New York.Google Scholar
- Hopkins, M. E. [1971] An optimizing compiler design. Proc. IFIP Congress, 71, TA-3. North-Holland, Amsterdam, pp. 69--73.Google Scholar
- Huxtable, D. H. R. [1964] On writing an optimizing translator for ALGOL 60. In Introduction to System Programming, Academic Press, New York.Google Scholar
- Irons, E. T. [1963a] An error correcting parse algorithm. Comm. ACM 6:11, 669--673.Google ScholarDigital Library
- 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.Google Scholar
- 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.)Google Scholar
- McIlroy, M. D. [1968] Coroutines. Unpublished manuscript, Bell Laboratories, Murray Hill, N.J.Google Scholar
- Moore, E. F. [1964] Sequential Machines: Selected Papers. Addison-Wesley, Reading, Mass.Google Scholar
- Paterson, M. S. [1968] Program schemata. Machine Intelligence, Vol. 3 (Michie, ed.). Edinburgh University Press, Edinburgh, pp. 19--31.Google Scholar
- 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.Google Scholar
- Post, E. L. [1943] Formal reductions of the general combinatorial decision problem. American J. of Math. 65, 197--215.Google ScholarCross Ref
- Post, E. L. [1965] Absolutely unsolvable problems and relatively undecidable propositions---account of an anticipation. In Davis [1965], pp. 338--433.Google Scholar
- Price, C. E. [1971] Table lookup techniques. ACM Computing Surveys, 3:2, 49--66.Google ScholarDigital Library
- Rabin, M. O. [1967] Mathematical theory of automata. In Schwartz [1967], pp. 173--175.Google Scholar
- Samelson, K., and F. L. Bauer [1960] Sequential formula translation. Comm. ACM 3:2, 76--83.Google ScholarDigital Library
- Schwartz, J. T. (ed.) [1967] Mathematical Aspects of Computer Science. Proc. Symposia in Applied Mathematics, Vol. 19. American Mathematical Society, Providence.Google Scholar
- 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.Google Scholar
- Shannon, C. E., and J. McCarthy (eds.) [1956] Automata Studies. Princeton University Press, Princeton, N.J.Google Scholar
- Stearns, R. E. [1971] Deterministic top-down parsing. Proc. Fifth Annual Princeton Conference on Information Sciences and Systems, pp. 182--188.Google Scholar
- Suppes, P. [1960] Axiomatic Set Theory. Van Nostrand Reinhold, New York.Google Scholar
- Tarjan, R. [1972] Depth first search and linear graph algorithms. SIAM J. on Computing 1:2, 146--160.Google ScholarCross Ref
- Warshall, S. [1962] A theorem on Boolean matrices. J. ACM 9:1, 11--12.Google ScholarDigital Library
- Winograd, S. [1965] On the time required to perform addition. J. ACM 12:2, 277--285.Google ScholarDigital Library
- Winograd, S. [1967] On the time required to perform multiplication. J. ACM 14:4, 793--802.Google ScholarDigital Library
- Wood, D. [1969b] A note on top on top-down deterministic languages. BIT 9:4, 387--399.Google ScholarCross Ref
- Wozencraft, J. M., and A. Evans, Jr. [1969] Notes on Programming Languages. Department of Electrical Engineering, Massachusetts Institute of Technology, Cambridge, Mass.Google Scholar
- Yershov, A. P. [1966] ALPHA---an automatic programming system of high efficiency. J. ACM 13:1, 17--24.Google ScholarDigital Library
- Church, A. [1956] Introduction to Mathematical Logic. Princeton University Press, Princeton, N.J.Google Scholar
- Halmos, P. R. [1963] Lectures on Boolean Algebras. Van Nostrand Reinhold, New York.Google Scholar
- Mendelson, E. [1968] Introduction to Mathematical Logic. Van Nostrand Reinhold, New York.Google Scholar
- Borodin, A. [1970] Computational complexity---a survey. Proc. Fourth Annual Princeton Conference on Information Sciences and Systems, pp. 257--262. Also see Aho [1973].Google Scholar
- Davis, M. [1958] Computability and Unsolvability. McGraw-Hill, New York.Google Scholar
- Davis, M. (ed.) [1965] The Undecidable. Basic papers in undecidable propositions, unsolvable problems and computable functions. Raven Press, New York.Google Scholar
- Hartmanis, J., and J. E. Hopcroft [1970] An overview of the theory of computational complexity. J. ACM 18:3, 444--475.Google ScholarDigital Library
- Hopcroft, J. E., and J. D. Ullman [1969] Formal Languages and Their Relation to automata. Addison-Wesley, Reading, Mass.Google Scholar
- 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.Google Scholar
- Kleene, S. C. [1952] Introduction to Metamathematics. Van Nostrand Reinhold, New York.Google Scholar
- Knuth, D. E. [1965] On the translation of languages from left to right. Information and Control 8:6, 607--639.Google ScholarCross Ref
- Minsky, M. [1967] Computation: Finite and Infinite Machines. Prentice-Hall, Englewoods Cliffs, N.J.Google Scholar
- Post, E. L. [1947] Recursive unsolvability of a problem of Thue. J. Symbolic Logic, 12, 1--11. Reprinted in Davis [1965], pp. 292--303.Google ScholarCross Ref
- Rogers, H., Jr. [1967] Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York.Google Scholar
- 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.Google Scholar
- Berge, C. [1958] The Theory of Graphs and Its Applications. Wiley, New York.Google Scholar
- Floyd, R. W. [1962a] Algorithm 97: shortest path. Comm. ACM 5:6, 345.Google ScholarDigital Library
- Harary, E. [1969] Graph Theory. Addison-Wesley, Reading, Mass.Google Scholar
- Knuth, D. E. [1968a] The Art of Computer Programming, Vol. 1: Fundamental Algorithms. Addison-Wesley, Reading, Mass.Google Scholar
- Munro, I. [1971] Efficient determination of the transitive closure of a directed graph. Information Processing Letters 1:2, 56--58.Google ScholarDigital Library
- Ore, O. [1962] Theory of Graphs. American Mathematical Society Colloquium Publications, Vol. 38, Providence.Google Scholar
- Strassen, V. [1969] Gaussian elimination is not optimal. Numerische Mathematik 13, 354--356.Google ScholarDigital Library
- 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.Google Scholar
- Chomsky, N. [1959a] On certain formal properties of grammars. Information and Control 2:2, 137--167.Google ScholarCross Ref
- 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.Google Scholar
- Christensen, C., and J. C. Shaw (eds.) [1969] Proc. of the extensible languages symposium. ACM SIGPLAN Notices 4:8.Google Scholar
- Engeler, E. (ed.) [1971] Symposium on Semantics of Algorithmic Languages. Lecture Notes in Mathematics. Springer, Berlin.Google Scholar
- Galler, B. A., and A. J. Perlis [1967] A proposal for definitions in ALGOL. Comm. ACM 10:4, 204--219.Google ScholarDigital Library
- Leavenworth, B. M. [1966] Syntax macros and extended translation. Comm. ACM 9:11, 790--793.Google ScholarDigital Library
- 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.Google Scholar
- McIlroy, M. D. [1960] Macro instruction extensions of compiler languages. Comm. ACM 3:4, 414--220.Google ScholarDigital Library
- Naur, P. (ed.) [1963] Revised report on the algorithmic language ALGOL 60. Comm. ACM 6:1, 1--17.Google ScholarDigital Library
- Sammet, J. E. [1969] Programming Languages: History and Fundamentals. Prentice-Hall, Englewood Cliffs, N.J.Google Scholar
- Steel, T. B. (ed.) [1966] Formal Language Description Languages for Computer Programming. North-Holland, Amsterdam.Google Scholar
- Van Wijngaarden, A. (ed.) [1969] Report on the algorithmic language ALGOL 68. Numerische Mathematik 14, 79--218.Google ScholarDigital Library
- Wegbreit, B. [1970] Studies in extensible programming languages. Ph. D. Thesis, Harvard University, Cambridge, Mass.Google Scholar
- Backus, J. W., et al. [1957] The FORTRAN Automatic Coding System. Proc. Western Joint Computer Conference, Vol. 11, pp. 188--198.Google Scholar
- Brooker, R. A., and D. Morris [1963] The compiler-compiler. Annual Review in Automatic Programming, Vol. 3. Pergamon, Elmsford, N.Y., pp. 229--275.Google Scholar
- Cheatham, T. E., [1965] The TGS-II translator-generator system. Proc. IFIP Congress 65. Spartan, New York, pp. 592--593.Google Scholar
- Cheatham, T. E., and T. Standish [1970] Optimization aspects of compiler-compilers. ACM SIGPLAN Notices 5: 10, 10--17.Google ScholarDigital Library
- Cocke, J., and J. T. Schwartz [1970] Programming Languages and Their Compilers (2nd ed.). Courant Institute of Mathematical Sciences, New York University, New York.Google Scholar
- Conway, R. W., and W. L. Maxwell [1963] CORC: the Cornell computing language. Comm. ACM 6:6, 317--321.Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- Dewar, R. B. K., R. R. Hochsprung, and W. S. Worley [1969] The IITRAN programming language. Comm. ACM 12: 10, 569--575.Google ScholarDigital Library
- Elspas, B., M. W. Green, and K. N. Levitt [1971] Software reliability. Computer 1, 21--27.Google ScholarDigital Library
- Feldman, J. A. [1966] A formal semantics for computer languages and its application in a compiler-compiler. Comm. ACM 9:1, 3--9.Google ScholarDigital Library
- Feldman, J. A., and D. Gries [1968] Translator writing systems. Comm. ACM 11:2, 77--113.Google ScholarDigital Library
- Floyd, R. W. [1967a] Assigning meanings to programs. In Schwartz [1967], pp. 19--32.Google Scholar
- 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.Google Scholar
- Gries, D. [1971] Compiler Construction for Digital Computers. Wiley, New York.Google Scholar
- Hopgood, F. R. A. [1969] Compiling Techniques. American Elsevier, New York.Google Scholar
- Ingerman, P. Z. [1966] A Syntax Oriented Translator. Academic Press, New York.Google Scholar
- 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.Google Scholar
- Lee, J. A. N. [1967] Anatomy of a Compiler. Van Nostrand Reinhold, New York.Google Scholar
- McCarthy, J. [1963] A basis for the mathematical theory of computation. In Braffort and Hirschberg [1963], pp. 33--71.Google Scholar
- McCarthy, J., and J. A. Painter [1967] Correctness of a compiler for arithmetic expressions. In Schwartz [1967], pp. 33--41.Google Scholar
- McClure, R. M. [1965] TMG---a syntax directed compiler. Proc. ACM National Conference, Vol. 20, pp. 262--274.Google Scholar
- McKeeman, W. M., J. J. Horning, and D. B. Wortman [1970] A Compiler Generator. Prentice-Hall, Englewood Cliffs, N.J.Google Scholar
- Morgan, H. L. [1970] Spelling correction in systems programs. Comm. ACM 13:2, 90--93.Google ScholarDigital Library
- Moulton, P. G., and M. E. Muller [1967] A compiler emphasizing diagnostics. Comm. ACM 10:1, 45--52.Google ScholarDigital Library
- Painter, J. A. [1970] Effectiveness of an optimizing compiler for arithmetic expressions. ACM SIGPLAN Notices 5:7, 101--126.Google ScholarDigital Library
- Randell, B., and L. J. Russell [1964] ALGOL 60 Implementation. Academic Press, New York.Google Scholar
- Reynolds, J. C. [1965] An introduction to the COGENT programming system. Proc. ACM National Conference, Vol. 20, p. 422.Google Scholar
- Rosen S. (ed.) [1967a] Programming Systems and Languages. McGraw-Hill, New York.Google Scholar
- Rosen, S. [1967b] A compiler-building system developed by Brooker and Morris. In Rosen [1967a], pp. 306--331.Google Scholar
- Schorre, D. V. [1964] META II, a syntax oriented compiler writing language, Proc. ACM National Conference, Vol. 19, pp. D1.3--1D1.3--11.Google Scholar
- 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.Google Scholar
- Bar-Hillel, Y. [1964] Language and Information. Addison-Wesley, Reading, Mass.Google Scholar
- 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.Google Scholar
- Chomsky, N. [1965] Aspects of the Theory of Syntax. M.I.T. Press, Cambridge, Mass.Google Scholar
- 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.Google Scholar
- Montanari, U. G. [1970] Separable graphs, planar graphs and web grammars. Information and Control 16:3, 243--267.Google ScholarCross Ref
- Pavlidis, T. [1972] Linear and context-free graph grammars. J. ACM 19:1, 11--23.Google ScholarDigital Library
- Pfaltz, J. L., and A. Rosenfeld [1969] Web grammars. Proc. International Joint Conference on Artificial Intelligence, Washington, D. C., pp. 609--619.Google Scholar
- Shaw, A. C. [1970] Parsing of graph-representable pictures. J. ACM 17:3, 453--481.Google ScholarDigital Library
- Aho, A. V. [1968] Indexed grammars---an extension of context-free grammars. J. ACM 15:4, 647--671.Google ScholarDigital Library
- Bar-Hillel, Y. [1964] Language and Information. Addison-Wesley, Reading, Mass.Google Scholar
- 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].Google Scholar
- Chomsky, N. [1956] Three models for the description of language. IEEE Trans. on Information Theory 2:3, 113--124.Google ScholarCross Ref
- Chomsky, N. [1957] Syntactic Structures. Mouton and Co., The Hague.Google Scholar
- Chomsky, N. [1959a] On certain formal properties of grammars. Information and Control 2:2, 137--167.Google ScholarCross Ref
- Chomsky, N. [1959b] A note on phrase structure grammars. Information and Control 2: 4, 393--395.Google ScholarCross Ref
- 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.Google Scholar
- Ginsburg, S. [1966] The Mathematical Theory of Context-Free Languages. McGraw-Hill, New York.Google Scholar
- Ginsburg, S., and S. A. Greibach [1969] Abstract families of languages. Memoir American Math. Soc. No. 87, 1--32.Google Scholar
- Greibach S. A., and J. E. Hopcroft [1969] Scattered context grammars. J. Computer and System Sciences 3:3, 233--247.Google ScholarDigital Library
- Haines, L. H. [1970] Representation theorems for context-sensitive languages. Department of Electrical Engineering and Computer Sciences, University of California, Berkeley.Google Scholar
- Hopcroft, J. E., and J. D. Ullman [1967] An approach to a unified theory of automata. Bell System Tech. J. 46:8, 1763--1829.Google Scholar
- Hopcroft, J. E., and J. D. Ullman [1969] Formal Languages and Their Relation to automata. Addison-Wesley, Reading, Mass.Google Scholar
- McCulloch, W. S., and W. Pitts [1943] A logical calculus of the ideas immanent in nervous activity. Bulletin of Math. Biophysics 5, 115--133.Google ScholarCross Ref
- Moore, E. F. [1956] Gedanken experiments on sequential machines. In Shannon and McCarthy [1956], pp. 129--153.Google Scholar
- 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.Google ScholarDigital Library
- Rosenkrantz, D. J. [1968] Programmed grammars and classes of formal languages. J. ACM 16:1, 107--131.Google ScholarDigital Library
- Brzozowski, J. A. [1962] A survey of regular expressions and their applications. IRE Trans. on Electronic Computers 11:3, 324--335.Google ScholarCross Ref
- Chomsky, N., and G. A. Miller [1958] Finite state languages. Information and Control 1:2, 91--112.Google ScholarCross Ref
- Kleene, S. C. [1956] Representation of events in nerve nets. In Shannon and McCarthy [1956], pp. 3--40.Google Scholar
- 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.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- Salomaa, A. [1966] Two complete axiom systems for the algebra of regular events. J. ACM 13:1, 158--169.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- Arbib, M. A. [1969] Theories of Abstract Automata. Prentice-Hall, Englewood Cliffs, N.J.Google Scholar
- Booth, T. L. [1967] Sequential Machines and Automata Theory. Wiley, New York.Google Scholar
- Brzozowski, J. A. [1964] Derivatives of regular expressions. J. ACM 11:4, 481--494.Google ScholarDigital Library
- Gill, A. [1962] Introduction to the Theory of Finite State Machines. McGraw-Hill, New York.Google Scholar
- Ginsburg, S. [1962] An Introduction to Mathematical Machine Theory. Addison-Wesley, Reading, Mass.Google Scholar
- Ginzburg, A. [1968] Algebraic Theory of Automata. Academic Press, New York.Google Scholar
- Harrison, M. A. [1965] Introduction to Switching and Automata Theory. McGraw-Hill, New York.Google Scholar
- 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.Google Scholar
- Huffman, D. A. [1954] The synthesis of sequential switching circuits. J. Franklin Institute 257, 3--4, 161, 190, and 275--303.Google ScholarCross Ref
- 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.Google Scholar
- Kosaraju, S. R. [1970] Finite state automata with markers. Proc. Fourth Annual Princeton Conference on Information Sciences and Systems, p. 380.Google Scholar
- Minsky, M. [1967] Computation: Finite and Infinite Machines. Prentice-Hall, Englewoods Cliffs, N.J.Google Scholar
- Moore, E. F. [1956] Gedanken experiments on sequential machines. In Shannon and McCarthy [1956], pp. 129--153.Google Scholar
- Prather, R. E. [1969] Minimal solutions of Paull-Unger problems. Math. System Theory 3:1, 76--85.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- Salomaa, A. [1969a] Theory of Automata. Pergamon, Elmsford, N.Y.Google Scholar
- Thompson, K. [1968] Regular expression search algorithm. Comm. ACM 11:6, 419--422.Google ScholarDigital Library
- Chomsky, N. [1959a] On certain formal properties of grammars. Information and Control 2:2, 137--167.Google ScholarCross Ref
- 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.Google Scholar
- Chomsky, N., and M. P. Schutzenberger [1963] The algebraic theory of context-free languages. In Braffort and Hirschberg [1963], pp. 118--161.Google Scholar
- Evey, R. J. [1963] Applications of pushdown-store machines. Proc. AFIPS Fall Joint Computer Conference, Vol. 24. Spartan, New York, pp. 215--227.Google Scholar
- Floyd, R. W. [1963] Syntactic analysis and operator precedence. J. ACM 10:3, 316--333.Google ScholarDigital Library
- Ginsburg, S., and H. G. Rice [1962] Two families of languages related to ALGOL. J. ACM 9:3, 350--371.Google ScholarDigital Library
- Greibach, S. A. [1965] A new normal form theorem for context-free phrase structure grammars. J. ACM 12:1, 42--52.Google ScholarDigital Library
- Rosenkrantz, D. J. [1967] Matrix equations and normal forms for context-free grammars. J. ACM 14: 3, 501--507.Google ScholarDigital Library
- 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.Google ScholarCross Ref
- Chomsky, N. [1962] Context-free grammars and pushdown storage. Quarterly Progress Report No. 65. Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, Mass.Google Scholar
- 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.Google Scholar
- Evey, R. J. [1963] Applications of pushdown-store machines. Proc. AFIPS Fall Joint Computer Conference, Vol. 24. Spartan, New York, pp. 215--227.Google Scholar
- Gray, J. N., M. A. Harrison, and O. Ibarra [1967] Two way pushdown automata. Information and Control 11:1, 30--70.Google ScholarCross Ref
- 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.Google Scholar
- 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.Google Scholar
- Schutzenberger, M. P. [1963] On context-free languages and pushdown automata. Information and Control 6:3, 246--264.Google ScholarCross Ref
- 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.Google Scholar
- 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.Google Scholar
- 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].Google Scholar
- Cantor, D. G. [1962] On the ambiguity problem of Backus systems. J. ACM 9:4, 477--479.Google ScholarDigital Library
- Chomsky, N. [1959a] On certain formal properties of grammars. Information and Control 2:2, 137--167.Google ScholarCross Ref
- Chomsky, N., and M. P. Schutzenberger [1963] The algebraic theory of context-free languages. In Braffort and Hirschberg [1963], pp. 118--161.Google Scholar
- Floyd, R. W. [1962a] Algorithm 97: shortest path. Comm. ACM 5:6, 345.Google ScholarDigital Library
- Ginsburg, S. [1966] The Mathematical Theory of Context-Free Languages. McGraw-Hill, New York.Google Scholar
- Ginsburg, S., and S. A. Greibach [1966] Deterministic context-free languages. Information and Control 9:6, 620--648.Google ScholarCross Ref
- Gross, M., and A. Lentin [1970] Introduction to Formal Grammars. Springer-Verlag, New York.Google Scholar
- Hopcroft, J. E., and J. D. Ullman [1969] Formal Languages and Their Relation to automata. Addison-Wesley, Reading, Mass.Google Scholar
- Ogden, W. [1968] A helpful result for proving inherent ambiguity. Mathematical Systems Theory 2:3, 191--194.Google ScholarCross Ref
- Parikh, R. J. [1966] On context-free languages. J. ACM 13:4, 570--581.Google ScholarDigital Library
- Salomaa, A. [1969b] On the index of a context-free grammar and language. Information and Control 14:5, 474--477.Google ScholarCross Ref
- Stearns, R. E. [1967] A regularity test for pushdown machines. Information and Control 11: 3, 323--340.Google ScholarCross Ref
- Barnett, M. P., and R. P. Futrelle [1962] Syntactic analysis by digital computer. Comm. ACM 5: 10, 515--526.Google ScholarDigital Library
- Ginsburg, S. [1962] An Introduction to Mathematical Machine Theory. Addison-Wesley, Reading, Mass.Google Scholar
- Griffiths, T. V. [1968] The unsolvability of the equivalence problem for A-free nondeterministic generalized machines. J. ACM 15:3, 409--413.Google ScholarDigital Library
- Irons, E. T. [1961] A syntax directed compiler for ALGOL 60. Comm. ACM 4:1, 51--55.Google ScholarDigital Library
- Lewis, P. M., II, and R. E. Stearns [1968] Syntax directed transduction. J. ACM 15:3, 464--488.Google ScholarDigital Library
- Aho, A. V., and J. D. Ullman [1969a] Syntax directed translation and the pushdown assembler. J. Computer and System Sciences 3:1, 37--56.Google ScholarDigital Library
- Aho, A. V., and J. D. Ullman [1969b] Properties of syntax directed translations. J. Computer and System Sciences 3:3, 319--334.Google ScholarDigital Library
- 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.Google Scholar
- 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.Google ScholarDigital Library
- Morgan, H. L. [1970] Spelling correction in systems programs. Comm. ACM 13:2, 90--93.Google ScholarDigital Library
- Thompson, K. [1968] Regular expression search algorithm. Comm. ACM 11:6, 419--422.Google ScholarDigital Library
- Cheatham, T. E. [1967] The Theory and Construction of Compilers (2nd ed.). Computer Associates, Inc., Wakefield, Mass.Google Scholar
- Gray, J. N. [1969] Precedence parsers for programming languages. Ph. D. Thesis, Department of Computer Science, University of California, Berkeley.Google Scholar
- 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.Google Scholar
- Reynolds, J. C., and R. Haskell [1970] Grammatical coverings. Unpublished memorandum, Syracuse University.Google Scholar
- Cheatham, T. E., and K. Sattley [1964] Syntax directed compiling. Proc. AFIPS Spring Joint Computer Conference, Vol. 25. Spartan, New York, pp. 31--57.Google Scholar
- Cohen, D. J., and C. C. Gotlieb [1970] A list structure form of grammars for syntactic analysis. Computing Surveys 2: 1, 65--82.Google ScholarDigital Library
- Floyd, R. W. [1964b] The syntax of programming languages---a survey. IEEE Trans. on Electronic Computers EC-13: 4, 346--353.Google ScholarCross Ref
- Floyd, R. W. [1967b] Nondeterministic algorithms. J. ACM 14:4, 636--644.Google ScholarDigital Library
- Griffiths, T. V., and S. R. Petrick [1965] On the relative efficiencies of context-free grammar recognizers. Comm. ACM 8:5, 289--300.Google ScholarDigital Library
- Hext, J. B., and P. S. Roberts [1970] Syntax analysis by Domolki's algorithm. Computer J. 13:3, 263--271.Google ScholarCross Ref
- Irons, E. T. [1961] A syntax directed compiler for ALGOL 60. Comm. ACM 4:1, 51--55.Google ScholarDigital Library
- Kuno, S., and A. G. Oettinger [1962] Multiple-path syntactic analyzer. Information Processing 62 (IFIP Congress), Popplewell (ed.). North-Holland, Amsterdam, pp. 306--311.Google Scholar
- Reynolds, J. C. [1965] An introduction to the COGENT programming system. Proc. ACM National Conference, Vol. 20, p. 422.Google Scholar
- Rosen, S. [1967b] A compiler-building system developed by Brooker and Morris. In Rosen [1967a], pp. 306--331.Google Scholar
- Schorre, D. V. [1964] META II, a syntax oriented compiler writing language, Proc. ACM National Conference, Vol. 19, pp. D1.3--1D1.3--11.Google Scholar
- Unger, S. H. [1968] A global parser for context-free phrase structure grammars. Comm. ACM 11:4, 240--246, and 11:6, 427.Google ScholarDigital Library
- 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.Google Scholar
- Hays, D. G. [1967] Introduction to Computational Linguistics. American Elsevier, New York.Google Scholar
- 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.Google Scholar
- Kasami, T., and K. Torii [1969] A syntax analysis procedure for unambiguous context-free grammars. J. ACM 16:3, 423--431.Google ScholarDigital Library
- Younger, D. H. [1967] Recognition and parsing of context-free languages in time n3. Information and Control 10:2, 189--208.Google ScholarCross Ref
- Culik, K., II [1968] Contribution to deterministic top-down analysis of context-free languages. Kybernetika 4:5, 422--431.Google Scholar
- 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.Google ScholarDigital Library
- 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.Google Scholar
- Kurki-Suonio, R. [1969] Notes on top-down languages. BIT 9, 225--238.Google ScholarCross Ref
- 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.Google Scholar
- Lewis, P. M., II, and R. E. Stearns [1968] Syntax directed transduction. J. ACM 15:3, 464--488.Google ScholarDigital Library
- 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.Google Scholar
- Rosenkrantz, D. J., and R. E. Stearns [1970] Properties of deterministic top-down grammars. Information and Control 17:3, 226--256.Google ScholarCross Ref
- Wood, D. [1970] Bibliography 23: Formal language theory and automata theory. Computing Reviews 11:7, 417--430.Google Scholar
- Aho, A. V., and J. D. Ullman [1971] Translations on a context-free grammar. Information and Control 19:5, 439--475.Google ScholarCross Ref
- DeRemer, F. L. [1969] Practical translators for LR(k) languages. Ph. D. Thesis, Massachusetts Institute of Technology, Cambridge, Mass.Google Scholar
- Hopcroft, J. E., and J. D. Ullman [1969] Formal Languages and Their Relation to automata. Addison-Wesley, Reading, Mass.Google Scholar
- Knuth, D. E. [1965] On the translation of languages from left to right. Information and Control 8:6, 607--639.Google ScholarCross Ref
- Korenjak, A. J. [1969] A practical method for constructing LR(k) processors. Comm. ACM 12:11, 613--623.Google ScholarDigital Library
- Walters, D. A. [1970] Deterministic context-sensitive languages. Information and Control 17:1, 14--61.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- Bauer, H., S. Becker, and S. Graham [1968] ALGOL W implementation. CS98, Computer Science Department, Stanford University, Stanford, Cal.Google Scholar
- Fischer, M. J. [1972] Efficiency of equivalence algorithms. Memo No. 256, Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, Mass.Google Scholar
- Floyd, R. W. [1961] A descriptive language for symbol manipulation. J. ACM 8:4, 579--584.Google ScholarDigital Library
- 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.Google Scholar
- Gray, J. N. [1969] Precedence parsers for programming languages. Ph. D. Thesis, Department of Computer Science, University of California, Berkeley.Google Scholar
- 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.Google ScholarDigital Library
- Leinius, R. P. [1970] Error detection and recovery for syntax directed compiler systems. Ph. D. Thesis, University of Wisconsin, Madison.Google Scholar
- McKeeman, W. M. [1966] An approach to computer language design. CS48. Computer Science Department, Stanford University, Stanford, Cal.Google Scholar
- Pair, C. [1964] Trees, pushdown stores and compilation. RFTI---Chiffres 7:3, 199--216.Google Scholar
- Wirth, N. [1968] PL 360---a programming language for the 360 computers. J. ACM 15:1, 37--34.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- Evans, A., Jr. [1964] An ALGOL 60 compiler. Annual Review in Automatic Programming, Vol. 4. Pergamon, Elmsford, N.Y., pp. 87--124.Google Scholar
- Feldman, J. A. [1966] A formal semantics for computer languages and its application in a compiler-compiler. Comm. ACM 9:1, 3--9.Google ScholarDigital Library
- Floyd, R. W. [1961] A descriptive language for symbol manipulation. J. ACM 8:4, 579--584.Google ScholarDigital Library
- Floyd, R. W. [1963] Syntactic analysis and operator precedence. J. ACM 10:3, 316--333.Google ScholarDigital Library
- Floyd, R. W. [1964a] Bounded context syntactic analysis. Comm. ACM 7:2, 62--67.Google ScholarDigital Library
- Floyd, R. W. [1964b] The syntax of programming languages---a survey. IEEE Trans. on Electronic Computers EC-13: 4, 346--353.Google ScholarCross Ref
- Graham, R. M. [1964] Bounded context translation. Proc. AFIPS Spring Joint Computer Conference, Vol. 25. Spartan, New York, pp. 17--29.Google Scholar
- 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.Google Scholar
- Hopgood, F. R. A. [1969] Compiling Techniques. American Elsevier, New York.Google Scholar
- Irons, E. T. [1964] Structural connections in formal languages. Comm. ACM 7:2, 62--67.Google ScholarDigital Library
- Loeckx, J. [1970] An algorithm for the construction of bounded-context parsers. Comm. ACM 13:5, 297--307.Google ScholarDigital Library
- McKeeman, W. M., J. J. Horning, and D. B. Wortman [1970] A Compiler Generator. Prentice-Hall, Englewood Cliffs, N.J.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google ScholarDigital Library
- McClure, R. M. [1965] TMG---a syntax directed compiler. Proc. ACM National Conference, Vol. 20, pp. 262--274.Google Scholar
- Schorre, D. V. [1964] META II, a syntax oriented compiler writing language, Proc. ACM National Conference, Vol. 19, pp. D1.3--1D1.3--11.Google Scholar
- 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.Google Scholar
- Colmerauer, A. [1970] Total precedence relations. J. ACM 17:1, 14--30.Google ScholarDigital Library
- 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.Google Scholar
- Aho, A. V., and J. D. Ullman [1972a] Linear precedence functions for weak precedence grammars. International J. Computer Mathematics, Section A, 3, 149--155.Google ScholarCross Ref
- Aho, A. V., and J. D. Ullman [1972b] Error detection in precedence parsers. Mathematical Systems Theory, 7:2 (February 1973), 97--113.Google Scholar
- Bell, J. R. [1969] A new method for determining linear precedence functions for precedence grammars. Comm. ACM 12:10, 316--333.Google ScholarDigital Library
- Floyd, R. W. [1963] Syntactic analysis and operator precedence. J. ACM 10:3, 316--333.Google ScholarDigital Library
- Martin, D. F. [1972] A Boolean matrix method for the computation of linear precedence functions. Comm. ACM 15:6, 448--454.Google ScholarDigital Library
- Wirth, N. [1965] Algorithm 265: Find precedence functions. Comm. ACM 8:10, 604--605.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- Beals, A. J. [1969] The generation of a deterministic parsing algorithm. Report No. 304, Department of Computer Science, University of Illinois, Urbana.Google Scholar
- 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.Google Scholar
- Cheatham, T. E. [1967] The Theory and Construction of Compilers (2nd ed.). Computer Associates, Inc., Wakefield, Mass.Google Scholar
- 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.Google Scholar
- Earley, J. [1966] Generating a recognizer for a BNF grammar. Computation Center Report, Carnegie-Mellon University, Pittsburgh.Google Scholar
- Haynes, H. R., and L. J. Schutte [1970] Compilation of optimized syntactic recognizers from Floyd-Evans productions. ACM SIGPLAN Notices 5:7, 38--51.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- LaFrance, J. [1970] Optimization of error recovery in syntax directed parsing algorithms. ACM SIGPLAN Notices 5:12, 2--17.Google ScholarDigital Library
- Aho, A. V., and J. D. Ullman [1972c] Optimization of LR(k) parsers. J. Computer and System Sciences, 6:6, 573--602.Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- Pager, D. [1970] A solution to an open problem by Knuth. Information and Control 17:5, 462--473.Google ScholarCross Ref
- 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.Google Scholar
- DeRemer, F. L. [1969] Practical translators for LR(k) languages. Ph. D. Thesis, Massachusetts Institute of Technology, Cambridge, Mass.Google Scholar
- DeRemer, F. L. [1971] Simple LR(k) grammars. Comm. ACM 14:7, 453--460.Google ScholarDigital Library
- 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.Google Scholar
- Korenjak, A. J. [1969] A practical method for constructing LR(k) processors. Comm. ACM 12:11, 613--623.Google ScholarDigital Library
- Leinius, R. P. [1970] Error detection and recovery for syntax directed compiler systems. Ph. D. Thesis, University of Wisconsin, Madison.Google Scholar
- Aho, A. V., S. C. Johnson, and J. D. Ullman [1972] Deterministic parsing of ambiguous grammars. Unpublished manuscript, Bell Laboratories, Murray Hill, N.J.Google Scholar
- DeRemer, F. L. [1969] Practical translators for LR(k) languages. Ph. D. Thesis, Massachusetts Institute of Technology, Cambridge, Mass.Google Scholar
- 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.Google ScholarDigital Library
- 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.Google Scholar
- Kurki-Suonio, R. [1969] Notes on top-down languages. BIT 9, 225--238.Google ScholarCross Ref
- McNaughton, R. [1967] Parenthesis grammars. J. ACM 14:3, 490--500.Google ScholarDigital Library
- Paull, M. C., and S. H. Unger [1968a] Structural equivalence of context-free grammars. J. Computer and System Sciences 2:1, 427--463.Google ScholarDigital Library
- Rosenkrantz, D. J., and R. E. Stearns [1970] Properties of deterministic top-down grammars. Information and Control 17:3, 226--256.Google ScholarCross Ref
- Aho, A. V., P. J. Denning, and J. D. Ullman [1972] Weak and mixed strategy precedence parsing. J. ACM 19:2, 225--243.Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- Knuth, D. E. [1965] On the translation of languages from left to right. Information and Control 8:6, 607--639.Google ScholarCross Ref
- Fischer, M. J. [1969] Some properties of precedence languages. Proc. ACM Symposium on Theory of Computing, pp. 181--190.Google Scholar
- Backus, J. W., et al. [1957] The FORTRAN Automatic Coding System. Proc. Western Joint Computer Conference, Vol. 11, pp. 188--198.Google Scholar
- Elson, M., and S. T. Rake [1970] Code-generation technique for large-language compilers. IBM Systems J. 9:3, 166--188.Google ScholarDigital Library
- Grau, A. A., U. Hill, and H. Langmaack [1967] Translation of ALGOL 60. Springer-Verlag, New York.Google Scholar
- IBM [1969] System 360 Operating System PL/I (F) Compiler Program Logic Manual. Publ. No. Y286800, IBM, Hursley, Winchester, England.Google Scholar
- Knuth, D. E. [1968a] The Art of Computer Programming, Vol. 1: Fundamental Algorithms. Addison-Wesley, Reading, Mass.Google Scholar
- Randell, B., and L. J. Russell [1964] ALGOL 60 Implementation. Academic Press, New York.Google Scholar
- 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.Google Scholar
- Aho, A. V., and J. D. Ullman [1969a] Syntax directed translation and the pushdown assembler. J. Computer and System Sciences 3:1, 37--56.Google ScholarDigital Library
- Aho, A. V., and J. D. Ullman [1972g] LR(k) syntax directed translation. Unpublished manuscript, Bell Laboratories, Murray Hill, N.J.Google Scholar
- Lewis, P. M., II, and R. E. Stearns [1968] Syntax directed transduction. J. ACM 15:3, 464--488.Google ScholarDigital Library
- McClure, R. M. [1965] TMG---a syntax directed compiler. Proc. ACM National Conference, Vol. 20, pp. 262--274.Google Scholar
- McIlroy, M. D. [1972] A manual for the TMG compiler writing language. Unpublished memorandum, Bell Laboratories, Murray Hill, N.J.Google Scholar
- Schorre, D. V. [1964] META II, a syntax oriented compiler writing language, Proc. ACM National Conference, Vol. 19, pp. D1.3--1D1.3--11.Google Scholar
- Aho, A. V., and J. D. Ullman [1971] Translations on a context-free grammar. Information and Control 19:5, 439--475.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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.Google Scholar
- Bell, J. R. [1970] The quadratic quotient method: a hash code eliminating secondary clustering. Comm. ACM 13:2, 107--109.Google ScholarDigital Library
- Knuth, D. E. [1973] The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison-Wesley, Reading, Mass.Google Scholar
- Maurer, W. D. [1968] An improved hash code for scatter storage. Comm. ACM 11:1, 35--38.Google ScholarDigital Library
- Morris, Robert [1968] Scatter storage techniques. Comm. ACM 11:1, 35--44.Google ScholarDigital Library
- Peterson, W. W. [1957] Addressing for random access storage. IBM J. Research and Development 1:2, 130--146.Google ScholarDigital Library
- Radke, C. E. [1970] The use of quadratic residue search. Comm. ACM 13:2, 103--109.Google ScholarDigital Library
- Ullman, J. D. [1972a] A note on hashing functions. J. ACM 19:3, 569--575.Google ScholarDigital Library
- 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.Google Scholar
- Fischer, M. J. [1972] Efficiency of equivalence algorithms. Memo No. 256, Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, Mass.Google Scholar
- Hopcroft, J. E., and J. D. Ullman [1972a] Set merging algorithms. Unpublished memorandum. Department of Computer Science, Cornell University, Ithaca, N.Y.Google Scholar
- Stearns, R. E., and P. M. Lewis, II [1969] Property grammars and table machines. Information and Control 14:6, 524--549.Google ScholarCross Ref
- 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.Google Scholar
- Aho, A. V., and J. D. Ullman [1972e] Optimization of straight line code. SIAM J. on Computing 1:1, 1--19.Google ScholarCross Ref
- Aho, A. V., and J. D. Ullman [1972f] Equivalence of programs with structured variables. J. Computer and System Sciences 6:2, 125--137.Google ScholarDigital Library
- 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.Google Scholar
- Bracha, N. [1972] Transformations on loop-free program schemata. Report No. UIUCDCS-R-72-516, Department of Computer Science, University of Illinois, UrbanaGoogle Scholar
- Breuer, M. A. [1969] Generation of optimal code for expressions via factorization. Comm. ACM 12:6, 333--340.Google ScholarDigital Library
- Caviness, B. F. [1970] On canonical forms and simplification. J. ACM 17:2, 385--396.Google ScholarDigital Library
- De Bakker, J. W. [1971] Axiom systems for simple assignment statements. In Engeler [1971], pp. 1--22.Google Scholar
- Floyd, R. W. [1961a] An algorithm for coding efficient arithmetic operations. Comm. ACM 4:1, 42--51.Google ScholarDigital Library
- 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.Google Scholar
- Richardson, D. [1968] Some unsolvable problems involving elementary functions of a real variable. J. Symbolic Logic 33, 514--520.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- Anderson, J. P. [1964] A note on some compiling algorithms. Comm. ACM 7:3, 149--150.Google ScholarDigital Library
- Baer, J. L., and D. P. Bovet [1968] Compilation of arithmetic expressions for parallel computations. Proc. IFIP Congress 68, B4--B10.Google Scholar
- Beatty, J. C. [1972] An axiomatic approach to code optimization for expressions. J. ACM, 19: 4.Google ScholarDigital Library
- Belady, L. A. [1966] A study of replacement algorithms for a virtual storage computer. IBM Systems J. 5, 78--82.Google ScholarDigital Library
- Chen, S. [1972] On the Sethi-Ullman algorithm. Unpublished memorandum, Bell Laboratories, Holmdel, N.J.Google Scholar
- Floyd, R. W. [1961a] An algorithm for coding efficient arithmetic operations. Comm. ACM 4:1, 42--51.Google ScholarDigital Library
- Frailey, D. J. [1970] Expression optimization using unary complement operators. ACM SIGPLAN Notices 5:7, 67--85.Google ScholarDigital Library
- 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.Google Scholar
- Hellerman, H. [1966] Parallel processing of algebraic expressions. IEEE Trans. on Electronic Computers EC-15:1, 82--91.Google ScholarCross Ref
- Horwitz, L. P., R. M. Karp, R. E. Miller, and S. Winograd [1966] Index register allocation. J. ACM 13:1, 43--61.Google ScholarDigital Library
- 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.Google Scholar
- Meyers, W. J. [1965] Optimization of computer code. Unpublished memorandum. G. E. Research Center, Schenectady, N.Y.Google Scholar
- Nakata, I. [1967] On compiling algorithms for arithmetic expressions. Comm. ACM 12:2, 81--84.Google Scholar
- Redziejowski, R. R. [1969] On arithmetic expressions and trees. Comm. ACM 12:2, 81--84.Google ScholarDigital Library
- Sethi, R. [1972] Validating register allocations for straight line programs. Ph. D. Thesis, Department of Electrical Engineering, Princeton University.Google Scholar
- Sethi, R., and J. D. Ullman [1970] The generation of optimal code for arithmetic expressions. J. ACM 17:4, 715--728.Google ScholarDigital Library
- Stone, H. S. [1967] One-pass compilation of arithmetic expressions for a parallel processor. Comm. ACM 10:4, 220--223.Google ScholarDigital Library
- Allen, F. E. [1969] Program optimization. Annual Review in Automatic Programming, Vol. 5., Pergamon, Elmsford, N.Y.Google Scholar
- 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.Google Scholar
- Busam, V. A., and D. E. Englund [1969] Optimization of expressions in Fortran. Comm. ACM 12:12, 666--674.Google ScholarDigital Library
- Clark, E. R. [1967] On the automatic simplification of source language programs. Comm. ACM 10:3, 160--164.Google ScholarDigital Library
- Gear, C. W. [1965] High speed compilation of efficient object code. Comm. ACM 8:8, 483--487.Google ScholarDigital Library
- Ianov, I. I. [1958] On the equivalence and transformation of program schemes. Translation in Comm. ACM 1:10, 8--11.Google ScholarDigital Library
- Kaplan, D. M. [1970] Proving things about programs. Proc. 4th Annual Princeton Conference on Information Sciences and Systems, pp. 244--251.Google Scholar
- Lowry, E. S., and C. W. Medlock [1969] Object code optimization. Comm. ACM 12:1, 13--22.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- Manna, Z. [1973] Program schemas. In Aho [1973].Google Scholar
- Marill, M. [1962] Computational chains and the size of computer programs. IRE Trans. on Electronic Computers, EC-11:2, 173--180.Google Scholar
- McKeeman, W. M. [1965] Peephole optimization. Comm. ACM 8: 7, 443--444.Google ScholarDigital Library
- Nievergelt, J. [1965] On the automatic simplification of computer programs. Comm. ACM 8:6, 366--370.Google ScholarDigital Library
- 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.Google Scholar
- 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.Google ScholarDigital Library
- Allen, F. E. [1970] Control flow analysis. ACM SIGPLAN Notices 5:7, 1--19.Google ScholarDigital Library
- Busam, V. A., and D. E. Englund [1969] Optimization of expressions in Fortran. Comm. ACM 12:12, 666--674.Google ScholarDigital Library
- Cocke, J. [1970] Global common subexpression elimination. ACM SIGPLAN Notices 5:7, 20--24.Google ScholarDigital Library
- Cocke, J., and J. T. Schwartz [1970] Programming Languages and Their Compilers (2nd ed.). Courant Institute of Mathematical Sciences, New York University, New York.Google Scholar
- Hecht, M. S., and J. D. Ullman [1972a] Flow graph reducibility. SIAM J. on Computing 1:2, 188--202.Google ScholarCross Ref
- Hecht, M. S., and J. D. Ullman [1972b] Unpublished memorandum, Department of Electrical Engineering, Princeton UniversityGoogle Scholar
- 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.Google Scholar
- Kennedy, K. [1971] A global flow analysis algorithm. International J. Computer Mathematics 3:1, 5--16Google Scholar
- Knuth, D. E. [1971] An empirical study of FORTRAN programs. Software-Practice and Experience 1:2, 105--134.Google ScholarCross Ref
- Lowry, E. S., and C. W. Medlock [1969] Object code optimization. Comm. ACM 12:1, 13--22.Google ScholarDigital Library
- Schaefer, M. [1973] A Mathematical Theory of Global Program Optimization Prentice-Hall, Englewood Cliffs, N.J., to appear.Google Scholar
- 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.Google Scholar
Cited By
- Handzhiyski N and Somova E (2022). Tunnel Parsing with the Token’s Lexeme, Cybernetics and Information Technologies, 22:2, (125-144), Online publication date: 1-Jun-2022.
- Italiano G, Karczmarz A and Parotsidis N Planar reachability under single vertex or edge failures Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, (2739-2758)
- Pshenitsyn T Hypergraph Basic Categorial Grammars Graph Transformation, (146-162)
- Maletti A and Stier K On Tree Substitution Grammars Developments in Language Theory, (237-250)
- Koechlin F, Nicaud C and Rotondo P On the Degeneracy of Random Expressions Specified by Systems of Combinatorial Equations Developments in Language Theory, (164-177)
- Gildea D, Satta G and Peng X (2019). Ordered tree decomposition for hrg rule extraction, Computational Linguistics, 45:2, (339-379), Online publication date: 1-Jun-2019.
Jepsen T, Alvarez D, Foster N, Kim C, Lee J, Moshref M and Soulé R Fast String Searching on PISA Proceedings of the 2019 ACM Symposium on SDN Research, (21-28)- Krishnamurthy V and Gao S (2018). Syntactic Enhancement to VSIMM for Roadmap Based Anomalous Trajectory Detection, IEEE Transactions on Signal Processing, 66:20, (5212-5227), Online publication date: 1-Oct-2018.
- Slivnik B (2017). On different LL and LR parsers used in LLLR parsing, Computer Languages, Systems and Structures, 50:C, (108-126), Online publication date: 1-Dec-2017.
- Efanov N and Emelyanov P Constructing the formal grammar of system calls Proceedings of the 13th Central & Eastern European Software Engineering Conference in Russia, (1-5)
- El-Qurna J, Yahyaoui H and Almulla M (2017). A new framework for the verification of service trust behaviors, Knowledge-Based Systems, 121:C, (7-22), Online publication date: 1-Apr-2017.
- Georgiadis L, Italiano G and Parotsidis N Strong connectivity in directed graphs under failures, with applications Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, (1880-1899)
- Henglein F and Rasmussen U PEG parsing in less space using progressive tabling and dynamic analysis Proceedings of the 2017 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, (35-46)
- Carmantini G, beim Graben P, Desroches M and Rodrigues S (2017). A modular architecture for transparent computation in recurrent neural networks, Neural Networks, 85:C, (85-105), Online publication date: 1-Jan-2017.
- Aizikowitz T and Kaminski M (2016). LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata, Journal of Computer and System Sciences, 82:8, (1329-1359), Online publication date: 1-Dec-2016.
- Voelter M, Szabó T, Lisson S, Kolb B, Erdweg S and Berger T Efficient development of consistent projectional editors using grammar cells Proceedings of the 2016 ACM SIGPLAN International Conference on Software Language Engineering, (28-40)
- Statter D and Armoni M Teaching Abstract Thinking in Introduction to Computer Science for 7th Graders Proceedings of the 11th Workshop in Primary and Secondary Computing Education, (80-83)
- Kurš J, Vraný J, Ghafari M, Lungu M and Nierstrasz O Optimizing Parser Combinators Proceedings of the 11th edition of the International Workshop on Smalltalk Technologies, (1-13)
- Leung A, Sarracino J and Lerner S (2015). Interactive parser synthesis by example, ACM SIGPLAN Notices, 50:6, (565-574), Online publication date: 7-Aug-2015.
- Romanov V, Yudakova E, Efimova S and Varfolomeeva A Virtual enterprise synthesis by web services composition with HTN-like parsing algorithm (WIP) Proceedings of the Conference on Summer Computer Simulation, (1-6)
- Leung A, Sarracino J and Lerner S Interactive parser synthesis by example Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation, (565-574)
- Adams M and Ağacan Ö (2014). Indentation-sensitive parsing for Parsec, ACM SIGPLAN Notices, 49:12, (121-132), Online publication date: 11-May-2015.
- Adams M and Ağacan Ö Indentation-sensitive parsing for Parsec Proceedings of the 2014 ACM SIGPLAN symposium on Haskell, (121-132)
- Scott E and Johnstone A (2013). GLL parse-tree generation, Science of Computer Programming, 78:10, (1828-1844), Online publication date: 1-Oct-2013.
- Kutrib M and Worsch T Time-Symmetric machines Proceedings of the 5th international conference on Reversible Computation, (168-181)
- Kutrib M and Malcher A (2013). One-Dimensional Cellular Automaton Transducers, Fundamenta Informaticae, 126:2-3, (201-224), Online publication date: 1-Apr-2013.
- Talton J, Yang L, Kumar R, Lim M, Goodman N and Měch R Learning design patterns with bayesian grammar induction Proceedings of the 25th annual ACM symposium on User interface software and technology, (63-74)
- Büchse M, Maletti A and Vogler H Unidirectional derivation semantics for synchronous tree-adjoining grammars Proceedings of the 16th international conference on Developments in Language Theory, (368-379)
- Hayashi K, Watanabe T, Asahara M and Matsumoto Y Head-driven transition-based parsing with top-down prediction Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics: Long Papers - Volume 1, (657-665)
- Karlov B Abstract automata and a normal form for categorial dependency grammars Proceedings of the 7th international conference on Logical Aspects of Computational Linguistics, (86-102)
- van Schijndel M, Exley A and Schuler W Connectionist-inspired incremental PCFG parsing Proceedings of the 3rd Workshop on Cognitive Modeling and Computational Linguistics, (51-60)
- Ganitkevitch J, Van Durme B and Callison-Burch C Monolingual distributional similarity for text-to-text generation Proceedings of the First Joint Conference on Lexical and Computational Semantics - Volume 1: Proceedings of the main conference and the shared task, and Volume 2: Proceedings of the Sixth International Workshop on Semantic Evaluation, (256-264)
- Brailsford D (2012). Reconstituting typeset Marriage Registers using simple software tools, Computer Science - Research and Development, 27:2, (113-126), Online publication date: 1-May-2012.
- Jourdan J, Pottier F and Leroy X Validating LR(1) parsers Proceedings of the 21st European conference on Programming Languages and Systems, (397-416)
- Logacheva V and Klyshinsky E (2012). Generation of finite state machine for named entities transliteration task, Automatic Documentation and Mathematical Linguistics, 46:1, (22-30), Online publication date: 1-Feb-2012.
- Matsuda K, Inaba K and Nakano K Polynomial-time inverse computation for accumulative functions with multiple data traversals Proceedings of the ACM SIGPLAN 2012 workshop on Partial evaluation and program manipulation, (5-14)
- Hafiz R and Frost R Modular natural language processing using declarative attribute grammars Proceedings of the 10th Mexican international conference on Advances in Artificial Intelligence - Volume Part I, (291-304)
- Quesada L, Berzal F and Cubero J A language specification tool for model-based parsing Proceedings of the 12th international conference on Intelligent data engineering and automated learning, (50-57)
- Ganitkevitch J, Callison-Burch C, Napoles C and Van Durme B Learning sentential paraphrases from bilingual parallel corpora for text-to-text generation Proceedings of the Conference on Empirical Methods in Natural Language Processing, (1168-1179)
- Hanneforth T A practical algorithm for intersecting weighted context-free grammars with finite-state automata Proceedings of the 9th International Workshop on Finite State Methods and Natural Language Processing, (57-64)
- Maletti A How to train your multi bottom-up tree transducer Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies - Volume 1, (825-834)
- Maletti A (2011). An alternative to synchronous tree substitution grammars*, Natural Language Engineering, 17:2, (221-242), Online publication date: 1-Apr-2011.
- Johnstone A, Scott E and van den Brand M LDT Proceedings of the Eleventh Workshop on Language Descriptions, Tools and Applications, (1-8)
- Bahadur P, Jain A and Chauhan D English to Sanskrit machine translation Proceedings of the International Conference & Workshop on Emerging Trends in Technology, (641-645)
- Piecha J and Staniek M The context-sensitive grammar for vehicle movement description Proceedings of the 2010 international conference on Computer vision and graphics: Part II, (193-202)
- Hundeshagen N, Otto F and Vollweiler M Transductions computed by PC-systems of monotone deterministic restarting automata Proceedings of the 15th international conference on Implementation and application of automata, (163-172)
- Gecse R and KováCs A (2010). Consistency of stochastic context-free grammars, Mathematical and Computer Modelling: An International Journal, 52:3-4, (490-500), Online publication date: 1-Aug-2010.
- Van Asch V and Daelemans W Using domain similarity for performance estimation Proceedings of the 2010 Workshop on Domain Adaptation for Natural Language Processing, (31-36)
- Saers M, Nivre J and Wu D Linear inversion transduction grammar alignments as a second translation path Proceedings of the Joint Fifth Workshop on Statistical Machine Translation and MetricsMATR, (167-171)
- Huang L and Sagae K Dynamic programming for linear-time incremental parsing Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, (1077-1086)
- Maletti A A tree transducer model for synchronous tree-adjoining grammars Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, (1067-1076)
- Blum N On LR(k)-parsers of polynomial size Proceedings of the 37th international colloquium conference on Automata, languages and programming: Part II, (163-174)
- Avinesh P A data mining approach to learn reorder rules for SMT Proceedings of the NAACL HLT 2010 Student Research Workshop, (52-57)
- Maletti A Why synchronous tree substitution grammars? Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, (876-884)
- Saers M, Nivre J and Wu D Word alignment with Stochastic Bracketing Linear Inversion Transduction Grammar Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, (341-344)
- Melichar B Arbology Proceedings of the 4th international conference on Language and Automata Theory and Applications, (32-49)
- Matuszek C, Fox D and Koscher K Following directions using statistical machine translation Proceedings of the 5th ACM/IEEE international conference on Human-robot interaction, (251-258)
- Nederhof M and Satta G Algorithmic aspects of natural language processing Algorithms and theory of computation handbook, (23-23)
- Boullier P, Nasr A and Sagot B Constructing parse forests that include exactly the n-best PCFG trees Proceedings of the 11th International Conference on Parsing Technologies, (117-128)
- Søgaard A and Wu D Empirical lower bounds on translation unit error rate for the full class of inversion transduction grammars Proceedings of the 11th International Conference on Parsing Technologies, (33-36)
- Saers M, Nivre J and Wu D Learning stochastic bracketing inversion transduction grammars with a cubic time biparsing algorithm Proceedings of the 11th International Conference on Parsing Technologies, (29-32)
- Steffen P, Giegerich R and Giraud M GPU parallelization of algebraic dynamic programming Proceedings of the 8th international conference on Parallel processing and applied mathematics: Part II, (290-299)
- Lavee G, Rivlin E and Rudzsky M (2009). Understanding video events, IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 39:5, (489-504), Online publication date: 1-Sep-2009.
- Huang L, Jiang W and Liu Q Bilingually-constrained (monolingual) shift-reduce parsing Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing: Volume 3 - Volume 3, (1222-1231)
- Lu W, Ng H and Lee W Natural language generation with tree conditional random fields Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing: Volume 1 - Volume 1, (400-409)
- Pavlatos C, Dimopoulos A, Koulouris A, Andronikos T, Panagopoulos I and Papakonstantinou G (2009). Efficient reconfigurable embedded parsers, Computer Languages, Systems and Structures, 35:2, (196-215), Online publication date: 1-Jul-2009.
- Head M and Govindaraju M Performance enhancement with speculative execution based parallelism for processing large-scale xml-based application data Proceedings of the 18th ACM international symposium on High performance distributed computing, (21-30)
- Søgaard A On the complexity of alignment problems in two synchronous grammar formalisms Proceedings of the Third Workshop on Syntax and Structure in Statistical Translation, (60-68)
- Saers M and Wu D Improving phrase-based translation via word alignments from stochastic inversion transduction grammars Proceedings of the Third Workshop on Syntax and Structure in Statistical Translation, (28-36)
- Søgaard A and Kuhn J Empirical lower bounds on alignment error rates in syntax-based machine translation Proceedings of the Third Workshop on Syntax and Structure in Statistical Translation, (19-27)
- Shoukourian A (2009). Equivalence of regular expressions over a partially commutative alphabet, Cybernetics and Systems Analysis, 45:3, (387-396), Online publication date: 1-May-2009.
- Aho A (2008). Teaching the compilers course, ACM SIGCSE Bulletin, 40:4, (6-8), Online publication date: 30-Nov-2008.
- Barbar K Automatic generator of XML documents editors based on attributed grammars Proceedings of the 5th international conference on Soft computing as transdisciplinary science and technology, (166-172)
- Song X, Ding S and Lin C Better binarization for the CKY parsing Proceedings of the Conference on Empirical Methods in Natural Language Processing, (167-176)
- Sangeorzan L, Burada M and Iakab K (2008). Aspects of dictionary making developing an in-house text parsing tool, WSEAS Transactions on Computers, 7:10, (1731-1741), Online publication date: 1-Oct-2008.
- Imada K and Nakamura K Towards machine learning of grammars and compilers of programming languages Proceedings of the 2008th European Conference on Machine Learning and Knowledge Discovery in Databases - Volume Part II, (98-112)
- Haslum P A new approach to tractable planning Proceedings of the Eighteenth International Conference on International Conference on Automated Planning and Scheduling, (132-139)
- Francez N and Kaminski M (2008). Commutation-augmented pregroup grammars and push-down automata with cancellation, Information and Computation, 206:9-10, (1018-1032), Online publication date: 1-Sep-2008.
- Sangeorzan L, Burada M and Iakab K Designing a text parsing programme for a specialized bilingual online dictionary Proceedings of the 8th conference on Applied informatics and communications, (110-114)
- Minock M, Olofsson P and Näslund A Towards Building Robust Natural Language Interfaces to Databases Proceedings of the 13th international conference on Natural Language and Information Systems: Applications of Natural Language to Information Systems, (187-198)
- Bonev S An adaptable FSA simulator Proceedings of the 9th International Conference on Computer Systems and Technologies and Workshop for PhD Students in Computing, (II.3-1)
- Schmitz S (2008). An Experimental Ambiguity Detection Tool, Electronic Notes in Theoretical Computer Science (ENTCS), 203:2, (69-84), Online publication date: 1-Apr-2008.
- Setzer B Minimal finite automata from finite training sets Proceedings of the 46th Annual Southeast Regional Conference on XX, (294-297)
- Deba E On the conformity of models Proceedings of the 2008 ACM symposium on Applied computing, (791-796)
- Frost R, Hafiz R and Callaghan P Parser combinators for ambiguous left-recursive grammars Proceedings of the 10th international conference on Practical aspects of declarative languages, (167-181)
- Loukanova R Linear context free languages Proceedings of the 4th international conference on Theoretical aspects of computing, (351-365)
- Johnstone A and Scott E (2007). Automatic recursion engineering of reduction incorporated parsers, Science of Computer Programming, 68:2, (95-110), Online publication date: 1-Sep-2007.
- Caymes-Scutari P, Morajko A, Margalef T and Luque E Automatic generation of dynamic tuning techniques Proceedings of the 13th international Euro-Par conference on Parallel Processing, (13-22)
- Bordihn H and Vaszil G Top-down deterministic parsing of languages generated by CD grammar systems Proceedings of the 16th international conference on Fundamentals of Computation Theory, (113-124)
- Steinby M and Tîrnăucă C Syntax-directed translations and quasi-alphabetic tree bimorphisms Proceedings of the 12th international conference on Implementation and application of automata, (265-276)
- Brabrand C, Giegerich R and Møller A Analyzing ambiguity of context-free grammars Proceedings of the 12th international conference on Implementation and application of automata, (214-225)
- Xing H (2007). Fuzzy pushdown automata, Fuzzy Sets and Systems, 158:13, (1437-1449), Online publication date: 1-Jul-2007.
- Head M and Govindaraju M Approaching a parallelized XML parser optimized for multi-coreprocessors Proceedings of the 2007 workshop on Service-oriented computing performance: aspects, issues, and approaches, (17-22)
- Frost R, Hafiz R and Callaghan P Modular and efficient top-down parsing for ambiguous left-recursive grammars Proceedings of the 10th International Conference on Parsing Technologies, (109-120)
- Papushev E and Bonev S A tale of three LR(1) syntax analyzers Proceedings of the 2007 international conference on Computer systems and technologies, (1-6)
- Dreyer M, Hall K and Khudanpur S Comparing reordering constraints for SMT using efficient Bleu oracle computation Proceedings of the NAACL-HLT 2007/AMTA Workshop on Syntax and Structure in Statistical Translation, (103-110)
- Zhang H and Gildea D Factorization of synchronous context-free grammars in linear time Proceedings of the NAACL-HLT 2007/AMTA Workshop on Syntax and Structure in Statistical Translation, (25-32)
- Bonzini P and Pozzi L Polynomial-time subgraph enumeration for automated instruction set extension Proceedings of the conference on Design, automation and test in Europe, (1331-1336)
- Sarker M, Rahman S and Mottalib M (2007). Bottom-up context-sensitive algorithms for Bengali parser in natural language processing, International Journal of Knowledge-based and Intelligent Engineering Systems, 11:2, (79-87), Online publication date: 1-Apr-2007.
- Cousot P and Cousot R Grammar analysis and parsing by abstract interpretation Program analysis and compilation, theory and practice, (175-200)
- Meduna A and Masopust T (2007). Self-regulating finite automata, Acta Cybernetica, 18:1, (135-153), Online publication date: 1-Jan-2007.
- Floyd R The paradigms of programming ACM Turing award lectures
- La Torre S, Napoli M and Parente M On the membership problem for visibly pushdown languages Proceedings of the 4th international conference on Automated Technology for Verification and Analysis, (96-109)
- Starkie B, van Zaanen M and Estival D The tenjinno machine translation competition Proceedings of the 8th international conference on Grammatical Inference: algorithms and applications, (214-226)
- Žemlička M Parsing with oracle Proceedings of the 9th international conference on Text, Speech and Dialogue, (309-316)
- Steffen P and Giegerich R (2006). Table design in dynamic programming, Information and Computation, 204:9, (1325-1345), Online publication date: 1-Sep-2006.
- Zhang H and Gildea D Inducing word alignments with bilexical synchronous trees Proceedings of the COLING/ACL on Main conference poster sessions, (953-960)
- Gildea D, Satta G and Zhang H Factoring synchronous grammars by sorting Proceedings of the COLING/ACL on Main conference poster sessions, (279-286)
- Huang L, Knight K and Joshi A A syntax-directed translator with extended domain of locality Proceedings of the Workshop on Computationally Hard Problems and Joint Inference in Speech and Language Processing, (1-8)
- Huang L Efficient algorithms for richer formalisms Proceedings of the 2006 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology: companion volume: doctoral consortium, (223-226)
- Naumann U and Vehreschild A Tangent-Linear models by augmented LL-Parsers Proceedings of the 6th international conference on Computational Science and Its Applications - Volume Part I, (865-874)
- Giegerich R and Steffen P Challenges in the compilation of a domain specific language for dynamic programming Proceedings of the 2006 ACM symposium on Applied computing, (1603-1609)
- Meduna A (2006). Deep pushdown automata, Acta Informatica, 42:8-9, (541-552), Online publication date: 1-Apr-2006.
- Yoshimoto K, Kobayashi M, Nakamura H and Mori Y Processing of information structure and floating quantifiers in japanese Proceedings of the 2005 international conference on New Frontiers in Artificial Intelligence, (103-110)
- Johnstone A and Scott E (2005). Recursion Engineering for Reduction Incorporated Parsers, Electronic Notes in Theoretical Computer Science (ENTCS), 141:4, (143-160), Online publication date: 1-Dec-2005.
- Asveld P (2005). Fuzzy context-free languages, Theoretical Computer Science, 347:1-2, (191-213), Online publication date: 30-Nov-2005.
- Asveld P (2005). Fuzzy context-free languages, Theoretical Computer Science, 347:1-2, (167-190), Online publication date: 30-Nov-2005.
- Goldstine J, Leung H and Wotschke D (2005). Measuring nondeterminism in pushdown automata, Journal of Computer and System Sciences, 71:4, (440-466), Online publication date: 1-Nov-2005.
- Huang L, Zhang H and Gildea D Machine translation as lexicalized parsing with hooks Proceedings of the Ninth International Workshop on Parsing Technology, (65-73)
- Leinenbach D, Paul W and Petrova E Towards the Formal Verification of a C0 Compiler Proceedings of the Third IEEE International Conference on Software Engineering and Formal Methods, (2-12)
- Sakakibara Y (2005). Learning context-free grammars using tabular representations, Pattern Recognition, 38:9, (1372-1383), Online publication date: 1-Sep-2005.
- Sakakibara Y (2005). Grammatical Inference in Bioinformatics, IEEE Transactions on Pattern Analysis and Machine Intelligence, 27:7, (1051-1062), Online publication date: 1-Jul-2005.
- Nederhof M (2019). A general technique to train language models on language models, Computational Linguistics, 31:2, (173-185), Online publication date: 1-Jun-2005.
- Reussner R, Happe J and Habel A Modelling parametric contracts and the state space of composite components by graph grammars Proceedings of the 8th international conference, held as part of the joint European Conference on Theory and Practice of Software conference on Fundamental Approaches to Software Engineering, (80-95)
- Bulatewicz T, Cuny J and Warman M The potential coupling interface Proceedings of the 36th conference on Winter simulation, (183-190)
- Bonev S A flexible table driven LR(1) parser Proceedings of the 5th international conference on Computer systems and technologies, (1-6)
- Nederhof M and Satta G (2004). IDL-expressions, Journal of Artificial Intelligence Research, 21:1, (287-317), Online publication date: 1-Jan-2004.
- Sima'an K Robust data oriented spoken language understanding New developments in parsing technology, (323-338)
- Prolo C An efficient LR parser generator for tree-adjoining grammars New developments in parsing technology, (125-155)
- Durham A, Sussumu E and da Conceição A A framework for building language interpreters Companion of the 18th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, (191-196)
- Rahonis G Alphabetic pushdown tree transducers Proceedings of the 7th international conference on Developments in language theory, (423-436)
- Nickell E and Smith I Three patterns in java unit testing Proceedings of the 4th international conference on Extreme programming and agile processes in software engineering, (170-179)
- Johnstone A and Scott E Generalised regular parsers Proceedings of the 12th international conference on Compiler construction, (232-246)
- Král J and Žemlička M Software confederations Managing globally with information technology, (57-81)
- Goldstine J Formal languages Encyclopedia of Computer Science, (716-720)
- Kuikka E, Leinonen P and Penttonen M Towards automating of document structure transformations Proceedings of the 2002 ACM symposium on Document engineering, (103-110)
- Ţiplea F and Mäkinen E (2002). On the complexity of a problem on monadic string rewriting systems, Journal of Automata, Languages and Combinatorics, 7:4, (599-609), Online publication date: 1-Sep-2002.
- (2001). On parsing LL-languages, Theoretical Computer Science, 267:1-2, (49-59), Online publication date: 26-Sep-2001.
- Albert J, Giammarresi D and Wood D (2001). Normal form algorithms for extended context-free grammars, Theoretical Computer Science, 267:1-2, (35-47), Online publication date: 26-Sep-2001.
- Garcia A and Haeusler E (2001). Code migration and program maintainability---a categorical perspective, Information Processing Letters, 79:5, (249-254), Online publication date: 1-Sep-2001.
- Picó D and Casacuberta F (2001). Some Statistical-Estimation Methods for Stochastic Finite-State Transducers, Machine Language, 44:1-2, (121-141), Online publication date: 1-Jul-2001.
- Landauer C and Bellman K Self-modeling systems Proceedings of the 2nd international conference on Self-adaptive software: applications, (238-256)
- Kasyanov V (2001). Graph Applications in Programming, Programming and Computing Software, 27:3, (146-164), Online publication date: 1-May-2001.
- Zhogolev E (2001). Graphical Editors and Graphic Grammars, Programming and Computing Software, 27:3, (130-138), Online publication date: 1-May-2001.
- Pijls W (2000). LR and LL parsing, ACM SIGCSE Bulletin, 32:4, (24-27), Online publication date: 1-Dec-2000.
- Ciressan C, Sanchez E, Rajman M and Chappelier J An FPGA-Based Coprocessor for the Parsing of Context-Free Grammars Proceedings of the 2000 IEEE Symposium on Field-Programmable Custom Computing Machines
- Rao A and Pande S (1999). Storage assignment optimizations to generate compact and efficient code on embedded DSPs, ACM SIGPLAN Notices, 34:5, (128-138), Online publication date: 1-May-1999.
- Rao A and Pande S Storage assignment optimizations to generate compact and efficient code on embedded DSPs Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, (128-138)
- Fanton M Finite state automata and Arabic writing Proceedings of the Workshop on Computational Approaches to Semitic Languages, (26-33)
- Mohri M and Pereira F Dynamic compilation of weighted context-free grammars Proceedings of the 36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics - Volume 2, (891-897)
- Chidlovskii B, Borghoff U and Chevalier P Towards sophisticated wrapping of web-based information repositories Computer-Assisted Information Searching on Internet, (123-135)
- Paakki J, Koskinen J and Salminen A (1997). From relational program dependencies to hypertextual access structures, Nordic Journal of Computing, 4:1, (3-36), Online publication date: 1-Mar-1997.
- Cyre W (1997). Capture, Integration, and Analysis of Digital System Requirements with Conceptual Graphs, IEEE Transactions on Knowledge and Data Engineering, 9:1, (8-23), Online publication date: 1-Jan-1997.
- Kannan S, Sweedyk Z and Mahaney S Counting and random generation of strings in regular languages Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, (551-557)
- Corazza A, De Mori R, Gretter R and Satta G (1994). Optimal Probabilistic Evaluation Functions for Search Controlled by Stochastic Context-Free Grammars, IEEE Transactions on Pattern Analysis and Machine Intelligence, 16:10, (1018-1027), Online publication date: 1-Oct-1994.
- Shelekhov V and Kuksenko S (1994). Object analysis of program, ACM SIGPLAN Notices, 29:9, (125-134), Online publication date: 1-Sep-1994.
- Dedene G and Snoeck M (1994). M.E.R.O.DE.: a model-driven entity-relationship object-oriented Development method, ACM SIGSOFT Software Engineering Notes, 19:3, (51-61), Online publication date: 1-Jul-1994.
- Naur P (1994). Proof versus formalization, BIT, 34:1, (148-164), Online publication date: 1-Mar-1994.
- Zima E Numeric code optimization in computer algebra systems and recurrent relations technique Proceedings of the 1993 international symposium on Symbolic and algebraic computation, (42-46)
- Canfora G, Cimitile A and de Carlini U (1992). A Logic-Based Approach to Reverse Engineering Tools Production, IEEE Transactions on Software Engineering, 18:12, (1053-1064), Online publication date: 1-Dec-1992.
- Dymetman M A generalized Greibach Normal Form for definite clause grammars Proceedings of the 14th conference on Computational linguistics - Volume 1, (366-372)
- Steegmans E, Lewi J and Van Horebeek I (1992). Generation of Interactive Parsers with Error Handling, IEEE Transactions on Software Engineering, 18:5, (357-367), Online publication date: 1-May-1992.
- van den Bosch P (1992). A bibliography on syntax error handling in context free languages, ACM SIGPLAN Notices, 27:4, (77-86), Online publication date: 1-Apr-1992.
- Ammarguellat Z (1992). A Control-Flow Normalization Algorithm and its Complexity, IEEE Transactions on Software Engineering, 18:3, (237-251), Online publication date: 1-Mar-1992.
- Zue V, Glass J, Goddeau D, Goodine D, Hirschman L, Phillips M, Polifroni J and Seneff S The MIT ATIS system Proceedings of the workshop on Speech and Natural Language, (84-88)
- Tague J, Salminen A and McClellan C Complete formal model for information retrieval systems Proceedings of the 14th annual international ACM SIGIR conference on Research and development in information retrieval, (14-20)
- Corazza A, De Mori R, Gretter R and Satta G (1991). Computation of Probabilities for an Island-Driven Parser, IEEE Transactions on Pattern Analysis and Machine Intelligence, 13:9, (936-950), Online publication date: 1-Sep-1991.
- Satta G and Stock O A tabular method for island-driven context-free grammar parsing Proceedings of the ninth National conference on Artificial intelligence - Volume 1, (143-148)
- Schabes Y Polynomial time and space shift-reduce parsing of arbitrary context-free grammars Proceedings of the 29th annual meeting on Association for Computational Linguistics, (106-113)
- Purtilo J and Callahan J (1989). Parse tree annotations, Communications of the ACM, 32:12, (1467-1477), Online publication date: 1-Dec-1989.
- Seyed-Abbassi B and Thompson J G-base fourth normal form in relational database Proceedings of the 17th conference on ACM Annual Computer Science Conference, (54-61)
- Schabes Y and Joshi A An Earley-type parsing algorithm for Tree Adjoining Grammars Proceedings of the 26th annual meeting on Association for Computational Linguistics, (258-269)
- Yeh D and Kastens U (1988). Automatic construction of incremental LR(1)—parsers, ACM SIGPLAN Notices, 23:3, (33-42), Online publication date: 1-Mar-1988.
- Gonnet G and Tompa F Mind Your Grammar Proceedings of the 13th International Conference on Very Large Data Bases, (339-346)
- Gerardy R (1987). Experimental comparison of some parsing methods, ACM SIGPLAN Notices, 22:8, (79-88), Online publication date: 1-Aug-1987.
- Girardot J and Rollin F (1987). The syntax of APL, an old approach revisited, ACM SIGAPL APL Quote Quad, 17:4, (441-449), Online publication date: 1-May-1987.
- Park J (1987). Remarks on recent algorithms for LALR lookahead sets, ACM SIGPLAN Notices, 22:4, (30-32), Online publication date: 1-Apr-1987.
- Girardot J and Rollin F The syntax of APL, an old approach revisited Proceedings of the international conference on APL: APL in transition, (441-449)
- Moura A (1986). Early error detection in syntax-driven parsers, IBM Journal of Research and Development, 30:6, (617-626), Online publication date: 1-Nov-1986.
- Partsch H (1986). Transformational program development in a particular problem domain, Science of Computer Programming, 7:C, (99-241), Online publication date: 1-Jun-1986.
- Vijay-Shankar K and Joshi A Some computational properties of tree adjoining grammars Proceedings of the workshop on Strategic computing natural language, (212-223)
- Botting R (1986). Into the fourth dimension—an introduction to dynamic analysis and design, ACM SIGSOFT Software Engineering Notes, 11:2, (36-48), Online publication date: 1-Apr-1986.
- Newell A and Card S (1985). The prospects for psychological science in human-computer interaction, Human-Computer Interaction, 1:3, (209-242), Online publication date: 1-Sep-1985.
- Vijay-Shankar K and Joshi A Some computational properties of Tree Adjoining Grammars Proceedings of the 23rd annual meeting on Association for Computational Linguistics, (82-93)
- Ottenstein K (1984). Intermediate program representations in compiler construction, ACM SIGPLAN Notices, 19:7, (25-27), Online publication date: 1-Jul-1984.
- Bose P and Davidson E (1984). Design of instruction set architectures for support of high-level languages, ACM SIGARCH Computer Architecture News, 12:3, (198-206), Online publication date: 1-Jun-1984.
- Orman L (1984). A multilevel design architecture for decision support systems, ACM SIGMIS Database: the DATABASE for Advances in Information Systems, 15:3, (3-10), Online publication date: 1-Apr-1984.
- Forman I An algebra for data flow anomaly detection Proceedings of the 7th international conference on Software engineering, (278-286)
- Bose P and Davidson E Design of instruction set architectures for support of high-level languages Proceedings of the 11th annual international symposium on Computer architecture, (198-206)
- Riis Nielson H (1983). Computation sequences, Acta Informatica, 19:3, (255-268), Online publication date: 1-Jul-1983.
- Matsumoto Y, Tanaka H, Hirakawa H, Miyoshi H and Yasukawa H (1983). BUP: A Bottom-Up parser embedded in Prolog, New Generation Computing, 1:2, (145-158), Online publication date: 1-Jun-1983.
- Requa J and McGraw J (1983). The Piecewise Data Flow Architecture, IEEE Transactions on Computers, 32:5, (425-438), Online publication date: 1-May-1983.
- Bundschuh F (1983). Global data flow analysis in Aldes, ACM SIGSAM Bulletin, 17:1, (6-11), Online publication date: 1-Feb-1983.
- Forman I Global data flow analysis by decomposition into primes Proceedings of the 6th international conference on Software engineering, (386-392)
- Park J (1982). A new LALR formalism, ACM SIGPLAN Notices, 17:7, (47-61), Online publication date: 1-Jul-1982.
- Ukkonen E (1982). Structure preserving elimination of null productions from context-free grammars, Theoretical Computer Science, 17:1, (43-54), Online publication date: 1-Jun-1982.
- Ancona M, Dodero G and Gianuzzi V (1982). Building collections of LR(K) items with partial expansion of lookahead strings, ACM SIGPLAN Notices, 17:5, (25-28), Online publication date: 1-May-1982.
- Oyang Y and Hsu C Extended LL(k) grammars and parsers Proceedings of the 20th annual Southeast regional conference, (240-245)
- Bose P, Rau B and Schlansker M Systematically derived instruction sets for high-level language support Proceedings of the 20th annual Southeast regional conference, (73-84)
- Jalili F and Gallier J Building friendly parsers Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, (196-206)
- Yih-Chyun Jenq (1981). Digital Convolution Algorithm for Pipelining Multiprocessor Systems, IEEE Transactions on Computers, 30:12, (966-973), Online publication date: 1-Dec-1981.
- van Hulzen J Breuer's grow factor algorithm in computer algebra Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, (100-104)
- Kuck D, Kuhn R, Padua D, Leasure B and Wolfe M Dependence graphs and compiler optimizations Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, (207-218)
- Filipski G, Moore D and Newton J Ada as a software transition tool Proceedings of the ACM-SIGPLAN symposium on Ada programming language, (176-182)
- Sherman M and Borkan M A flexible semantic analyzer for Ada Proceedings of the ACM-SIGPLAN symposium on Ada programming language, (62-71)
- Filipski G, Moore D and Newton J (1980). Ada as a software transition tool, ACM SIGPLAN Notices, 15:11, (176-182), Online publication date: 1-Nov-1980.
- Sherman M and Borkan M (1980). A flexible semantic analyzer for Ada, ACM SIGPLAN Notices, 15:11, (62-71), Online publication date: 1-Nov-1980.
- Zolnowski J and Simmons D Measuring program complexity in a COBOL environment Proceedings of the May 19-22, 1980, national computer conference, (757-766)
- Daini O and Scheuermann P A data definition and mapping language for numerical data bases Proceedings of the ACM 1980 annual conference, (418-432)
- Sherman M and Borkan M A flexible semantic analyzer for Ada Proceedings of the ACM-SIGPLAN symposium on The ADA programming language, (62-69)
- Floyd R (1979). The paradigms of programming, Communications of the ACM, 22:8, (455-460), Online publication date: 1-Aug-1979.
- Morel E and Renvoise C (1979). Global optimization by suppression of partial redundancies, Communications of the ACM, 22:2, (96-103), Online publication date: 1-Feb-1979.
- Cohen R and Harry E Automatic generation of near-optimal linear-time translators for non-circular attribute grammars Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, (121-134)
- Fong A Inductively computable constructs in very high level languages Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, (21-28)
- Samet H (1978). Proving the correctness of heuristically optimized code, Communications of the ACM, 21:7, (570-582), Online publication date: 1-Jul-1978.
- Mickunas M and Modry J (1978). Automatic error recovery for LR parsers, Communications of the ACM, 21:6, (459-465), Online publication date: 1-Jun-1978.
- Cohen J and Roth M (1978). Analyses of deterministic parsing algorithms, Communications of the ACM, 21:6, (448-458), Online publication date: 1-Jun-1978.
- Daley J A laboratory approach to teaching compiler writing Papers of the SIGCSE/CSA technical symposium on Computer science education, (19-21)
- Daley J (1978). A laboratory approach to teaching compiler writing, ACM SIGCSE Bulletin, 10:1, (19-21), Online publication date: 1-Feb-1978.
- Kaplan M and Ullman J A general scheme for the automatic inference of variable types Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, (60-75)
- Solomon M Type definitions with parameters Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, (31-38)
- Sudborough I Separating tape bounded auxiliary pushdown automata classes Proceedings of the ninth annual ACM symposium on Theory of computing, (208-217)
- Tai K The recovery of parsing configurations for LR(1) parsers Proceedings of the 15th annual Southeast regional conference, (154-160)
- Jeffords R and Benson D A vector encoding technique applicable to tabular parsing methods Proceedings of the 15th annual Southeast regional conference, (140-153)
- Hunt H, Ullman J and Szymanski T (1977). Operations on sparse relations, Communications of the ACM, 20:3, (171-176), Online publication date: 1-Mar-1977.
- Reif J and Lewis H Symbolic evaluation and the global value graph Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, (104-118)
- Kennedy K and Zucconi L Applications of a graph grammar for program control flow analysis Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, (72-85)
- Fong A Generalized common subexpressions in very high level languages Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, (48-57)
- Wegner P (1976). Programming Languages The First 25 Years, IEEE Transactions on Computers, 25:12, (1207-1225), Online publication date: 1-Dec-1976.
- Standish T, Kibler D and Neighbors J Improving and refining programs by program manipulation Proceedings of the 1976 annual conference, (509-516)
- Wegner P Research paradigms in computer science Proceedings of the 2nd international conference on Software engineering, (322-330)
- Jazayeri M Formal specification and automatic programming Proceedings of the 2nd international conference on Software engineering, (293-296)
- Bennett-Novak G (1976). Optimized machine-independent extended FORTRAN for minicomputer programming, ACM SIGPLAN Notices, 11:4, (40-44), Online publication date: 1-Apr-1976.
- Bennett-Novak G Optimized machine-independent extended FORTRAN for minicomputer programming Proceedings of the ACM SIGMINI/SIGPLAN interface meeting on Programming systems in the small processor environment, (40-44)
- Allen F and Cocke J (1976). A program data flow analysis procedure, Communications of the ACM, 19:3, (137), Online publication date: 1-Mar-1976.
- Thompson R (1976). Language Correction Using Probabilistic Grammars, IEEE Transactions on Computers, 25:3, (275-286), Online publication date: 1-Mar-1976.
- Shapiro H and Mickunas M (1976). A new approach to teaching a first course in compiler construction, ACM SIGCUE Outlook, 10:SI, (158-166), Online publication date: 1-Feb-1976.
- Shapiro H and Mickunas M (1976). A new approach to teaching a first course in compiler construction, ACM SIGCSE Bulletin, 8:1, (158-166), Online publication date: 1-Feb-1976.
- Shapiro H and Mickunas M A new approach to teaching a first course in compiler construction Proceedings of the ACM SIGCSE-SIGCUE technical symposium on Computer science and education, (158-166)
- LaLonde W On directly constructing LR(k) parsers without chain reductions Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, (127-133)
- Baker B An algorithm for structuring programs (Extended Abstract) Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, (113-126)
- Fong A and Ullman J Induction variables in very high level languages Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, (104-112)
- Kennedy K and Warren S Automatic generation of efficient evaluators for attribute grammars Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, (32-49)
- Aho A, Johnson S and Ullman J Code generation for expressions with common subexpressions (Extended Abstract) Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, (19-31)
- Hunt H A complexity theory of grammar problems Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, (12-18)
- Hoffmann C and Landweber L (1976). A Completeness Theorem for Straight-Line Programs with Structured Variables, Journal of the ACM, 23:1, (203-220), Online publication date: 1-Jan-1976.
- Kam J and Ullman J (1976). Global Data Flow Analysis and Iterative Algorithms, Journal of the ACM, 23:1, (158-171), Online publication date: 1-Jan-1976.
- Mickunas M (1976). On the Complete Covering Problem for LR(k)Grammars, Journal of the ACM, 23:1, (17-30), Online publication date: 1-Jan-1976.
- Thomason M (1975). Stochastic Syntax-Directed Translation Schemata for Correction of Errors in Context-Free Languages, IEEE Transactions on Computers, 24:12, (1211-1216), Online publication date: 1-Dec-1975.
- Aho A and Ullman J Node listings for reducible flow graphs Proceedings of the seventh annual ACM symposium on Theory of computing, (177-185)
- Wedel D (1975). Fortran for the Texas Instruments ASC system, ACM SIGPLAN Notices, 10:3, (119-132), Online publication date: 1-Mar-1975.
- Wedel D Fortran for the Texas Instruments ASC system Proceedings of the conference on Programming languages and compilers for parallel and vector machines, (119-132)
- Graham S and Wegman M A fast and usually linear algorithm for global flow analysis Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, (22-34)
- Fong A, Kam J and Ullman J Application of lattice algebra to loop optimization Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, (1-9)
- Thomason M and Gonzalez R (1975). Syntactic Recognition of Imperfectly Specified Patterns, IEEE Transactions on Computers, 24:1, (93-95), Online publication date: 1-Jan-1975.
- Hecht M and Ullman J Analysis of a simple algorithm for global data flow problems Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, (207-217)
- Aho A, Johnson S and Ullman J Deterministic parsing of ambiguous grammars Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, (1-21)
- Aho A, Hopcroft J and Ullman J On finding lowest common ancestors in trees Proceedings of the fifth annual ACM symposium on Theory of computing, (253-265)
- Tarjan R Testing flow graph reducibility Proceedings of the fifth annual ACM symposium on Theory of computing, (96-107)
- Ullman J Applications of language theory to compiler design Proceedings of the May 16-18, 1972, spring joint computer conference, (235-242)
- Hecht M and Ullman J Flow graph reducibility Proceedings of the fourth annual ACM symposium on Theory of computing, (238-250)
Index Terms
- The theory of parsing, translation, and compiling
Recommendations
Parsing and compiling using Prolog
This paper presents the material needed for exposing the reader to the advantages of using Prolog as a language for describing succinctly most of the algorithms needed in prototyping and implementing compilers or producing tools that facilitate this ...
Compiling a functional language
LFP '84: Proceedings of the 1984 ACM Symposium on LISP and functional programmingThis paper summarizes my experience in implementing a compiler for a functional language. The language is ML(1) [Milner 84] and the compiler was first implemented in 1980 as a personal project when I was a postgraduate student at the University of ...
On compiling embedded languages in LISP
LFP '80: Proceedings of the 1980 ACM conference on LISP and functional programmingIn INTERLISP we find a number of embedded languages such as the iterative statement and the pattern match facility in the CLISP package, the editor and makefile languages and so forth. We will in this paper concentrate on the problem of extending the ...