Electronic Thesis and Dissertation Repository


Master of Science


Computer Science


James H. Andrews


Grammar-based testing has interested the academic community for decades, but little work has been done with regards to testing with invalid input strings. For our research, we generated LR parse tables from grammars. We then generated valid and invalid strings based on coverage of these tables. We evaluated the effectiveness of these strings in terms of code coverage and fault detection by inputting them to subject programs which accept input based on the grammars. For a baseline, we then compared the effectiveness of these strings to a more general approach where the tokens making up each string are chosen randomly. Analysis revealed that the LR strategy achieved higher code coverage than the randomly generated strings in most cases. Even when the LR strategy garnered less code coverage, it still covered substantial code not touched by the benchmark. The LR strategy also showed effective fault finding ability for some programs.