A technique for generating almost optimal Floyd-Evans productions for precedence grammars

ABSTRACT

A technique is developed for generating almost optimal Floyd-Evans productions given a precedence grammar. A graph formulation is used for the problem of merging productions. The productions generated correspond to the minimum cost inverse-arborescence of that graph. The validity of the technique is demonstrated for weak precedence grammars defined here, but the productions mechanically generated for any precedence grammar can often be modified in such a way that correct, almost optimal parsers are obtained.

REFERENCES

• 1: BERGE, C., AND GHOUILA-HOIIRI, A. Programmes, jeux et roseaux de transport. Dunod, Paris, 1962, pp. 121-142.
• 2: CHEATHAM, W. E., JR. The theory and construction of compilers. Notes for AM219 R, Harvard U., Cambridge, Mass., spring 1967.
• 3: --. The introduction of definitional facilities into higher level programming languages. Proc. AFIPS 1966, Fall Joint Comput. Conf., Vol. 29, Spartan Books, New York, pp. 623-637.
• 4: Ole-Johan Dahl, SIMULA 67 common base language, (Norwegian Computing Center. Publication), 1968
• 5: EARLEY, J. C. Generating a recognizer for a BNF grammar. Computation Center Rep., Carnegie-Mellon U., Pittsburgh, Pa., 1965.
• 6: EVANS, A., JR. An ALGOL 60 Compiler. Ann. Rev. Automatic Programming (1964) 87-124.
• 7: Syntax analysis by a production language. Carnegie- Mellon U., Pittsburgh, Pa., 1965.
• 8: FELDMAN, J. A. A formal semantics for computer oriented languages. Carnegie-Mellon U., Pittsburg., Pa., 1965.
• 9: Jerome Feldman , David Gries, Translator writing systems, Communications of the ACM, v.11 n.2, p.77-113, Feb. 1968 [doi>10.1145/362896.362902]
• 10: 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]
• 11: KAY, A. C. FLEX-A flexible extendable language. Tech. Rep. 4-7, U. of Utah, Salt Lake City, Utah, June, 1968.
• 12: MONDSCHEIN, L. VITAL compiler-compiler reference manual. TN 1967-1, Lincoln Lab., MIT, Lexington, Mass., Jan. 1967.
• 13: Rot, B. Cheminement et connexit~ dans les graphes, application aux problmes d'ordonnancement. Metra Special Serie No. 1., 1962, pp. 67-81.
• 14: Niklaus Wirth, PL360, a Programming Language for the 360 Computers, Journal of the ACM (JACM), v.15 n.1, p.37-74, Jan. 1968 [doi>10.1145/321439.321442]
• 15: Niklaus Wirth , Helmut Weber, EULER: a generalization of ALGOL and it formal definition: Part 1, Communications of the ACM, v.9 n.1, p.13-25, Jan. 1966 [doi>10.1145/365153.365162]
• 16: A manual for BASIC. Dartmouth Coll., Hanover, N. H., Jan. 1965.
• 17: Michael J. Fischer, Some properties of precedence languages, Proceedings of the first annual ACM symposium on Theory of computing, p.181-190, May 05-07, 1969, Marina del Rey, California, United States [doi>10.1145/800169.805432]

INDEX TERMS

Keywords:
Floyd-Evans productions, graph theory, merger algorithm, minimum cost inverse-arborescence, precedence grammars, syntatic analysis, translator optimization, translator writing systems