An Improved Context-Free Recognizer

ABSTRACT

A new algorithm for recognizing and parsing arbitrary context-free languages is presented, and several new results are given on the computational complexity of these problems. The new algorithm is of both practical and theoretical interest. It is conceptually simple and allows a variety of efficient implementations, which are worked out in detail. Two versions are given which run in faster than cubic time. Surprisingly close connections between the Cocke-Kasami-Younger and Earley algorithms are established which reveal that the two algorithms are “almost” identical.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
• 3: ARLAZAROV, V.L., DINIC, E.A., KRONROD M.A., AND FARADZEV, I.A. On economical construction of the transitive closure of a directed graph. Dokl. Akad. Nauk SSSR 194 (1970), 487-488 (in Russian). {English translation Soviet Math. Dokl. 11, 5 (1970), 1209-1210.}
• 4: BAYER, P.J. Personal communication, 1977.
• 5: BOUCKAERT, M., PIROTrE, A., AHD SNELLING, M. Efficient parsing algorithms for general context free grammars. Inf. Sci. 8, 1 (Jan. 1975), 1-26.
• 6: COCKE, J., AND SCHWARTZ, J.I. Programming Languages and Their Compilers. Courant Institute of Mathematical Sciences, New York University, New York, 1970.
• 7: Jay Clark Earley, An efficient context-free parsing algorithm, 1968
• 8: Jay Earley, An efficient context-free parsing algorithm, Communications of the ACM, v.13 n.2, p.94-102, Feb 1970 [doi>10.1145/362007.362035]
• 9: FLOYD, R.W. A machine-oriented recognition algorithm for context-free languages. Unpublished manuscript, 1969.
• 10: GALIL, Z. Two fast simulations which imply some fast string matching and palindrome-recognition algorithms. Inf. Process. Lett. 4, 4 (Jan. 1976), 85-87.
• 11: GELLER, M.M., A~O HARRISON, M.A. Characteristic parsing: A framework for producing compact deterministic parsers, I. J. Comput. Syst. Sci. 14, 3 (June 1977), 265-317.
• 12: GRAHAM, S.L., AND HARRISON, M.A. Parsing of general context-free languages. In Advances in Computers, I7ol. 14. Academic Press, New York, 1976, pp. 77-185.
• 13: Susan L. Graham , Michael A. Harrison , Walter L. Ruzzo, On line context free language recognition in less than cubic time(Extended Abstract), Proceedings of the eighth annual ACM symposium on Theory of computing, p.112-120, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803638]
• 14: T. V. Griffiths , S. R. Petrick, On the relative efficiencies of context-free grammar, Communications of the ACM, v.8 n.5, p.289-300, May 1965 [doi>10.1145/364914.364943]
• 15: M.A. A. Harrison , M. A. Harrison, Introduction to Formal Language Theory, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1978
• 16: HAYS, D.G. Automatic language-data processing. In Computer Applications in the Behavioral Sciences, H. Borko, Ed., Prentice-Hall, Englewood Cliffs, N.J., 1962, pp. 394-423.
• 17: HoPcRO~r, J.E., PAUL, W., ANO VALIANT, L. On time versus space and related problems. Conf. Record IEEE 16th Ann. Syrup. on Foundations of Computer Science, Berkeley, Calif., 1975, pp. 57-64.
• 18: Edgar T. Irons, Experience with an extensible language, Communications of the ACM, v.13 n.1, p.31-40, Jan. 1970 [doi>10.1145/361953.361966]
• 19: C B Jones, Formal development of correct algorithms: An example based on earley's recogniser, ACM SIGACT News
• 20: KASAMI, T. An efficient recognition and syntax analysis algorithm for context free languages. Sci. Rep. AF CRL-65-758, Air Force Cambridge Research Laboratory, Bedford, Mass., 1965.
• 21: KNUTH, D.E. On the translation of languages from left to right. Inf. Control 8 (1965), 607-639.
• 22: Susumu Kuno, The predictive analyzer and a path elimination technique, Communications of the ACM, v.8 n.7, p.453-462, July 1965 [doi>10.1145/364995.365689]
• 23: LIPTON, R.J., A~O SNYDER, L. On the optimal parsing of speech. Res. Rep. No. 37, Dep. Computer Science, Yale Univ., New Haven, Conn., 1974.
• 24: Gordon Lyon, Syntax-directed least-errors analysis for context-free languages: a practical approach, Communications of the ACM, v.17 n.1, p.3-14, Jan. 1974 [doi>10.1145/360767.360771]
• 25: MANACHER, G.K. An improved version of the Cocke-Younger-Kasami algorithm. Comput. Lang. 3 (1978), 127-133.
• 26: MARQUE-PuCm~N, G. Analyses des langages alg~briques. Th/~se de 3~ Cycle, Institute de Programmation, IP75-23, Universit~ Paris VI, 1975 (in French).
• 27: PRATT, V.R., LINGOL--A progress report. Advance Papers 4th Int. Joint Conf. on Artificial Intelligence, Tbilisi, Georgia, USSR, 1975, 422-428.
• 28: PRATT, V.R. Personal communication, 1976.
• 29: PRATT, V.R. Personal communication, 1977.
• 30: PRATT, V.R., AND STOCKMEYER, L.J. A characterization of the power of vector machines. J. Cornput. Syst. Sci. 12 (1976), 198-221.
• 31: Walter Lawrence Ruzzo, General context-free language recognition., 1978
• 32: Walter L. Ruzzo, On the Complexity of General Context-Free Language Parsing and Recognition (Extended Abstract), Proceedings of the 6th Colloquium, on Automata, Languages and Programming, p.489-497, July 16-20, 1979
• 33: Walter L. Ruzzo, Tree-size bounded alternation(Extended Abstract), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.352-359, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804428]
• 34: Rvzzo, W.L. An improved characterization of the power of vector machines. In preparation.
• 35: TOWNLEY, J.G. The measurement of complex algorithms. Ph.D. Dissertation, Harvard Univ., Cambridge, Mass., 1973 (TR14-73).
• 36: VALIANT, L. General context free recognition in less than cubic time. J. Comput. Syst. Sci. 10 (1975), 308-315.
• 37: WEOBR~.i?, B. Studies in extensible programming languages. Ph.D. Dissertation, Harvard Univ., Cambridge, Mass., 1972.
• 38: WEICK~.R, R. Context free language recognition by a RAM with uniform cost criterion in time n21og n. In Symposium on New Directions and Recent Results in Algorithms and Complexity, J.F. Traub, Ed., Academic Press, New York, 1976.
• 39: YOVSCER, D.H. Recognition of context-free languages in time n3. Inf. Control 10, 2 (Feb. 1967), 189-208.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

General Terms:
Design, Languages, Performance, Theory