基于图算法的二元组合文法分析

为解决二元组合文法(BCG)的算符优先计算分析中不能共享分析树空间的问题，并降低分析算法的空间花费以提高分析效率，提出了一种基于图算法的BCG分析方法。该方法以表格方式存储分析过程中产生的所有边，分析完成后根据边的跨度构造分析树，从而使边不再局限于某一特定分析树中，再根据BCG文法的特性实现分析过程中的剪枝。实验结果表明，该方法在花费的时间、产生边的数量和最终结果树的数量上都明显低于传统的图算法和基于算符优先的算法。

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.