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

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

ШАРОВ ОЛЕГ ГЕННАДЬЕВИЧ

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

05 13 12 — Системы автоматизации проектирования (промышленность)

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

003065854

Работа выполнена на кафедре "Вычислительная техника" Ульяновского государственного технического университета

Научный руководитель кандитат технических наук, и о профессора

АФАНАСЬЕВ АЛЕКСАНДР НИКОЛАЕВИЧ

Официальные оппоненты доктор технических наук, профессор,

МИХЕЕВ МИХАИЛ ЮРЬЕВИЧ

Ведущая организация ФНПЦ ОАО "НПО МАРС"

Защита состоится " 10 " октября 2007 г. в 15:00 на заседании диссертационного совета Д 212 277 01 при Ульяновском государственном техническом университете, ауд 211

Отзывы в двух экземплярах, заверенные печатью, просим направлять по адресу 432027, г. Ульяновск, ул. Северный Венец, д 32. УлГТУ, ученому секретарю совета Д 212.277 01

С диссертацией можно ознакомиться в библиотеке Ульяновского государственного технического университета

Автореферат разослан " 7 " сентября 2007 г.

доктор технических наук, доцент,

КИСЕЛЕВ СЕРГЕЙ КОНСТАНТИНОВИЧ

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

диссертационного совета

доктор технических наук, профессор

/

Г

М К Казаков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы. В последнее время при проектировании средств вычислительной техники, автоматизированных систем активно используются графические представления спецификаций, поскольку они предлагают более удобные способы изложения данных, процессов и т п Так, функциональные описания представляют диаграммами потоков данных (DFD), в рамках стандарта SDL или методологии IDEF0 Для описания информационных моделей наибольшее распространение получили диаграммы сущность-связь (ERD), в которых предусмотрены средства для описания сущностей, атрибутов и отношений Стандартной методикой построения таких диаграмм является IDEF1X Поведенческие модели представляют в виде граф-схем, диаграмм переходов состояний (STD), сетей Петри Объектный подход представлен унифицированным языком моделирования (UML), стандартом SDL-2000 и методологией IDEF4 Для описаний архитектур автоматизированных систем используются языки xADL 2 0, Darwin, UML

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

1 Известные методы синтаксического анализа и преобразования ДГЯ обладают значительными затратами по времени (экспоненциальные, полиномиальные характеристики) и памяти

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

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

4 Практически не развиты автоматизированные средства создания схем анализа и схем синтаксически ориентированной трансляции диаграмм графических языков

Вышеизложенное обуславливает актуальность задачи исследования методов и средств реализации диаграммных графических языков (ДГЯ) САПР

Целью диссертационной работы является расширение возможностей методов и средств реализации ДГЯ САПР за счет разработки автоматных методов анализа и преобразования ДГЯ, позволяющих сократить время анализа, затраты памяти, обладающих необходимой полнотой контроля, а также синтаксически - ориентированных программ их поддержки

В соответствии с поставленной целью в работе формулируются и решаются следующие задачи исследования

1 Анализ существующих подходов синтаксического анализа и синтаксически - ориентированной трансляции ДГЯ

2 Разработка метода анализа ДГЯ о временной сложностью анализатора не превосходящей сложность существующих аналогов и обеспечивающего необходимую полноту контроля

3 Разработка метода синтаксически ориентированной трансляции ДГЯ в текстовые и графические формальные представления

4 Разработка информационного и программного обеспечения, позволяющего производить синтаксический анализ ДГЯ, их синтаксически - ориентированную трансляцию в другие формы (текст, графика)

Объектом исследования является автоматизация процесса обработки ДГЯ САПР

Предметом исследования является разработка комплекса методов анализа и трансляции ДГЯ, программных средств, обеспечивающих автоматизацию обработки ДГЯ

Методы исследования основаны на использовании положений и методов теории алгоритмов, теории множеств, теории графов, теории автоматов, теории формальных языков, - теории графических языков, теории параллельного программирования, а также использовании основ системотехники и теории автоматизированного проектирования

Научная новизна определяется разработанными методами анализа и преобразования ДГЯ САПР, основу которых составляет предложенное семейство автоматных ¡IV - грамматик

В результате проведенных исследований получены следующие научные результаты

1 Предложен новый метод синтаксического анализа диаграмм графических языков на основе автоматной графической грамматики (ГО/ - грамматики), отличающийся от известных линейной временной характеристикой анализа, малыми затратам памяти Метод обеспечивает полноту контроля и позволяет создавать метаописания неструктурированных ДГЯ и ДГЯ, содержащих параллелизм

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

ошибок, тем самым сократить время проектирования корректных диаграмм

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

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

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

1 Разработанный анализатор графических схем алгоритмов, являющийся расширением для графического редактора Microsoft Visio

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

3 Разработанная архитектура системы реализации ДГЯ., предлагающая полный набор функциональности для построения и редактирования диаграмм различных ДГЯ, средств их анализа и преобразования в тектовые и/или графические представления Компоненты системы позволяют

а) формировать библиотеки примитивов ДГЯ, нагруженные описанием взаимодействия в реализуемых диаграммах,

б) строить схемы анализа в виде трех вариантов авторской автоматной графической грамматики (RV / RVN / RVH -грамматики),

в) ставить в соответствие графические или тектовые языки графическому языку посредством использования авторской автоматной транслирующей грамматики, (RVT - грамматики), для целевого текстового языка - RVTt - грамматика, а для целевого графического языка - RVTg - грамматика,

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

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

Разработаны компоненты системы

На реализованные программные средства получено шесть СВИДЕТЕЛЬСТВ (РОСПАТЕНТ) об официальной регистрации программы для ЭВМ № 2003612553, 2005610662, 2005611312, 2005611314, 2007611772, 2007611773

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

1) учебный процесс Ульяновского государственного технического университета (г Ульяновск),

2) учебный процесс Ульяновского института повышения квалификации и переподготовки работников образования (г Ульяновск),

3) процесс подготовки производства ОАО "Автодеталь-Сервис" (г Ульяновск),

4) проектный процесс ООО "Микро" (г Ульяновск),

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на следующих международных и региональных конференциях 7-ой международной научно-технической конференции "Интерактивные системы Проблемы человеко-компьютерного взаимодействия / ИС-2007", г Ульяновск, 2007, Международной "Конференции по логике, информатике, науковедению (КЛИН-2007)", г Ульяновск, 2007, VII Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям, г Красноярск, 2006, Международной конференции "Континуальные алгебраические логики, исчисления и нейроинформатика в науке и технике с.(КЛИН-2005)", г Ульяновск, 2005, Международной конференции "Интерактивные системы Проблемы человеко-компьютерного взаимодействия 2003", г Ульяновск, 2003, Ежегодных внутривузовских конференциях профессорско-преподавательского состава., г Ульяновск, 2002, 2003, 2004, 2005, 2006, 2007

Публикации По теме диссертации опубликовано 13 печатных работ, в том числе две в журналах списка ВАК Получено шесть СВИДЕТЕЛЬСТВ (РОСПАТЕНТ) об официальной регистрации программ для ЭВМ № 2003612553, 2005610662, 2005611312, 2005611314, 2007611772, 2007611773

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность исследуемой проблемы, сформулированы цель и задачи диссертационной работы, перечислены полученные в диссертации новые результаты, их практическая ценность, представлены положения, выносимые на защиту и описана структура диссертации

