Abstract
A fast algorithm is given to produce a small set of short sentences from a context free grammar such that each production of the grammar is used at least once. The sentences are useful for testing parsing programs and for debugging grammars (finding errors in a grammar which causes it to specify some language other than the one intended). Some experimental results from using the sentences to test some automatically generated simpleLR(1) parsers are also given.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Richard L. Sander,A General Test Data Generator for Cobol, Spring Joint Computer Conference 1962.
K. V. Hanford,Automatic Generation of Test Cases, I.B.M. System Journal Vol. 9 No. 4 (1970), 242–257.
F. L. DeRemer,Simple LR(k) Grammars, CACM 14 (1971), 453.
John Reynolds, See J. C. Earley,An Efficient Context-Free Parsing Algorithm, Thesis (1968), 128, 129, Computer Science Department, Carnegie-Mellon University.
F. L. DeRemer,Practical Translators for LR(k), Languages, Project MAC TY-65 MIT.
A. J. Korenjak,Deterministic Language Processing, Thesis, Princeton, 1967.
N. Wirth and H. Weber,EULER: A generalization of ALGOL and its Formal Definition, CACM, Vol. 9 No. 1 (1966), 13–25 and No. 2, 89–99.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Purdom, P. A sentence generator for testing parsers. BIT 12, 366–375 (1972). https://doi.org/10.1007/BF01932308
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01932308