| 摘要: |
| 提出一种上下文无关文法的句子生成算法.对于给定文法,算法生成一个满足该文法分支覆盖准则的句子集.结合长度控制、冗余消除和句子集规模控制等策略,使得生成的句子较短、无冗余、句子集规模较小.考察了算法在基于文法的软件系统的测试数据生成方面的应用情况.实验结果表明,该算法生成的测试数据具有较强的程序揭错能力,并且能够帮助测试人员提高测试速度. |
| 关键词: 上下文无关文法 句子生成 分支覆盖 长度控制 |
| DOI：10.3724/SP.J.1001.2011.03964 |
| 分类号: |
| 基金项目:国家自然科学基金(61070038, 60573013) |
|
| Algorithm for Generating Short Sentences from Grammars Based on Branch Coverage Criterion |
|
ZHENG Li-Xiao1,2, XU Zhi-Wu1,2, CHEN Hai-Ming1
|
|
1.State Key Laboratory of Computer Science, Institute of Software, The Chinese Academy of Sciences, Beijing 100190, China;2.Graduate University, The Chinese Academy of Sciences, Beijing 100049, China
|
| Abstract: |
| This paper presents a sentence generation algorithm, which takes as input a context-free grammar and produces a set of sentences that achieves branch coverage for the grammar. The algorithm incorporates length control, redundancy elimination, and sentence-set size control strategies into a sentence generation process such that the generated sentences are short and simple, and the sentence set is small with no redundancy. The paper also investigates the application of this algorithm to test data generation for grammar-based systems. Experimental results show that the generated test data not only has high fault detection ability, but can also help testers improve the testing speed. |
| Key words: context-free grammar sentence generation branch coverage length control |
