Generation of semantic analyzer tests

Authors

  • M.V. Arkhipova

Keywords:

статическая семантика
семантический анализатор
автоматическая генерация тестов

Abstract

The paper addresses the problem of generating test cases for semantic checkers of compilers. While many works on formal specification of programming language semantics have proposed several powerful techniques, many challenges remain in applying them to realistic test generators. We present a novel approach to the formal specification of a programming language static semantics and show that our approach is suitable for test program generation.

New computational technologies

Downloads

Published

2006-09-15

Issue

Vol. 7 (2006): Issue 3.

Section

Section 2. Programming

Author Biography

M.V. Arkhipova

Ivannikov Institute for System Programming of RAS (ISP RAS)

References

  1. Hanford K.V. Automatic generation of test cases // IBM System Journal. 1970. 9, N 4. 242-257.
  2. Purdom P. A sentence generator for testing parsers // Behavior and Information Technology. 1972. 12, N 3. 366-375.
  3. Wichmann B.A., Jones B. Testing ALGOL 60 compilers // Software -Practice and Experience. 1976. 6, N 2. 261-270.
  4. Celentano A., Crespi Reghezzi S., Della Vigna P., Ghezzi C., Granata G., Savoretti F. Compiler testing using a sentence generator // Software -Practice and Experience. 1980. 10, N 11. 897-918.
  5. Duncan A.G., Hutchison J.S. Using attributed grammars to test designs and implementation // Proceedings of the 5th International Conference on Software Engineering. Piscataway: IEEE Press, 1981. 170-178.
  6. 愦灭;percentEmin G.u n Sirer, Brian N. Bershad. Using production grammars in software Sirer E.G., Bershad B.N. Using production grammars in software testing // Proceedings of the 2nd Conference on Domain-Specific Languages. New York: ACM Press, 1999. 1-13.
  7. Kalinov A., Kossatchev A., Petrenko A., Posypkin M., Shishkov V. Using ASM specifications for automatic test suite generation for mpC parallel programming language compiler // Proceedings of the 4th International Workshop on Action Semantics. BRISC Notes Series. University of Aarhus (Denmark), 2002. 96-106.
  8. Kalinov A., Kossatchev A., Petrenko A., Posypkin M., Shishkov V. Using ASM specifications for compiler testing // 愦灭;percent In Abstract State Machines -愦灭;percentAdvances in Theory and Applications10th International Workshop, ASM 2003. 愦灭;percent2003. Volume 2589 of LNCS. 415. Proceedings of the 10th International Workshop on Abstract State Machines. Lecture Notes in Computer Science. Vol. 2589. New York-Heidelberg-Berlin: Springer-Verlag, 2003. 415.
  9. Kossatchev A.S., Kutter P., Posypkin M.A. Automated generation of strictly conforming tests based on formal specification of dynamic semantics of the programming language // Programming and Computing Software. 2004. 30, N 4. 218-229.
  10. Van Wijngaarden A., Mailloux B.J., Peck J.E., Koster C.H. A. Report on the algorithmic language Algol-68. MR 101, Mathematisch Centrum. Amsterdam, 1969.
  11. Hoare C.A. R., Wirth N. An axiomatic definition of the programming language PASCAL // Acta Informatica. 1973. 2, N 4. 335-355.
  12. Lee J.A. N. Computer semantics. New York: Van Nostrand Co., 1972.
  13. Lucas P., Lauer P., Stigleitner H. Method and notation for the formal definition of programming languages. IBM Technical Report 25.087. IBM Lab. Vienna, 1968.
  14. Lucas P., Walk K. On the formal description of PL/1 // Annual Review Automatic Programming. 1969. 6, N 3. 105-182.
  15. Wegner P. The Vienna definition language // Computer Surveys. 1972. 4, N 1. 5-63.
  16. Knuth D.E. Semantics of context-free languages // Mathematical Systems Theory. 1968. 2, N 2. 127-146.
  17. Knuth D.E. Semantics of context-free languages: Correction // Mathematical Systems Theory. 1971. 5, N 1. 179.
  18. Yacc and Lex. http://dinosaur.compilertools.net/
  19. Kastens U. Attribute grammars as a specification method // Proceedings of the International Summer School on Attribute Grammars. Lecture Notes in Computer Science. Vol. 545. New York-Heidelberg-Berlin: Springer-Verlag, 1991. 16-47.
  20. Bischoff K.M. Ox: An attribute-grammar compiling system based on yacc, lex and c: User reference manual. User Manual, 1993. http://citeseer.ist.psu.edu/bischoff93ox.html
  21. Pagan F. Formal specification of programming languages: A panoramic primer. Englewood Cliffs: Prentice Hall, 1981.
  22. Slonneger K., Barry L. Kurtz formal syntax and semantics of programming languages: A laboratory based approach. London: Addison-Wesley Longman Publishing Co., 1995.
  23. Зеленов С.В., Зеленова С.А., Косачев А.С., Петренко А.К. Генерация тестов для компиляторов и других текстовых процессоров // Программирование. 2003. 29, № 3. 104-111.
  24. Gurevich Y. Abstract state machines: An overview of the project // Foundations of Information and Knowledge Systems. Lecture Notes in Computer Science. Vol. 2942. New York-Heidelberg-Berlin: Springer-Verlag, 2004. 6-13.
  25. Посыпкин М.А. Применение формальных методов для тестирования компиляторов. Диссертационная работа на соискание ученой степени кандидата физико-математических наук. М., ИСП РАН, 2004.
  26. Архипова М.В. Генерация тестов для семантических анализаторов. Препринт ИСП РАН. № 9. M., ИСП РАН, 2006.