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

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

имени М.В. Ломоносова факультет ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И

КИБЕРНЕТИКИ

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

Рагозин Алексей Сергеевич

Автоматическая генерация и исполнение программ по спецификациям на языке SDL

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

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

Научный руководитель: Кандидат физико-математических наук доцент H.H. Мансуров

Москва 1999

Оглавление

Введение 6

Глава 1. Языки формальных спецификаций и автоматическая генерация программ 10

1.1. Применение автоматической генерации программ по спецификациям 11

1.2. Основные понятия 13

1.2.1. Генерация программ 13

1.2.2. Свойства генерируемых программ 15

1.3. Языки формальных спецификаций 16

1.3.1. Язык SDL 16

1.3.2. Язык ASN.1 22

1.3.3. Язык LOTOS 22

1.3.4. Язык Estelle 23

1.3.5. Методология ROOM и система ObjecTime 23

1.3.6. Язык UML 24

1.4. Особенности автоматической генерации программ 25

1.5. Недостатки автоматической генерации программ 27

1.5.1. Снижение качества при автоматической генерации программ 27

1.5.2. Потребность в доводке сгенерированного кода 29

1.5.3. Императивность отображения 3 6

1.6. Оценка качества сгенерированных программ 3 8

1.7. Выводы 39 Глава 2. Концепция декларативных отображений для реализации

языков исполнимых спецификаций 40

2.1. Декларативные отображения 40

2.2. Достоинства декларативных отображений 43

2.2.1. Налядность генерируемого текста 44

2.2.2. Поддержка процесса разработки 44

2.2.3. Разработка генератора 46

2.3. Недостатки декларативных дотбражений 4 8

2.4. Выводы 50

Глава 3. Декларативное отображение для языка SDL 51

3.1. Особенности автоматической генерации программ для языка SDL 52

3.2. Предлагаемая схема генерации для языка SDL 54

3.2.1. Трансляционные преобразования SDL-спецификации 55

3.2.2. Особенности предлагаемого подхода 57

3.3. Основные решения по отображению 60

3.3.1. Объектная ориентация 60

3.3.2. Вложенные описания 60

3.3.3. Поэтапное определение 61

3.3.4. Шаблоны классов 62

3.3.5. Перегрузка операторов 63

3.3.6. С++-методы без ограничения на тип и количество параметров 63

3.3.7. Использование препроцессора 64

3.3.8. Объекты вместо классов 64

3.3.9. Статические члены классов 65

3.3.10. Внутреннее дерево структуры системы 65 3.3.11 .Взаимодействие СПЭВ и генерируемой программы 65 3.3.12. Нумерация объектов 66

3.4. Схема генерации структуры системы 67

3.4.1. Файловая структура сгенерированной программы 67

3.4.2. Отображение SDL структуры 70

3.4.3. Нумерация генерируемых объектов 73

3.4.4. Отображение SDL коммуникации 74

3.4.5. Пример 79

3.5. Схема генерации для тела SDL процесса 82

3.5.1. Пример 82

3.5.2. Генерируемые классы для SDL графа 84

3.5.3. Реализация графа 85

3.5.4. Операции в графе 88

3.5.5. Схема отображения данных 99

3.6. Отображение объектно-ориентированных расширений языка SDL 101

3.6.1. Структурные типы 102

3.6.2. Нсаледование структурных типов 103

3.6.3. Виртуализация 103

3.6.4. Параметризация структурных типов 105

3.7. Достоинства и недостатки декларативного отображения 106

3.7.1. Прямая поддержка трансформаций 106

3.7.2. Наглядность генерируемого текста 109

3.7.3. Гибкость настройки сгенерированных программ 109

3.7.4. Недостатки предлагаемого подхода 111

3.8. Выводы 112 Глава 4. Система поддержки этапа выполнения SDL системы 113

4.1. Предназначение СПЭВ 113

4.2. Принципы построения СПЭВ 114

4.3. Структура СПЭВ 117

4.3.1. Базове классы 117

4.3.2. Вспомогательные классы 124

4.3.3. Инициализационная часть 129

4.3.4. Функционирование системы 132

4.3.5. Интерфейс с платформой 136

4.3.6. Система отладки 137

4.4. Выводы 138 Глава 5. Оценка качества сгенерированных программ 139

5.1. Метрики качества сгенерированных программ

5.1.1. Статические метрики

5.1.2. Динамические метрики

5.2. Кодогенераторы для языка SDL

5.2.1. Кодогенератор системы SDT

5.2.2. Кодогенератор системы ObjectGeode

5.2.3. RASTA

5.3. Сравнительная оценка отображений для языка SDL

5.3.1. Рост объема

5.3.2. Сохранение структуры

5.3.3. Сохранение имен

5.3.4. Фрагментация

