Chart algorithm-based binary combinatorial grammar parsing
基于图算法的二元组合文法分析

In order to resolve the share-space problem about parsing trees in operator-precedence based parsing of Binary Combinatorial Grammar (BCG), a chart algorithm based parsing approach was proposed to reduce the spent space and to improve the parsing efficiency. All edges produced during the parsing process were stored by a tabular structure. By tracing the table, parsing trees were constructed according to the span of edges, so that these edges were no longer restricted in a particular tree. Then, the pruning in parsing process was achieved according to the characteristics of BCG grammar. The experiment showed that all of the spent time, produced edges and result trees of this approach were less than those of traditional chart algorithm and operator-precedence based algorithm.