On line context free language recognition in less than cubic time(Extended 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.