В первой главе "Использование и реализация диаграммных графических языков в САПР" проводится анализ предметной области исследований Рассматриваются ее основные понятия "проектная деятельность", "проектирование технического объекта", "системный подход в проектировании", а также рассматриваются обобщенные подходы к проектированию и структурные элементы процесса проектирования

Определяется возможность использования ДГЯ на этапах проектирования средств вычислительной техники, автоматизированных систем Проводится соответствие ДГЯ аспектам описания системы

Даются основные понятия теории графических языков Подробно описаны структурные особенности графических языков, группы свойств элементов графических языков (графические, синтаксические, семантические) и их назначение Проведен анализ распространенных ДГЯ САПР (UML, SDL, IDEFO, IDEF1X, DFD), представлены алфавиты языков, раскрыты особенности реализации диаграмм для каждого из языков

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

Проводится анализ современных инструментальных средств САПР для работы с ДГЯ, описаны подходы и методы их реализации Определены основные типы графических редакторов, как основного визуального инструмента проектировщика, сформированы требования к ним, указаны области применения каждого из них

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

Во второй главе "Разработка и исследование графической грамматики ДГЯ САПР" предлагается комплекс методов синтаксического контроля диаграмм графических языков, которые можно обобщить в семейство автоматных графических грамматик

1 ИУ - грамматика, обеспечивающая анализ диаграмм графических языков, в том числе и неструктурированных

2 КУИ - грамматика, построенная на базе формализма КУ -грамматики и обеспечивающая нейтрализацию ошибок

3 КУН - грамматика - иерархическая грамматика, обеспечивающая анализ диаграмм структурированных языков с минимальными затратами памяти

ЕУ - грамматика языка Ь (в) определяется как упорядоченная пятерка непустых множеств б = (V, Е, Е, К, го), где

• V = {гуе, е = вспомогательный алфавит (алфавит операций над внутренней памятью),

• Е = {04, £ = 1,Т} - терминальный алфавит графического языка, являющийся объединением множеств его графических объектов и связей (множество примитивов графического языка),

• Е = {щ, г = 1,Г} - квазитерминальный алфавит, являющийся расширением терминального алфавита Алфавит Е состоит из квазитермов графических объектов, графических объектов имеющих более одного входа, связей - меток с определенными для них семантическими различиями и квазитерма, определяющего отсутствие связей - меток,

• Я = {гг, г = 0,/} - схема грамматики С (множество имен комплексов продукций, причем каждый комплекс гг состоит из подмножества Ргз продукций гг = 2 = 1,7}),

• го 6 Я - аксиома КУ - грамматики (имя начального комплекса продукций), г к ей - заключительный комплекс продукций

Продукция Рг] е гг имеет вид _гу щ-> гт, где

• (71, , 7п) - п - арное отношение, определяющее вид операции над внутренней памятью в зависимости от V е {0,1,2,3},

• - оператор модификации, определенным образом изменяющий вид операции над памятью, причем р, € {0,1,2},

• гт£ 12 - имя комплекса продукции - преемника

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

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

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

КУИ - грамматика является расширением ¡IV - грамматики за счет нейтрализации ошибок, которая позволяет сократить время получения качественной синтаксически - корректной диаграммы

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

1 Квазитерминальный алфавит расширяется квазитермами графических объектов - продолжателей анализа и квазитермом для проверки их наличия Множество объектов - продолжателей анализа формируется проектировщиком на этапе синтеза грамматики Такие квазитермы необходимы для обработки событий "первичного" и "вторичного" анализа объекта

Эти события возникают в следствие следующих типов переходов к графическому объекту во время анализа естественного перехода от связи к графическому объекту, выбора данного объекта, в качестве продолжателя анализа

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

Иерархическая КУ - грамматика (КУН - грамматика) в качестве символов, помечающих дуги графа БУ - грамматики, позволяет использовать не только терминальные (квазитерминальные) символы, но и нетерминальные символы, обозначающие сложные синтаксические конструкции, наличие которых необходимо, чтобы переход по дуге в следующий комплекс был допустим В качестве нетерминальных символов могут выступать имена комплексов продукций, а в качестве самих комплексов - другие ЫУ(Н) - грамматики (их можно называть подграмматиками) Для организации работы по БУН - грамматике используется стековый механизм аналогичный тому, который применяется при вызове подпрограмм из основной программы с последующим возвращением в основную программу Продукция, в левой части которой находится нетерминал, выполняется следующим образом Имя комплекса

- преемника запоминается в стеке, а управление передается комплексу

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

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

Использование стекового механизма ЕУН - грамматикой позволяет сократить издержки памяти, но сужает ее применение в рамках структурированных графических языков

Приведенные в главе сравнительные характеристики анализаторов графических языков показывают несомненное превосходство БУ -анализатора Так, временная сложность анализа графических языков по КУ - грамматике является линейной, зависит от числа анализируемых объектов и не достигает двойного количества элементов содержащихся в диаграммы, в то время как другие формализмы имеют полиномиальную, либо экспоненциальную оценку временной сложности анализа Для КУТС -грамматики, где вносится поправка на возможные ошибки в диаграмме, время анализа не достигает тройного количества используемых в ней элементов Следует отметить, что для ИУ - формализмов указана верхняя оценка, для каждого языка она рассчитывается индивидуально, но не превышает указанного значения Затраты памяти при работе КУ -анализатора в среднем в 5 раз меньше существующих аналогов При этом качество анализа не страдает, авторский анализатор обнаруживает как топологические ошибки, так и некоторые семантические ошибки (например, для алгоритмических языков зависание, неоднозначность, дедлок)

В третьей главе "Исследование методов семантического анализа ДГЯ САПР Разработка транслирующей 'грамматики" рассматривается вопрос семантического контроля ДГЯ, обобщается существующий опыт по данному вопросу и предлагается метод формирования семантического значения диаграмм графических языков на базе авторской автоматной транслирующей грамматики (КУТ - грамматики)

Подавляющее большинство ДГЯ САПР, анализ которых был приведен в первой главе, являясь синтаксически формальными не являются семантически формальными Такие языки гибки и позволяют строить диаграммы, которые могут быть применены в различных предметных областях

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

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

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

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

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

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

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

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

Для реализации этого подхода предлагается транслирующая RVT -грамматика, позволяющая производить синтаксически - ориентированную трансляцию диаграмм графического языка в текстовые и/или графические формальные описания Для повышения эффективности реализации инструментальных средств на базе RVT грамматики вводится два типа RVT - грамматик

1 RVTt - грамматика Грамматика, для которой целевым является текстовое формальное описание (программы на языке программирования, текст на специфичном языке разметки и т п )

2 RVTg - грамматика Грамматика, позволяющая формировать выходные цепочки в терминах графических языков

RVT - грамматика является развитием RV - грамматики Продукции схемы RVT - грамматики расширены для хранения в них терминов целевого формального описания, внутренняя память содержит информацию, необходимую для процесса трансляции

RVTt - грамматикой языка L (G) называется упорядоченная семерка непустых множеств G = (У, U, Е, Е, М, R, tq)

