Содержание к диссертации
Введение
1 Обзор области применения графов. методов их представления и обработки в компьютерных системах. постановка задачи 25
1.1 Использование графов в компьютерных системах 25
1.2 Области использования неоднородных графовых структур 27
1.3 Общие сведения 28
1.4 Основные методы описания структуры графов 29
1.4.1 Описание структуры текстовых документов 30
1.4.2 Описание структуры xml документов 31
1.4.3 Другие методы описания структуры графов 32
1.4.4 Описание структуры внутрипрограммного представления графов 33
1.4.4.1 Объектно-ориентированное представление данных 33
1.4.4.2 Гомогенное представление графа 34
1.4.4.3 Гетерогенное представление графа 36
1.4.4.4 Использование описания структуры текстового, xml или другого внепрограммного представления данных для описания структуры внутрипрограммного представления 42
1.4.4.5 Описание структуры внутрипрограммного представления графов на специализированных языках 44
1.5 Необходимые возможности языка описания структуры графов 45
1.5.1 Синтаксис языка 46
1.5.2 Типизация элементов структуры данных 48
1.5.3 Поддержка жизненного цикла графа 51
1.5.4 Определение операций над графами 53
1.5.5 Модульность описания структуры графов 54
1.5.6 требования к инструментальной поддержке 56
1.6 Постановка задачи 57
2 Язык описания графовых структур treedl 60
2.1 Синтаксис языка 60
2.2 Типы данных 61
2.2.1 Типы вершин 62
2.2.2 Предопределенные типы 63
2.2.3 Перечислимые типы 64
2.2.4 Пользовательские типы 66
2.2.5 Типовые выражения 66
2.2.6 Поддержка жизненного цикла графа 68
2.2.7 Дополнительная декларативная информация 69
2.2.8 Пользовательский код 71
2.2.8.1 Ограничения на значение отдельного поля 71
2.2.8.2 Ограничения на совокупность значений полей 72
2.2.8.3 Синтезируемые атрибуты 73
2.2.8.4 Поля с отложенным вычислением значения 74
2.2.8.5 Поддержка нескольких целевых языков программирования 75
2.2.9 Наследование типов вершин 76
2.3 Модули 81
2.4 Операции над графом 84
2.4.1 Определение операций над графом 84
2.4.2 Расширение определения операций 89
2.5 Пример использования языка treedl для описания графовой структуры -описание структуры абстрактного синтаксиса bnf грамматики 90
2.6 Общая схема трансляции 93
2.7 Основные результаты главы 93
3 Инструментальная поддержка языка treedl 95
3.1 Анализатор языка 96
3.2 Открытая платформа для обработки языка treedl 97
3.3 Запуск инструмента из командной строки 100
3.4 Интеграция со средой разработки eclipse 101
3.5 Общая структура библиотеки атр 103
3.6 Общая структура инструмента treedl 104
3.7 Основные результаты главы 106
4 Апробация языка treedl 108
4.1 Транслятор исполнимого подмножества языка спецификации rsl в процедурный fl3bikprotel 108
4.2 Транслятор спецификационного расширения языка java ill
4.3 Транслятор спецификационного расширения языка с# 114
4.4 Модуль интеграции транслятора спецификационного расширения языка со
средой разработки 116
4.5 Генератор тестов на основе моделей 117
4.6 открытый анализатор языка java для специализированной обработки и расширения языка 119
4.7 Основные результаты главы 121
Заключение 123
Благодарности 125
Литература
- Области использования неоднородных графовых структур
- Поддержка жизненного цикла графа
- Открытая платформа для обработки языка treedl
- Транслятор спецификационного расширения языка java
Введение к работе
Общая характеристика работы
Графы являются естественным и наглядным средством представления сложных структур. Это позволяет широко использовать их в компьютерных системах при решении различных задач. Во многих из этих задач графы используются для представления данных неоднородной структуры. К таким задачам относятся представление деревьев абстрактного синтаксиса программ в трансляторах языков программирования, описание структуры и обработки объектных моделей документов, обработка сложных структур данных предметной области в прикладных задачах и т.п.
Хорошо исследованы методы решения широкого класса задач на графах, изучены алгоритмы обработки графов, обеспечивающие эффективное решение этих задач. Однако для успешного решения задач на графах необходим не только правильный выбор алгоритма, но и такое представление графа в компьютерной системе, которое обеспечивает эффективную реализацию выбранного алгоритма обработки графа.
Алгоритм оказывает наибольшее влияние на эффективность решения задачи, а представление графа и способ реализации алгоритма определяют трудоемкость реализации и сопровождения. Естественно, возникает необходимость создания таких методов представления графов и реализации операций над ними, которые облегчают разработку и сопровождение программ, использующих графовые структуры данных.
Особенно важны такие методы при работе с графами, используемыми для представления неоднородных данных. Структура таких графов также может быть неоднородна и нагружена дополнительной информацией. Обеспечение заданной структуры графа и поддержание соответствия между структурой графа и определениями операций над ним в процессе разработки и развития
программы является одной из основных задач методов представления графов и реализации алгоритмов их обработки.
Существуют различные виды представления данных - внепрограммные (текстовое, XML, графическое представления, базы данных и т.п.) и внутрипрограммное. Внутрипрограммное представление является основным при обработке данных. Для описания структуры данных внутри программы используются языки программирования общего назначения. Однако возможностей языков общего назначения часто недостаточно для адекватного описания графовых структур данных и операций над ними. Это затрудняет реализацию и сопровождение, а также негативно сказывается на надежности программных систем, использующих графовые структуры данных.
Таким образом, актуальной задачей является разработка языков, обладающих специализированными возможностями для описания структуры графов и операций над ними.
Цели и задачи работы
Целью диссертационной работы являлась разработка метода описания графовых структур данных, применимого для решения таких задач как представление деревьев абстрактного синтаксиса программ в трансляторах языков программирования, описание структуры и обработки объектных моделей документов, обработка сложных структур данных предметной области в прикладных задачах и т.п.
Для достижения поставленной цели были поставлены следующие задачи:
Разработка специализированного языка описания структуры графов.
Реализация инструментальной поддержки этого метода.
Апробация этого метода и его инструментальной поддержки.
Методы исследования
При решении поставленных задач использовались следующие методы исследования: метод сравнений и аналогий, метод обобщений, методы построения формальных моделей и анализа их свойств.
При решении поставленных задач использовались следующие теории и подходы:
Методы объектно-ориентированного проектирования использовались как при анализе необходимых возможностей языка описания структуры графов, так и при разработке инструментальной поддержки этого языка.
Теория контекстно-свободных грамматик использовалась при разработке языка описания структуры графов.
Компонентный подход к разработке программного обеспечения использовался при реализации расширяемого транслятора языка описания структуры графов.
Научная новизна
В диссертации представлен новый метод описания графовых структур данных, основанный на использовании разработанного автором работы нового специализированного языка TreeDL и расширяемого транслятора этого языка.
Практическая значимость
Практическая значимость работы подтверждается успешным использованием различных версий языка TreeDL для описания структуры деревьев абстрактного синтаксиса программ в 1995-2005 годах в проектах по разработке:
Транслятора исполнимого подмножества языка спецификации RSL в
язык программирования PROTEL, в рамках проекта по тестированию на
основе формальных спецификаций ядра операционной системы,
выполненного для компании Nortel, Канада.
Транслятора спецификационного расширения языка Java в сам язык программирования Java, в рамках проекта по созданию инструментов автоматизированной разработки тестов для программ на платформе Java.
Транслятора спецификационного расширения языка С# в сам язык программирования С# и модели данных, создаваемой с помощью графического интерфейса пользователя, в рамках проекта по созданию инструментов автоматизированной разработки тестов для программ на платформе .NET.
Генератора тестов на основе моделей в рамках проекта ОТК по созданию методов и инструментов для тестирования оптимизирующих компиляторов.
Открытого анализатора языка Java в рамках проекта по дальнейшему развитию инструментов автоматизированной разработки тестов для программ на платформе Java.
Транслятора самого языка TreeDL в языки программирования Java и С#.
Разработанный язык описания структуры данных может использоваться при решении различных задач, в которых используются графовые структуры данных, в частности, при разработке трансляторов языков программирования, при описании структуры и обработки объектных моделей документов, разработке интерфейса пользователя по схеме Model-View-Controller, анализе и обработке моделей и сложных структур данных предметной области в прикладных задачах и т.п.
Апробация работы и публикации
По теме диссертации опубликовано 6 работ, представляющих основные научные результаты диссертации.
Основные положения работы обсуждались на
семинаре ВМиК МГУ им. М.В.Ломоносова в 1998 году;
конференции «Технологии Microsoft в научных исследованиях и высшем образовании» в июне 2003 года;
семинаре ИСП РАН в 2005-2006 годах;
семинаре ИПМ им. М.В.Келдыша РАН в октябре 2006 года.
Структура и объем диссертации
Диссертация состоит из введения, четырех основных глав, заключения, четырех приложений и списка литературы. Общий объем диссертации составляет 125 страниц. Список литературы содержит 97 наименований.
Краткое содержание работы
Во введении описываются цели и задачи работы, обосновываются её актуальность, научная новизна и практическая значимость. Также во введении приводится краткий обзор работы.
В первой главе содержится обзор области применения графов, видов представления и способов обработки графовых структур данных. Этот обзор является обоснованием актуальности темы работы. На основе анализа необходимых возможностей языка описания структуры графов формулируются цели исследования.
Во второй главе описан разработанный автором данной работы специализированный язык описания графовых структур TreeDL. При создании языка приняты следующие основные проектные решения:
Для языка TreeDL определены конкретный текстовый синтаксис и абстрактный синтаксис. Для определения абстрактного синтаксиса использован сам язык TreeDL.
Типы вершин и атрибутов графа задаются декларативно в объектно-ориентированном стиле с множественным наследованием. Механизм задания дополнительной декларативной информации обеспечивает расширение возможностей системы типов. Для императивного задания
контекстных ограничений используются блоки кода на языках программирования.
Набор типов вершин составляет тип графа. Тип графа может быть повторно использован при определении другого типа графов.
Операции над графами определяются в виде мультиметодов над ограниченным набором типов - набором типов вершин графа.
Основой типовой системы языка TreeDL являются типы вершин графа, которые задаются как именованные записи (record)1. Запись состоит из набора полей, которые задают набор атрибутов и соседних вершин, допустимых для вершин данного типа. Для полей определены операции получения значения и установки нового значения, аналогично свойствам (properties) в языке С# или в связанной с языком Java технологии JavaBeans. Операции полей вершины составляют интерфейс типа вершин.
type VarDecl {
Type varType;
string name; }
рис. 1. Пример типа вершины
Язык TreeDL предоставляет набор предопределенных типов, соответствующий системе типов современных объектно-ориентированных языков:
bool char short int long float double string object node
Тип node является дополнением к системе типов объектно-ориентированных языков общего назначения и отражает специфику графовых структур данных. Этот тип позволяет среди всех объектных типов выделить типы вершин.
Этот тип данных часто называют структурой, возможно из-за ключевого слова struct, которое используется для обозначения таких типов данных в языке С. Чтобы не создавать конфликта с понятием структура данных, в этой работе используется термин запись (record).
В языке TreeDL имеется возможность определения перечислимых типов, которые задаются явным перечислением множества именованных значений. Для удобства определения перечислимого типа введена возможность его определения на основе других перечислимых типов. Однако это отношение не является отношением наследования, поскольку не все значения перечислимого типа по смыслу являются значениями базовых перечислимых типов, на основании которых определен данный тип.
рис. 2. Пример определения перечислимых типов Color, Mono и определения на их
основе перечислимого типа BackgroundColor
Описанные базовые возможности определения типов вершин графа не зависят от конкретного языка программирования. При необходимости использования типов данных языка программирования могут использоваться пользовательские типы, определенные на языке программирования. Определение таких типов относится к расширенным возможностям языка описания структуры графов TreeDL.
type File = { Java.io.File }
рис. 3. Пример определения пользовательского типа
На основе существующих типов данных могут быть построены типовые выражения, которые могут быть использованы при определении типов вершин графа и операций над ними.
Пусть Т - предопределенный тип, перечислимый тип, пользовательский тип или тип вершин. На его основе могут быть построены следующие типовые выражения:
Т - поле такого типа хранит ссылку на объект типа Т. Такая ссылка является обязательной, то есть, в отличие от большинства языков
программирования, обязательно должна указывать на объект такого типа. Если тип не является ссылочным, поле хранит само значение.
Т ? - поле такого типа содержит необязательную ссылку на объект типа Т.
Значением ссылки является объект типа Т или специальное значение
null. Для типов, которые не являются ссылочными, модификатор ? не
меняет набора возможных значений.
Контроль использования null значения приводит к исчезновению или сокращению числа ошибок, связанных с попыткой доступа к объекту по ссылке, имеющей такое значение. В зависимости от возможностей целевого языка программирования, информация о запрете null значения может использоваться либо для статического анализа, либо для генерации проверок времени выполнения.
Т* - список из 0 или более значений типа Т.
Т+ - список из 1 или более значений типа Т.
Ті: Т2 - отображение, ключами которого являются значения типа Тх, а значениями - значения типа Т2.
Для поддержки жизненного цикла графа в языке TreeDL присутствуют следующие возможности:
Выделение в графе структуры опорного дерева.
Указание времени инициализации полей вершин.
Чтобы при создании вершины графа не нарушались требования, задаваемые типом вершины, необходимо, чтобы уже существовали все соседние вершины, связи с которыми являются обязательными. Построение графа, содержащего цикл, все связи в котором обязательные, невозможно без временного нарушения соответствующих требований типов вершин. Выделение опорного дерева, которое содержит все вершины графа, позволяет разбить построение
графа на два этапа: построение собственно опорного дерева и установка остальных связей между вершинами.
При выделении структуры опорного дерева тип корневой вершины дерева помечается модификатором root. Для хранения ссылки на родительскую вершину каждый тип вершин имеет предопределенное поле parent типа node, а поле вершины, предназначенное для хранения ссылки на дочернюю вершину, помечается модификатором child. Таким образом, между родительской и дочерней вершинами устанавливается двусторонняя связь.
root type CompilationUnit { }
type VarDecl {
child Type varType;
string name; }
abstract type Type { ... }
рис. 4. Пример выделения структуры опорного дерева
Указание времени инициализации полей позволяет выделить поля вершины, которые задают связи, не входящие в опорное дерево. Значения этих полей устанавливаются после создания вершины.
type VarExpr {
string name;
late VarDecl decl; }
рис. 5. Пример определения поздней связи decl
Для каждой сущности в описании структуры графа возможно указать дополнительную декларативную информацию. Это позволяет более детально описать структуру данных без изменения самого языка описания. Декларативная информация доступна на этапе обработки структуры графа и может быть использована инструментом обработки.
Хранение дополнительной информации непосредственно в описании структуры графа позволяет обойтись без дополнительных конфигурационных файлов.
Декларативная информация задается в виде набора именованных свойств булевского, целочисленного или строкового типов. Имена свойств являются квалифицированными идентификаторами, что позволяет избежать конфликтов имен.
В конце раздела 2.2 обсуждается механизм наследования типов вершин в языке TreeDL. В отличие от современных языков программирования Java иСІв языке TreeDL допустимо множественное наследование, поскольку это позволяет более точно описывать структуру графа. Для разрешения известного конфликта, возникающего при множественном наследовании, независимо от количества путей в иерархии наследования, данные наследуются в одном экземпляре.
При наследовании типов вершин могут быть определены дополнительные поля и переопределены некоторые свойства унаследованных полей. Переопределение может дополнять, уточнять или усиливать свойства поля, но не нарушать свойства, заданные ранее. Например, при переопределении можно потребовать инициализацию поля при создании вершины, если ранее этого не требовалось, но тип поля изменить нельзя.
В разделе 2.3 обсуждается поддержка модульности описания структуры графов в языке TreeDL. Описание структуры графа или его часть, имеющая самостоятельную ценность для повторного использования, оформляются в виде именованных модулей.
t treedl.language.Java ] structure ast.Variable;
type Type {
string name; }
type VarDecl {
child Type type;
string name; }
type VarExpr {
string name;
late VarDecl decl; }
рис. 6. Пример определения модуля
Модули могут использовать друг друга. Типы вершин используемых модулей могут применяться следующими способами:
Расширение - определение новых типов вершин, унаследованных от типов вершин используемого модуля.
Использование - определение в новых типах вершин полей, типы которых определены в используемом модуле.
Доопределение - добавление к определенным в используемом модуле типам вершин базовых типов вершин и полей.
Фактически, модуль описания структуры графа является самостоятельным типом данных, описывающим графы заданной структуры. В разделе 2.4 обсуждается способ определения операций над графами.
Определение операций над графом в языке TreeDL осуществляется с помощью мультиметодов. По сравнению с общим случаем определение мультиметодов на типах вершин графа позволяет преодолеть отсутствие контроля за определением специализации мультиметода для каждого возможного типа вершин. В случае определения операции над графом набор возможных типов вершин известен заранее, при анализе определения мультиметода может быть
проверена полнота определения, то есть наличие специализации мультиметода для каждого наследника типа его параметра.
Определение операции состоит из сигнатуры и тела. Сигнатура операции аналогична сигнатуре обычного метода и определяет имя, набор типов входных параметров и тип возвращаемого значения. В отличие от обычных методов, некоторые параметры операции могут быть помечены как виртуальные. Тип виртуального параметра может быть типом вершин, перечислимым или булевским типом.
Для каждого возможного набора фактических типов или значений виртуальных параметров должна быть определена своя реализация операции - ветвь операции. Возможными типами виртуального параметра, тип которого является типом вершин, считаются все неабстрактные наследники формального типа виртуального параметра, видимые в модуле определения операции, включая сам тип. Возможными значениями виртуальных параметров перечислимого типа являются все константы этого типа, булевского типа - значения true и false.
Ветвь операции состоит из метки и блока кода на языке программирования. Блок кода разделяется несколькими ветвями операции, метки которых находятся непосредственно перед блоком. Разделение блока кода несколькими ветвями операции является сокращением такой записи, когда каждой ветви операции соответствует своя текстуальная копия блока кода.
В зависимости от фактического типа или значения параметра выполняется блок кода, соответствующий ветви операции. После выполнения блока кода выполнение операции завершается, переход к следующему блоку кода не происходит, даже если оператор возврата управления в блоке кода отсутствует.
Семантика операции, единственным параметром которой является виртуальный параметр перечислимого типа, аналогична семантике конструкции switch языков программирования.
feature ast.ToString : ast.Variable;
operation string toString ( virtual node n ) { case ( Type n ) : case ( VarExpr n ): { return n.getName(); } case ( VarDecl n ):
{
return toString( n.getType () ) + " " + n.getName() ; } }
рис. 7. Пример определения операции
Операции над модулем описания структуры, который использует другие модули описания структуры, могут быть определены как расширение операций над используемыми модулями. При этом требуется определить только ветви операции, не покрытые расширяемыми операциями.
В рамках выбранного подхода, то есть без фиксации целевого языка программирования, полный контроль проблем, связанных с расширением модулей, осуществить невозможно, поскольку код на языке программирования не анализируется.
Исп ользование. _ описанного, _ способа, _ огщедел ения_ _ РЩШий. _ .над. _ графами ,пРРА0Л1ращает_ _возншшо
структуры,графа. Предположим, что в модуль описания структуры был добавлен новый тип вершин, который является наследником типа вершин, использованного в качестве типа виртуального параметра некоторых операций. При проверке корректности определения этих операций возникнет сообщение об ошибке, что для этого типа вершин не определена ветвь операции. Аналогичное сообщение возникнет при удалении типа вершины - в этом случае тип, используемый в метке ветви операции, окажется не определен.
ТрудоМОС1ь_ _в_нес?ния .изменений _ в_ реализацию _рпер_аций_ _пр_и .добавлении норШІ-ІШй-ЗРРШІ^-иешЛьиРЛШ'- если обработка нового типа вершины текстуально совпадает с одним из блоков, использующихся ветвями операции,
то достаточно перед этим блоком добавить метку ветви операции. Если требуется специальная обработка нового типа вершины, требуется реализовать её в новом блоке.
В завершение второй главы в разделе 2.5 приведен законченный пример использования языка TreeDL для описания графовой структуры. В качестве примера выбран абстрактный синтаксис широко известного формального языка описания BNF грамматики. В Приложении IV приведен более сложный пример - описание абстрактного синтаксиса самого языка TreeDL.
В третьей главе описана разработанная автором данной работы инструментальная поддержка языка TreeDL.
Для обработки описаний графовых структур данных на языке TreeDL разработан инструмент treed I, реализованный на языке Java.
Основным назначением этого инструмента является:
Анализ корректности описания структуры данных и операций над ними на языке TreeDL.
Генерация программного кода по описанию структуры данных на языке TreeDL, в частности трансляция описания структуры данных и операций над ними в язык программирования, а также генерация реализации операций, которые зависят только от структуры данных.
В завершение третьей главы сведены в таблицу размеры основных компонентов разработанного комплекта инструментов. Из таблицы видно, что сгенерированное описание абстрактного синтаксиса языка TreeDL составило около 15% общего количества строк разработанного вручную кода инструмента. Использование языка TreeDL позволило примерно в 5 раз сократить объем ручной работы по описанию абстрактного синтаксиса.
В четвертой главе анализируется опыт практического использования языка TreeDL. Различные версии языка описания абстрактного синтаксиса,
послужившие основой для языка TreeDL, были использованы в ряде проектов в 1995-2005 годах.
В 1996-1998 годах в рамках проекта по тестированию на основе формальных спецификаций был разработан транслятор исполнимого подмножества языка спецификации RSL в процедурный язык PROTEL.
Для реализации этого транслятора был разработан простейший формат описания дерева абстрактного синтаксиса и инструмент gentree для перевода этого описания в целевой язык программирования.
Сгенерированное описание абстрактного синтаксиса языка RSL составило около 25% общего количества строк разработанного вручную кода инструмента. Использование специализированного языка описания графовых структур данных позволило примерно в 10 раз сократить объем ручной работы по описанию абстрактного синтаксиса.
В 2000-2002 годах было создано спецификационное расширение языка Java и транслятор этого расширения в язык Java.
Для реализации этого транслятора с учетом опыта использования инструмента gentree был разработан язык описания абстрактного синтаксиса и инструмент ast, осуществляющий обработку этого описания и генерацию кода на языке Java. В язык описания абстрактного синтаксиса были добавлены возможности, которых не хватало при использовании инструмента gentree.
Сгенерированное описание абстрактного синтаксиса спецификационного
расширения языка Java составило около 30% общего количества строк
разработанного вручную кода инструмента. Использование
специализированного языка описания графовых структур данных позволило примерно в 15 раз сократить объем ручной работы по описанию абстрактного синтаксиса.
В 2002-2003 годах было создано спецификационное расширение языка С# и транслятор этого расширения в язык С#.
Сгенерированное описание абстрактного синтаксиса спецификационного
расширения языка С# составило около 18% общего количества строк
разработанного вручную кода инструмента. Использование
специализированного языка описания графовых структур данных позволило примерно в 6 раз сократить объем ручной работы по описанию абстрактного синтаксиса.
Возможностей языка описания структуры графов оказалось достаточно не только для описания абстрактного синтаксиса языков, но и для других задач. Одно из таких применений язык описания структуры графов нашел в проекте ОТК, целью которого являлась разработка методов и инструментов для генерации тестовых данных сложной структуры.
В проекте ОТК разработан способ итерации моделей, структура которых задана на языке TDL (который является ранней версией языка TreeDL). По каждой из полученных моделей строятся тестовые данные, соответствующие этой модели. Обычно тестовые данные представляют собой текст, который создается по модели при помощи той же техники генерации на основе шаблонов.
Отличие использования языка описания структуры данных в проекте ОТК от использования в проектах по разработке трансляторов в том, что описание абстрактного синтаксиса транслятора необходимо только разработчикам самого транслятора и не является неотъемлемой частью взаимодействия с пользователями, а в проекте ОТК язык TDL предлагается пользователям инструмента ОТК, разработчикам тестов. Такое использование предъявляет дополнительные требования к языку, его документации и инструментальной поддержке - введение дополнительного языка не должно создавать для пользователя значительных неудобств, связанных с изучением и использованием этого языка.
Успешное применение ОТК для создания тестов оптимизирующих модулей компиляторов, показало, в частности, что использование языка TDL не вызывает у пользователей затруднений при описании структуры данных.
Язык TreeDL используется для описания структуры абстрактного синтаксиса языка Java в проекте по созданию открытого анализатора языка Java. Результатом работы анализатора является граф абстрактного синтаксиса языка Java, который может быть использован для специализированной обработки языка Java.
Использование специализированного языка описания графовых структур данных позволило примерно в 12 раз сократить объем ручной работы по описанию абстрактного синтаксиса языка Java.
Области использования неоднородных графовых структур
Неоднородные графовые структуры являются мощным средством решения различных задач, в которых структура графа неоднородна и нагружена дополнительной информацией. Перечислим некоторые области, в которых применяются такие графы: Разработка трансляторов [10]. В качестве внутреннего представления входной программы используются деревья абстрактного синтаксиса. Визуальные языки [11]. Графы используются как представление визуальной модели. Для генерации кода по модели используются трансформации графов [12]. Представление структуры объектно-ориентированных систем. Графы являются естественным представлением объектов и связей в объектно ориентированных системах и могут быть использованы для верификации таких систем [13]. Представление и обработка сложных данных предметной области в различных прикладных задачах.
В этом разделе приведены общие определения, использующиеся в данной работе. Формальные определения приводятся в любой книге по теории графов [2,3,4,5]. Определение 1. Граф - это множество вершин, некоторые пары которых соединены ребрами. Вершины, соединенные ребром, называются смежными или соседними вершинами. Определение 2. Ориентированный граф - это граф, имеющий ориентированные ребра или дуги. Вершины, соединенные дугой, называют началом и концом дуги. Определение 3. Путь в графе - это последовательность вершин, в которой соседние вершины соединены ребрами. В ориентированном графе ребра ориентированного пути должны быть одинаково направлены. Определение 4. Связный граф - это граф, который для каждой пары вершин содержит путь их соединяющий. Определение 5. Цикл - это путь, в котором первая и последняя вершины совпадают. Определение 6. Дерево - это связный граф без циклов. Вершины дерева часто называют узлами. Узел дерева, из которого выходит ровно одно ребро, называется листом. Определение 7. Атрибутированный граф - это граф, с каждой вершиной которого связан набор атрибутов . Определение 8. Типизированный атрибутированный граф - это атрибутированный граф, каждая вершина которого имеет тип, определяющий структуру набора соседних вершин и структуру набора атрибутов, связанных с вершиной. Любой граф может рассматриваться как типизированный атрибутированный граф.
Методы описания структуры графов можно разделить в соответствии с видом представления данных, к которому они применимы. В следующих разделах рассмотрены методы описания структуры графов для наиболее распространенных видов представления данных: текстовое представление; XML представление; визуальное или графическое представление; базы данных; представление внутри программ. Эти виды представления используются не только для графов. Графам соответствуют только наборы данных, которые удовлетворяют описанной структуре.
Поддержка жизненного цикла графа
Специализированный язык может обладать возможностями для определения операций, как в общем случае, так и в широко распространенных частных случаях. К таким частным случаям относятся, например: Трансформация графа в соответствии с заданным набором правил. Каждое правило представляет собой шаблон и преобразования, которые необходимо выполнить над частью графа, которая этому шаблону соответствует [62,63]. Генерация текста по шаблонам, параметрами которых являются элементы графа {template engines) [48,53,64].
Как упоминалось в пункте 1.4.4.3, в общем случае операция над графом требует выполнения в каждой из его вершин определенных действий, зависящих от типа вершины. Эти действия могут быть реализованы набором виртуальных методов, либо с использованием шаблона проектирования Посетитель, либо с использованием мультиметодов. Всё это общие способы определения функциональности, при определении операций над графами они имеют свои недостатки. В специализированном языке определения структуры графов может быть сделана попытка преодолеть недостатки описанных способов определения операций за счет их адаптации на случай описания структуры графа. Основное отличие этого случая состоит в том, что набор возможных типов вершин известен заранее.
Модульность описания структуры графов
Одним из важнейших методов облегчения разработки и сопровождения программного обеспечения является повторное использование программных компонентов. Описание структуры графа или его часть, имеющая самостоятельную ценность, могут рассматриваться в качестве модуля, пригодного для повторного использования. Такая возможность может быть обеспечена средствами языка описания структуры графов, позволяющими явно определять модули и связи между ними.
Набор типов вершин модуля должен быть замкнут, то есть все используемые типы вершин должны быть определены в самом модуле, либо в используемых им модулях. В зависимости от способа описания типов вершин, используемые типы могут быть либо перечислены явно, либо должны быть заданы самим модулем. Первый случай соответствует определению типов в функциональном стиле или стиле BNF грамматики, когда альтернатива задает все возможные типы. Такой подход используется в Тт и Cocktail/AST. На рис. 13 приведен пример определения типа выражений Ехрг на языке Тт. Все возможные альтернативы перечислены явно.
Второй случай соответствует определению типов с наследованием в стиле объектно-ориентированных языков программирования. Вместо базового типа свободно могут использоваться любые типы наследники, которые определяются независимо. На рис. 14 показано определение того же типа Expr на языке treecc. Возможные варианты зависят от того, какой определен набор типов-наследников. %node Expr %abstract = {} %node VarExpr Expr = { string name; } %node AddExpr = { Expr left; Expr left; } %node ConstExpr Expr = { int value; } рис. 14. Неявное указание альтернатив типа выражений с помощью наследования
Таким образом, при использовании наследования для замыкания набора типов необходимо, чтобы возможные типы-наследники были перечислены в модуле.
Выделение группы типов в самостоятельную сущность языка программирования и определение отношений между группами предлагается в работах [70,71,72,73]. Такой подход позволяет справиться с проблемами расширения групп, плохо поддающимися решению в рамках языков программирования, система типов которых допускает наследование только на уровне отдельных типов.
Использование специализированного языка требует инструментальной поддержки. Для большинства упомянутых в этом обзоре языков разработаны инструменты, обеспечивающие трансляцию описания структур данных и операций над ними в язык программирования. Помимо собственно трансляции некоторые инструменты поддерживают реализацию операций, которые зависят только от структуры данных. К таким операциям относятся: сериализация/десериализация структуры данных для долговременного хранения; обход с возможностью выполнения заданных действий в каждой вершине; генерация документации; сравнение; глубокое копирование;
У пользователей специализированного языка может возникнуть потребность в расширении набора возможностей транслятора, например, с целью поддержки нового целевого языка программирования или новой операции над данными. Однако набор возможностей большинства инструментов ограничен и его расширение требует модификации исходных текстов. В работе [51] поставлена интересная задача создания для специализированного языка описания данных транслятора с открытой архитектурой, обеспечивающей легкое расширение функциональности. Частично такой подход реализован инструментами Тт и ANTLR/StringTemplate, поскольку соответствующие языки описания данных дополнены средствами генерации текста по шаблонам, что позволяет описывать схему генерации результатов, необходимых пользователю. Однако возможности этих инструментов ограничены генерацией данных, а возможны и другие направления расширения, например, создание специализированных анализаторов описания структуры данных.
Открытая платформа для обработки языка treedl
Платформа treedl.platform реализована с использованием библиотечного компонента atp.platform, который реализует общие механизмы работы с подключаемыми модулями - загрузку, передачу конфигурационных параметров, сбор диагностической информации и т.п.
Платформа использует анализатор языка TreeDL (treedl.analyzer) для построения дерева абстрактного синтаксиса входного описания структуры данных. Вся дальнейшая обработка абстрактного синтаксиса выполняется подключаемыми модулями. В частности, анализатор контекстных ограничений языка TreeDL (treedl.analyzer.checker, см. рис. 42) запускается подключаемым модулем treedl.plugin.checker.
Подключаемый модуль treedl.plugin.xref осуществляет генерацию описания структуры данных в HTML представлении, которое содержит перекрестные ссылки между использованием и определением сущностей. Это представление может быть использовано в качестве удобной документации.
Генерация программного кода на языках Java и С# осуществляется подключаемыми модулями treedl.plugin.java и treedl. plugin.csharp соответственно. Реализация этих модулей использует библиотечный компонент atp.generation обеспечивающий генерацию текста на основе шаблонов.
Эти подключаемые модули помимо трансляции описания структуры графа и операций над ним обеспечивают генерацию следующих компонентов: интерфейс Посетитель (Visitor) для вершин графа; пустую реализацию интерфейса Посетитель; реализацию интерфейса Посетитель, обеспечивающую глубокое копирование дерева; реализацию интерфейса Посетитель, обеспечивающую обход дерева в глубину с выполнением указанных действий в каждой вершине до и после обхода дочерних вершин; интерфейс Фабрика (Factory) для создания вершин графа; реализацию интерфейса Фабрика, которая создает вершины графа; пустую реализацию интерфейса Фабрика - используется в синтаксических анализаторах для прекращения построения дерева абстрактного синтаксиса при возникновении синтаксических ошибок;
Создание дополнительных подключаемых модулей не требует изменения исходных текстов платформы и существующих подключаемых модулей. Набор доступных подключаемых модулей определяется в конфигурационном файле платформы.
Традиционным интерфейсом запуска инструментов, обеспечивающим обработку в пакетном режиме, является запуск из командной строки. Такой интерфейс позволяет легко включить инструмент в цикл сборки программной системы, осуществляемый с помощью make [83,84], Ant [85,86] или Maven [87,88].
При реализации интерфейса командной строки treedl.main использован библиотечный компонент atp.main, осуществляющий разбор параметров командной строки, загрузку конфигурационных параметров, вывод диагностических сообщений на стандартные потоки вывода. Для непосредственной обработки описания структуры данных используется ранее описанная платформа treedl.platform обработки языка TreeDL.
В настоящее время при разработке программного обеспечения широко используются интегрированные среды разработки. Такие среды поддерживают весь цикл создания программы - создание, редактирование и навигацию по исходным текстам, трансляцию, выполнение, отладку и тестирование.
Специализированный редактор, поддерживающий создание, редактирование и навигацию по исходным текстам на некотором языке, тесно связан с анализатором этого языка. Анализатор языка предоставляет информацию о структуре исходных текстов, которая может использоваться для подсветки синтаксиса, выделения блочной структуры, навигации между связанными сущностями, согласованного преобразования исходных текстов (рефакторинга) и т.п. В фоновом режиме может производиться анализ исходных текстов и вывод диагностических сообщений.
Трансляция исходных текстов требует запуска транслятора с необходимыми параметрами, получения от него результатов трансляции и диагностических сообщений в формате, подходящем для среды разработки. Отладка на уровне исходных текстов требует от транслятора предоставления информации о соответствии между исходными текстами и результатом трансляции.
Для языка TreeDL разработан модуль интеграции с популярной средой разработки на платформе Eclipse [82]. Общая схема модуля интеграции показана на рис. 45.
Транслятор спецификационного расширения языка java
В 2000-2002 годах было создано спецификационное расширение языка Java [92] и транслятор этого расширения в язык Java.
В качестве языка реализации транслятора использовался язык Java. По сравнению с C/C++ этот язык обладает достаточно мощными механизмами общего назначения, в частности, автоматическим управлением памятью и более строгим контролем типов.
Для реализации этого транслятора с учетом опыта использования инструмента gentree был разработан язык описания абстрактного синтаксиса и инструмент ast, осуществляющий обработку этого описания и генерацию кода на языке Java.
В язык описания абстрактного синтаксиса были добавлены возможности, которых не хватало при использовании инструмента gentree. К этим возможностям относятся:
Предотвращает ошибочное создание вершин, тип которых должен использоваться только для создания на его основе других типов вершин.
Задание__ _имени__ .соседних. _ .вершин _ _ _и _ _ А"Щибу_тов. Использование осмысленных имен для соседних вершин и атрибутов позволяет снизить количество ошибок, связанных с неправильным использованием значений одного типа.
Жние__до_чернюс__верш Это дает возможность автоматически устанавливать в дочерних вершинах обратную ссылку на родительскую вершину.
Это позволяет контролировать, какие поля вершины, которые должны быть инициализированы при её создании.
Зададие_режима доступа _к .атвибуту.. Атрибут может быть объявлен как доступный только для чтения. Это снижает количество ошибок, связанных с несанкционированной модификацией полей вершины.
Рлределшие__п_ег2ечислимых__тш Ранние версии языка Java не содержали конструкции определения перечислимых типов, использование языка описания структуры данных позволило справиться с этим неудобством.
Задание,дользов_ат_едьскогр__кода в определениях операций доступа к полям вершины, в конструкторе и теле типа вершины. Это позволяет задавать дополнительные ограничения на соседние вершины и атрибуты, как в целом, так и по отдельности.
Это дает возможность определять операции над графом без изменения классов, соответствующих типам вершин.
Этот язык уже обладал основными возможностями описания структуры данных, присутствующими в языке TreeDL, но не предоставлял способа определения операций. Операции над деревом реализовывались средствами языка программирования с использованием шаблона проектирования Посетитель. Недостатки этого способа описаны в пункте 1.5.4. Некоторые конструкции языка описания структуры данных зависели от целевого языка программирования, поэтому трансляция в языки отличные от Java вызвала бы необходимость изменения языка описания структуры данных.
Инструмент ast по сравнению с gentree обладал следующими дополнительными возможностями:
Открытая __арх_итектур_а, позволяющая расширять функциональность инструмента с помощью подключаемых модулей. в виде HTML представления описания структуры данных, которое содержит перекрестные ссылки между использованием и определением сущностей.
ФорматиррвАние_опис_ания_структуры данных.
Генерация .базовых г2еали_змий_шабшзна_Посетитель - не выполняющей никаких действий и осуществляющей глубокое копирование дерева.
Гмерапия _текста_ н_а_ізснрв_е_ шаблонов. Для широко распространенного вид операций над деревом - генерации текста, в частности кода на языке программирования - была создана библиотека, позволяющая создавать кодогенераторы на основе шаблонов, параметризованных именами полей типов вершин.
Архитектура инструмента ast уже обладала основными достоинствами архитектуры инструмента treed I: открытым интерфейсом анализатора языка и возможностью расширения функциональности подключаемыми модулями. Структура дерева абстрактного синтаксиса, которое строилось анализатором языка ast, была описана на самом языке ast.
Размер реализации инструмента ast вместе подключаемыми модулями, осуществляющими генерацию кода на языке Java, и библиотекой поддержки составил около 8000 строк на языке Java. Размер описания абстрактного синтаксиса самого языка ast, используемый при расширении инструмента -около 200 строк.
Использование явного описания абстрактного синтаксиса спецификационного расширения языка Java существенно уменьшило взаимные зависимости основных компоненты транслятора: синтаксического анализатора, анализатора контекстных ограничений и кодогенератора. Уменьшение зависимостей между этими компонентами позволило вести их разработку одновременно разными разработчиками, что сократило сроки реализации транслятора и упростило его сопровождение.
Количество типов вершин в дереве абстрактного синтаксиса спецификационного расширения языка Java - 205, из них 145 соответствуют конструкциям языка Java, 14 - дескрипторам семантических сущностей языка. Размер описания абстрактного синтаксиса спецификационного расширения языка Java - около 1500 строк. Размер сгенерированного кода - около 22000 строк.
Общий объем разработанного вручную кода транслятора спецификационного расширения языка Java в язык программирования Java составил около 50000 строк, из них около 6000 строк - грамматика спецификационного расширения языка Java для генератора синтаксических анализаторов JavaCC, общий объем кода проекта - около 72000 строк.
Таким образом, сгенерированное описание абстрактного синтаксиса спецификационного расширения языка Java составило около 30% общего количества строк разработанного вручную кода инструмента. Использование специализированного языка описания графовых структур данных позволило примерно в 15 раз сократить объем ручной работы по описанию абстрактного синтаксиса.
