Генерация тестов для семантических анализаторов

Авторы

  • М.В. Архипова Институт системного программирования имени В.П. Иванникова РАН (ИСП РАН)

Ключевые слова:

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

Аннотация

В статье исследуется проблема построения программ-тестов для модулей проверки статической семантики в компиляторах, рассматриваются существующие способы формального описания правил статической семантики языков программирования и обсуждаются причины, мешающие использованию существующих нотаций для решения задачи генерации семантически корректных программ-тестов. Кроме того, предлагается собственный подход к описанию правил статической семантики языков программирования, удобный для построения семантически управляемого генератора программ-тестов.

Автор

М.В. Архипова

Институт системного программирования имени В.П. Иванникова РАН (ИСП РАН)
ул. А. Солженицына, 25, 109004, Москва

Библиографические ссылки

  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.
Новые вычислительные технологии

Загрузки

Опубликован

15-09-2006

Как цитировать

Архипова М. Генерация тестов для семантических анализаторов // Вычислительные методы и программирование. 2006. 7. 55-70

Выпуск

Том 7 (2006): Выпуск 3.

Раздел

Раздел 2. Программирование