上下文无关文法测试充分性  

On adequate testing of context-free grammars

作　　者：李虎[1] 金茂忠[1] 高仲仪[1] 刘超[1] 

机构地区：[1]北京航空航天大学计算机学院,北京100083

出　　处：《北京航空航天大学学报》2003年第10期869-872,共4页Journal of Beijing University of Aeronautics and Astronautics

摘　　要：讨论了文法测试的基本概念 ,分析了文法测试的特点、应用场景及其与一般软件测试的异同 .形式化地定义了上下文无关文法的测试充分性准则 ,提出了一个上下文无关文法的测试充分性准则族 .分析了该准则族中各准则之间的包含关系 ,以及这种包含关系与揭示文法所特有的 2类缺陷的能力之间的关系 .计算和比较了准则族中各准则的测试集规模复杂性 .为了评价文法的测试开销 ,定义了一个上下文无关文法的测试复杂性度量 ,该度量能够从测试充分性的角度反映测试一个文法的难易程度和测试开销的大小 .Grammar testing was discussed, including related concepts, its characteristics, application scenarios, and a comparison with traditional software testing. Test adequacy criterion of context free grammar was formally defined and a family of grammar testing criteria was proposed. A formal analysis of the subsume relation between test adequacy criteria in the family was presented, and how the subsume relation between adequacy criteria guarantees a better fault detecting in the context of two classes of faults specific to grammar was also proved. Size complexity of the test adequacy criteria in the family was computed and compared. A grammar testing complexity metric was also developed, which can reflect the difficulty and effort to testing a grammar from the view of test adequacy.

关 键 词：上下文无关文法 文法测试 测试充分性准则 测试复杂性 

分 类 号：TP301.2[自动化与计算机技术—计算机系统结构] TP311.5[自动化与计算机技术—计算机科学与技术]