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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М. В. ЛОМОНОСОВА

НАУЧНО-ИССЛЕДОВАТЕЛЬСКИЙ ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

РГ8 ОД

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

6

ПАВЛОВ Михаил Владимирович

УДК 681.3.00

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

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

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

Москва 1994

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

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

кандидат физико-математических наук С. И. Рыбин.

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

доктор физико-математических наук, профессор Е. А. Жоголев,

кандидат технических паук, доцент Г. В. Пеледов. Ведущая организация —

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

Защита диссертации состоится « ^. » МОЯ? . 1994 г.

в .Ф. часов па заседании специализированного совета К.053.05.84 в МГУ по адресу: 119899, Москва В-234, Ленинские Горы, МГУ, научно-исследовательский вычислительный центр, конф.-зал.

С диссертацией можно ознакомиться в библиотеке НИВЦ

МГУ.

Ученый секретарь совета

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

Актуальность темы. К настоящему времени накоплен богатый опыт стандартизации языков программирования (ЯП). Разработаны и активно применяются стандарты ■ большинства промышленных языков программирования. Создаются метастандарты языковых стандартов.

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

Широкое распространение получают стандарты ЯП с развитым статическим компонентом (или иначе, набором статически проверяемых ограничений). Многие дефекты современных трансляторов для таких языков связаны с неправильным диагностированием ошибок в программах. Как показывает практика контроля языковых стандартов, тестированию диагностики трансляторов не уделяется должного внимания. Однако ущерб от отсутствия диагностики того или иного нарушения стандарта может оказаться катастрофическим. Особенно это верно для больших программных комплексов, к которым предъявляется требование повышенной надежности.

Существовавшую к началу работы ситуацию можно охарактеризовать следующим образом:

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

- методы и средства контроля конформности трансляторов, разработанные в рамках методики ВТТ (внешнего тестирования трансляторов), обладая несомненными достоинствами, не решали ряда проблем, связанных с созданием и использованием полных комплектов тестов;

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

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

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

которая расставила бы приоритеты, определила бы последовательность действий и критерии тестирования диагностики, предлагала бы решение проблемы опережающего создания средств контроля конформности (диагностики) для пересматриваемого стандарта.

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

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

(2) Методы опережающего создания средств контроля диагностики трансляторов и поиска ошибок в определении ЯП для пересматриваемого стандарта (на примере Проекта Ада-9Х).

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

\

Практическая ценность. Предложенная в диссертации концепция тестирования диагностики позволяет:

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

- осуществлять рациональную автоматизацию анализа результатов тестирования;

- разрабатывать средства тестирования диагностики трансляторов параллельно с созданием новой версии ЯП.

Методика опережающего создания средств контроля диагностики трансляторов для пересматриваемого стандарта ЯП дает возможность:

- максимально использовать методы и сродства контроля диагностики, разработанные для "старой" версии стандарта ЯП;

- выявлять дефекты в определении языка на фазе его совершенствования.

Мобильный аттестационный комплекс

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

- обеспечивает приемлем^ уровень надежности и автоматиза-

ции при работе с большим (более 1QOO тестов) комплектом тестов.

Мобильный аттестационный комплекс применяется в настоящее время для тестирования системы программирования Паллада, разработанной специалистами Санкт-Петербургского университета.

Апробация. Содержание и основные результаты диссертации докладывались на семинаре в ИнтерЗВМ (Москва. 1991), на научно-исследовательских семинарах по языкам программирования факультета ВМиК МГУ (Москва. 1992), по автоматизации программирования МГУ (Москва, 1992), на кафедре высшей математики Ивановского государственного энергетического университета (Иваново. 1993), на совместном семинаре отделов информационных систем и математического обеспечения НИВЦ МГУ (Москва, 1993), на научной конференции, посвященной 20-летип Ивановского государственного университета (Иваново, 1994).

Публикации. Основные результаты работы опубликованы в статьях [1), [2], [3].

Структура и объем диссертации.

Диссертация состоит из 4 глав, приложения, списка литературы (75 наименований) и заключения. Объем диссертации 165 страниц, в том числе приложений - 42 страницы.

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