5.3.5. Использование имен

5.3.6. Производительность сгенерированных программ

5.4. Выводы Заключение Литература

ВВЕДЕНИЕ

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

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

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

В сфере телекоммуникационных приложений применяется целый ряд языков спецификаций. К ним относятся SDL, TTCN, Lotos, Estelle, ASN.l, ROOM, UML.

Язык спецификаций и описаний SDL является наиболее широко распространенным стандартом, утвержденным Международным Телекоммуникационным Союзом (ITU-T). Язык

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

Важнейшими достоинствами языка SDL являются:

• иерархическое описание структуры системы;

• описание поведения компонент системы в виде взаимодействующих конечных автоматов;

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

• объектная ориентированность;

• графическое представление;

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

SDL позволяет создавать детальные спецификации систем. Язык применяется не только для анализа и проектирования, но и для получения исполняемых программ. Таким образом, SDL позволяет значительно сократить время от выдвижения требований к системе до получения автоматически сгенерированных программ на машинно-ориентированном языке программирования. Существует достаточно много инструментальных систем, генерирующих по SDL-спецификациям программы на таких языках программирования как С, С++, CHILL и др. В то же время известно на удивление немного промышленных проектов с использованием SDL, где в конечном продукте использовался бы автоматически генерируемая программа: разработчики используют язык для анализа и проектирования систем, иногда для трассировки и верификации спецификаций, но само кодирование осуществляют вручную. Одна из основных причин такого положения состоит в недостаточно высоком качестве генерируемых программ, в сложности их адаптации к требованиям конкретного проекта.

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

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

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

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

В связи с вышесказанным значительный интерес представляет исследование методов автоматической генерации программ в целом и особенно в применении к языку спецификаций SDL. В диссертации обобщается опыт разработок SDL кодогенераторов. На этой основе

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

2) разрабатывается отображение, позволяющее генерировать программы на языке С++ по SDL-спецификациям;

3) рассматривается система поддержки этапа выполнения сгенерированных программ (СПЭВ);

4) применяется метод оценки качества отображения.

В диссертации разрабатывается так называемый декларативный подход к автоматическому синтезу программ. Декларативный подход позволяет в достаточно широких пределах управлять (варьировать) структуными свойствами сгенерированных программ. В данной работе основное внимание уделяется генерации максимально наглядных программ на языке С++ по спецификациям на языке SDL. Сущность декларативного подхода заключается в использовании исполняемых конструкций целевого языка для представления декларативный ыконструкций исходного языка с последующей перестройкой внутренней структуры целевой программы в самом начале ее исполнения на так называемом этапе <<раскрутки». Этап раскрутки является ключевым средством декларативного подхода. Его введение позволило

• вынести многие детали реализации за пределы сгенерированной части программы;

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

• упростить процесс проектирования отображения.

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

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

Цели диссертационной работы:

1) Исследование современного опыта автоматической генерации программ по спецификациям на языке SDL и выявление возможностей управления структурными свойствами сгенерированных программ.

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

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

4) Реализация системы поддержки этапа выполнения сгенерированных программ.

5) Применение метода оценки качества отображения для сравнения предлагаемого подхода с существующими аналогами.

Научная новизна:

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

2) Предложена и апробирована методика сравнения качества генерации программ по спецификациям на языке SDL.

3) Предложено прямое и полное отображение всех конструкций языка SDL стандарта 1992 года.

Практическая ценность:

1) Разработана схема отображения из языка SDL в гибкие, эффективные и наглядные программы на языке С++. На ее основе реализован генератор программ.

2) Разработана и реализована эффективная система поддержки этапа выполнения, обеспечивающая исполнение сгенерированных программ.

3) Проведена сравнительная оценка качества программ, сгенерированных несколькими кодогенериторами для языка SDL. Измерения показали, что предложенный подход приводит к существенному сокращению размера генерируемых программ и значительному улучшению их наглядности. Кроме того, в ряде случаев наблюдается повышение производительности сгенерированных программ (в среднем на 30%) по сравнению с некоторыми зарубежными аналогами.

Структура и объем диссертационной работы:

Диссертация состоит из введения, пяти глав, заключения,списка литературы, включающего 67

названий.Текст диссертации занимает 160 машинописных страниц.

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

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

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

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

В четвертой главе подробно рассматриваются принципы организации и структура системы поддержки этапа выполнения (СПЭВ) для программ, сгенерированных в соответствии с отображением, описанным в главе 3, по SDL-спецификациям

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

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

Основные результаты работы были получены автором самостоятельно.

Автор глубоко признателен H.H. Мансурову за начное руководство и поддержку работы на всех этапах ее выполнения.

ГЛАВА 1

Языки формальных спецификаций и автоматическая генерация программ

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