WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 || 3 |

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

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

На основании этих выводов была поставлена задача данной работы:

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

o Независимый от языка программирования синтаксис.

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

o Модульность описания структуры данных, которая обеспечивает повторное использование описания структуры данных.

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

• Разработать общую схему трансляции этого языка описания графовых структур в современные объектно-ориентированные языки общего назначения.

• Реализовать инструментальную поддержку этого языка, в число возможностей которой входят:

o Трансляция разработанного языка описания графовых структур в современные объектно-ориентированные языки общего назначения.

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

o Интеграция разработанного языка в широко используемые среды разработки программного обеспечения.

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

• Для языка TreeDL определены конкретный текстовый синтаксис и абстрактный синтаксис. Для определения абстрактного синтаксиса использован сам язык TreeDL.

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

• Набор типов вершин составляет тип графа. Тип графа может быть повторно использован при определении другого типа графов.

• Операции над графами определяются в виде мультиметодов над ограниченным набором типов – набором типов вершин графа.

Основой типовой системы языка TreeDL являются типы вершин графа, которые задаются как именованные записи (record)1. Запись состоит из набора полей, которые задают набор атрибутов и соседних вершин, допустимых для вершин данного типа. Для полей определены операции получения значения и установки нового значения, аналогично свойствам (properties) в языке C# или в связанной с языком Java технологии JavaBeans. Операции полей вершины составляют интерфейс типа вершин.

type VarDecl { Type varType;

string name;

} рис. 1. Пример типа вершины Язык TreeDL предоставляет набор предопределенных типов, соответствующий системе типов современных объектно-ориентированных языков:

bool char short int long float double string object node Тип node является дополнением к системе типов объектно-ориентированных языков общего назначения и отражает специфику графовых структур данных.

Этот тип позволяет среди всех объектных типов выделить типы вершин.

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

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

Этот тип данных часто называют структурой, возможно из-за ключевого слова struct, которое используется для обозначения таких типов данных в языке С. Чтобы не создавать конфликта с понятием структура данных, в этой работе используется термин запись (record).

enum Color { RED, GREEN, BLUE } enum Mono { BLACK, WHITE } enum BackgroundColor : Color, Mono { TRANSPARENT } рис. 2. Пример определения перечислимых типов Color, Mono и определения на их основе перечислимого типа BackgroundColor Описанные базовые возможности определения типов вершин графа не зависят от конкретного языка программирования. При необходимости использования типов данных языка программирования могут использоваться пользовательские типы, определенные на языке программирования. Определение таких типов относится к расширенным возможностям языка описания структуры графов TreeDL.

type File = { java.io.File } рис. 3. Пример определения пользовательского типа На основе существующих типов данных могут быть построены типовые выражения, которые могут быть использованы при определении типов вершин графа и операций над ними.

Пусть T – предопределенный тип, перечислимый тип, пользовательский тип или тип вершин. На его основе могут быть построены следующие типовые выражения:

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

Если тип не является ссылочным, поле хранит само значение.

• T – поле такого типа содержит необязательную ссылку на объект типа T.

Значением ссылки является объект типа T или специальное значение null. Для типов, которые не являются ссылочными, модификатор не меняет набора возможных значений.

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

• T* – список из 0 или более значений типа T.

• T+ – список из 1 или более значений типа T.

• T1:T2 – отображение, ключами которого являются значения типа T1, а значениями – значения типа T2.

Для поддержки жизненного цикла графа в языке 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 и C# в языке TreeDL допустимо множественное наследование, поскольку это позволяет более точно описывать структуру графа. Для разрешения известного конфликта, возникающего при множественном наследовании, независимо от количества путей в иерархии наследования, данные наследуются в одном экземпляре.

При наследовании типов вершин могут быть определены дополнительные поля и переопределены некоторые свойства унаследованных полей.

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

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

[ 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.обсуждается способ определения операций над графами.

Определение операций над графом в языке 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. Пример определения операции Операции над модулем описания структуры, который использует другие модули описания структуры, могут быть определены как расширение операций над используемыми модулями. При этом требуется определить только ветви операции, не покрытые расширяемыми операциями.

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

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

При проверке корректности определения этих операций возникнет сообщение об ошибке, что для этого типа вершин не определена ветвь операции.

Pages:     | 1 || 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»