В главе содержится краткий обзор области исследования. В нем изложены основные положения системно-динамической концепции стандартизации языков программирования, связанные с контролем конформности трансляторов, способы решения проблемы контроля на уровне ISO. Подробно рассматриваются проблемы стандартизации языка Ада. в том числе стратегия аттестации Лда-трансляторов в рамках AJP0-AV0 (служба аттестации Ада-трансляторов при Министерстве обороны США) и современное состояние Проекта Ада-9Х.

Цель» диссертационной работы является создание концепции тестирования диагностики трансляторов языков программирования с развитым статическим компонентом (на примере Алы). а также отра-

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

2. Во второй главе изложена концепция тестирования диагностики Ада-трансляторов.

Необходимость создания концепции следует из: (а) непригодности для практического применения существующих метастандартов ISO на методы и средства контроля конформности трансляторов стандартизованных языков программирования; (б) опыта применения методики внешнего тестирования трансляторов (ВТТ) для создания таких методов и средств; (в) реальной практической потребности в средствах контроля со стороны реализаторов и пользователей Ада.

Особенности предлагаемой концепции:

2.1. Диагностика трансляторов.

2.1.1. Особенности тестирования диагностики:

(а) диагностический эффект нечетко определен в стандартах ЯП (в т.ч. Ады). Его приходится сначала проектировать и только затем контролировать; (б) тестирование диагностики - это не только'обнаружение случаев несоответствия стандарту, но и оценка качества диагностики по 6 критериям (фильтрация, локализация, устойчивость, параметризация, классификация, понятность); (в) каиболее уязвимой и трудной для проверки является реализация контекстно-зависимых свойств ЯП. причем подавляющая часть таких нарушений должна обнаруживаться при статическом контроле.

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

2.2. Проектирование комплекта диагностических тестов.

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

2.2.2. Выбор критерия полнсты для построения комплекта осуществляется по результатам эксперимента для фрагментов комплекта, построенных по различным критериям полноты. Показаны высока., эффективность комплекта первого покрытия (КПП) и избыгочносп-

комплекта на базе частично-формализованных моделей диагностического эффекта (ЧФМ ДЭ).

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

2.4. Возможности автоматизации при тестировании диагностики:

- выделены этапы тестирования на базе комплекта первого покрытия (подготовка теста к прогону, трансляция теста, анализ результатов тестирования, отчет);

- разработан прототип лабораторного комплекса (инструментальных средств автоматизации тестирования) в виде принципиальной схемы;

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

- показано, что работоспособны относительно простые средства и усиление средств автоматизации нецелесообразно.

2.5. Опережающее создание средств контроля диагностики для пересматриваемого проекта стандарта Ада-9Х:

- необходимость опережающего создания средств контроля конформности (в частности, диагностики) Ада-9Х-трансляторов обусловлена принципами стандартизации языка Ада;

- усилия должны быть направлены на максимальное использование существующих методов (ЧФМ ДЭ, методика первого покрытия) и средств (КПП, МАК) контроля диагностики (для "старой" Ады) для:

а) создания средств контроля диагностики Ады-9Х;

б) анализа и совершенствования текста документов по Аде-9Х.

3. Третья глава посвящена изложению методики контроля диагностики трансляторов для пересматриваемого стандарта Ады (Проект Ада-9Х).

По крайней мере, три причины нацеливают нас на разработку

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

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

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

3.1. Схема перехода от комплекта для Ады-83 к аналогичному комплекту для Ады-ЭХ. Она состоит из следующих этапов.

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

3.1.2. Разработка переходной версии комплекта для ядра Ады-9Х! Предложено создать переходную версию комплекта тестов, которая была бы подмножеством существующего комплекта тестов для Ады-83 и состояла бы только из' тех тестов, для которых фрагменты контекстно-синтаксической модели (КСМ) не претерпели изменений в новой редакции стандарта. Современное состояние работ - отслеживание по документам Проекта фрагментов КСМ.

- 3.1.3. Выделение новых аспектов и свойств Ады-ЭХ и создание фрагментов КСМ для них.

3.1.4. Создание недостающих фрагментов комплекта по одной из методик, разработанных для расширений ЯП. Современное состояние документов Проекта Ада-9Х таково, что вопрос о выборе yate готовой методики, либо ее модификации или создании новой для построения недостающих фрагментов пока остается открытым.

