Comparison of Context-free Grammars Based on Parsing Generated Test Data
There exist a number of software engineering scenarios that essentially involve equivalence or correspondence assertions for some of the context-free grammars in the scenarios. For instance, when applying grammar transformations during parser development---be it for the sake of disambiguation or grammar-class compliance---one would like to preserve the generated language. Even though equivalence is generally undecidable for context-free grammars, we have developed an automated approach that is practically useful in revealing evidence of nonequivalence of grammars and discovering correspondence mappings for grammar nonterminals. The approach is based on systematic test data generation and parsing. We discuss two studies that show how the approach is used in comparing grammars of open source Java parsers as well as grammars from the course work for a compiler construction class.
|Keywords||grammar-based testing, test data generation, coverage criteria, grammar equivalence, parsing, compiler construction, course work|
|ACM||Testing and Debugging (acm D.2.5), Processors (acm D.3.4), Grammars and Other Rewriting Systems (acm F.4.2)|
|MSC||Grammars and rewriting systems (msc 68Q42)|
|THEME||Software (theme 1)|
|Publisher||Centro de Ciências e Tecnologias de Computação|
|Editor||U. Aßmann , J. Saraiva , A.M. Sloane|
|Project||GrammarLab: Foundations of a Grammar Laboratory , GrammarLab: Foundations of a Grammar Laboratory|
|Conference||International Conference on Software Language Engineering|
|Grant||This work was funded by the The Netherlands Organisation for Scientific Research (NWO); grant id nwo/612.001.007 - GrammarLab: Foundations of a Grammar Laboratory|
Fischer, B, Lämmel, R, & Zaytsev, V. (2011). Comparison of Context-free Grammars Based on Parsing Generated Test Data. In U Aßmann, J Saraiva, & A.M Sloane (Eds.), Pre-proceedings of the Fourth International Conference on Software Language Engineering (pp. 323–342). Centro de Ciências e Tecnologias de Computação.