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

讨论了文法测试的基本概念,分析了文法测试的特点、应用场景及其与一般软件测试的异同.形式化地定义了上下文无关文法的测试充分性准则,提出了一个上下文无关文法的测试充分性准则族.分析了该准则族中各准则之间的包含关系,以及这种包含关系与揭示文法所特有的2类缺陷的能力之间的关系. 计算和比较了准则族中各准则的测试集规模复杂性.为了评价文法的测试开销,定义了一个上下文无关文法的测试复杂性度量,该度量能够从测试充分性的角度反映测试一个文法的难易程度和测试开销的大小. 

On adequate testing of context-free grammars

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.