3.1.5. Разработка комплекта тестов для ограничений периода связывания. Для ограничений периода связывания (С-ограничений). которые впервые вводятся в стандарт, существует принципиальная возможность построить комплект тестов по методике первого покры-

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

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

З.2. Вторым компонентом методики опережающего создания средств контроля' для пересматриваемого стандарта ЯП является распространение методики частично-формализованных моделей на поиск дефектов в рабочем определении языка Ада-9Х.

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

Методика ЧФМ предполагает согласование каждого шага построения модели с исходным неформальным определением языка (текстом стандарта на естественном языке). Методика позволяет строить неполные ЧФМ для отдельных аспектов языка, используя лишь существенные свойства изучаемых объектов, что дает возможность сосредоточиться на рассмотрении тех аспектов языка, вероятность обнаружения дефектов в которых наиболее велика.

В качестве объектов исследования нами выбраны принципиально новые аспекты Ады-9Х: защищенные записи-мониторы, библиотечные дочерние единицы, тэговые типы.

3.2.1. Контекстно-синтаксическая модель1 для параллельных конструктов в Аде-83 весьма проста. Основные проблемы, связанные с ними," лежат за пределами статической диагностики. Полученная из рабочих документов по Аде-ЭХ информация позволяет сделать вывод о том, что КСМ для защищенных записей в Дде-9Х так же не является сложной.

3.2.2. Библиотечные пакеты могут иметь дочерние библиотеч-

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

В рамках фрагмента ЧФМ ДЭ для проблем именования в Аде-83 была предложена модель полного контекста многомодульной программы, представляющая собой описание перехода от физической к логической структуре программы.

Для версии определения Ады-9Х установлено, что

- ЧФМ ДЭ для полного контекста для Ады-9Х может быть построена на базе уже существующей модели для Ады-83;

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

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

- обнаруженные Т2-ситуации представляют собой следствия из Т2-ситуаций для Ады-83 и из нового определения языка.

3.2.3. Понятие надклассового типа в Аде-9Х является обобщением понятия универсального типа в Аде-83. Вводится понятие надклассовых операций над объектами любого типа, принадлежащего классу. Существенная часть выразительной силы объектно-ориентированного программирования происходит icaic раз из возможности определять такие операции.

Вводится такте понятие тэгового (расширяемого по данным) типа. Наш интерес к тэговым типам обусловлен прежде всего тек, что в связи с введением этого конструкта существенно услояняется

операция преобразования типов.

В рассматриваемой версии Ады-9Х во время преобразования к расширению тэгового типа необходимо определить дополнительные компоненты. При преобразовании из расширенного типа к его менее "богатому" предку дополнительные компоненты теряются. Таким образом. преобразование типов, в отличие от Ады-83,' не всегда обратимо.

Для различных случаев преобразования тэговых типов введены два вида преобразования: view-преобразование, если не требуется доопределения новых компонентов, и conatructor-преобразсБание -в противном случае.

Проведенное исследование преобразования тэговых типов в Аде-9Х:

- позволило на основании построенной ЧФМ ДЭ выявить ряд существенных дефектов определения языка;

- потребовало построить наряду со статической 4JM ДЭ динамическую ЧФМ, поскольку определение вида преобразования типа оказывается рассредоточенным по всем этапам обработки программы;

- дало возможность при помощи динамической модели обнаружить в тексте языкового определения противоречие с концепцией универсального типа в Аде-83.

3.2.4. Построение фрагментов частично-формализованной модели рабочей версии определения языка позволяет: (а) найти в нем дефекты; (б) определить цели тестов, тем самым позволяя по фрагментам модели окончательной версии сразу строить фрагменты комплекта тестов.

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

МАК состоит из двух компонентов: комплект диагностических, тестов и инструментальный комплекс (ИК) для прогона к анализа результатов тестирования.

,4.1. Актуальная версия комплекта диагностических тестов первого покрытия содержит 1052 теста. Критерий первого покрытия выполнен для глав 2-12 и для не зависящего от реализации компонента главы 13 стандарта полностью.

Комплект диагностических тестов первого покрытия и КСМ реп-

лизованы совокупностью текстовых файлов, согласованным образом разбитых на фрагменты.