Множества V, Е, Е, R, Го наследуются от RV - грамматики и используются для определения синтаксической корректности анализируемой диаграммы Множества U,M необходимы для придания грамматике транслирующих функций (U = {ve, е = 1 ,К} - алфавит операций над внутренней памятью, используемый целевым языком, М = ТТ U TN - объединение алфавитов терминальных (ТТ) и нетерминальных (TN) символов целевого языка) Продукция Р„ 6 гг имеет вид

„ ЗДИ-Чть , 7n)]{ep[W„(71, ,-Уп)]} г ,

Ргз 0,t -rm{x}, где

• Ци (©/i) ~ оператор модификации, определенным образом изменяющий вид операции над памятью базового (целевого) языка, причем ¡л е {0,1,2},

• остальные элементы продукции были рассмотрены ранее (см определение RV - грамматики)

Методика построения RVTt - грамматики расширяется на фазе синтеза следующими этапами

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

2) определение операций над внутренней памятью для элементов целевого языка

На этапе анализа устранение недетерминированности и неопределенности производится по аналогии с соответствующими операциями RV - грамматики Задача минимизация грамматики претерпевает некоторые изменения Для RVT грамматики она заключается в циклическом применении двух типов минимизаций минимизация количества состояний, минимизация отображений

Этап минимизации количества состояний соответствует этапу минимизации RV - грамматики Однако, в данном случае эквивалентными состояниями считаются состояния, у которых кроме одинаковых продолжений распознаваемой цепочки справа и операций над внутренней памятью одинаковыми являются транслирующие операции над внутренней памятью и отображения в терминах целевого языка Сама процедура минимизации остается неизменной

Минимизация отображений предполагает поиск и свертку

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

1) выделение эквивалентных фрагментов (цепочек или подцепочек) отображений и назначение каждому классу эквивалентности нового нетерминального символа,

2) замена эквивалентных фрагментов соответствующими нетерминальными символами

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

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

RVTg - грамматика языка L (G) определяется упорядоченной восьмеркой непустых множеств G = (V, U, S, £,M,F, R, г0), где F = {generate__mput(), generate __output(), stick _amnection_points(), select _output()} множество функций обработки элементов

терминального и нетерминального алфавита целевого языка, назначение остальных множеств аналогично назначению множеств RVTt -грамматики

RVTg - грамматику является расширением RVTt - грамматики для ДГЯ Она наследует правила формирования продукций грамматики, а также все этапы фаз синтеза и анализа грамматики Отличием является то, что элементы множества М - это графические примитивы Некоторые из них, а именно, графические объекты, содержащие более одного входа или выхода, могут быть нагружены транслирующими функциями из множества F для обеспечения соответствия входов и выходов таких объектов базового и целевого языков

Назначение транслирующих функций и выполняемые ими операции

1 generate_injmt{) - генерация точек соединения для входящих связей Выполняется при первичной анализе графических объектов, содержащих более одного входа

2 generate_output() - генерация точек соединения для исходящих связей Выполняется при первичной анализе графических объектов, содержащих более одного выхода

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

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

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

Входящие точки, отличные от той по которой анализатор достиг графического объекта, при первичном анализе обрабатываются функцией generate jinputQ, при вторичном анализе на базе ее результатов выполняется связывание фрагментов диаграммы, выполненной в терминах целевого языке, применением функции sttck_connectwn_pomts()

В четвертой главе "Разработка программных средств реализации ДГЯ САПР" рассматриваются авторские разработки анализатор графических схем алгоритмов, синтаксически - ориентированный графический редактор и система реализации ДГЯ САПР

Реализация анализатора графических схем алгоритмов показывает возможность внедрения методов контроля на базе RV - грамматики в универсальные графические редакторы, в данном случае Microsoft Visio 2002 Представлено описание внедренного в Visio анализатора и схема его работы

Синтаксически - ориентированный графический редактор

является специализированным векторным графическим редактором предназначении для построения и редактирования параллельных графических схем алгоритмов Графический редактор обеспечивает одновременную работу с несколькими проектами, поддержку многостраничное™ в одном проекте, выбор необходимого элемента ПГСА из палитры примитивов, выполнение типовых операций редактирования как над одиночными объектами, так и над их группами, эффективный алгоритм прокладки связей между элементами ПГСА, экспорт данных в формат масштабируемой векторной графики (SVG), вывод на печать

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

Предлагается архитектура системы реализации ДГЯ САПР, отражающей накопленный на сегодняшний день мировой опыт по созданию средств построения ДГЯ, их синтаксическому и семантическому анализу (получению семантических значений, формированию динамической семантики) В системе выделяется 4 подсистемы

1 АРМ разработчика ДГЯ Подсистема служит для поэлементного построения библиотеки примитивов, покрывающей все символы реализуемого графического языка Формирование каждого примитива заключается в построении графического изображения из элементарных геометрических объектов (линия, дуга, окружность, прямоугольник и тп), указании точек соединения, описании назначения примитива и взаимодействия с другими примитивами библиотеки в свободной текстовой форме

2 АРМ разработчика средств анализа языка Подсистема предназначена для автоматизированного построения средств синтаксического анализа и синтаксически ориентированной трансляции В первом случае разработчику предлагается на выбор три типа автоматной графической грамматики (RV -грамматика, RVN - грамматика, RVH - грамматика) В качестве средства синтаксически - ориентированной трансляции предлагается использовать RVT - грамматику и расширить данный АРМ блоками, отвечающими за формирование отображений для каждой продукции грамматики и минимизацию отображений Отображения могут формироваться в том числе и с целью получения денотационной и операционной семантик Следует заметить, что отображения создаются с использованием библиотеки примитивов целевого языка, т е она должна быть предварительно создана

3 АРМ пользователя Подсистема позволяет производить построение, синтаксический анализ диаграмм графических языков и их

синтаксически - ориентированную трансляцию в текстовые и/или графические языки (формальные описания) Для реализации такой функциональности используются библиотека примитивов графического языка (алфавит языка), описание схемы анализа и схемы трансляции

4 АРМ эксперта по семантике Подсистема служит для построения динамической семантики диаграммы В ней символам языка назначается индивидуальное значение, те новое отображение в терминал того же целевого языка, что и оригинальное отображение Но это новое отображение будет наделять символ некой спецификой характерной только для него Программа используется как расширение АРМ пользователя

АРМы разработчика ДГЯ, разработчика средств анализа языка (формирование синтаксических схем анализа) и пользователя реализованы в среде Microsoft NET для операционных систем Microsoft Windows 98/ME/NT/2000/ХР/Vista

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1 Предложен метод синтаксического анализа диаграмм графических языков САПР, в том числе неструктурированных и содержащих параллелизм Метод оформлен в виде автоматной графической RV - грамматики, которая отличается от известных линейной временной сложностью анализа, не превосходящей двойного количества элементов диаграммы для любого из поддерживаемых языков, а также сокращением затрат памяти в среднем в 5 раз, и обеспечивает необходимую полноту контроля

2 Предложен метод нейтрализации ошибок в анализируемых диаграммах графических языков Метод реализован на базе автоматной графической RVN - грамматики, позволяющей сократить время создания корректных диаграмм за счет формирования списка всех допущенных проектировщиком ошибок за один прогон Известный метод нейтрализации ошибок уступает авторскому по временным характеристикам (экспоненциальная временная сложность против линейной) и затратам памяти в среднем в 5 раз

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

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

