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

• Автор: Архипова, Мария Викторовна
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Москва
• Количество страниц: 219 с. : ил.

ВВЕДЕНИЕ.
1 ГЕНЕРАЦИЯ ТЕСТОВ ДЛЯ АНАЛИЗАТОРОВ КОНТЕКСТНЫХ УСЛОВИЙ ТРАНСЛЯТОРОВ СОВРЕМЕННОЕ СОСТОЯНИЕ

1.1 Обзор методов генерации тестов для трансляторов.

1.2 Основные принципы проектирования набора тестов для анализатора

контекстных условий транслятора

1.3 Организация целенаправленной генерации тестов с использованием

классических атрибутных грамматик

1.4 Анализ результатов генерации тестов с использованием классических

АТРИБУТНЫХ ГРАММАТИК.

2 КОНСТРУКТИВНОЕ ОПИСАНИЕ СТАТИЧЕСКОЙ СЕМАНТИКИ ФОРМАЛЬНЫХ ЯЗЫКОВ

2.1 Неформальное описание идеи

2.2 Конструктивное описание семантики.
2.3 Критерий покрытия.
2.3.1 Критерий покрытия для позитивных тестов.
2.3.2 Критерий покрытия для негативных тестов.
3 СЕМАНТИЧЕСКИ УПРАВЛЯЕМАЯ ГЕНЕРАЦИЯ ТЕСТОВЫХ ВХОДНЫХ ДАННЫХ.
3.1 Представление данных
3.2 ГЕНЕРАЦИЯ входных данных для позитивных тестов на основе
конструктивного описания статической семантики.
3.2.1 Построение первичных поддеревьев
3.2.2 Обеспечение семантической корректности тестовых текстов
3.3 Генерация негативных тестовых входных данных на основе
конструктивного описания статической семантики
4 ОПИСАНИЕ НЕТРИВИАЛЬНЫХ КОНТЕКСТНЫХ УСЛОВИЙ.
4.1 Контекст семантического правила
4.2 Семантические правила с фильтрами
4.3 Зависимые семантические правила
4.4 Описание объектов семантического правила посредством задания пути
4.5 Семантика типов
4.6 Семантические ограничения на синтаксис.
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


Синтаксически корректный текст, удовлетворяющий всем контекстным условиям языка, на котором этот текст написан, называется семантически корректным. Для тестирования анализатора контекстных условий транслятора существенными являются семантически корректные тексты (позитивные тестовые входные данные), и синтаксически корректные тексты, в которых нарушены определенные контекстные ограничения {негативные тестовые входные данные). Позитивные тесты, частью которых являются позитивные тестовые входные данные, позволяют проверить правильность реализации контекстных условий в трансляторе. Негативные тесты, частью которых являются негативные тестовые входные данные, могут использоваться для проверки правильности сообщений об ошибках, выдаваемых анализатором, и для проверки способности транслятора обнаруживать ошибочные места во входных данных. Начиная с -х годов века, были опубликованы результаты многих исследований, посвященных вопросам генерации тестов для трансляторов [-, - и др. Большинство из предложенных способов вообще не позволяют генерировать тексты с учетом контекстных ограничений входного языка, а те немногие, что позволяют, обладают существенными недостатками. Рассмотрим основные существующие подходы. В ранних исследованиях, посвященных генерации тестов для трансляторов, К. В. Ханфорд [] и П. Пардом [] представили методы, позволяющие генерировать синтаксически корректные без учета правил статической семантики программы для компиляторов процедурных языков. Так в году была опубликована работа [], в которой автор предлагал способ генерации тестовых данных для компилятора Р1 на основе динамической грамматики. В результате работы алгоритма были получены синтаксически корректные программы, среди которых присутствовали семантически некорректные. Далее следует упомянуть работу [], ставшую фундаментальной в области генерации тестов для трансляторов. Это исследование в дальнейшем было базовым для многих других. В качестве входных данных алгоритм П. Пардома использует контекстно-свободную грамматику, из которой выводит множество фраз так, чтобы при этом каждое продукционное правило использовалось не менее одного раза. Данный алгоритм не позволяет учитывать контекстные правила входного формального языка и может использоваться только для генерации тестов для парсеров. В году была опубликована работа Б. А. Уичмана и Б. При этом другие правила статической семантики, например, касающиеся использования имен переменных, при построении тестовых программ опять не учитывались. В А. Челентано и др. Синтаксически корректные программы генерируются по алгоритму Пардома. Грамматика входного языка, подаваемая на вход генератору, дополняется кодом, в котором производится проверка контекстных условий и преобразование синтаксически корректных программ в семантически корректные, если это необходимо. Предложенный метод применялся для подмножества языка Pascal. Было отмечено, что описание семантических проверок, например, для пользовательских типов в Pascal, уже требует значительных усилий. Стало понятно, что использование данного метода для тестирования компиляторов с объектно-ориентированных языков нецелесообразно, так как потребует еще больше усилий. В работе [] А. Г. Данкэн и Дж. С. Хатчисон предложили использовать атрибутные грамматики для описания входных данных генератора тестов. В процессе генерации последовательно раскрываются все нетерминальные символы, если это позволяют контекстные ограничения. Таким образом, в результате получается набор синтаксически и семантически корректных тестов, покрывающий все продукционные правила грамматики и все контекстные условия. Такой подход позволяет только вести анализ выполненных контекстных условий. Это ведет к большому количеству пустых прогонов генератора, когда из-за невыполненных контекстных условий приходится прерывать процесс генерации, и к построению большого числа семантически неинтересных тестов. В исследовании [], авторами которого являются Е. Г. Сирер и Б. Н. Бершэд, описывается спецификационный язык lava.