Использование алгоритмов анализа левоконтекстных терминальных грамматик в задачах автоматического тестирования программ
Ключевые слова:
алгоритм, сценарий тестирования, тестирование программ, формальная грамматика, левоконтекстная грамматикаАннотация
При построении сценариев тестирования программ может возникнуть потребность анализа их свойств. Для формального задания сценариев можно применить левоконтекстные терминальные грамматики. В работе доказывается эквивалентность порождающей мощности левоконтекстных терминальных грамматик и контекстно-свободных грамматик и рассматриваются алгоритмы анализа левоконтекстных грамматик, которые могут быть использованы для анализа свойств сценариев тестирования.Литература
Ахо А., Сети Р., Ульман Дж. Компиляторы. Принципы, технологии, инструменты. 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 с.
Опубликован
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).
