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

Chart algorithm-based binary combinatorial grammar parsing

作　　者：张玉艳[1] 杨潇[2] 黄国栋[3] 侯金奎[2] 

机构地区：[1]潍坊学院计算机与通信工程学院,山东潍坊261061 [2]山东大学计算机科学与技术学院,济南250101 [3]中国人民解放军防化指挥工程学院计算机教研室,北京102205

出　　处：《计算机应用》2008年第7期1668-1671,共4页journal of Computer Applications

基　　金：山东省自然科学基金资助项目(Y2005G16)

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

关 键 词：图算法 二元组合文法 句法分析 自然语言处理 

分 类 号：TP182[自动化与计算机技术—控制理论与控制工程]