Комплект тестов удовлетворяет ранее сформулированным требованиям концепции тестирования диагностики Ада-трансляторов к автоматизации прогона тестов и анализа результатов тестирования.

4.2. В ИК выделены машинно-зависимый и машинно-независимый компоненты. Машинно-зависимый компонент отвечает за запуск целевого транслятора. Остальные модули относятся к машинно-независимому компоненту. Часть из них нуждается в настройке на параметры целевого транслятора.

4.3. Мобильность МАК достигается за счет выбора языка реализации и простых алгоритмов, на базе которых реализуется ИК.

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

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

'4.4. Различные версии МАК прошли лабораторные испытания на 7 Ада-трансляторах в 3 различных средах. Среди них было три транслятора, версии которых прошли аттестацию на тестах комплекта ACVC (официального комплекта тестов для аттестации Ада-трансляторов). Во всех них. включая аттестованные, были обнаружены десятки ошибок диагностики периода компиляции, за исключением транслятора VAX Ada. в котором удалось обнаружить лишь 4 ошибки. 2.наименее качественных транслятора оказались не в состоянии обработать ИК как функциональный тест. Результаты испытаний приведены в таблице 1.

4.5. Таким образом, ■ ■ .

(а) Разработана версия- МАК, которая яоляется минимальным

- i-a" -

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

(б) Опыт применения МАК показывает, что, во-первых, комплект первого покрытия в состоянии находить ошибки диагностики, не обнаруженные подсистемой диагностических тестов комплекта АСУС; во-вторых, уровень автоматизации работы' с комплектом вполне приемлем (на тестирование незнакомого транслятора требуется не более трех-четырех человеко-дней); в-третьих, сфера применения МАК - тестирование диагностики трансляторов, пригодных к аттестации.

(в) Сформулированы предложения по дальнейшему развитию МАК.

КОМПИЛЯТОР Глава стандарта Всего

г 3- 4 5 6 7 8 9 10 11 12 13

ARTEK 2 37 8 15 28 22 10 4 11 4 12 - 143

MERIDIAN 1 7 7 3 1 1 10 - 1 - - 5 36

JANUS - 5 9 - - - 1 - - - 1 - 16

VAX Ada 1 - 3 4 1

4 223 191 66 85 132 66 41 29 14 147 60 1052

Таблица 1.

Примечание. В последней строке таблицы приведено количество тестов в главе (комплекте).

5. Приложение содержит:

- частично-формализованную модель диагностического эффекта полного контекста;

- динамическую ЧФМ и ЧФМ диагностического эффекта преобразования тэговых типов;

- технологическую схему инструментального комплекса;

' - примеры фрагментов контекстно-синтаксической модели, комплекта диагностических тестов первого покрытия;

- таблицу результатов тестирования трансляторов с помощью комплекта первого покрытия;

- примеры обнаруженных дефектов трансляторов. '

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

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

(2) На основе предложенной концепции разработана методика создания средств контроля диагностики трансляторов для пересматриваемого стандарта языка Ада, состоящая из двух компонентов:

- схемы перехода от комплекта первого покрытия для Ады-83 к аналогичному комплекту для Ады-9Х;

- обогащенной методики ЧФМ, применяемой для анализа и совершенствования текста промежуточных версий языка программирования.

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

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

[1] Рыбин С.И., Павлов М.В. Комплект диагностических тестов для Ада-трансляторов: современное состояние. // Программирование, H 1, 1991, с. 81-83.

[2] Kaufman V., Pavlov M., Hybln S. The Testing oî Ada Compiler Diagnostics. // ACM Ada Letters, vol.13. no. 4 (July/August 1993). pp.71-76.

[3] Павлов M.B. Тестирование диагностики трансляторов языка Ада.' Элементы концепции. // Ивановский государственный университет - региональный центр гуманитарного образования. Тезисы научной конференции, посвященной 20-летию Ивановского государственного университета. - Иваново. 1994, с. 201-202.

■.iL^iiii .4

Подписано к печати 2.03.94 г. Формат бумаги 60x84 1/16.Печ.л. 0,75. Усл.п.л. 0,69. Ътоаж 100 экз. Заказ 661/р.

Tunorpa'fsm IT К ПК Минтопэнерго РФ, г. -Иваново, ул. Ермака, 41