синтаксически - ориентированной трансляции

5 Предложена архитектура системы реализации ДГЯ, имеющая полный набор функциональности для построения и редактирования диаграмм различных графических языков САПР, средств их анализа и преобразования в текстовые и/или графические представления Реализованы компоненты системы

Публикации в журналах, входящих в список ВАК

1 Шаров О Г, Афанасьев А Н Нейтрализация синтаксических ошибок в графических языках // Программирование - 2007 - № 6 -принята к публикации

2 Шаров О Г, Афанасьев АН Синтаксически - ориентированная реализация графических языков на основе автоматных графических грамматик // Программирование - 2005 - № 6 - С 56-66

Публикации

3 РОСПАТЕНТ СВИДЕТЕЛЬСТВО об официальной регистрации программы для ЭВМ № 2005611312 "Анализатор графических схем алгоритмов" - Москва, 2005

4 РОСПАТЕНТ СВИДЕТЕЛЬСТВО об официальной регистрации программы для ЭВМ № 2005610662 "Графический конструктор электронных учебно - методических комплексов" - Москва, 2005

5 РОСПАТЕНТ СВИДЕТЕЛЬСТВО об официальной регистрации программы для ЭВМ № 2003612553 "Графический редактор алгоритмов управления" - Москва, 2003

6 РОСПАТЕНТ СВИДЕТЕЛЬСТВО об официальной регистрации программы для ЭВМ № 2005611314 "Синтаксически -ориентированный графический редактор алгоритмов управления" -Москва, 2005

7 РОСПАТЕНТ СВИДЕТЕЛЬСТВО об официальной регистрации программы для ЭВМ № 2007611772 "Система построения спецификаций графических языков на основе RV - грамматик" - Москва, 2007

8 РОСПАТЕНТ СВИДЕТЕЛЬСТВО об официальной регистрации программы для ЭВМ № 2007611773 "Универсальная система анализа графических языков на базе RV - грамматик" - Москва, 2007

9 Sharov О G, Afanas 'ev А N Automaton methods of syntactic analysis and syntax-directed translation of diagram visual languages // Proceedings of the International Conference Interactive Systems and Technologies The Problems of Human - Computer Interaction - Collection of scientific papers - Ulyanovsk 2007 - September - Pp 129-135

10 Sharov O G Development of graphic editor CAD of associative processors of management // Proceedings of the International Conference Interactive Systems The Problems of Human - Computer Interaction

Ulyanovsk 2003 - September - Pp 168 - 169

11 Sharov О G, Afanasjev A N The concept of construction and realization of graphical editors for CAD // Proceedings of the International Conference Interactive Systems The Problems of Human - Computer Interaction - Ulyanovsk 2003 - September - Pp 248-252

12 Шаров О Г Алгоритм анализа диаграммных языков на базе автоматной RV - грамматики / / Труды международной конференции "Континуальные алгебраические логики, исчисления и нейроинформатика в науке и технике - КЛИН - 2005" Ульяновск УлГТУ, 2005 г - Том 2 - С 177

13 Шаров О Г Анализ и разработка графических средств представления и обработки алгоритмов управления // Тезисы докладов XXXVII научно - технической конференции УлГТУ - Т 2 - Ульяновск 2003 -С 14-15

14 Шаров О Г Задачи нейтрализации ошибок в RV - грамматиках // Труды международной конференции "Континуальные алгебраические логики, исчисления и нейроинформатика в науке и технике - КЛИН - 2005" Ульяновск УлГТУ, 2005 г - Том 2 - С 178

15 Шаров О Г Методы семантической формализации графических языков // Труды международной конференции "Конференции по логике, информатике, науковедению - КЛИН - 2007" - Ульяновск УлГТУ - 2007 - Т 2 - С 87

16 Шаров О Г Семантика диаграммных языков // VII Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям (с участием иностранных ученых) Программа и тезисы докладов Новосибирск 2006 - С 99 - 100

17 Шаров О Г Средства синтаксического анализа графических языков САПР // Тезисы докладов международная XXXIX-я научно-техническая конференция ППС "Вузовская наука в современных условиях" - Ульяновск, УлГТУ, 2005 - Том 1 - С 128

18 Шаров О Г, Афанасьев АН Автоматная графическая грамматика // Вестник Ульяновского государственного технического университета - 2005 -№ 1 - С 54-56

19 Шаров О Г, Афанасьев АН Транслирующая автоматная графическая грамматика // Вестник Ульяновского государственного технического университета - 2007 - № 1 - С 47-50

ПЕРЕЧЕНЬ ПРИНЯТЫХ СОКРАЩЕНИЙ ДГЯ - диаграммный графический язык САПР система автоматизированного проектирования

АВТОРЕФЕРАТ

ШАРОВ Олег Геннадьевич

Исследование и разработка методов и средств реализации диаграммных графических языков САПР

Подписано в печать 05 09 2007 Формат 60x84/16 Бумага писчая Уел п л 1,16 Тираж 100 экз Заказ № 1159

Типография УлГТУ 432027 Ульяновск, Сев Венец, 32

Введение

Глава 1. Использование и реализация диаграммных графических языков в САПР

1.1. Проектная деятельность.

1.1.1. Понятия проектной деятельности.

1.1.2. Структура процесса проектирования.

1.1.3. Диаграммные графические языки в проектной деятельности.

1.2. Обзор графических языков.

1.2.1. Основные нонятия графических языков.

1.2.2. Диаграммные графические языки САПР.

1.3. Модели графических языков.

1.3.1. Синтаксические модели графических языков.

1.3.2. Классификация графических грамматик

1.3.3. Веб - грамматика (Web Grammars).

1.3.4. Позиционная грамматика (Positional Grammar)

1.3.5. Реляционная грамматика (Relational Grammar)

1.3.6. Многоуровневая графовая грамматика

Layered Graph Grammars)

1.3.7. Сохраняющая графовая грамматика

Reserved Graph Grammar)

1.3.8. Транслирующие графические грамматики

1.3.9. Достоинства и недостатки графических грамматик

1.4. Инструментальные средства.

1.4.1. Универсальные графические редакторы

1.4.2. Специализированные графические редакторы

1.4.3. Примеры инструментальных средств.

1.5. Постановка задачи.

1.6. Выводы.

Глава 2. Разработка и исследование графической грамматики

ДГЯ САПР

2.1. RV - грамматика.

2.1.1. Определение RV - грамматики.

2.1.2. Методика построения RV - грамматики.

2.1.3. Пример построения RV - грамматики для языка ПГСА

2.1.4. Автоматная интерпретация алгоритма контроля

2.2. RVN - грамматика.

2.2.1. Определение RVN - грамматики.

2.2.2. Пример RVN - грамматики для языка ПГСА.

2.3. Алгоритмическая структура RV (RVN) - анализатора

2.4. Иерархическая RV - грамматика.

2.5. Сравнение анализаторов графических грамматик.

2.5.1. Временная оценка эффективности RV - анализатора

2.5.2. Временная оценка эффективности RVN - анализатора

2.5.3. Сравнение временных характеристик анализаторов

2.5.4. Сравнение затрат памяти анализаторами.

2.5.5. Выявляемые ошибки.

