An analysis of rule coverage as a criterion in generating minimal test suites for grammar-based software
Authors:
Open Access
- 7 November 2005
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 104-113
Abstract
The term grammar-based software describes software whose\ud input can be specified by a context-free grammar. This\ud grammar may occur explicitly in the software, in the form\ud of an input specification to a parser generator, or implicitly,\ud in the form of a hand-written parser, or other inputverification\ud routines. Grammar-based software includes not\ud only programming language compilers, but also tools for\ud program analysis, reverse engineering, software metrics and\ud documentation generation. Such tools often play a crucial\ud role in automated software development, and ensuring their\ud completeness and correctness is a vital prerequisite for their\ud use.\ud In this paper we propose a strategy for the construction\ud of test suites for grammar based software, and illustrate this\ud strategy using the ISO C++ grammar. We use the concept of\ud rule coverage as a pivot for the reduction of implementationbased\ud and specification-based test suites, and demonstrate\ud a significant decrease in the size of these suites. To demonstrate\ud the validity of the approach, we use the reduced test\ud suite to analyze three grammar-based tools for C++. We\ud compare the effectiveness of the reduced test suite with the\ud original suite in terms of code coverage and fault detectionKeywords
This publication has 10 references indexed in Scilit:
- Toward an engineering discipline for grammarwareACM Transactions on Software Engineering and Methodology, 2005
- Test-suite reduction and prioritization for modified condition/decision coverageIEEE Transactions on Software Engineering, 2003
- Decorating tokens to facilitate recognition of ambiguous language constructsSoftware: Practice and Experience, 2002
- Grammar Testing2001
- Effect of test set minimization on fault detection effectivenessSoftware: Practice and Experience, 1998
- An experimental determination of sufficient mutant operatorsACM Transactions on Software Engineering and Methodology, 1996
- A methodology for controlling the size of a test suiteACM Transactions on Software Engineering and Methodology, 1993
- An Automatic Generator for Compiler TestingIEEE Transactions on Software Engineering, 1982
- Compiler testing using a sentence generatorSoftware: Practice and Experience, 1980
- A sentence generator for testing parsersBIT Numerical Mathematics, 1972