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

Г6 од

г 5 ЛПР 1993

МОСКОВСКИЙ ОРДЕНА ЛЕНИНА, ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ И ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В.ЛОМОНОСОВА

Факультет вычислительной математики и кибернетики

На правах рукописи

ЯРКО Людмила Владимировна

УДК 681.3.06

ПОЛНОТА ТЕСТИРОВАНИЯ РЕАЛИЗАЦИИ КОНТЕКСТНЫХ СВОЙСТВ ЯЗЫКА ПРОГРАММИРОВАНИЯ В ТРАНСЛЯТОРАХ

Специальность: 05.13.11 математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва 1992

Работа выполнена на кафедре алгоритмических языков факультета вычислительной математики и кибернетики Московского государственного университета имени М.В.Ломоносова.

Научный руководитель

доктор физико-математических наук,

профессор

В.Ш.КАУФМАН

Официальные оппоненты

доктор физико-математических наук,

профессор

Е.А.ЖОГОЛЕВ-----

кандидат физико-математических наук,

доцент

В.М.МАЛЫШЕВ

Ведущая организация

Российский научно-исследовательский институт информационных технологий и систем автоматизированного проектирования (г.Москва)

Защита диссертации состоится _

1993 г. в _ часов на заседании специализированного

Совета МГУ Д.053.05.38 по математике по адресу 119899, ГСП, Москва В-234, Ленинские горы, МГУ, факультет вычислительной математики и кибернетики, аудитория _.

С диссертацией можно ознакомиться в библиотеке факультета вычислительной математики и кибернетики МГУ. Ученый секретарь специализированного Совета МГУ Д.053.05.38 по математике

профессор ¿^"Нт—— Н.П.Трифонов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ.

Аятуальностз тзмы. К настоящему времени накоплен богатый опыт стандартизации языков программирования. Активно разрабатываются языковые стандарты, как для новых, так и для ранее стандартизованных языкоз программирования (ФОРТРАНа, Паскаля, Ады, ХОВОЛа и др.).

Одной из проблем, связанных со стандартизацией языков программирования, является проблема контроля за соблюдением требований стандарта в трансляторах и программах. В связи с повышением "требований к качеству программного обеспечения ужесточаются и требования стандартов к трансляторам; задача контроля согласованности трансляторов со стандартами становится все более зазнсй. На практике эта задача решается путем знешнего тестирования трансляторов специально разработанными комплектами тестов. Большинство дефектов современных трансляторов сзязано с неправильным диагностированием ошибок в программах. Поэтому создание методик проектирования тестов для проверки этого аспекта трансляторов представляется актуальной.

Комплекты тестов, разработанные для контроля согласованности, часто используются и при отладке трансляторов. При .этом возникает необходимость разработки дополнительных тестов для более полной проверки того или иного аспекта реализации языка. Проблема пополнения комплекта тестов возникает и . при тестировании расширяющих стандарт реализаций. К последним могут быть отнесены и трансляторы для новых версий старых стандартов, например, ФОРТРАНа 90. Принципы построения известных комплектов тестов не учитывают возможности их последующего развития, поэтому работа по систематическому пополнению такого комплекта сопоставима с созданием нового комплекта тестов. Тем самым актуальной оказывается разработка методики построения комплектов тестов, учитывающей возможность их последующего развития.

Данное диссертационное исследование выполнено в рамках разрабатываемой на хафедре алгоритмических языков факультета ВМиК МГУ темы внешнего тестирования трансляторов.

Цель» диссертационного исследования является: разработка и испытание методики проектирования раззизаемых комплектов

тестов для проверки реализации в трансляторах контекстных свойств языков программирования.

Научная новизна. В диссертационной работе впервые предложены:

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

2. Систематический подход к проверкё контекстных свойств языка в расширенных реализациях стандарта.

На основе результатов диссертационного исследования спроектирован развиваемый комплект тестов для трансляторов ФОРТРАНа-77.

Прахтичесхая ценность. Предложенная в диссертации методика позволяет проектировать комплекты тестов на основе эволюционирующих стандартов языков программирования и использовать их для аттестации и отладки существующих и разрабатываемых трансляторов. Созданный при апробации методики комплект тестов пригоден для отладки, испытаний и аттестации трансляторов ФОРТРАНа-77.

Апробация. Содержание и основные результаты диссертационной работы докладывались на Всесоюзной конференции по методам трансляции и конструирования программ (Новосибирск, 1988),заседаниях рабочих групп по проблемам расширяемых средств программирования и методам оценки трансляторов (Фрунзе, 1989; Владивосток, Г990), на научно-исследовательском семинаре по автоматизации программирования (Москва, 1992), на заседании кафедры алгоритмических языков факультета ВМиК МГУ (Москва, 1992). МетЪдика проектирования тестов была использована при тестировании параллельных расширений ФОРТРАНа-77 в трансляторе ФОРТРАНа для ЭВМ ПС-3000 в ИПУ АН СССР.