2.6. Выводы.

Глава 3. Исследование методов семантического анализа ДГЯ

САПР. Разработка транслирующей грамматики

3.1. Семантика графических языков

3.2. Транслирующая грамматика.

3.2.1. Определение RVTt - грамматики.

3.2.2. Специфика трансляции в текстовый целевой язык

3.2.3. Пример RVTt - грамматики для языка ПГСА

3.2.4. Определение RVTg - грамматики.

3.2.5. Пример RVTg - грамматики для языка ПГСА . 131 3.3. Выводы.

Глава 4. Разработка программных средств реализации ДГЯ

4.1. Разработка анализатора графических схем алгоритмов

4.1.1. Общие сведения о Microsoft Visio

4.1.2. Реализация алгоритма контроля.

4.2. Разработка синтаксически ориентированного графического редактора.

4.2.1. Функциональное назначение и возможности.

4.2.2. Проектирование функциональности графического редактора.

4.2.3. Разработка алгоритма прокладки связей.

4.2.4. Разработка формата хранения данных.

4.2.5. Проектирование и реализация транслятора.

4.2.6. Параметры реализации и используемые технологии

4.3. Разработка системы реализации графических языков САПР

4.3.1. Система построения спецификаций графических языков на основе RV - грамматик

4.3.2. Универсальная система анализа графических языков на базе RV - грамматик.

4.3.3. Формат храпения метаоппсання графического языка

4.4. Выводы.

Актуальность темы. В последнее время при проектировании средств вычислительной техники, автоматизированных систем активно используются графические представления спецификаций, поскольку они предлагают более удобные способы изложения данных, процессов и т.п. Так, функциональные описания представляют диаграммами потоков данных (DFD), в рамках стандарта. SDL или методологии IDEF0. Для описания информационных моделей наибольшее распространение получили диаграммы сущность-связь (ERD), в которых предусмотрены средства для описания сущностей, атрибутов и отношений. Стандартной методикой построения таких диаграмм является IDEF1X. Поведенческие модели представляют в виде граф-схем, диаграмм переходов состояний (STD), сетей Петри. Объектный подход представлен унифицированным языком моделирования (UML), стандартом SDL-2000 и методологией IDEF4. Для описаний архитектур автоматизированных систем используются языки xADL 2.0, Darwin, UML.

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

1. Известные методы синтаксического анализа и преобразования ДГЯ обладают значительными затратами но времени (экспоненциальные, полиномиальные характеристики) и памяти.

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

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

4. Практически не развиты автоматизированные средства создания схем анализа и схем синтаксически - ориентированной трансляции диаграмм графических языков.

Вышеизложенное обуславливает актуальность задачи исследования методов и средств реализации диаграммных графических языков (ДГЯ) САПР.

Целью диссертационной работы является расширение возможностей методов н средств реализации ДГЯ САПР за счет разработки автоматных методов анализа и преобразования ДГЯ, позволяющих сократить время анализа, затраты памяти, обладающих необходимой полнотой контроля, а также синтаксически ориентированных программ их поддержки.

В соответствии с поставленной целью в работе формулируются и решаются следующие задачи исследования.

1. Анализ существующих подходов синтаксического анализа н синтаксически - ориентированной трансляции ДГЯ.

2. Разработка метода анализа ДГЯ с временной сложностью анализатора не превосходящей сложность существующих аналогов п обеспечивающего необходимую полноту контроля.

3. Разработка метода синтаксически - ориентированной трансляции ДГЯ в текстовые и графические формальные представления.

4. Разработка информационного и программного обеспечения, позволяющего производить синтаксический анализ ДГЯ, их синтаксически - ориентированную трансляцию в другие формы (текст, графика).

Объектом исследования является автоматизация процесса обработки ДГЯ САПР.

Предметом исследования является разработка комплекса методов анализа, и трансляции ДГЯ, программных средств, обеспечивающих автоматизацию обработки ДГЯ.

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

Научная новизна определяется разработанными методами анализа и преобразования ДГЯ САПР, основу которых составляет предложенное семейство автоматных ЯУ - грамматик.

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

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

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

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

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

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

1. Разработанный анализатор графических схем алгоритмов, являющийся расширением для графического редактора Microsoft Visio.

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

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

Компоненты системы позволяют: а) формировать библиотеки примитивов ДГЯ, нагруженные описанием взаимодействия в реализуемых диаграммах; б) строить схемы анализа в виде трех вариантов авторской автоматной графической грамматики (ЯУ / КУК / ИУН -грамматики); в) ставить в соответствие графические или тектовые языки графическому языку посредством использования авторской автоматной транслирующей грамматики, (КУТ - грамматики), для целевого текстового языка - ПУТЧ. - грамматика, а для целевого графического языка - - грамматика; г) назначать индивидуальные отображения элементам графических диаграмм в терминах целевого языка, определенного используемой схемой трансляции; д) организовывать структуры данных содержащие библиотеки примитивов, соответствующие им схемы анализа, наборы схем трансляции в разные целевые языки, а также библиотеки индивидуальных отображений для каждого набора, схем трансляции.

Разработаны компоненты системы.

На реализованные программные средства получено шесть СВИДЕТЕЛЬСТВ (РОСПАТЕНТ) об официальной регистрации программы для ЭВМ № 2003612553, 2005610662, 2005611312, 2005611314, 2007611772, 2007611773.

Реализация и внедрение результатов работы. Разработанные программные средства внедрены в:

1) учебный процесс Ульяновского государственного технического университета (г. Ульяновск);

2) учебный процесс Ульяновского института повышения квалификации и переподготовки работников образования (г. Ульяновск);

3) процесс подготовки производства ОАО "Автодеталь-Сервис" (г. Ульяновск);

4) проектный процесс ООО "Микро" (г. Ульяновск);

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на следующих международных и региональных конференциях: 7-ой международной научно-технической конференции "Интерактивные системы: Проблемы человеко-компьютерного взаимодействия / ИС-2007", г. Ульяновск, 2007; Международной "Конференции по логике, информатике, науковедению (КЛИН-2007)", г. Ульяновск, 2007; VII Всероссийская конференция молодых ученых по математическому моделированию н информационным технологиям, г. Красноярск, 2006; Международной конференции "Континуальные алгебраические логики, исчисления и нейроипформатика в науке и технике (КЛИН-2005)", г. Ульяновск, 2005; Международной конференции "Интерактивные системы: Проблемы человеко-компьютерного взаимодействия 2003", г. Ульяновск, 2003; Ежегодных внутривузовских конференциях профессорско-преподавательского состава, г. Ульяновск, 2002, 2003, 2004, 2005, 2006, 2007.

Публикации. По теме диссертации опубликовано 13 печатных работ, в том числе две в журналах списка ВАК. Получено шесть СВИДЕТЕЛЬСТВ (РОСПАТЕНТ) об официальной регистрации программ для ЭВМ № 2003612553, 2005610662, 2005611312, 2005611314, 2007611772, 2007611773.

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

4.4. Выводы

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

Анализатор графических схем алгоритмов является надстройкой па Microsoft Visio, определяющей корректность реализованных проектировщиком диаграмм в рамках одного графического языка (ГСА).

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

Графический редактор оснащен авторским алгоритмом прокладки связей и форматом храпения диаграмм на базе формата XML.

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

