Direct parsing

摘要

This paper describes direct parsing algorithms for a context-free language which use neither “list” as the Earley's algorithm nor “table” as the CKY's algorithm. The idea behind the algorithms lies in the fact that parsing is nothing but constructing a parse tree for an input. The time complexity of the algorithms is O(cn) and the space complexity of them is O(n) for an input with length n, where c is a constant. However, the computer simulations show that the algorithms are faster than the Earley's algorithm for chromosome patterns. Based on the algorithms a good context-sensitive parser without recopies of terms is able to be constructed.