An analysis of rule coverage as a criterion in generating minimal test suites for grammar-based software

Abstract

The term grammar-based software describes software whose input can be specified by a context-free grammar. This grammar may occur explicitly in the software, in the form of an input specification to a parser generator, or implicitly, in the form of a hand-written parser, or other input-verification routines. Grammar-based software includes not only programming language compilers, but also tools for program analysis, reverse engineering, software metrics and documentation generation. Such tools often play a crucial role in automated software development, and ensuring their completeness and correctness is a vital prerequisite for their us.In this paper we propose a strategy for the construction of test suites for grammar based software, and illustrate this strategy using the ISO CPP grammar. We use the concept of rule coverage as a pivot for the reduction of implementation-based and specification-based test suites, and demonstrate a significant decrease in the size of these suites. To demonstrate the validity of the approach, we use the reduced test suite to analyze three grammar-based tools for CPP++. We compare the effectiveness of the reduced test suite with the original suite in terms of code coverage and fault detection.