1. АРМ разработчика графического языка. Подсистема служит для поэлементного построение библиотеки примитивов, покрывающей все символы реализуемого графического языка.

2. АРМ разработчика средств анализа языка. Подсистема предназначена для автоматизированного построения средств синтаксического анализа и синтаксически - ориентированной трансляции на базе RV/RVN/RVH - грамматик и RVT - грамматик, соответственно.

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

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

На программные продукты, описанные в данной главе, получено шесть свидельств РОСПАТЕНТа ([88, 89, 90, 91, 92, 93]).

Заключение

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

1. Предложен метод синтаксического анализа диаграмм графических языков САПР, в том числе неструктурированных и содержащих параллелизм. Метод оформлен в виде автоматной графической ЯУ - грамматики, которая отличается от известных линейной временной сложностью анализа, не превосходящей двойного количества элементов диаграммы для любого из поддерживаемых языков, а также сокращением затрат памяти в среднем в 5 раз, и обеспечивает необходимую полноту контроля.

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

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

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

5. Предложена архитектура системы реализации ДГЯ, имеющая полный набор функциональности для построения и редактирования диаграмм различных графических языков САПР, средств их анализа и преобразования в текстовые и/или графические представления. Реализованы компоненты системы.

1. Andries M., Engels G., Rekers J. How to represent а. visual specification?http://citeseer.ist.psu.edu/article/andrics96how.htnil.

2. Bardohl R., et al. Formal relationship between petri nets and graph grammars as basis for animation view in genged.http://citeseer.ist.psu.edu/bardohl02formal.html.

3. Bardohl R., Niemann M., Schwarze M. Genged: A development environment for visual languages // AGTIVE. — 1999.- Pp. 233-240.http://(:itcsecr.ist.psu.cdu/bardohl99gengc(l.html.

4. Baresi L., Garzotto F., Paolini P. Extending UML for modeling web applications // Proc. 34th Annual Hawaii International Conference on System Sciences (HICSS-34) / Ed. by R. H. Sprague, Jr. IEEE Computer Society, 2001.

5. Baresi L., Heckel R. Tutorial introduction to graph transformation: A software engineering perspective // ICGT '02: Proceedings of the First International Conference on Graph Transformation. London, UK: SpringerVerlag, 2002. Pp. 402-429.

6. Baresi L., Pezz M. Formal interpreters for diagram notations // ACM Trans. Softw. Eng. Methodol. 2005. - Vol. 14, no. 1. - Pp. 42-84.

7. Baresi L., Pezzé M. On formalizing UML with high-level Petri Nets: Tech. Rep. 09.98: Dipartimento di Elettronica e Informazione Politécnico di Milano, 1998.

8. Baresi L., Pezzé M. Toward formalizing structured analysis. // ACM Trans. Softw. Eng. Methodol. 1998. - Vol. 7, no. 1. - Pp. 80-107.

9. Baresi L., Pezzé M. A formal definition of stuctured analysis with programmable graph grammars. // AGTIVE / Ed. by M. Nagl, A. Schiirr, M. Münch. — Vol. 1779 of Lecture Notes in Computer Science. — Springer, 1999. Pp. 193-208.

10. Baresi L., Pezzé M. A toolbox for automating visual software engineering. // FASE / Ed. by R.-D. Kutsche, H. Weber. Vol. 2306 of Lecture Notes in Computer Science. — Springer, 2002. — Pp. 189-202.

11. Baresi L., Pezzé M. Petri nets as semantic domain for diagram notations. // Electr. Notes Theor. Comput. Sci. 2005. - Vol. 127, no. 2,-Pp. 29 44.

12. Baresi L., Pezzé M., Taentzer G. Introduction graph transformation and visual modeling techniques - gt-vmt 2001. // Electr. Notes Theor. Comput. Sci. - 2001. - Vol. 50, no. 3.

13. Boshernitsan M., Downes M. Visual programming languages: A survey. — 1997. http://citeseer.ist.psu.c(lu/boshcrnitsan97visual.html.

14. Brumfield R. Type systems in visual languages.http://cit(;s(;(;r.nj.ncc.com/lTiiinfid(li)5tyj)o.htin.

15. Corradini A. General theory of graph transformation systems (getgrats).http://citcsccr.ist.psu.edu/80y7.html.

16. Davis M. Media streams: An iconic visual language for video annotation.htt.)://wvvw.w3.org/Pcoplc/howc'omc/p/telcktronikk-4-93/DavisM.html.20. de Graaf A. Levis lexical scanning for visual languages.http://citcsecr.ist.psu.wlu/2C255.htinl.

17. Denaro G., Pezze M. Petri nets and software engineering. // Lectures on Concurrency and Petri Nets / Ed. by J. Desel, W. Reisig, G. Rozen-berg. — Vol. 3098 of Lecture Notes in Computer Science.— Springer, 2003. Pp. 439-466.

18. Deufemia V.— A Grammar-based Approach to Specify and Implement Visual Languages.— Master's thesis, 2002.http://www.dia.unisa.it/dottorato/TESI/tesi-deufemia.pdf.

19. Engels G., Heckel R., Kiister J. M. Rule-based specification of behavioral consistency based on the UML meta-model // Lecture

20. Notes in Computer Science.- 2001.- Vol. 2185,- Pp. 272-287.http://citcsccr.ist.psu.cdu/engcls01rulcbascd.html.

21. Feder J. Plex languages // Information Science. 1971.- no. 3. — Pp. 225-241.

22. Formal Methods in Software and Systems Modeling, Essays Dedicated to Hartmut Ehrig, on the Occasion of His 60th Birthday / Ed. by HJ. Kreowski, U. Montanari, F. Orejas et al. — Vol. 3393 of Lecture Notes in Computer Science, Springer, 2005.

23. Costagliola G., Lucia A. D., Orefice S., Tortora G. A framework of syntactic models for the implementation of visual languages. http://www.dmi.unisa.it/pcoplc/costagliola/www/home/papers/vI97.ps.gz.

24. Golin E. Parsing visual languages with picture layout grammars // Journal of Visual Languages and Computing.— 1991.— Vol. 2, no. 4.— Pp. 371-394.

25. Graph Transformation, First International Conference, ICGT 2002, Barcelona, Spain, October 7-12, 2002, Proceedings / Ed. by A. Corradini, H. Ehrig, H.-J. Kreowski, G. Rozenberg. — Vol. 2505 of Lecture Notes in Computer Science, Springer, 2002.

26. HI-VISUAL as a user-customizable visual programming environment / E. Miller, M. Kado, M. Hirakawa, T. Ichikawa // Visual Languages.— 1995. — P. 107. http://citeseer.nj.nec.com/372043.html.

27. ITU. Message sequence charts (MSC).— 1999. http://www.itu.int/lTU

28. T/st.udygn>ups/com10/laiiguages/Z.1201199.pdf.

29. ITU. Specification and description language (SDL). 1999.http://www.itu.int/ITU-T/studygroups/comlO/languages/Z. 1001199.pdf.

30. Koth 0., Minas M. Structure, abstraction and direct manipulation in diagram editors, http://citeseer.ist.psu.edu/611548.html.

31. Marriott K., Meyer B. Towards a hierarchy of visual languages. // VL. — 1996. Pp. 196-203.

