上下文无关文法的句子生成、枚举与分析技术

1. 成果简介

课题组设计并实现了上下文无关文法的通用句子生成工具Grammar。该工具实现以下算法和功能：上下文无关文法的操作（文法编辑，非终结符可用性和可达性检查），基于覆盖规则的句子生成（Purdom算法，Purdom的扩展算法，CDRC-P算法，CDRC-P的扩展算法），句子枚举（董韫美的线性算法，基于句子枚举的句子生成方法），句子分析（Earley算法，覆盖性分析），图形用户界面（GUI）（句子生成面板，句子枚举面板，句子分析面板）。其中关于句子生成和枚举的算法中，除了经典的Purdom算法外，都是课题组的工作，其中董韫美提出的句子枚举的线性算法解决了国际上关于是否存在线性算法的未决问题。

课题组提出了标准确定性正则表达式的第一个文法，证明所属的文法类为上下文无关文法，给出了判定有效文法产生式的规则，可以有效减少产生式的数量，提出了文法的随机生成算法。

课题组提出了扩展确定性正则表达式的第一个文法，证明所属的文法类为上下文无关文法，给出了判定有效文法产生式的规则，可以有效减少产生式的数量，提出了文法的随机生成算法。

课题组提出了确定性正则表达式的一个重要子类，即Deterministic Chain Regular Expressions（dCHAREs）的第一个文法，并实现了dCHAREs工具链。该工具支持dCHAREs的文法与简洁文法的构建、辅助书写与随机生成。

2. 技术先进性

董韫美院士提出的上下文无关文法的句子枚举问题的线性算法，解决了国际上该问题是否存在线性算法的未决问题。

在国际上第一个解决了确定性正则表达式、扩展确定性正则表达式与dCHAREs的语法表示问题。从而解决了使用这几类确定性正则表达式的主要困难之一，即这几类确定性正则表达式只有语义定义而没有语法定义。

3. 技术成熟度

该技术已形成产品，可应用并推广于可应用领域。Grammar是目前国际上上下文无关文法的句子生成功能最强的工具之一，已获数千次下载，并应用于多个研究项目。

4. 可应用领域

该技术可应用于语法分析器与编译器测试、自然语言处理、文法的验证与测试生成与生物信息学等。

5. 联系人

陈海明，chm@ios.ac.cn，13801061026