Содержание к диссертации
Введение
1. Анализ основных предпосылок совершенствования получения и обработки информации для задач управления социальными и экономическими системами. Выбор и обоснование основных направлений исследований 14
1.1 Основные особенности современного этапа развития распределенных систем управления и задачи сетей обмена разнородными данными и знаниями в распределенных системах управления социально-экономическими системами 14
1.2 Обобщенная концептуальная модель и основные классы задач, решаемых сетями обмена разнородными данными и знаниями в распределенных системах управления 19
1.3 Обзор известных инструментальных средств проектирования сетей обмена разнородными данными и знаниями 25
1.4 Анализ особенностей стандартов семейства IEEE 802.3 и особенностей построения структурированной кабельной системы для выбора непроизводных элементов и атрибутов 29
1.5 Анализ и применимость известных методов синтеза, обоснование и выбор частных задач исследований 53
Выводы по разделу 60
2. Особенности применения стохастических атрибутных метаграмматик для формального структурно- параметрического описания вариантов построения топологической структуры сети обмена разнородными данными и знаниями 62
2.1 Стохастические атрибутные метаграмматики. Основные понятия и определения. Формальные свойства 63
2.2 Особенности эталонного метаграмматического описания топологической структуры 70
2.3 Особенности формальных грамматик, входящих в общее структурно-параметрическое описание топологической структуры 73
Выводы по разделу 79
3. Метод и алгоритмы структурно- параметрического синтеза топологической структуры сетей обмена данными и знаниями распределенных систем управления 80
3.1 Анализ особенностей задачи структурно- параметрического синтеза топологической структуры сетей обмена данными и знаниями распределенных систем управления 81
3.2 Метод и алгоритмы структурно- параметрического синтеза топологической структуры сетей обмена разнородными данными и знаниями распределенных систем управления 83
3.3 Общая итерационная схема структурно- параметрического синтеза топологической структуры сетей обмена разнородными данными и знаниями распределенных систем управления 91
Выводы по разделу 96
4. Особенности реализации разработанного метода и алгоритмов при создании программного комплекса для структурно- параметрического синтеза топологической структуры сетей обмена разнородными данными и знаниями распределенных систем управления 97
4.1 Особенности реализации программного комплекса для синтеза и анализа топологической структуры сетей обмена разнородными данными и знаниями 98
4.2 Особенности системы синтаксического синтеза и анализа топологической структуры сетей обмена разнородными данными и знаниями 119
4.3 Экспериментальная проверка разработанного метода структурно-параметрического синтеза топологической структуры сетей обмена разнородными данными и знаниями распределенных систем управления 126
Выводы по разделу 132
Заключение 134
- Обобщенная концептуальная модель и основные классы задач, решаемых сетями обмена разнородными данными и знаниями в распределенных системах управления
- Особенности эталонного метаграмматического описания топологической структуры
- Метод и алгоритмы структурно- параметрического синтеза топологической структуры сетей обмена разнородными данными и знаниями распределенных систем управления
- Особенности системы синтаксического синтеза и анализа топологической структуры сетей обмена разнородными данными и знаниями
Введение к работе
Актуальность. На современном этапе развития информационных технологий, при повышении значимости представительного класса социальных и экономических систем, все большее значение приобретают распределенные системы управления, включающие в себя разнообразные по составу, связям, выполняемым функциям и носящие структурно-сложный характер объекты управления, агенты управления, обеспечивающие сбор, получение, хранение, обработку и выдачу информации. Неотъемлемой составляющей РСУ являются сети обмена разнородными данными и знаниями.
СО РДЗ РСУ в первую очередь крупных корпораций, систем безопасности, центральных и региональных органов управления РФ, характеризуются гетерогенной, территориально разнесенной топологической структурой, необходимостью оперативной передачи больших объемов РДЗ, включающих в себя документальные, мультимедийные аудиовизуальные и сигнализационные данные о состоянии социально- экономических объектов и процессов.
Особенность управления социально- техническими системами связана
с принципиальной невозможностью полного учета факторов, неполнотой,
неточностью обработки данных и применяемых к ним фрагментов знаний,
что обусловливает необходимость динамического обмена РДЗ в
асинхронные моменты времени. В связи с этим одной из наиболее важных
задач при создании перспективных СО РДЗ является формирование такой
топологической структуры сети, которая адекватна требованиям,
поставленным перед системой управления. В известных работах
отечественных и зарубежных ученых показано, что, создание
сложноструктурированных, масштабируемых, распределенных,
гетерогенных, включающих как локальные, так и глобальные сети, СО РДЗ, соответствующих международным стандартам и отвечающих современным требованиям разнородных групп пользователей, является наукоемкой
задачей, требующей привлечения адекватных методов и технологий для лица принимающего решение, способных в полной мере учесть слабоформализуемый характер современных распределенных систем управления социальных и экономических объектов.
Существующие системы, методы и средства характеризуются следующими основными моментами:
в настоящее время при создании СО РДЗ в основном нашли методы и технологии, допускающие низкую степень автоматизации процессов генерации и направленного выбора вариантов построения СО РДЗ при структурно- параметрическом синтезе СО РДЗ за счет применения эвристических, аналитических и комбинированных переборно-аналитических процедур и ориентированных на них алгоритмов, требующих участия в процессе создания представительной группы экспертов в данной области;
в последние годы существенно выросли требования международных и отечественных стандартов в области проектирования СО РДЗ, в первую очередь для важных в социальном и экономическом плане систем, а также систем ответственного применения, что существенно усложняет процессы синтеза перспективных СО РДЗ;
в рамках большинства методов существует принципиальное ограничение по синтезу компактных и легко расширяемых описаний современных СО РДЗ, учитывающего специфику современных стандартов проектирования СО РДЗ и современного сетевого оборудования.
Проведенный анализ показал, что одним из наиболее перспективных подходов для создания СО РДЗ является использование структурно-алгебраического подхода к структурно- параметрическому синтезу сложных систем на основе метаграмматик, предложенного и развитого в работах Атакищева О.И., Городецкого В.И., Довгаля В.М., Емельянова С.Г., Захарова И.С., Сизова А.С., Фомина ЯА, Харангозо Дж., Юсупова P.M.. В то же время в известных работах недостаточно полно рассмотрены конкретные
вопросы синтеза топологической структуры СО РДЗ для перспективных распределенных систем управления, характеризующиеся использованием разнотипного оконечного, сетевого и передающего оборудования, расширяемой гетерогенной архитектурой и смешанной топологией.
В этих условиях преодоление сложившегося объективного противоречия между современными требованиями по оперативности синтеза и модификации к создаваемым СО РДЗ в рамках РСУ, и возможностями существующих методов и алгоритмов, возможно в рамках структурно-алгебраического подхода с использованием стохастических атрибутных метаграмматик.
В связи с этим задача разработки метода и алгоритмов синтеза топологической структуры СО РДЗ для РСУ является актуальной.
Объектом исследования является топологическая структура сети обмена РДЗ РСУ.
Предмет исследования - методы и алгоритмы структурно-параметрического синтеза топологической структуры СО РДЗ РСУ.
Цель диссертации - повышение оперативности создания СО РДЗ путем разработки процессов структурно- параметрического синтеза и их автоматизации.
Основными задачами являются:
Анализ социально- экономических и научно- технических предпосылок решения задач структурно- параметрического синтеза топологической структуры СО РДЗ РСУ. Обоснование и выбор основных направлений исследований в рамках структурно- алгебраического подхода.
Разработка модифицированного подкласса метаграмматик стохастических атрибутных метаграмматик как основы для структурно-параметрического описания правил формирования топологической структуры СО РДЗ РСУ.
Создание в рамках единой структурно- параметрической модели эталонных метаграмматических описаний для синтеза СО РДЗ РСУ.
Разработка метода и алгоритмов синтаксического анализа САМ, учитывающих особенности предложенного подкласса МГ, а также учитывающих особенности построения топологической структуры современной СО РДЗ.
Реализация предложенного метода и алгоритмов при создании программного комплекса для синтеза топологической структуры СО РДЗ типовых РСУ. Проверка оперативности создания СО РДЗ с использованием предложенного метода и алгоритмов.
Научная новизна результатов, полученных в диссертационной работе, заключается, в следующем:
Разработан модифицированный подкласс МГ - САМ как основа для структурно- параметрического описания правил формирования топологической структуры СО РДЗ РСУ. Особенность САМ определяется введением в ее состав дополнительного правила согласования АА, что позволяет учесть нерегулярные связи и сложные семантические зависимости.
На основе САМ созданы эталонные метаграмматические описания правил формирования топологической структуры СО РДЗ РСУ, учитывающие специфику построения современных СО РДЗ, и обеспечивающие генерацию вариантов топологических структур и расчет основных параметров вариантов построения СО РДЗ за счет использования синтезируемых и наследуемых атрибутов и правил согласования АА.
Разработаны метод и построены алгоритмы синтаксического анализа САМ как процедурная основа метода структурно- параметрического синтеза топологической структуры СО РДЗ, позволяющие снизить временную сложность алгоритмов синтеза с экспоненциальной до квадратичной для типовых вариантов построения топологической структуры СО РДЗ путем учета специфики топологической структуры современных СО РДЗ.
Методы исследований основаны на использовании теории формальных грамматик и метаграмматик, общей теории управления, синтеза сложных
распределенных информационно- технических комплексов и систем, поддержки принятия решений в интеллектуализированных системах управления, искусственного интеллекта.
Практическая ценность работы состоит в том, что ее результаты позволили:
разработать общую итерационную схему структурно-параметрического синтеза топологической структуры СО РДЗ для типовых РСУ крупных корпоративных структур на основе САМ и ориентированных на нее алгоритмов синтаксического анализа «снизу- вверх» и «сверху- вниз», обеспечившую снижение на 1-2 порядка числа операций при выборе вариантов построения топологической структуры СО РДЗ по сравнению с лучшими из известных методов синтаксического анализа.
реализовать предложенный метод и алгоритмы при создании программного комплекса «METAGrammar» для синтеза топологической структуры СО РДЗ типовых РСУ. Проведенная проверка предложенного метода показала, что его применение позволяет снизить в 1,3-1,4 раза общее время создания СО РДЗ для типовых корпоративных систем.
Реализация и внедрение . Результаты диссертационной работы были использованы в учебном процессе Курского государственного технического университета в рамках дисциплин «Системы искусственного интеллекта» и «Сети ЭВМ и Телекоммуникации» и внедрены в ГОУ «Курскгражданпроект», что подтверждается соответствующими актами.
Апробация и публикации
Основные положения диссертационной работы докладывались и получили положительную оценку на международной конференции: «Классификация информационных атак в вычислительных системах» (г. Сочи, 2006г.); на ведомственной конференции «Применение метаграмматических моделей для описания и синтеза высокоскоростных локальных сетей», «Особенности метода и алгоритмы структурно -параметрического синтеза сетей связи» (г. Курск, 2006 г.) и семинарах
кафедры ПО ВТ Курского государственного технического университета. По теме диссертации опубликовано 8 печатных работ, в том числе 2 статьи по перечню центральных рецензируемых журналов и изданий ВАК, а также в разделах 4 отчетов о НИР.
Личный вклад автора. В работах, опубликованных в соавторстве, лично соискателем разработаны модифицированный подкласс МГ САМ, эталонные метаграмматические описания правил формирования топологической структуры СО РДЗ РСУ, метод и алгоритмы синтаксического анализа САМ, метод и алгоритмы синтеза топологической структуры СО РДЗ РСУ,
На защиту выносятся:
Эталонные метаграмматические описания правил формирования топологической структуры СО РДЗ РСУ, позволяющие направленно генерировать варианты, а также производить расчёт основных параметров создаваемой СО РДЗ РСУ за счет введения и обработки наследуемых и синтезируемых атрибутов.
Метод и алгоритмы синтаксического анализа САМ, позволяющие уменьшить оценку временной и емкостной сложностей до квадратичной и линейной соответственно для типовых структур СО РДЗ путем учета специфики топологической структуры современных СО РДЗ.
Общая итерационная схема структурно- параметрического синтеза топологической структуры СО РДЗ РСУ на основе САМ и ориентированных на нее алгоритмов синтаксического анализа «снизу- вверх» и «сверху- вниз», обеспечивающая снижение на 1-2 порядка числа операций при выборе вариантов построения топологической структуры СО РДЗ путем введения априорного распределения атрибутных зависимостей и дифференциации по системам и уровням СО РДЗ.
Объем и структура работы. Диссертационная работа состоит из введения, четырех разделов, заключения, списка литературы. Общий объем работы составляет 145 страниц, включая 35 рисунков, 10 таблиц, список литературы состоит из 113 наименований.
Области возможного применения. Результаты диссертационной работы могут найти применение при построении сложноструктурированных СО РДЗ, входящих в состав РСУ крупных корпораций, систем безопасности, систем обмена информацией силовых ведомств, центральных и региональных органов управления РФ.
Во введении обоснована актуальность темы, сформулированы цель и задачи диссертационных исследований» научная новизна, практическая ценность, основные научные положения, выносимые на защиту, а также приведено краткое содержание каждой из глав.
В первом разделе на основе анализа социально- экономических и научно- технических предпосылок решения задач структурно-параметрического синтеза, особенностей существующих и перспективных СО РДЗ РСУ крупных корпораций, систем безопасности и государственных органов управления РФ приводится постановка задачи и выбор основных направлений исследований.
Во втором разделе для решения второй задачи диссертационных исследований и создания формальных основ структурно- параметрического синтеза топологической структуры СО РДЗ РСУ приведена разработка формального аппарата для эталонных грамматических описаний.
Вводятся основные понятия и определения нового подкласса метаграмматик- стохастических атрибутных МГ. Проводится описание формальных свойств.
Для решения третьей задачи диссертационного исследования, на основе разработанного формального аппарата МГ, а также проведенного анализа существующих протоколов обмена данными и знаниями и методологии проектирования современных сетей обмена данными и знаниями входящих в состав распределенных систем управления, проводиться разработка эталонных формальных метаграмматических описаний правил формирования топологической структуры СО РДЗ.
В третьем разделе в рамках решения четвертой задачи исследований, на основе созданных САМ формальных основ разработана процедурная компонента метода структурно- параметрического синтеза топологической структуры СО РДЗ РСУ для автоматизированной генерации и проверки существующих вариантов топологической структуры СО РДЗ РСУ.
В четвертом разделе предложенный метод и его алгоритмы реализованы в виде программного комплекса (ПК METAGrammar), также предложена методика проведения экспериментальных исследований для определения основных характеристик и возможностей предложенного метода синтеза топологической структуры СО РДЗ по спектру решаемых научно- технических задач.
В заключении приводятся основные результаты диссертационного исследования.
Обобщенная концептуальная модель и основные классы задач, решаемых сетями обмена разнородными данными и знаниями в распределенных системах управления
В данном подразделе, с целью начальной формализации поставленной задачи проведен анализ для выявления основных факторов, влияющих на процесс создания современных СО РДЗ РСУ, на основе которого разработана обобщенная концептуальная модель типовой СО РДЗ РСУ.
В качестве основных уровней (страт) выделены уровни множеств подсистем корпорации, множество классов абонентов, множество требований абонентов, множество служб обмена информацией, множество терминальных средств сбора и обмена информацией, множество сетевых средств, множество средств безопасности, множество сред обмена информацией, множество природных условий.
Современный подход к проектированию СО РДЗ позволяет объединить все эти подсистемы в единообразную, стандартизированную СО РДЗ, выполняющую все требования, выдвигаемые каждой подсистемой по отдельности.
Характер проявления воздействия на СО РДЗ множества классов абонентов Cj заключается в дополнительных затратах на обеспечение безопасности СО РДЗ, в случае наличия различных по правам абонентов, таких как: временные абоненты (гости), обычные абоненты (пользователи), привилегированные абоненты (опытные пользователи), администраторы (сети, безопасности, баз данных). Также немаловажное значение имеет состав множества требований абонентов Qk, определяющий требования предъявляемые к СО РДЗ по оперативности, целостности передаваемых данных. Данное множество также связано с задачей обеспечения безопасности.
Требования абонентов прежде всего складываются из круга задач, который стоит перед системой управления в целом. Основными задачами является обмен знаниями и данными между пользователями системой и интеллектуальными автоматизированными человеко-машинными комплексами. Также требования находятся в зависимости от уровня развития программного и аппаратного обеспечения. На современном этапе наиболее распространенными задачами обмена данными являются: www - обмен данными по http и https протоколам, включающий данные на основе HTML, XML и других языков реализующих структурную разметку документов в том числе динамическую (различные CMS), данные не требуют доставки в реальном режиме времени, характеризуются средним объемом и могут использоваться для корпоративных сайтов, блогов; отправка и прием электронной почты по протоколам SMTP, РОРЗ, IMAP4, данные не требуют доставки в реальном режиме времени, характеризуются средним объемом; голосовая почта, IP телефония, Internet телефония (Skype, Google Talk) является альтернативой стандартной телефонии, позволяет обмениваться голосовыми данными в реальном режиме времени, требует доставки данных в реальном режиме времени, также характеризуется средним объемом передаваемых данных; мультимедиа (потоковые видео и аудио данные) в зависимости от формата используемого для кодирования, а также качества данных (используются алгоритмы сжатия с потерей данных) требует доставки данных в реальном режиме времени, характеризуется большим объемом передаваемых данных; Instant Messenger - служба обмена мгновенными сообщениями, в последнее время широко используется как средство коммуникации, характеризуется маленьким объемом передаваемых данных; службы терминалов используется для обеспечения доступа к корпоративным (внутренним) ресурсам, обеспечивает функциональные возможности в среде, подобной централизованному хосту на основе терминала, или мэйнфрейма, в которой различные терминалы соединяются с главной ЭВМ. Каждый терминал обеспечивает канал для ввода и вывода данных между пользователем и главной ЭВМ. Пользователь может войти в основной сервер через терминал, и затем выполнять различные приложения, обращаясь к файлам, базам данных, сетевым ресурсам главного сервера. Использование терминалов позволяет повысить безопасность СО РДЗ, а также снизить затраты на оборудование и разработку клиентского программного обеспечения. Характеризуется средним объемом передаваемых данных; базы данных позволяют осуществлять хранение, обработку и выдачу различной информации по требованию абонента. виртуальные сети позволяют организовать защищенный обмен данными между некоторой группой пользователей; распределенные, GRID вычисления обычно не требуют доставки данных в реальном режиме времени, также характеризуются средним объемом передаваемых данных.
Данное оборудование различается как по техническим характеристикам, так и по стоимости, что создает дополнительные трудности при выборе конкретного оборудования для реализации СО РДЗ. Необходимым требованием несомненно является соответствие международным и национальным стандартам, т.к. использование нестандартизированного оборудования в будущем может создать проблемы при расширении или модернизации СО РДЗ.
Множество средств безопасности Р0 включает в себя следующие элементы, оказывающие непосредственное влияние на множество сетевых средств и находится в зависимости от требований абонентов. Прежде всего, это физическая защита линий связи, телекоммуникационного оборудования, оконечного терминального оборудования. Также в данное множество входят средства шифрования (криптошлюзы) обеспечивающие изолированный защищенный обмен данными, брандмауэры, системы обнаружения атак (IDS).
В данном множестве не рассматриваются такие специфичные каналы как водная среда, по причине использования исключительно в средствах связи специального назначения, а также инфракрасный канал связи, из-за низкой скорости обмена данными.
Достаточно неявное влияние на СО РДЗ оказывают природные условия эксплуатации. Среди множества природных условий Wr следует выделить основные элементы, такие как: топология местности (горная местность, равнина) прежде всего накладывает ограничения на использование радиоканала, также необходимо учитывать данный параметр и для кабельных каналов связи; температурный режим ограничивает спектр используемого телекоммуникационного оборудования, необходимо использовать активное охлаждение, также оказывает влияние на выбор типа кабеля для повышения пожарной безопасности; повышенная влажность также повышает требования к оборудованию, которое используется в СО РДЗ; географическое положение ограничивает использование спутниковых каналов связи, некоторые спутники могут находиться ниже линии горизонта, т.е. не доступны для приема; в районах с повышенной ветровой нагрузкой требуется повышение прочности приемно-передающих антенн или отказ от использования радиоканала; сейсмическая активность накладывает ограничения на использование кабельных каналов связи из-за сложной конструкции зданий, а также ненадежности (высока возможность обрыва).
Особенности эталонного метаграмматического описания топологической структуры
Для решения задачи структурно- параметрического синтеза предлагается использовать разработанный специальный подкласс метаграмматик -стохастические атрибутные метаграмматики.
Применение правил согласования типа «терминал - начальный нетерминал» (TS) позволяет снизить громоздкость структурно-лингвистического описания сложных структур данных за счет исключения повторных описаний однотипных элементов.
Проведенный анализ стандартов проектирования СО РДЗ, а также ключевых параметров, отвечающих за эффективное функционирование СО РДЗ показал, что в общем случает топологическая структура представляет собой топологию «расширенная звезда», также показано, что использование СКС при создании СО РДЗ создает иерархическую систему.
Для описания правил генерации топологической структуры с использованием САМ достаточно использовать регулярные грамматики, что позволяет использовать высокоскоростные алгоритмы и их модификации для синтаксического анализа, составляющего процедурную основу синтеза топологической структуры СО РДЗ.
1. Разработан специальный подкласс метаграмматик - стохастические атрибутные метаграмматики (САМ). Произведена формализация основных понятий развиваемого теоретического аппарата метаграмматик, позволившая создать теоретические основы для классификации и исследования основных свойств САМ. Классификация САМ по разработанной системе признаков, показала отсутствие строгих ограничений на вид применяемых грамматик.
2. Произведен анализ свойств САМ, показавший существенное уменьшение громоздкости синтаксических описаний при сохранении дескриптивной выразительной мощности порождаемых языков. Показано, что использование помимо стандартных правил согласования типа «терминал- начальный символ» (TS) и «терминал- нетерминал» (TN) дополнительного правила согласования типа «атрибут-атрибут» (АА), позволяет порождать языки относящиеся к более сложным по иерархии Хомского, а также учитывать нерегулярные связи, семантические зависимости, отражающие сложноструктурированный характер топологической структуры современных СО РДЗ РСУ.
3. Разработаны эталонные метаграмматические описания правил формирования топологической структуры СО РДЗ, основанные на САМ и позволяющие направленно генерировать варианты, а также производить расчет основных параметров создаваемой СО РДЗ и учесть специфику современных СО РДЗ, использующихся в распределенных системах управления.
4. Показано, что применение САМ позволяет использовать в качестве процедурной компоненты синтеза модификации алгоритмов синтаксического анализа регулярных метаграмматик, имеющих квадратичную временную сложность.
Метод и алгоритмы структурно- параметрического синтеза топологической структуры сетей обмена разнородными данными и знаниями распределенных систем управления
С целью разработки процедурной компоненты генерации и анализа вариантов построения топологической структуры СО РДЗ предложен модифицированный метод синтаксического анализа (СА) ориентированный на САМ - метод «горизонтального расширения» (ГР).
Суть предложенного метода заключается в процедуре рекурсивного спуска по правилам согласования TS, с задержкой на текущем уровне метаграмматики, с последующей полной генерацией варианта построения топологической структуры на этом уровне, на основе предсказания терминалов на следующем уровне и грамматическим разбором полученной входной цепочки. После завершения генерации и разбора на текущем уровне, процедура повторяется для следующего, более низкого уровня.
Особенностью данного метода является возможность проверки корректности уже существующих систем, а также их модернизации, помимо генерации новых СО РДЗ. Для выбора последующего шага синтаксического анализа используется стохастическая составляющая, позволяющая, в зависимости от выбранного приоритетного ресурсного ограничения, применять различные правила подстановки. Стохастическая составляющая вводится «учителем» при проектировании эталонных метаграмматических описаний, ее значения определяются эвристически, согласно стандартам проектирования СО РДЗ. Также возможно задание стохастической составляющей на основе анализа уже существующих, функционирующих систем. Параметры синтезируемой топологической структуры соответствуют синтезируемым и наследуемым атрибутам терминалов и нетерминалов САМ. Процесс генерации вариантов прекращается, как только найден первый вариант, удовлетворяющий всем ограничениям.
Разрабатываемый метод СА ориентирован на применение регулярных САМ с TS, TN и АА правилами согласования. Аналогично известным работам определяется интерпретация правил согласования TS и TN. Правила согласования АА (атрибут-атрибут) интерпретируются как глобальный наследуемый или синтезируемый атрибут. Область действия этих атрибутов распространяется на всю метаграмматику, что позволяет учитывать нерегулярные связи, семантические зависимости, отражающие сложноструктурированный характер топологической структуры современных СО РДЗ РСУ.
Для формального описания алгоритмов, реализующих предложенный метод СА, введены следующие обозначения. Состояние САМ -М={А, а, к, 1, х, z }, где: вектор TS правил согласования - х; вектор АА правил согласования - z; вектор текущих терминалов - а; вектор текущих нетерминалов - А; вектор текущих значений синтезированных атрибутов - к; вектор текущих значений наследуемых атрибутов -1. Предложенный алгоритм синтаксического анализа «горизонтального расширения» заключается в последовательном выполнении следующих шагов для грамматики im произвольного уровня т: 1. В грамматике і уровня m производится поиск наиболее вероятного правила подстановки Л - а, где Л" текущее состояние вектора нетерминалов, согласно стохастической составляющей йш) из ранее не использовавшихся правил. Выполняется, если возможно, вычисление унаследованных и синтезированных атрибутов, значения которых заносятся в соответствующие вектора. 2. Производится определение правил согласования TS вида g гс 2-і где $J L начальный нетерминал грамматики G уровня n , M n m и занесение их в вектор TS. 3. В грамматике і уровня m производятся операции по грамматическому разбору согласно шагам 1-2 до тех пор, пока не останется нетерминалов во входной цепочке или не будут выполнены требования для текущего уровня системы. 4. В случае применения всех обычных правил и правил согласования TS, производится переход на уровень n=m-l. Также производится перенос в грамматику GJ, согласно правилам согласования АА наследуемых и синтезируемых атрибутов. 5. Для уровня п повторяются процедуры 1-2 с удалением TS правил для уровня п из вектора TS и добавлением новых, для уровня о= п-1. 6. На каждом уровне производится вычисление унаследованных атрибутов и генерация синтезируемых атрибутов, в случае невыполнения заданных требований, текущему правилу подстановки назначается наименьший приоритет. В случае, когда возможна генерация и анализ, производится предсказание в грамматике следующего состояния на К шагов (К =1), в зависимости от заданных настроек синтаксического анализа. 7. В случае невозможности выполнения заданных требовании и ограничений, производится возврат на уровень выше и перераспределение значений атрибутов. Если это невозможно, производится заново генерация цепочки для этого уровня.
Процедура СА считается завершенной, как только выполнены все требования и ограничения заданные пользователем. Оставшиеся завершения работы процедуры СА нетерминалы могут быть использованы для последующей модернизации топологической структуры СО РДЗ. Использование векторов позволяет производить возвраты, в случае неудачного разбора, для проверки другой ветви разбора. В общем случае, алгоритм ГР является модификацией алгоритма синтаксического разбора «сверху- вниз», что позволяет использовать фрагменты хорошо известных алгоритмов синтаксического анализа, ориентированных на регулярные грамматики.
Сущность предложенного алгоритма заключается в следующем: Установка начальных значений параметров работы алгоритма и требований к создаваемой топологической структуре, таких как стоимость, количество рабочих станций, режим и условия работы и др.
Производится ввод анализируемой цепочки. На этом этапе цепочка разбивается на группы символов с одинаковыми атрибутами, для повышения скорости синтаксического анализа. Из текущей цепочки берется первый левый символ и производится попытка поиска продукции вида A, Pi yakAj, содержащей в левой части текущий символ. На этом этапе возможно применение одного из модифицированных алгоритмов поиска продукции.
Особенность модифицированных алгоритмов заключаются в порядке просмотра продукций. Выбирается параметр, по которому будут сортироваться продукции. Это либо вероятность применения продукции, либо, в случае одинаковой вероятности применения данной продукции атрибутные зависимости, прежде всего синтезированные атрибуты. Это позволяет более эффективно усекать множество генерируемых вариантов и снижает вероятность ложного выбора продукции.
Далее, когда продукция найдена, производится замена текущего символа входной цепочки правой частью продукции. Производиться расчет унаследованных, синтезированных атрибутов, а также занесение правил согласования АА в вектор и их вычисление.
Особенности системы синтаксического синтеза и анализа топологической структуры сетей обмена разнородными данными и знаниями
В целях реализации разработанного метода структурно- параметрического синтеза СО РДЗ в рамках реализованной основы ПК разработано ядро системы синтаксического синтеза и анализа, представляющая из себя программную библиотеку (Addln), динамически включаемый в состав ПК.
Основу составляющую ядро системы представляет разработанный framework (каркас) - стандартную библиотеку, включающая в себя библиотеку готовых решений (типы данных, коллекции, функции реализующие служебные алгоритмы) и набор ограничений (автоматическая проверка корректности кода и метаданных). Данная библиотека реализована на платформе .NET, что не накладывает жестких ограничений на используемый язык программирования. В данном конкретном случае использовался CSharp(C#) как базовый язык реализации, а также проблемно-зависимый мета язык Lua, для повышения гибкости и масштабируемости приложений.
Lua — легковесный (англ. light-weight) интерпретируемый язык программирования, разработанный подразделением Tecgraf Католического университета Рио-де-Жанейро (Computer Graphics Technology Group of Pontifical Catholic University of Rio de Janeiro in Brazil). Является свободно распространяемым, с открытыми исходными текстами на языке Си. По возможностям, идеологии и реализации язык ближе всего к JavaScript, однако Lua отличается более мощными и гораздо более гибкими конструкциями, спроектирован с целью «не плодить сущности сверх необходимого». Хотя Lua не содержит понятия класса и объекта в явном виде, механизмы объектно-ориентированного программирования с поддержкой прототипов (включая множественное наследование) легко реализуются с использованием метатаблиц, которые также позволяют перегрузку операций и т. п. Реализуемая модель ООП (как и в JavaScript) — прототипная. Синтаксис Lua можно описать как нечто среднее между Си (JavaScript) и Паскалем. Подобно таким скриптовым языкам, как Python и Icon, допускает многократные присваивания.
В настоящее время используется в различных системах, где требуется встроить достаточно быстрый и нетрудный в освоении скриптовый язык программирования. Как и многие интерпретируемые языки программирования, реализация LUA имеет отдельно компилятор с исходного языка в исполняемый байт-код и виртуальную машину для исполнения сгенерированного байт-кода. Надо отметить компактность байт-кода: в генерируемом коде используется всего 35 команд. Причём байт-код — это не команды стековой машины, а команды некоего виртуального процессора с несколькими регистрами, что повышает эффективность исполнения. В стандартной виртуальной машине LUA используется распределение памяти со сборкой мусора (аналогично Java). Для задач критичных по времени имеется ЛТ компилятор LUA LuaJIT. LUA использует единый строковой пул, что позволяет снизить расходы памяти на хранение строк.
Рассмотрим функциональные особенности представленных блоков системы, а также их реализацию в составе framework.
Редактор грамматических и метаграмматических описаний представляет собой полнофункциональный текстовый редактор, с несколькими видами представлений. Основным форматом, поддерживаемым данным редактором является GML формат. Реализована подсветка синтаксиса данного формата, а также свертка кода и динамические подсказки при редактировании. При вводе формальных описаний на панели представления представлено дерево грамматики, с разделением его структуры на основные части, описание символов грамматики, продукций. Существует альтернативное представление формального описания в виде РБНФ и диаграмм Вирта. Основная особенность данного подходя заключается в возможности редактировать формальное описание в любом из доступных видов представления. Также представлена возможность сохранять созданное формальное описание в одном из поддерживаемых форматов. Между тем, основным форматом является GML, все остальные форматы получаются путем преобразования через внутренние типы данных. Возможности ПК позволяют создать собственное представление, необходимое пользователю, что повышает универсальность ПК.
Эталонные грамматические описания (модели) представляют собой несколько классов, реализованные в составе Framework. Абстрактные классы, такие как: 1. Abstractltem - представляющий собой общий класс для всех элементов грамматики. 2. AbstractFormalGrammar - абстрактный класс, являющийся наследником Abstarctltem и представляющий собой формальную грамматику в ее общем виде. 3. AbstractProduction - абстрактный класс, являющийся наследником Abstarctltem и представляющий собой продукцию в ее общем виде. 4. AbstractSymbol - абстрактный класс, являющийся наследником Abstarctltem и представляющий собой символ грамматики в его общем виде. На основе абстрактных классов созданы классы, отражающие конкретные грамматики и их элементы. Также реализованны коллекции - специальные классы для хранения объектов составляющих грамматики и их элементы: 1. SymbolCollection - служит для хранения символов грамматики. 2. ProductionCollection - служит для хранения продукций, входящих в грамматику.
