WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

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

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

ИСП РАН, Москва, maryn@ispras.ru

Введение

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

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

Целью синтаксического тестирования является проверка правильности работы синтаксического анализатора в составе компилятора. Синтаксическим тестированием компилятора называют процесс тестирования с использованием набора программ, построенных с учетом синтаксиса исходного языка [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

Abstract

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.





Похожие работы:

«Учебник по игре точки Точки - захватывающая логическая игра с простыми правилами и в то же время с бесконечным количеством комбинаций и сложной стратегией. Вашей целью является окружение точек соперника и защита собственных. Большое поле размером до 39х32 клеток обеспечивает вам свободу действий. Вас ожидают соперники от новичков, с которыми будет просто, до сильных игроков, которые никогда не дадут вам свободно вздохнуть. Чтобы стать лучше вам придется показать все, на что вы способны, но и...»

«УТВЕРЖДАЮ МИНЗДРАВ РОССИИ Проректор по учебной, внеучебной и государственное бюджетное образовательное воспитательной работе учреждение высшего профессионального образования Южно-Уральский государственный медицинский университет И.А. Волчегорский Министерства здравоохранения Российской Федерации 2013 г (ГБОУ ВПО ЮУГМУ Минздрава России) Кафедра терапии факультета дополнительного образования РАБОЧАЯ ПРОГРАММА по интернатуре на 2013-2014 учебный год Дисциплина Терапия Специальность Терапия Форма...»

«Министерство культуры Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Московский государственный университет культуры и искусств Кафедра прикладной информатики Программа дополнительного экзамена кандидатского минимума ИНФОРМАЦИОННЫЕ СИСТЕМЫ И ПРОЦЕССЫ В СОЦИОКУЛЬТУРНОЙ СФЕРЕ Специальность: 05.25.05 Информационные системы и процессы Москва, 2011 2 Утверждено Ученым советом МГУКИ 04 апреля 2011 г., протокол №9 Программа...»

«МЧС России Министерство Российской федерации по делам гражданской обороны, чрезвычайным ситуациям и ликвидации последствий стихийных бедствий www.mchs.gov.ru Академия Государственной противопожарной службы МЧС России   Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования – Академия Государственной противопожарной службы МЧС России - ведущий вуз страны по подготовке специалистов с высшим и послевузовским профессиональным образованием, проведению...»

«Министерство образования и науки Российской Федерации Учебно-методическое объединение вузов по образованию в области информационной безопасности СБОРНИК ПРИМЕРНЫХ ПРОГРАММ УЧЕБНЫХ ДИСЦИПЛИН ПО НАПРАВЛЕНИЮ ПОДГОТОВКИ 090900 ИНФОРМАЦИОННАЯ БЕЗОПАСНОСТЬ КВАЛИФИКАЦИЯ (СТЕПЕНЬ) - БАКАЛАВР XIV Пленум Учебно-методического объединения по образованию в области информационной безопасности Методический семинар Переход на ФГОС ВПО нового поколения и особенности организации учебного процесса по основным...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ Московский государственный горный университет Кафедра теоретической и прикладной механики УТВЕРЖДАЮ Проректор по методической работе и качеству образования В. Л. Петров _2011 г. РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА ПО ДИСЦИПЛИНЕ ОПД.Ф.02.01. ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Направление подготовки 130400 Горное дело Специальность Физические процессы горного или нефтегазового...»

«Орден Знак ПОчета №1 январь ЛИТЕраТУрнО-ХУДОЖЕСТвЕннОЕ ПрИЛОЖЕнИЕ 2011 № 1 январь 2011 издание ёфицировано И.И. Левитан, Осенний день. Сокольники, 1879 г. Эту картину Левитан написал, когда ему было 19 лет! Увидев Осенний день. Сокольники, Павел Третьяков сразу же приобрел ее для своей галереи. Интересный факт — фигура женщины на полотне написана Николаем Чеховым. Читайте на стр. 33 СодеРжаНие 2 0 11 янв А рь 3 Нам пишут Сподвижник просвещения миНувшее Светлана Бестужева-Лада Резина ЗаБЫтЫе С...»

«МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное образовательное учреждение высшего профессионального образования КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ АГРАРНЫЙ УНИВЕРСИТЕТ УТВЕРЖДАЮ: Декан факультета плодоовощеводства и виноградарства доцент С.М. Горлов июля 2010 г. РАБОЧАЯ ПРОГРАММА дисциплины: История виноградарства для специальности 110202 Плодоовощеводства и виноградарство Факультет Плодоовощеводства и виноградарства Ведущая кафедра виноградарства Виды занятий Форма...»

«Учреждение образования “Белорусский государственный педагогический университет имени Максима Танка” Утверждаю Проректор по учебной и информационно-аналитической работе _ В.М. Зеленкевич “ 30 ” августа 2007 г. Программа по курсу “Астрономия” для специальности 1-02 05 04 – 01 “Физика. Математика” и 1 – 02 05 04 – 02 “Физика. Информатика” Факультет Физический Кафедра Методики преподавания Физики Курс V Семестр IX – X Лекции 48 часов Экзамен Х семестр УСРС 18 часов Практические занятия УСРС -...»

«www.innoclusters.ru Информационно-справочный материал для участников территориальных кластеров Томской области Возможности и порядок участия в Президентской программе повышения квалификации инженерных кадров на 2012годы Томск 2013 Аннотация В Информационно-справочном материале изложены сведения о содержании, возможностях и порядке участия в Президентской программе повышения квалификации инженерных кадров на 2012-2014 годы. Материал предназначен для руководителей, менеджеров и специалистов...»

«Приложение № 1 Основные термины, используемые в программе Ключевые компетенции - совокупность знаний, умений, мотивации и ценностей, обеспечивающих успешное решение часто встречаемых проблем повседневной жизнедеятельности современного человека. Самоопределение - процесс, включающий: осознание требований общества к поведению личности в типичных жизненных ситуациях; принятие этих требований в качестве ориентиров действий; выявление индивидуальных задатков и способностей, на основе которых...»

«ПРОГРАММА ВСТУПИТЕЛЬНЫХ ИСПЫТАНИЙ ПО СПЕЦИАЛЬНОЙ ДИСЦИПЛИНЕ 40.00.01 - ЮРИСПРУДЕНЦИЯ (12.00.03 - гражданское право, предпринимательское право, семейное право, международное частное право) для поступающих на очную и заочную формы обучения по направлению подготовки научно-педагогических кадров в аспирантуре Москва 2014 Программа составлена в соответствии с государственным образовательным стандартом высшего профессионального образования второго поколения по специальности 021100 – “Юриспруденция”....»

«Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Уральский государственный педагогический университет Экономический факультет Кафедра экономики и методики обучения экономическим дисциплинам РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА по дисциплине ИСТОРИЯ ЭКОНОМИЧЕСКИХ УЧЕНИЙ по направлению 050400.62 – Социально-экономическое образование профиль Экономика по циклу ГСЭ.Р.01 Очная форма обучения курс - 4...»

«МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственноебюджетное образовательное учреждение высшего профессионального образования КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ АГРАРНЫЙ УНИВЕРСИТЕТ Рабочая программа дисциплины (модуля) Б.1. Иностранный язык Направление подготовки 280100.62 Природообустройство и водопользование Профиль подготовки Мелиорация, рекультивация и охрана земель Квалификация (степень) выпускника Бакалавр Форма обучения очная Краснодар 2013 1. Цели освоения...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ АРМЕНИИ АРМЯНСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ Х.АБОВЯНА ПРОГРАММА ТИПОЛОГИЯ ЛИТЕРАТУРНОГО ПРОЦЕССА _ назв ание предм ета, в с оотв етс тв ии с гос у дарс тв енным образов атель ным с тандартом ПРОГРАММА ДЛЯ МАГИСТРАТУРЫ по специальности -,,РУССКИЙ ЯЗЫК И ЛИТЕРАТУРА” 032400 шифр специаль ности, название ЕРЕВАН Утверждено на заседании N 2013г. Совета филологического факультета Армянского государственного педагогического...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ федеральное государственное бюджетное образовательное учреждение высшего профессионального образования КРАСНОЯРСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ им. В.П. Астафьева Стратегические и тактические задачи в становлении коммуникативности будущего педагога Учебная программа дисциплины по выбору Направление подготовки Педагогическое образование Степени: бакалавр, магистр Красноярск 2012 Автор программы И. И. Барахович, кандидат...»

«1. Цели освоения дисциплины Изучение дисциплины Метрология, стандартизация, сертификация в технологии углей предполагает уяснение объективных закономерностей и методологии получения количественной информации о свойствах окружающего мира, процессах, явлениях, результатах практической и профессиональной деятельности, методах формирования требований к результатам практической и профессиональной деятельности, механизмах закрепления требований за продукцией и услугами, как результатами...»

«Министерство молодежной политики и спорта Республики Башкортостан Министерство образования Республики Башкортостан Башкирская выставочная компания при участии Администрации городского округа г.Уфа Академии наук Республики Башкортостан Уфимского научного центра РАН Высших учебных заведений Республики Башкортостан ПРОГРАММА Фестиваля Дни молодежной науки в Республике Башкортостан, Образовательного форума и XII Специализированной выставки Образование. Наука. Карьера–2012 27–30 марта 2012 г....»

«Министерство образования и науки Российской Федерации Беловский институт (филиал) федерального государственного бюджетного образовательного учреждения высшего профессионального образования Кемеровский государственный университет Кафедра экономики Рабочая программа учебной дисциплины МОТИВАЦИЯ И СТИМУЛИРОВАНИЕ ТРУДА Для специальности 080502.65 Экономика и управление на предприятии (по отраслям), цикл специальных дисциплин, форма обучения – очная, заочная Форма обучения: очная Курс – 5 экзамен –...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Г ОУ ВПО Р О С С ИЙ С К О-А Р МЯ Н С К ИЙ (С Л А ВЯ НС КИ Й) УН ИВ Е РСИ Т Е Т Составлена в соответствии с федеральными государственными требованиями к структуре основной профессиональной образовательной программы послевузовского УТВЕРЖДАЮ: профессионального образования (аспирантура) Проректор по научной работе _ П.С. Аветисян 2011г. Факультет : общественно-политических наук п ол и т и че с к о й т е о р и и Кафедра: Учебная программа...»






 
2014 www.av.disus.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.