Публикации. Результаты диссертации опубликованы ; в печатных работах [1,2].

Структура и объем диссертации. Диссертация состоит из четырех глав, заключения, списка литературы и приложения. Объем диссертации 96 страниц.

СОДЕРЖАНИЕ РАБОТЫ.

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

В глазе обсуждается текущее состояние задачи контроля согласованности трансляторов со стандартами языков программирования, методов тестирования программ и трансляторов. Изложены основные положения методики внешнего тестирования трансляторов (ВТТ), в тем числе основные принципы моделирования (представления знаний) при внешнем тестировании трансляторов и подходы к тестированию диагностики трансляторов.

С точки зрения контроля реализации контекстных свойств проанализированы существующие в ВТТ методики проектирования тестов и соответствующие им критерии полноты комплектов тестов. Эти критерии включают два уровня: уровень полноты выбора целей (относительно некоторой модели описания языка программирования) и полноты проверки отдельной цели тестами комплекта. Существующие методики концентрируются на разработке критериев первого уровня, выбирая для второго самый слабый критерий "одна цель - один тест". Другая особенность методик состоит в том, что модели, на основании которых генерируется перечень целей, не рассчитаны на создание "открытого" комплекта тестов, учитывающего возможность его пополнения при ревизии стандарта или тестировании расширяющей стандарт реализации.

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

Предложенная в диссертации методика ориентирована на создание комплекта тестов для контроля реализации контекстных свойстз в трансляторах. Методика включает этапы: моделирования и проектирования тестов.

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

модели составляет первый этап проектирования комплекта тестов в рамках предлагаемой методики.

На этапе моделирования по описанию языка (стандарту) разрабатывается атрибутно-ориентированная модель языка. Модель служит средством фиксации решений о полноте проверки целей тестами комплекта. Задача этапа моделирования выделить конструкции и понятия языка, существенные с точка зрения контроля реализации контекстных сзойств.

Описание языка вводит множество основных синтаксических классов (понятий, категорий) и связывает с каждым классом конечные множества атрибутов (свойств). Примеры таких классов в ФОРТРАНе-77: "символическое имя", "выражение", "метка", "оператор", "программная единица". Примеры атрибутов для класса символических имен: "класс имени", "тип", "принадлежность общему блоку" и т.д.. Описание языка определяет для каждого атрибута множество его допустимых значений. Значения атрибутов программных объектов, относящихся к тому или иному синтаксическому классу, задаются текстом программы.

Описание языка накладывает на атрибуты синтаксического класса глобальные ограничения, определяющие, какие из сочетаний значений этих атрибутов являются допустимыми в языке. Стандарт ФОРТРАНа-77, например, вводит следующие глобальные ограничения на атрибуты класса "символическое имя": "имя не может быть одновременно именем формального параметра и именем объекта, входящего в общий блок", "имена главного модуля, подпрограммы, общего блока и модуля-блока данных не имеют типа". Таким образом, объектам из синтаксического класса можно поставить в соответствие множество кортежей, составленных из значений различных атрибутов этого класса и удовлетворяющих глобальным ограничениям.

Объекты из синтаксических классов участвуют в формировании составных синтаксических конструкций. Будем рассматривать только синтаксически правильные конструкции. Описание языка определяет дополнительные ограничения на допустимые значения и сочетания значений атрибутов объектов, вошедших в конструкцию. Назовем такие ограничения локальными.

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

3) Для В-тестов из множества недопустимых кортежей значений выбираются те, в которых нарушены только локальные ограничения. Это объясняется тем, что нарушение глобальных ограничений не связано с данной синтаксической конструкцией, и диагностика этого нарушения должна происходить в других местах программы.

4) Для В-тестоз выбираются такие кортежи значений, з которых нарушено только одно локальное ограничение.

Заметим, что ограничение бесконечных множеств значений и выбор "характерных представителей" может происходить одновременно с разработкой атрибутно-ориентированной модели либо на основе уже разработанной модели.

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

Форма целевой синтаксической конструкции с

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

Общая методика "ВТТ определяет требования к структуре тестовых программ, проверяющих цель. Тест проектируется для проверки единственной цели. Существенным является требование "ничего лишнего в тесте". Тест обязательно включает целевое предложение (оператор либо объявление) и предложения, необходимые для ' формирования нужного для проверки цели контекста. Остальные фрагменты теста нужны для придания ему структуры законченной программы.

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

Зафиксированный кортеж значений атрибутов и множества соответствующих синтаксических шаблонов определяют набор

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

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

Введенные ограничения на формы целевых предложений, выбор множества кортежей значений атрибутов, способ перебора задающих синтаксических шаблонов определяют полноту проверки реализации контекстных свойств тестами комплекта. Заметим, что процесс принятия решений и о полноте перебора структурирован; все решения явно фиксируются в процессе проектирования комплекта тестов. Это облегчает процесс модификации комплекта тестов и позволяет получать развиваемые комплекты. Развитие комплекта тестов может идти как в сторону более полной проверки контекстных свойств на основе уже созданной атрибутно-ориентированной модели, так и в сторону адаптации комплекта ~ тестов для контроля ,реализаций расширенных описаний языка.

