A parser-generating system for constructing compressed compilers

ABSTRACT

This paper describes a parser-generating system (PGS) currently in use on the CDC-6500 computer at Purdue University. The PGS is a Fortran-coded program that accepts a translation grammar as input and constructs from it a compact, machine-coded compiler. In the input translation grammar, each BNF syntactic rule corresponds to a (possibly empty) “code generator” realizable as an assembly language, Fortran or Algol, subroutine that is called whenever that syntactic rule is applied in the parse of a program. Typical one-pass compilers constructed by the PGS translate source programs at speeds approaching 14,000 cards per minute. For an XPL compiler, the parser program and its tables currently occupy 288 words of 60-bit core memory of which 140 words are parsing table entries and 82 words are links to code generators.

REFERENCES

• 1: Robert W. Floyd, A Descriptive Language for Symbol Manipulation, Journal of the ACM (JACM), v.8 n.4, p.579-584, Oct. 1961 [doi>10.1145/321088.321096]
• 2: J. J. Horning , W. R. Lalonde, Empirical comparison of LR(k) and precedence parsers, ACM SIGPLAN Notices, v.5 n.11, November 1970 [doi>10.1145/987461.987463]
• 3: J. D. Ichbiah , S. P. Morse, A technique for generating almost optimal Floyd-Evans productions for precedence grammars, Communications of the ACM, v.13 n.8, p.501-508, Aug. 1970 [doi>10.1145/362705.362712]
• 4: Ichbiah, J.D. Computer printout of an ALGOL 60 parser run through the Ichbiah-Morse system, 1971.
• 5: McKeeman, W.M., Homing, J.J. and Wortman, D.B. A Copiler Generator. Prentice-Hall, Englewood Cliffs, N.J., 1970.
• 6: Mickunas, M.D. User's manual for the PUCSD translatorwriting system. Comput. Sci. Dep., Purdue U., Lafayette, Ind., 1971.
• 7: Schneider, V. Pushdown-store processors of context-free languages. Ph.D. diss., Northwestern U., Evanston, Ill., 1966.
• 8: Schneider, V. A system for designing fast programming language translators. Proc. AFIPS 1969 SJCC, AFIPS Press, Montvale, N.J.; pp. 777-792.
• 9: Schneider, V. Some syntactic methods for specifying extendible programming languages. Proc. AFIPS 1969 SJCC, AFIPS Press, Montvale, N.J.; pp. 145-156.
• 10: Schneider, V. A translation grammar for ALGOL 68. Proc. AFIPS 1970 SJCC, AFIPS Press, Montvale, N.J., pp. 493-505.
• 11: Niklaus Wirth , Helmut Weber, EULER: a generalization of ALGOL, and its formal definition: Part II, Communications of the ACM, v.9 n.2, p.89-99, Feb. 1966 [doi>10.1145/365170.365202]
• 12: Mickunas, M.D. and Schneider, V. B. Translation grammars for XPL and ALGOL 60. Tech. Rep., Comput. Sci. Dep., Purdue U., Lafayette, Ind., 1972.

INDEX TERMS

Keywords:
compression algorithm, normal-form grammars, parser generators, pushdown automata, syntactic analysis, translation grammars, translator optimization, translator writing systems