Stack automata and compiling

ABSTRACT

Compilation consists of two parts, recognition and translation. A mathematical model is presented which embodies salient features of many modern compiling techniques. The model, called the stack automaton, has the desirable feature of being deterministic in nature. This deterministic device is generalized to a nondeterministic device (nondeterministic stack automaton) and particular instances of this more general device are noted. Sets accepted by nondeterministic stack automata are recursive. Each set accepted by a deterministic linear bounded automaton is accepted by some nonerasing stack automaton. Each context-sensitive language is accepted by some (deterministic) stack automaton.

REFERENCES

• 1: BUcHI, J.R. Regular canonical systems. Arch. Math. Logik Grundlagenforschung 6 (1964), 91-111.
• 2: CHOMSKY, N r. Context-free grammars and pushdown storage. RLE Quart. Prog. Rep. No. 65, Research Lab. of Electronics, M.I.T., Cambridge, Mass., 1962.
• 3: DArts, M. Computability and Unsolvability. McGraw-Hill Book Co., New York, 1958.
• 4: DE BAKEa, J.W. Formal definition of algorithmic languages, with an application to the definition of ALGOL 60. Stichting, Mathematisch Centrum, MR 74, Amsterdam, May 1965.
• 5: Seymour Ginsburg , Joseph Ullian, Ambiguity in context free languages, Journal of the ACM (JACM), v.13 n.1, p.62-89, Jan. 1966 [doi>10.1145/321312.321318]
• 6: ---- XND GREmCFL S. Deterministic context free languages. Document No. TM-738/ 014/00, System Development Corp., Santa Monica, Calif., 1965. (Submitted to a technical journal).
• 7: Seymour Ginsburg , Sheila A. Greibach , Michael A. Harrison, One-way stack automata, Journal of the ACM (JACM), v.14 n.2, p.389-418, April 1967 [doi>10.1145/321386.321403]
• 8: GRAY, J. N., HRRmON, M. A., AND HARRAO. tI. Two-way pushdown automata. U. of California (Berkeley) document. (Submitted to a technical journal).
• 9: GEInACH, S. A. A note on pushdown store automata and regular systems. SDC Document No. TM-738/016/00, Aug. 1965. (Submitted to a technical journal).
• 10: HARAMNIS, J., LEWIS, P. M., AND STERNS, R .E . Classification of computations by time and memory requirements. Proc. IFIP Congr. 65 (1965), 31-35.
• 11: KNOTH, D. E. A history of writing compilers, Computers and Automation (Dec. 1962), 8-18
• 12: On the translation of languages from left to right. Inforra.. Contr.8 (1965),607-639.
• 13: Kurtona, S. Y. Classes of languages and linear bounded automata. Inform. Contr. 7 (1964), 202-223.
• 14: LArDWEBS, P. S. Decision problems of phrase structure grammars. IEEE Trans. EC-13 (1964), 354-362.
• 15: RABIN, I. O., AND SCOTT, D. Finite automata and their decision problems. IBM J. Res. Develop. 8 (1959), 114-125.
• 16: K. Samelson , F. L. Bauer, Sequential formula translation, Communications of the ACM, v.3 n.2, p.76-83, Feb. 1960 [doi>10.1145/366959.366968]
• 17: SHEPHERDSON, J. C. The reduction of two-way automata to one-way automata. IBM J. Res. Develop. 8 (1959), 198-200.
• 18: WALKER, R. J. An enumerative technique for a class of combinatorial problems. In Combinatorial Analysis, Proc. Symposia in Appl. Math., Vol. 10, Amer. Math. Soc., Providence, R. I., 1960, pp. 91-94.
• 19: YERSHOV, A. P, Programming Programme for the BESM Computer. Pergamon Press, New York, 1959.

INDEX TERMS

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

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Lists, stacks, and queues

General Terms:
Languages, Performance, Theory, Verification