On line context free language recognition in less than cubic time(Extended Abstract)

ABSTRACT

A new on-line context free language recognition algorithm is presented which is derived from Earley's algorithm and has several advantages over the original. First, the new algorithm not only is conceptually simpler than Earley's, but also allows significant speed improvements. Second, our algorithm serves to explain the connections between Earley's algorithm and the Cocke-Kasami-Younger algorithm. Third, our algorithm allows an implementation which uses only 0(n2/log n) operations on bit vectors of length n, or 0(n3/log n) operations on a RAM. This makes it the fastest known on-line context free language recognition algorithm.

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," Doklady Akademii Nauk SSSR, Vol. 194, pp. 487-488, 1970.
• 4: Bouckaert, M., Pirotte, A. and Snelling, M., "Efficient parsing algorithms for general context free grammars," Information Sciences, Vol. 8, pp. 1-26, 1975.
• 5: 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]
• 6: Graham, S.L. and Harrison, M.A., "Parsing of general context-free languages," in Advances in Computers, Vol. 14 (M. Yovits and M. Rubinoff, eds.), pp. 77-185, Academic Press, New York, 1976.
• 7: C B Jones, Formal development of correct algorithms: An example based on earley's recogniser, ACM SIGACT News
• 8: Kasami, T., "An efficient recognition and syntax analysis algorithm for context free languages," Science Report AF CRL-65-758, Air Force Cambridge Research Laboratory, Bedford, Mass., 1965.
• 9: Knuth, D.E., "On the translation of languages from left to right," Information and Control, Vol. 8, pp. 607-639, 1965.
• 10: 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]
• 11: Valiant, L., "General context free recognition in less than cubic time," Journal of Computer and System Science, Vol. 10, pp. 308-315, 1975.
• 12: Stephen Warshall, A Theorem on Boolean Matrices, Journal of the ACM (JACM), v.9 n.1, p.11-12, Jan. 1962 [doi>10.1145/321105.321107]
• 13: Younger, D.H., "Recognition and parsing of context-free languages in time n3," Information and Control, Vol. 10, pp. 189-208, 1967.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages
          Subjects: Classes defined by grammars or automata (e.g., context-free languages, regular sets, recursive sets)

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Parsing

General Terms:
Algorithms, Theory