32. Mehmet K.-D. Z. Compiled visual programs by vispro.http://citeseer.ist.psu.edu/728390.html.

33. Minas M. Xml-based specification of diagram editors.http://citest!er.ist.psu.(!(lu/mina.s03xmlba.scd.html.

34. Multimodal Human-Computer Communication, Systems, Techniques, and Experiments / Ed. by H. Bunt, R.-J. Beun, T. Borghuis.- Vol. 1374 of Lecture Notes in Computer Science, Springer, 1998.

35. Object-Oriented Technology, ECOOP'97 Workshop Reader, ECOOP'97 Workshops, Jyväskylä, Finland, June 9-13, 1997 / Ed. by J. Bosch, S. Mitchell. — Vol. 1357 of Lecture Notes in Computer Science, Springer, 1998.

36. Object-oriented visualization of program logic. / S.-P. Lahtinen, E. Suti-nen, A.-P. Tuovinen, J. Tarhio // TOOLS (23). IEEE Computer Society, 1997.-Pp. 76-88.

37. Paakki J., Tuovinen A.-P. Source-to-source translation of visual languages // Nordic J. of Computing. 1998. - Vol. 5, no. 3. - Pp. 235-264.

38. Costagliola G., Lucia A. D., Orefice S., Tortora G. A parsing methodology for the implementation of visual systems.http://www.dmi.unisa.it/people/costaglioIa/www/home/papers/method.ps.gz.

39. Pezze M., Baresi L. Can graph grammars make formal methods more human? // ICALP Satellite Workshops. 2000. - Pp. 387-394.

40. Pezze M., Young M. Constructing multi-formalism state-space analysis tools: Using rules to specify dynamic semantics of models. // ICSE. — 1997. Pp. 239-249.

41. Costagliola G., Lucia A. D., Orefice S., Tortora G. Positional grammars: a formalism for LR-Iike parsing of visual languages.http://www.dmi. unisa.it/peopIe/costagIiola/www/home/papers/t.vl96.ps.gz.

42. Proceedings of the 1992 IEEE Workshop on Visual Languages, September 15-18, 1992, Seattle, Washington, USA. IEEE Computer Society, 1992.

43. Rekers J., SchurrA. A parsing algorithm for context sensitive graph grammars: Tcch. Rep. 95-05: Leiden University, Dept. of Computer Science, the Netherlands, 1995. http://citeseer.ist.psu.edu/rekers95parsing.htrnl.

44. Rekers J., Schurr A. Defining and parsing visual languages with layered graph grammars // Journal of Visual Languages and Computing. — 1997. - Vol. 8, no. 1.Pp. 27-55. http://(;itcsair.ist.psu.(:(lu/rckers!)7(lofining.htmI.

45. Ferrucci F., Tortora G., Tucci M., Vitiello G. Relation grammars: a grammatical model for a high-level specification of visual languages. — 1996.http://www.csse.monash.edu.au/ bemdm/TVL96/tvl96-papers.htmI.

46. TOOLS 1997: 23rd International Conference on Technology of Object-Oriented Languages and Systems, July 28 August 1,1997, Santa Barbara, CA, USA. - IEEE Computer Society, 1998.

47. Tuovinen A.-P. A framework for processors of visual languages. // ECOOP Workshops / Ed. by J. Bosch, S. Mitchell. Vol. 1357 of Lecture Notes in Computer Science. — Springer, 1997. — Pp. 119-122.

48. Tuovinen A.-P. Error recovery in parsing relational languages // Visual Languages. — 1998. — Pp. 6-13. citeseer.ist.psu.edu/tuovinen98error.htnil.

49. UML 2000 The Unified Modeling Language, Advancing the Standard, Third International Conference, York, UK, October 2-6, 2000, Proceedings / Ed. by A. Evans, S. Kent, B. Selic. Vol. 1939 of Lecture Notes in Computer Science, Springer, 2000.

50. Vermeulen J. — Viability of a Parsing Algorithm for Context Sensitive Graph Grammars: An Implementation of Rekers' and

51. Schürr's Graph Parsing Algorithm with several Runtime Improvements based on Set Theoretic Considerations. Master's thesis, 1996.http://citeseer.ist.psu.edu/vermeulen96viability.html.

52. W3C. Scalable vector graphics (svg) 1.1 specification.— 2003.http://www.w3.org/TR/2003/REC-SVG 11-20030114/.

53. W3C. Extensible markup language (xml). — 2004. http://www.w3.org/XML/.

54. W3C. Extensible markup language (xml) 1.0 (third edition).- 2004.http://www.w3.org/TR/2004/REC-xml-20040204/.

55. W3C. Scalable vector graphics (svg). xml graphics for the web. — 2004.http://www.w3.org/Graphics/SVG/.

56. Wikipedia.org. Earley parsers. http://i:n.wikipedia.org/wiki/Earl(!yParscr.

57. Wittenburg K. Earley-style parsing for relational grammars. // VL. — IEEE Computer Society, 1992. Pp. 192-199.

58. Wittenburg K. Visual language parsing: If i had a hammer. // Multimodal Human-Computer Communication / Ed. by H. Bunt, R.-J. Be-un, T. Borghuis. — Vol. 1374 of Lecture Notes in Computer Science. — Springer, 1995.- Pp. 231-249.

59. Wittenburg K., Weitzman L. Visual grammars and incremental parsing for interface languages. // VL. 1990. Pp. Ill 118.

60. Wittenburg K., Weitzman L. Relational grammars: Theory and practice in a visual language interface for process modeling. — 1996.http://citeseer.ist.psu.edu/wittenburg96relational.html.

61. Zhang D.-Q., Zhang K. Reserved graph grammar: A specification tool for diagrammatic VPLs // Proceedings. 1997 IEEE Symposium on Visual Languages.- Isle of Capri, Italy: 1997.-23-26.- Pp. 284-291.http://citcsccr.ist.psu.cdu/zhang97rcserved.html.

62. Zhang D.-Q., Zhang K. Vispro: A visual language generation toolset // Visual Languages. 1998. Pp. 195 - 202. http://ntosccr.ist.psu.oclu/199922.html.

63. Zhang D.-Q., Zhang K., Cao J. A context-sensitive graph grammar formalism for the specification of visual languages // The Computer Journal- 2001.- Vol. 44, no. 3.- Pp. 186-200.http://citeseer.ist.psu.edu/zhang01contextsensitive.html.

64. Zhang К., Orgun M., Zhang K. Visual language semantics specification in the vispro system. — 2002. http://citeseer.ist.psu.edu/zhang02visual.html.

65. Zhang K., Zhang D., Deng Y. A visual approach to xml document designand transformation. — 2001. http://citeseer.ist.psu.edu/zhang01visual.html.

66. Zhang K.-B., Zhang K., Orgun M. A. Using graph grammar to implement global layout for a visual programming language generation system.http://citeseer.ist.psu.edu/537427.html.

67. Афанасьев A. H., Гужавин А. А., Кокаев О. Г. Ассоциативное микропрограммирование. — Саратов: Издательство Саратовского университета, 1991.— 116 с.

