Skip to main content
SpringerLink
Log in
Book cover

International Conference on Software Language Engineering

SLE 2011: Software Language Engineering pp 324–343Cite as

Comparison of Context-Free Grammars Based on Parsing Generated Test Data

  • Conference paper

Part of the book series: Lecture Notes in Computer Science ((LNPSE,volume 6940))

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.

This is a preview of subscription content, log in via an institution.

Chapter
USD   29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD   39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD   54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Learn about institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

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

    Article  Google Scholar 

  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)

    Chapter  Google Scholar 

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

    Article  Google Scholar 

  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

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

    Google Scholar 

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

    Google Scholar 

  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)

    Article  Google Scholar 

  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)

    Article  Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  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)

    Chapter  Google Scholar 

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

    Google Scholar 

  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)

    Chapter  Google Scholar 

  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)

    Chapter  Google Scholar 

  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)

    Chapter  Google Scholar 

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

    Article  Google Scholar 

  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)

    Google Scholar 

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

    Article  Google Scholar 

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

    Google Scholar 

  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)

    Article  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Chapter  Google Scholar 

  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)

    Chapter  Google Scholar 

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

    Article  Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  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)

    Chapter  Google Scholar 

  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)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Electronics and Computer Science, University of Southampton, Southampton, United Kingdom

    Bernd Fischer

  2. Software Languages Team, Universität Koblenz-Landau, Koblenz, Germany

    Ralf Lämmel

  3. Software Analysis and Transformation Team, Centrum Wiskunde en Informatica, Amsterdam, The Netherlands

    Vadim Zaytsev

Authors
  1. Bernd Fischer
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ralf Lämmel
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Vadim Zaytsev
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computing, Macquarie University, 2109, Sydney, NSW, Australia

    Anthony Sloane

  2. Fakultät Informatik, Institut für Software- und Multimediatechnik (SMT), Technische Universität Dresden, Nöthnitzer Straße 46, 01062, Dresden, Germany

    Uwe Aßmann

Rights and permissions

Reprints and permissions

Copyright information

© 2012 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Fischer, B., Lämmel, R., Zaytsev, V. (2012). Comparison of Context-Free Grammars Based on Parsing Generated Test Data. In: Sloane, A., Aßmann, U. (eds) Software Language Engineering. SLE 2011. Lecture Notes in Computer Science, vol 6940. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-28830-2_18

Download citation

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

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-28829-6

  • Online ISBN: 978-3-642-28830-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation