Напрасникова М.В.

АВТОМАТИЧЕСКАЯ ГЕНЕРАЦИЯ СЕМАНТИЧЕСКИХ ТЕСТОВ ДЛЯ КОМПИЛЯТОРОВ

ИСП РАН, Москва, [email protected]

Введение

На первом этапе компиляции программа на исходном языке проходит обработку лексическим,

синтаксическим и семантическим анализаторами.

Целью синтаксического тестирования является проверка правильности работы синтаксического анализатора в составе компилятора. Синтаксическим тестированием компилятора называют процесс тестирования с использованием набора программ, построенных с учетом синтаксиса исходного языка [2].

Семантическое тестирование – это процесс проверки правильности работы семантического анализатора в составе компилятора. Для семантического тестирования строятся тестовые программы с учетом семантических правил исходного языка.

В основе автоматической генерации тестов для компиляторов лежит формализация спецификации исходного языка. Формальное описание языка состоит из описания синтаксиса, статической и динамической семантики.

Известны такие способы формального описания синтаксиса, как BNF(Backus-Naur Form, форма Бэкуса-Наура) [1,44-46], расширенная БНФ, синтаксические графы. Эти формализмы теоретически обоснованы и хорошо подходят для генерации синтаксических анализаторов и тестов для них.

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

Целью данного исследования является разработка технологии автоматической генерации семантических тестов для компиляторов. Для этого необходимо определить способ формализации семантики исходного языка и критерий тестирования для определения полноты тестового набора.

Генерация семантических тестов Рассмотрим некоторый целевой язык L. Для описания синтаксиса языка L традиционно используем широко применяемую запись, называемую контекстно-свободной грамматикой, или BNF(Backus-Naur Form, форма Бэкуса-Наура). Семантику языка L представим в виде зависимостей между нетерминалами.

Например, рассмотрим грамматику некоторого языка:

programm ::= expression (expression) expression::= assign | biexpres | var_descr “;” assign ::= id “=” biexpres biexpres ::= id oper id var_descr::= type id oper::= “+” | “-” | “*” type::= “int” | “float” id::= “A”| “B” | “C” Добавим семантические ограничения:

• идентификатор id может быть использован, только если он был описан (var_descr) где-то раньше в программе;

• в бинарном выражении (biexpres) и при инициализации (assign) типы левой и правой частей должны совпадать;

• тип переменных (id), участвующих в бинарном выражении (biexpres), определяет тип, который возвращается в качестве результата после выполнения операции.

Семантические ограничения устанавливают следующие зависимости между нетерминалами:

• biexpres зависит от var_descr, так как идентификатор id должен быть описан до своего использования; указанная связь является зависимостью нетерминалов вне какого-то одного правила, зависимость между двумя правилами;

• нетерминал assign зависит от var_descr, что также является зависимостью между двумя правилами вывода;

• id зависит от id в правиле biexpres; это зависимость в пределах одного правила;

• тип id определяет тип biexpres, это также зависимость в пределах одного синтаксического правила.

Ниже приведено графическое изображение семантических зависимостей:

biexpres id assign id oper biexpres id id var_descr type Будем рассматривать следующие виды семантических зависимостей между нетерминалами:

• однонаправленная зависимость в пределах одного синтаксического правила;

• двунаправленная зависимость в пределах одного синтаксического правила;

• однонаправленная зависимость между несколькими синтаксическими правилами;

• двунаправленная зависимость между несколькими синтаксическими правилами.

Следует заметить, что зависимости между несколькими синтаксическими правилами, не явно являются зависимостями между нетерминалами в этих правилах.

Синтаксические правила и нетерминалы, участвующие в семантических правилах называются существенными [3]. Для генерации программ будем использовать только существенные синтаксические правила и синтаксические правила, необходимые для достижимости существенных, назовем их необходимыми. В нашем примере необходимыми являются правила program и expression.

Семантические зависимости определяют порядок генерации. В случае двунаправленной зависимости будем рассматривать ее как две однонаправленные зависимости, то есть проводить генерацию сначала в одном направлении, затем в другом.

Теперь следует определить корректные и некорректные, с точки зрения семантики, способы раскрытия существенных нетерминалов. Назовем эти множества соответственно корректной и некорректной областями определения. Существенные нетерминалы, которые могут быть выведены через другие нетерминалы, всегда участвуют в зависимостях вне одного синтаксического правила, так как для получения их областей определения необходима дополнительная информация, назовем ее контекстом. В нашем примере для того, чтобы понять, какова область определения id нетерминала в biexpres, необходим список идентификаторов участвоваших в var_descr.

Имея области определения для нетерминалов, можем строить семантически корректные и некорректные тесты перебором с учетом порядка, установленного семантическими зависимостями.

Сформулируем требования, которые следует соблюдать для получения полного, с точки зрения семантики, набора тестов:

• области определения как-либо семантически связанных существенных нетерминалов должны перебираться как декартово произведение множеств;

• области определения существенных нетерминалов, участвующих в одном синтаксическом правиле, но не связанных семантически, должны перебираться так, чтобы во всем наборе полученных комбинаций встречались все элементы каждого из множеств по-крайней мере один раз;

• не существенные, но необходимые нетерминалы следует раскрывать так, чтобы были достигнуты все существенные нетерминалы.

Синтаксическая корректность и полнота набора тестов программ, построенных таким образом, должна гарантироваться по построению.

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

Данная работа является первым этапом в процессе разработки технологии автоматического построения семантических анализаторов и тестов для них на основе формального описания статической семантики исходного языка.

Предполагается применить данный подход для построения генератора семантических тестов для компилятора C#.

На данном этапе подход был реализован для генератора семантических тестов для транслятора языка TDL(Tree Description Language), разработанного группой RedVerst ИСП РАН и примененного этой группой в ряде коммерческих проектов. TDL является аналогом таких нотаций как ASN.1 [5,6] и ASDL [4].

Для проверки полноты полученного набора тестов использовались инcтрументы TrueCoverage и JProbe.

Полученные результаты покрытия тестами кода транслятора приведены в таблице:

Другие подходы к формализации семантики Существуют различные методы формального определения семантики. Ниже приводятся описания некоторых из них.

Ранние попытки добавить корректное определение семантики к языку программирования делались путем добавления расширений к БНФ-грамматике, определяющей этот язык. Дополнительную информацию о семантике можно было извлечь из дерева синтаксического разбора.

Одной из первых попыток разработки семантической модели языка программирования была концепция атрибутивной грамматики, предложенная Дональдом Кнутом. Идея заключалась в том, чтобы сопоставить каждому узлу дерева синтаксического разбора данной программы некоторую функцию, задающую семантическое содержание данного узла. Атрибутивные грамматики создавались путем добавления функций (атрибутов) к каждому правилу грамматики.

Примером формализации на основе операционной модели может служитьVDL. В 70-е гг. была разработана операционная модель языка под названием Vienna Definition Language (VDL) — метаязык, предназначенный для описания других языков. В этой модели дерево синтаксического анализа включает в себя также машинный интерпретатор. Состояние вычисления входит в дерево программы, а также в дерево, описывающее все данные для конкретной машины. Очередной оператор переводит дерево в новое состояние.

Функциональное определение языка пытается непосредственно сконструировать определение функции, которую вычисляет каждая программа, написанная на этом языке. Такое определение языка строится как иерархия определений функций, которые вычисляются каждой отдельной программной конструкцией. Примерами такого подхода к определению семантики являются метод денотационной семантики Скотта (Scott) и Стрэчи (Strachey) и метод функциональной семантики Миллза (Mills).

Литература 1. А. Ахо, Р.Сети, Д. Ульман. Компиляторы: принципы, технологии, инструменты // Москва–СанктПетербург–Киев, 2001.

2. Glossary of terms used in software testing. http://www.testingstandards.co.uk/bs_7925-1_online.htm 3. A.S. Kossatchev, A.K. Petrenko, S.V. Zelenov, S.A. Zelenova. Test Generation for Compilers and Other Formal Text Processors. Programming and Computer Software, Moscow-New-York, vol. 29, No. 3, 2003, 104-111.

4. D.C. Wang, A.W. Appel, J.L. Korn, C.S. Serra. The Zephyr

Syntax Description Language // USENIX, Proc. Conference on Domain-Specific Languages, October 15–17, 1997, Santa Barbara, California, USA; pp.

213–227.

5. Information Processing – Open Systems Interconnection – Specification of Abstract Syntax Notation One (ASN.1) // International Organization for Standardization and International Electrotechnical Committee, 1987.

International Standard 8824.

6. Information Technology – Abstract Syntax Notation One (ASN.1): Specification of Basic Notation // International Telecommuncation Union, 1995. ITU-T Recommendation X.680.