Article

Comparison of context-free grammars based on parsing generated test data

Authors:

Vadim ZaytsevAuthors Info & Claims

SLE'11: Proceedings of the 4th international conference on Software Language Engineering

Pages 324 - 343

https://doi.org/10.1007/978-3-642-28830-2_18

Published: 03 July 2011 Publication History

Abstract

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. Our 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.

References

[1]

Aho, A. V.: Teaching the Compilers Course. SIGCSE Bull. 40, 6-8 (2008)

Digital Library

[2]

Basten, H. J. S.: Tracking Down the Origins of Ambiguity in Context-Free Grammars. In: Cavalcanti, A., Deharbe, D., Gaudel, M.-C., Woodcock, J. (eds.) ICTAC 2010. LNCS, vol. 6255, pp. 76-90. Springer, Heidelberg (2010)

Digital Library

[3]

Burgess, C. J.: The Automated Generation of Test Cases for Compilers. Software Testing, Verification and Reliability 4(2), 81-99 (1994)

[4]

Gosling, J., Joy, B., Steele, G. L., Bracha, G.: The Java Language Specification, 3rd edn. Addison-Wesley (2005), all versions of the JLS are available at http://java.sun.com/docs/books/jls

Digital Library

[5]

Griswold, W. G.: Teaching Software Engineering in a Compiler Project Course. Journal on Educational Resources in Computing 2 (December 2002)

Digital Library

[6]

Harm, J., Lämmel, R.: Two-dimensional Approximation Coverage. Informatica 24(3) (2000)

[7]

Hennessy, M., Power, J. F.: Analysing the Effectiveness of Rule-coverage as a Reduction Criterion for Test Suites of Grammar-based Software. Empirical Software Engineering 13, 343-368 (2008)

Digital Library

[8]

Hoffman, D., Wang, H.Y., Chang, M., Ly-Gagnon, D., Sobotkiewicz, L., Strooper, P.: Two Case Studies in Grammar-based Test Generation. Journal of Systems and Software 83, 2369-2378 (2010)

Digital Library

[9]

IBM Corporation: VS COBOL II Application Programming Language Reference, 4th edn. (1993), Publication number GC26-4047-07

[10]

Kastens, U.: Studie zur Erzeugung von Testprogrammen für Übersetzer. Bericht 12/80, Institut für Informatik II, University Karlsruhe (1980)

[11]

Klint, P., van der Storm, T., Vinju, J.: EASY Meta-Programming with Rascal. In: Fernandes, J. M., Lämmel, R., Visser, J., Saraiva, J. (eds.) GTTSE 2009. LNCS, vol. 6491, pp. 222-289. Springer, Heidelberg (2011)

Digital Library

[12]

Kossatchev, A. S., Posypkin, M. A.: Survey of Compiler Testing Methods. Programming and Computing Software 31, 10-19 (2005)

Digital Library

[13]

Lämmel, R., Verhoef, C.: VS COBOL II grammar Version 1.0.4 (1999), http://www.cs.vu.nl/grammarware/browsable/vs-cobol-ii/

[14]

Lämmel, R.: Grammar Testing. In: Hussmann, H. (ed.) FASE 2001. LNCS, vol. 2029, pp. 201-216. Springer, Heidelberg (2001)

Digital Library

[15]

Lämmel, R., Schulte, W.: Controllable Combinatorial Coverage in Grammar-Based Testing. In: Uyar, M.Ü., Duale, A.Y., Fecko, M. A. (eds.) TestCom 2006. LNCS, vol. 3964, pp. 19-38. Springer, Heidelberg (2006)

Digital Library

[16]

Lämmel, R., Zaytsev, V.: An Introduction to Grammar Convergence. In: Leuschel, M., Wehrheim, H. (eds.) IFM 2009. LNCS, vol. 5423, pp. 246-260. Springer, Heidelberg (2009)

Digital Library

[17]

Lämmel, R., Zaytsev, V.: Recovering Grammar Relationships for the Java Language Specification. Software Quality Journal 19(2), 333-378 (2011)

Digital Library

[18]

Malloy, B. A., Power, J. F.: An Interpretation of Purdom's Algorithm for Automatic Generation of Test Cases. In: 1st Annual International Conference on Computer and Information Science, pp. 3-5 (2001)

[19]

Maurer, P.: Generating Test Data with Enhanced Context-free Grammars. IEEE Software 7(4), 50-56 (1990)

Digital Library

[20]

McKeeman, W. M.: Differential Testing for Software. Digital Technical Journal of Digital Equipment Corporation 10(1), 100-107 (1998)

[21]

Power, J. F., Malloy, B. A.: A Metrics Suite for Grammar-based Software. Journal of Software Maintenance and Evolution: Research and Practice 16, 405-426 (2004)

Digital Library

[22]

Purdom, P.: A Sentence Generator for Testing Parsers. BIT 12(3), 366-375 (1972)

[23]

Renggli, L., Denker, M., Nierstrasz, O.: Language Boxes: Bending the Host Language with Modular Language Changes. In: van den Brand, M., Gaševic, D., Gray, J. (eds.) SLE 2009. LNCS, vol. 5969, pp. 274-293. Springer, Heidelberg (2010)

Digital Library

[24]

Schwartzbach, M. I.: Design Choices in a Compiler Course or How to Make Undergraduates Love Formal Notation. In: Hendren, L. (ed.) CC 2008. LNCS, vol. 4959, pp. 1-15. Springer, Heidelberg (2008)

Digital Library

[25]

Sirer, E. G., Bershad, B. N.: Using Production Grammars in Software Testing. SIGPLAN Notices 35, 1-13 (1999)