68. Афанасьев А. Н., Кокаев О. Г. Подсистема лингвистического контроля САПР па базе иерархических RG грамматик // Автоматизация конструкторского проектирования РЭА и ЭВА: Тезисы докладов областной научно-технической конференции. — 1984. - С. 41-42.

69. Ахо А., Сети Р., Ульман Д. Компиляторы. Принципы, технологии, инструменты. — Москва: Издательский дом 'Вильяме', 2003. — 768 с.

70. Ахо А., Ульман Д. Теория синтаксического анализа, перевода и компиляции. — Москва: Мир, 1978. — Т. 1. — 612 с.

71. Буч Г., Рамбо Д., Джекобсон A. UML. Руководство пользователя.— М.: ДМК Пресс, 2001.- 432 с.

72. Фаулер М., Скотт К. 1ШЬ. Основы. — СПб.: Символ Плюс, 2002. — 192 с.

73. Фу К. Структурные методы в распознавании образов. М.: Мир, 1977. 319 с.

74. Глушков В. М., Цейтлин Г. Е., Ющенко Е. Л. Алгебра. Языки программирования. — Киев: Наукова думка, 1978. — 320 с.

75. Карабегов А. В., Тер-Микаэлян Т. М. Введение в язык ББЬ. — М.: Радио и связь, 1993. — 184 с.

76. Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение.— СПб.: БХВ Петербург, 2003.- 1104 с.

77. Контроль информации в системах автоматизации проектирования / А. Н. Афанасьев, А. А. Гужавин, О. Г. Кокаев и др.— Саратов: Издательство Саратовского университета, 1985. — 136 с.

78. Матьяш В. А., Щекин С. В. Использование компонент языка иш1 для структурного проектирования программного обеспечения систем реального времени // Авиакосмическое приборостроение. — 2003.— № 6. С. 28-32.

79. Норенков И. П. Основы автоматизированного проектирования. — М.: Издательство МГТУ им. Н.Э. Баумана, 2002. 336 с.

80. РОСПАТЕНТ: СВИДЕТЕЛЬСТВО об официальной регистрации программы для ЭВМ № 2003612553. "Графический редактор алгоритмов управления", Москва. — 2003.

81. РОСПАТЕНТ: СВИДЕТЕЛЬСТВО об официальной регистрации программы для ЭВМ № 2005610662. "Графический конструктор электронных учебно методических комплексов", Москва. 2005.

82. РОСПАТЕНТ: СВИДЕТЕЛЬСТВО об официальной регистрации программы для ЭВМ № 2005611312. "Анализатор графических схем алгоритмов", Москва. — 2005.

83. РОСПАТЕНТ: СВИДЕТЕЛЬСТВО об официальной регистрации программы для ЭВМ № 2005611314. "Синтаксически -ориентированный графический редактор алгоритмов управления", Москва. 2005.

84. РОСПАТЕНТ: СВИДЕТЕЛЬСТВО об официальной регистрации программы для ЭВМ № 2007611772. "Система построения спецификаций графических языков на основе гу грамматик", Москва. - 2007.

85. РОСПАТЕНТ: СВИДЕТЕЛЬСТВО об официальной регистрации программы для ЭВМ № 2007611773. "Универсальная система анализа графических языков на базе гу грамматик", Москва. — 2007.

86. Степанов П. А. Описание диаграммного языка и разработка генератора диаграммеров на основе универсального репозитория // Пятая Санкт-Петербургская Ассамблея молодых ученых и специалистов. — С-Петербург: 2000. — С. 45-46.

87. Степанов П. А. Объектное описание диаграммного языка с помощью математических отношений // Тезисы докладов IX Международной студенческой школы-семинара семинара.— М.: МГИЭМ, 2001.— С. 145-147.

88. Степанов П. А., Охтилев М. Ю. Вычислительная модель визуального языка // Изв. вузов. Приборостроение. 2006. № 11.--С. 28-32.

89. Жоголев Е. А. Графические редакторы и графические грамматики // Программирование. — 2001. — Л'2 3. — С. 30-42.

90. Волков Ю. Г. Диссертация: Подготовка, защита, оформление: Практическое пособие, — Москва: Гардарики, 2005. 185 с.

91. Вудс В. А. Сетевые грамматики для анализа естественных языков // Кибернетический сборник. Новая серия. — 1976. — № 13. — С. 120-158.

92. Захаров Н. Г., Рогов В. Н. Синтез цифровых автоматов. — Ульяновск: УлГТУ, 2003. 135 с.

93. Шалыто А. А. Использование граф-схем и графов переходов при программной реализации алгоритмов логического управления. Часть 1. // Автоматика и телемеханика. — 1996.— № 6.— С. 148—158. http://www.softcraft.ru/download/design/gsgp.zi.>.

94. Шалыто А. А. Использование граф-схем и графов переходов при программной реализации алгоритмов логического управления. Часть 2. // Автоматика и телемеханика. — 1996.— № 7.— С. 144—169. http://www.softcraft.ru/download/design/gsgp.zip.

95. Шалыто А. А. Реализация алгоритмов логического управления программами на языке функциональных блоков // Промышленные АСУ и контроллеры.— 2000.— № 4.— С. 45-50.http://www.softcraft.ru/download/dcsign/logctr.zip.

96. Шалыто А. А., Туккелъ Н. И. SWITCH технология - автоматный подход к созданию программного обеспечения 'реактивных' систем // Программирование.— 2001.— № 5.— С. 45-62.http://www.softcraft.ru/download/design/switch.zip.

97. Шаров 0. Г. Анализ и разработка графических средств представления и обработки алгоритмов управления // Тезисы докладов XXXVII научно технической конференции УлГТУ. — Т. 2. — Ульяновск: 2003. - С. 14-15.

98. Шаров О. Г. Средства синтаксического анализа графических языков САПР // Тезисы докладов международная XXXIX-я научно-техническая конференция ППС "Вузовская паука в современных условиях". Т. 1. - Ульяновск: 2005. - С. 128.

99. Шаров О. Г. Задачи нейтрализации ошибок в RV грамматиках // Труды международной конференции "Континуальные алгебраические логики, исчисления и нейроннформатика в пауке и технике - КЛИН - 2005". - Т. 2. - Ульяновск: 2005. - С. 178.

100. Шаров О. Г. Семантика диаграммных языков // VII Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям (с участием иностранных ученых). Программа и тезисы докладов. — Новосибирск: 2006. — С. 99-100.

101. Шаров О. Г. Методы семантической формализации графических языков // Труды международной конференции "Конференции по логике, информатике, науковедению КЛИН - 2007". — Т. 2. — Ульяновск: 2007. - С. 87.

102. Шаров О. Г., Афанасьев А. Н. Автоматная графическая грамматика // Вестник Ульяновского государственного технического университета. — 2005. — № 1. — С. 54-56.

103. Шаров О. Г., Афанасьев А. Н. Синтаксически ориентированная реализация графических языков на основе автоматных графических грамматик // Программирование. — 2005. — № 6. — С. 56-66.

104. Шаров О. Г., Афанасьев А. Н. Нейтрализация синтаксических ошибок в графических языках // Программирование. 2007. — № 6. — С. принята, к публикации.

105. Шаров О. Г., Афанасьев А. Н. Транслирующая автоматная графическая грамматика // Вестник Ульяновского государственного технического университета. — 2007. — № 1. — С. 47-50.