Automated Compiler Test Suite Generation from Montages Specifications

The technology is aimed at generating compiler test suites from the formal specification. Specifications are done in Montages visual formalism using the Gem-Mex tool. The reamrkable potential of the proposed approach is illustrated by application to mpC Parallel Programming Language compiler testing.

The formal specification is used in three ways:

The following figure illustrates the test generation scheme:

The Iterator produces syntactically correct mpC expressions. Then produced expressions are processed by the Montages specification and expressions are divided into two groups: correct and incorrect ones (violating semantics constraints).

Each expression from the generated set is used for constructing corresponding test program by accomplishing it with initialization and output parts. Obtained test program is processed by the specification in order to produce trustable output.

The Iterator generates test programs from two files: Template and Input. Template is a set of several mpC operators. Input is a set of several mpC expressions. The generating is implemented as a substitution of operands from Input as operands of operators from Template.

Initially Input consists of basic expressions like constants and identifiers. Therefore first step of the generating produces only expressions containing one operator. At the second step expressions generated at the first step are used as an Input thus allowing to generate expressions containing two operators. The third step uses expressions generated at the second step and so on.

The natural question arises: when to stop? Intuitively it is clear that first step (expressions with only one operator) is not enough. Obvious approach in testing is to use coverage-based heuristics to measure the test suite quality. We consider the coverage of the specification in order to provide implementation-independent test suite adequacy criterion.

The test program is added to postive or negative test suite if it increases the corresponding coverage. We elaborated several coverage criteria for postive and negative test suites.


  1. Using ASM Specifications for Compiler Testing, A. Kalinov, A. Kossatehev, A. Petrenko, M. Posypkin, V. Shishkov, Proceedings of Abstract State Machines - Advances in Theory and Applications 10th International Workshop, ASM 2003
  2. Using ASM specification for automatic test suite generation for mpC parallel programming language compiler, A. Kalinov, A. Kossatchev, M. Posypkin, and V. Shishkov, Proceedings of the Fourth International Workshop on Action Semantics, {AS~2002}, (Copenhagen, Denmark, July 21, 2002)
  3. Coverage-driven Automated Compiler Test Suite Generation, A. Kalinov, A. Kossatchev, A. Petrenko, M. Posypkin, and V. Shishkov, to appear in Proccedings of LDTA'2003