Grammatical parsing algorithm based on expected categories
基于期待类型的Chart句法分析算法

Chart algorithm is one of the most popular algorithms in grammatical parsing. Its computational efficiency, however, still needs to be improved. By analyzing two common used Chart algorithms, a new parsing algorithm was proposed based on the bottom-to-top Chart algorithm, combining with the predicating ability of the top-to-bottom Chart algorithm. The proposed algorithm executed exactly from left to right and bottom to top. At each word position in parsing, an expecting table was formed according to the active roles of existing active arcs and the grammatical rules, and was used to restrict the creating of arcs in the rest process of parsing. Experimental results show that the parsing speed improves about 24% compared with the standard Chart algorithm, meanwhile the number of the failed sentences reduces more than a half.