Testing Grammars for Top-Down Parsers

Abstract

During the past decades, the complexity of compilers has grown much and so has the importance of testing them. Compiler is essentially a software tool, and hence its testing should fulfill all the software testing criteria. Testing is the process of finding errors in an application by executing it. It is one of the essential and most time consuming phases of software development. Hence a lot of effort is directed to fully automate this process, making it more reliable, repeatable, less time consuming, less boring, and less expensive. Test cases for compiler should be generated so that they cover all possible valid and invalid input conditions. One of the major problems in generating test cases is the completeness of coverage, and the potentially unfeasible size of the generated test data. The test data for compilers should ideally cover all the syntax and semantic rules of the language in all possible combinations and in all possible contexts. When generating test cases for a compiler, the grammar act as the foundation as it defines the language for which the compiler is being built. In this research we addressed the issue of automatic generation of test data for parsers by implementing Purdom's algorithm in Java and C++ and generating test data for MAGS compiler.