Описанная методика была применена при создании комплекта В-тестов для контроля реализации контекстных свойств ФОРТРАНа-77. Использован перечень целевых предложений, полученный с помощью одной из методик ВТТ. Подробное описание комплекта и результаты его испытаний на трансляторах даны в приложении.

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

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

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

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

Сформулируем требования к транслятору, правильно реализующему контекстные сзойстза- - языка ■ программирования-.-■ Такой транслятор должен допускать (не выдавая диагностики) все синтаксически правильные программы, в которых каждой конкретной форме синтаксической конструкции соответствуют допустимые кортежи значений атрибутов и отвергать (диагностировать) все синтаксически правильные программы, в которых хотя бы одной форме синтаксической конструкции соответствует недопустимый кортеж значений атрибутов. Таким образом, комплекты тестов, предназначенные для контроля реализации контекстных свойств языка, должны включать тесты двух категорий: А (правильные программы) и В (неправильные программы).

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

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

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

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

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

В третьей главе диссертации обсуждаются применение атрибутно-ориентированной модели на этапе проектирования тестов и полнота получаемого комплекта тестов.

Этап проектирования тестов распадается на два подэтапа: получение по тексту стандарта перечня целевых синтаксических конструкций и проектирование групп тестов для проверки реализации контекстных свойств в рамках одной конструкции.

Первая задача решается применением к тексту стандарта одной из имеющихся в ВТТ методик. Полученные в результате цели формулируются относительно компонент некоторой целевой синтаксической конструкции-предложения (оператора либо объявления), для которой явно выписываются связанные с ней локальные ограничения.

Рассмотрим средства управления полнотой проверки выбранной цели.

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

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

1) Для атрибутов с бесконечным множеством значений выбирается представительное конечное множество значений.

2) Для зафиксированной синтаксической конструкции атрибуты делятся на два класса: существенные и несущественные. Решение о том, какие из атрибутов являются

стандартом) языковые средства и отменять часть ограничений стандарта. Транслятор строго расширенного языка должен:

-допускать и интерпретировать согласно стандарту согласованные со стандартом программы;

-допускать и интерпретировать согласно описанию расширения правильные программы, использующие дополнительные языхозыэ средства; з разряд правильных програ:«м могут входить программы, нарушающие требования стандарта, но

удовлетворяющие требованиям расширения;

| -отвергать программы, нарушающие требования описания расширения.

С точки зрения атрибутно-ориентированной модели, расширение языка сводится к следующим модификациям модели, построенной на основе стандарта:

1) добавить новый синтаксический класс со своим множеством атрибутов;

2) в множество атрибутов синтаксического класса добавить новый атрибут;

3) в множество значений атрибута" добавить новое значение;

4) в набор синтаксических шаблонов, задающих значение атрибута, добавить новый шаблон;

5) в набор глобальных ограничений, связанных с атрибутами синтаксического клайса, добавить новое глобальное ограничение;

6) удалить глобальное ограничение из соответствующего набора.

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

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

модифицированной модели не изменялись, часть тестов из построенного для стандарта комплекта является и тестами для расширения (все А-тесты и некоторые В-тесты).

Приложение содержит результаты применения описанной в диссертации методики проектирования тестов к языку ФОРТРАН-77. В него входят:

-фрагменты атрибутнс-ориентпрозаннсй модели ФОРТРАНа-77 с зафиксированной полнотой проверки реализации контекстных свойств для синтаксических объектов "имя", t "оператор", "выражение", "метка";

-примеры тестов, входящих в экспериментальный комплект тестов, построенный с использованием модели;

-результаты применения тестов комплекта к трансляторам ФОРТРАНа-77 на ЭВМ ЕС-1045 (транслятор FORTVS системы СЗМ) , Электроника-85 (FORTRAN PDP-11), IBM PC AT (FORTRAN Microsoft 5.0) .

В заключении сформулированы основные результаты диссертации:

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

2. Предложена методика проектирования комплектов тестов для контроля реализации контекстных свойств, обеспечивающая зафиксированную в модели языка полноту проверки. С использованием методики разработан комплект тестов для стандарта языка ФОРТРАН-77.

3. Предложена методика построения модели и комплекта тестов для расширений стандарта языка программирования путем пополнения имеющейся модели стандартизованного языка.

Основные результаты диссертации опубликованы в работах:

1.Ярко Л.В. Тестирование расширений стандарта ФОРТРАНа-77. В материалах школы семинара по проблемам расширяемых средстз программирования и методам оценки трансляторов. -Кишинев,1989.

2. Ярко Л.В. Об автоматизации проектирования комплектов тестов для контроля трансляторов. //Методы повышения качества программного обеспечения. -Владивосток: ДВО АН СССР, 1990.

Тираж 100 экз.