Digital Library

[26]

Sloane, A. M., Kats, L.C. L., Visser, E.: A Pure Object-Oriented Embedding of Attribute Grammars. In: Ekman, T., Vinju, J. (eds.) Proceedings of the Ninth Workshop on Language Descriptions, Tools, and Applications (LDTA 2009). Electronic Notes in Theoretical Computer Science. Elsevier Science Publishers (2009)

Digital Library

[27]

Waite, W. M.: The Compiler Course in Today's Curriculum: Three Strategies. In: Proceedings of the 37th SIGCSE Technical Symposium on Computer Science Education, SIGCSE 2006, pp. 87-91. ACM (2006)

Digital Library

[28]

Van Wyk, E., Krishnan, L., Bodin, D., Schwerdfeger, A.: Attribute Grammar-Based Language Extensions for Java. In: Bateni, M. (ed.) ECOOP 2007. LNCS, vol. 4609, pp. 575-599. Springer, Heidelberg (2007)

Digital Library

[29]

Zelenov, S., Zelenova, S.: Automated Generation of Positive and Negative Tests for Parsers. In: Grieskamp, W., Weise, C. (eds.) FATES 2005. LNCS, vol. 3997, pp. 187-202. Springer, Heidelberg (2006)

Digital Library

Cited By

Rossouw CFischer B(2024)Grammar-based test suite construction using coverage-directed algorithms over LR-graphsJournal of Systems and Software10.1016/j.jss.2024.112068214:COnline publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1016/j.jss.2024.112068
Rossouw CFischer BVisser EKolovos DSöderberg E(2021)Vision: bias in systematic grammar-based test suite construction algorithmsProceedings of the 14th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3486608.3486902(143-149)Online publication date: 17-Oct-2021
https://dl.acm.org/doi/10.1145/3486608.3486902
Raselimo MTaljaard JFischer BNierstrasz OGray JOliveira B(2019)Breaking parsers: mutation-based generation of programs with guaranteed syntax errorsProceedings of the 12th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3357766.3359542(83-87)Online publication date: 20-Oct-2019
https://dl.acm.org/doi/10.1145/3357766.3359542
Show More Cited By

Recommendations

LR(k)-parsing of Coupled-Context-Free Grammars
COLING '94: Proceedings of the 15th conference on Computational linguistics - Volume 1

Coupled-Context-Free Grammars are a generalization of context-free grammars obtained by combining nonterminals to parentheses which can only be substituted simultaneously. Referring to the generative capacity of the grammars we obtain an infinite ...
Left recursion in Parsing Expression Grammars

Parsing Expression Grammars (PEGs) are a formalism that can describe all deterministic context-free languages through a set of rules that specify a top-down parser for some language. PEGs are easy to use, and there are efficient implementations of PEG ...
Parsing Arabic using induced probabilistic context free grammar

The importance of the parsing task for NLP applications is well understood. However developing parsers remains difficult because of the complexity of the Arabic language. Most parsers are based on syntactic grammars that describe the syntactic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

SLE'11: Proceedings of the 4th international conference on Software Language Engineering

July 2011

387 pages

ISBN:9783642288296

Editors:
Anthony Sloane
Department of Computing, Macquarie University, Sydney, NSW, Australia
,
Uwe Aßmann
Fakultät Informatik, Institut für Software- und Multimediatechnik (SMT), Technische Universität Dresden, Nöthnitzer Straße 46, Dresden, NSW, Germany

Sponsors

Luso-American Foundation: Luso-American Foundation
FCT: Foundation for Science and Technology
Multicert: Multicert
CCTC: Centro de Ciências e Tecnologias de Computação, Portugal
SIG: Software Improvement Group

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 03 July 2011

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 28 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Rossouw CFischer B(2024)Grammar-based test suite construction using coverage-directed algorithms over LR-graphsJournal of Systems and Software10.1016/j.jss.2024.112068214:COnline publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1016/j.jss.2024.112068
Rossouw CFischer BVisser EKolovos DSöderberg E(2021)Vision: bias in systematic grammar-based test suite construction algorithmsProceedings of the 14th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3486608.3486902(143-149)Online publication date: 17-Oct-2021
https://dl.acm.org/doi/10.1145/3486608.3486902
Raselimo MTaljaard JFischer BNierstrasz OGray JOliveira B(2019)Breaking parsers: mutation-based generation of programs with guaranteed syntax errorsProceedings of the 12th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3357766.3359542(83-87)Online publication date: 20-Oct-2019
https://dl.acm.org/doi/10.1145/3357766.3359542
Raselimo MFischer BNierstrasz OGray JOliveira B(2019)Spectrum-based fault localization for context-free grammarsProceedings of the 12th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3357766.3359538(15-28)Online publication date: 20-Oct-2019
https://dl.acm.org/doi/10.1145/3357766.3359538
Zaytsev VPearce DMayerhofer TSteimann F(2018)An industrial case study in compiler testing (tool demo)Proceedings of the 11th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3276604.3276619(97-102)Online publication date: 24-Oct-2018
https://dl.acm.org/doi/10.1145/3276604.3276619
Zaytsev V(2015)Grammar ZooScience of Computer Programming10.1016/j.scico.2014.07.01098:P1(28-51)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1016/j.scico.2014.07.010
Zaytsev V(2012)Negotiated grammar transformationProceedings of the 2012 Extreme Modeling Workshop10.1145/2467307.2467313(27-32)Online publication date: 1-Oct-2012
https://dl.acm.org/doi/10.1145/2467307.2467313

View Options

View options

Figures

Tables

Media

View Table of Conten