Использование алгоритмов анализа левоконтекстных терминальных грамматик в задачах автоматического тестирования программ
Ключевые слова:
алгоритм, сценарий тестирования, тестирование программ, формальная грамматика, левоконтекстная грамматикаАннотация
При построении сценариев тестирования программ может возникнуть потребность анализа их свойств. Для формального задания сценариев можно применить левоконтекстные терминальные грамматики. В работе доказывается эквивалентность порождающей мощности левоконтекстных терминальных грамматик и контекстно-свободных грамматик и рассматриваются алгоритмы анализа левоконтекстных грамматик, которые могут быть использованы для анализа свойств сценариев тестирования.Литература
Ахо А., Сети Р., Ульман Дж. Компиляторы. Принципы, технологии, инструменты. M.: Вильямс, 2003. 768 с.
Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1. Синтаксический анализ, М.: Мир, 1978. 612 с.
Гладкий А.В. Формальные грамматики и языки. М.: Наука, 1973. 368 с.
Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. Новосибирск: Изд. НГУ, 1995. 112 с.
Кларк Э.М., Грамберг О., Пелед Д. Верификация моделей программ. Model Checking M.: Изд. МЦНМО, 2002. 416 с.
Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: Построение и анализ. М.: Вильямс, 2005. 1296 с.
Корнеев Г.А., Маврин П.Ю., Станкевич А.С. Использование конечных автоматов с магазинной памятью для автоматизации тестирования программных решений // Тр. XI Всерос. науч.-методич. конф. «Телематика-2005» СПб.: СПбГУ ИТМО. С. 510–511
Котляров В.П., Коликова Т.В. Основы тестирования программного обеспечения. М.: Бином, 2006. 288 с.
Маврин П.Ю., Парфенов В.Г., Станкевич А.С. Использование левоконтекстных грамматик для описания сценариев автоматического тестирования программных решений // Тр. XVII Всерос. науч.-методич. конф. «Телематика-2010» СПб.: СПбГУ ИТМО. С.197–198
Хомский Н., Миллер Дж. Введение в формальный анализ естественных языков // Кибернетический сборник. М.: Мир, 1965.
Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. M.: Вильямс, 2002. 528 с.
Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1. Синтаксический анализ, М.: Мир, 1978. 612 с.
Гладкий А.В. Формальные грамматики и языки. М.: Наука, 1973. 368 с.
Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. Новосибирск: Изд. НГУ, 1995. 112 с.
Кларк Э.М., Грамберг О., Пелед Д. Верификация моделей программ. Model Checking M.: Изд. МЦНМО, 2002. 416 с.
Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: Построение и анализ. М.: Вильямс, 2005. 1296 с.
Корнеев Г.А., Маврин П.Ю., Станкевич А.С. Использование конечных автоматов с магазинной памятью для автоматизации тестирования программных решений // Тр. XI Всерос. науч.-методич. конф. «Телематика-2005» СПб.: СПбГУ ИТМО. С. 510–511
Котляров В.П., Коликова Т.В. Основы тестирования программного обеспечения. М.: Бином, 2006. 288 с.
Маврин П.Ю., Парфенов В.Г., Станкевич А.С. Использование левоконтекстных грамматик для описания сценариев автоматического тестирования программных решений // Тр. XVII Всерос. науч.-методич. конф. «Телематика-2010» СПб.: СПбГУ ИТМО. С.197–198
Хомский Н., Миллер Дж. Введение в формальный анализ естественных языков // Кибернетический сборник. М.: Мир, 1965.
Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. M.: Вильямс, 2002. 528 с.
Algorithms of analyzing left context terminal grammars used for automated programs testing
Abstract
After designing testing scripts, sometimes it is needed to analyze their properties. To make script specification formal, one can use left context terminal grammars. The article gives proof of left context terminal grammars and context free grammars equivalence and develops algorithms for analyzing properties of such grammars that are useful in analyzing testing script properties.Опубликован
2010-06-01
Как цитировать
Станкевич, А. С. (2010). Использование алгоритмов анализа левоконтекстных терминальных грамматик в задачах автоматического тестирования программ. Труды СПИИРАН, 2(13), 106-121. https://doi.org/10.15622/sp.13.5
Раздел
Статьи
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
