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

Фадеев Роман Викторович

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ИНСТРУМЕНТАЛЬНЫХ СРЕДСТВ МНОГОЯЗЫКОВОЙ ТРАНСЛЯЦИИ

Специальности: 05.13.17- Теоретические основы информатики 05.13.11 - Математическое и программное

обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат

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

Таганрог - 2005

Работа выполнена в Таганрогском государственном радиотехническом университете.

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

Чернухин Юрий Викторович.

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

Финаев Валерий Иванович;

кандидат технических наук, старший научный сотрудник Сапрыкин Владимир Абрамович.

Ведущая организация: Ростовский государственный университет,

г.Ростов-на-Дону.

Защита состоится 19 мая 2005 г. в 14:20 на заседании диссертационного совета Д.212.259.02 Таганрогского государственного радиотехнического университета по адресу: 347928, Таганрог, пер. Некрасовский, 44, ауд. Д-406.

С диссертацией можно ознакомиться в библиотеке университета Автореферат разослан « & » апреля 2005 г.

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

диссертационного совета Д 212.259.02, доктор технических наук, профессор

Бабенко Л.К.

Общая характеристика работы

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

Используемые в настоящее время программные средства трансляции (СТ) - трансляторы позволяют автомагически выполнять заданный перевод. Однако известные СТ, как правило, являются завершенными программными продуктами, в то время как при решении некоторых современных прикладных задач с их применением возникает необходимость в оперативной коррекшровке реализованных в них правит перевода, работы или даже в самостоятельной разработке СТ пользователем. Например, современное разнообразие диалектов языков программирования приводит к необходимости адаптации существующих СТ под определенный диалект, а развитие систем моделирования постоянно требует разработки трансляторов для переноса моделей между системами. Аналогичные задачи возникают при переносе программ обработки данных между различными СУБД. Указанные прикладные задачи могут быть решены с помощью самостоятельной разработки СТ пользователем при наличии соответствующих инструментальных средств.

Несмотря на т о, что для разработки средств трансляции в настоящее время применяются специальные программные инструментальные средства - генераторы компиляторов, позволяющие автоматизировать значительную часть выполняемых разработчиками СТ действий, они не предоставляют возможности организации СТ пользователем. Данные средс1ва ориентированы на специалистов в области программирования и синтаксического перевода и компиляции (СГГиК). Известно, что задача построения трансляторов всегда определялась как высокотехнологичная и времяемкая, которая может быть решена только соответствующими специалистами. Это препятствует массовой разработке СТ, так как в прикладных областях разработка СТ для специфических задач может оказаться нерентабельной с учетом стоимости ее выполнения специалистами. Технические детали организации трансляторов, незнание пользователем языков программирования и отсутствие у нею профессиональных знаний в области СПиК исключают возможность создания и последующей модификации им средств трансляции для решения его прикладных задач. В связи с эти возникает проблема разработки инструментальных средств организации трансляции, предоставляющих возможности создания и модификсщии трансляторов, предназначенных для решения прикладных заоач, конечным пользователем без участия специачистов

Несмотря на актуальность отмеченной проблемы, исследования в области трансляции в настоящее время сосредоточены на дальнейшей разработке генераторов компиляторов (ГК). Однако данные средства ориентированы в основном на специалистов в области построения трансляторов и не предоставляют возможностей организации СТ пользователями.

В связи с этим представляет интерес новый класс средств построения СТ- средства многоязыковой трансляции (СМТ), предложенный на кафедре вычислительной техники Таганрогского государственного радиотехнического университета. Данные средства отличаются от традиционных ГК новым уровнем абстракции задачи трансляции за счет отделения описания правит трансляции от технических вопросов ее органи;ации, что предоставляет возможность 10*ОСЧНЩ1Й1Й1ййЙ,0Тгельио соз-1а"

I 1НЫНОТШ 1

1 ' удаы

в?ть и редактировать правила трансляции, не углубляясь в технические детали. При использовании СМТ задача создания трансляторов сводится не к разработке их как отдельных программных продуктов, а к формальному описанию правил трансляции, интеркрегируемых в дальнейшем средствами СМТ Это позволяет упростить процесс создания трансляторов и сделать его доступным пользователю

Указанные возможности СМТ позволяют применять их для решения отмеченной проблемы разработки прикладных средств трансляции пользователем

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

Для достижения поставленных целей работы решаются следующие задачи'

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

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

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

- создание и исследование программной реализации инструментальных СМТ, позволяющих пользователю создавать и редактировать правила многоязыковой трансляции;

Работа выполнена в соответствии с пунктами 3.3 («...Принципы создания языков данных, языков манипулирования данными, языков запросов...»), 3.5 («Разработка и исследование моделей и алгоритмов анализа данных... методов и алгоритмов анализа текста .>>) паспорта специальности 05.13.П и пунктом 3.2 («Синтаксис и семантика языков программирования, построение и оптимизация фанслягоров, создание и реа-тизацня языков npoi раммирования/>) паспорта специальности 05.13 11

Методы исследования. Для решения поставленных задач используются методы теории синтаксического анализа, перевода и компиляции, теории множеств, регулярных выражений и элементы теории искусственного интеллекта Для экспериментальною исследования предложенных методов организации СМТ была разработана про граччная инструментальная среда «Мультитранслятор» с использованием инструментальных средств Microsoft Visual О J, Borland Delphi и СУБД Inteibase. Для проведения экспериментов использовались исходные тексты программ на языках С/С++, Pascal/Object Pascal, ACSL, Modelica

Основные положения, выносимые на защиту На защиту выносятся следующие положения и результаты

- способ описания правил транс!япии в виде специального языка, включающего в себя описание t рамматики входного текста и действия по формированию выходного представления;

- алгоритмы оптимизации метода синтаксического анализа LL(Backtrack), повышающие .эффективность работы СМТ при обработке входных текстов;

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

Научная нови ¡на. Предложено решение проблемы построения прикладных СТ пользователем с помощью инструментальных средств многоязыковой трансляции на базе интегрированной среды, универсального ядра трансляции и специального языка описания правил трансляции. С целью повышения эффективности работы СМТ разработаны алгоритмы оптимизации используемого в них в качестве универсального механизма разбора метода синтаксического анализа LL(Backtrack), позволяющие достичь высокой скорости разбора входного текста и обеспечить простой и универсальный способ задания правил трансляции пользователем. В качестве метода автоматизации процесса формирования пользователем правил трансляции предложен синтез грамматик по исходному тексту и разработаны алгоритмы его выполнения, позволяющие упростить и ускорить процедуру ввода правил трансляции пользователем.

Основные научные результаты:

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

- исследованы способы описания в одном трансляционном модуле схем сопоставления одному входному языку нескольких выходных и наоборот;

- разработаны и исследованы методы оптимизации ЬЦВаск1гаск)-анализа, повышающие скорость его работы без сокращения функциональных возможностей, что позволяет более эффективно по сравнению с другими видами синтаксического анализа испочьзовать LI (Backtrack) в СМТ;

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

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

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

- на основе алгоритмов синтеза грамматик по исходному тексту реализованы инструментальные средства, позволяющие автоматизировать процесс ввода грамматики входного языка при описании правил трансляции; разработаны средства импорта и экспорта грамматических правил и? других форм описания в язык списания ПТ, что позволяет пользователю использовать имеющиеся грамматики входных языков, представ ¡енные в других форматах,

- в инструментальной среде «Мультитранслятор» применена открытая архитектора построения программных систем, позволяющая сторонним разработчикам добавлять свои расширения функциональных возможностей СМТ Так в частности. в виде подобных расширений были разработаны кодогенераторы исходных текстов трансляционных модулей для языков 0+ и Object Pascal.

В настоящее время на основе разработанной инструментальной среды многоязыковой трансляции «Мульгитранслятор» на кафедре вычислительной техники Таганрогского радиотехнического университета (ВТ ТРТУ) ведутся работы по организации комплекса распределенной многоязыковой трансляции с помощью сети Internet.

Использование результатов работы. Теоретические и практические результаты диссертационной работы использовались па кафедре ВТ ТРТУ при выполнении научных исследований совместно с Университетом штата Южная Каролина (США). Результаты диссертационной работы применены в ООО НПП «Спецстрой-Связь», г Таганрог при разработке языка описания конфигураций цифровых автоматических телефонных станций. Разработанная программная инструментальная среда многоязыковой трансляции «Мультитранслятор» использована на кафедре ВТ ТРТУ при организации лабораторного практикума «Исследование продукционных систем принятия решений» по курсу «Системы искусственного интеллекта и нейрокомпьютеры». Применения результатов диссертационной работы подтверждены соответствующими актами о внедрении Программный комплекс «Мультитранслятор» демонстрировался в музее ТРТУ в номинации «Достижения в информационных технологиях» в 2002 г.

Апробация работы. Основные результаты работы докладывались и обсуждались

на:

- V Всероссийской научной конференции с международным участием молодых ученых и аспирантов «Новые информационные технологии. Разработка и аспекты применения» (г. Таганрог, 2002 г);

- Международной научно-технической конференции «Интеллектуальные системы (IEEE AIS'03j» ( п Дивноморское, 2003 г.);

- Всероссийской научной конференции молодых ученых и аспирантов (г. Таганрог, 2003 г.);

- Международной научно-технической конференции «Интеллектуальные и многопроцессорные системы (ИМС 2004)» (г. Таганрог, 2004 г.);

- Научно-технических конференциях профессорско-преподавательского состава, аспирантов и сотрудников ТРТУ (г. Таганрог. 2000 - 2004гг.).

Публикации. По результатам диссертационной работы опубликовано 5 печатных работ и получено 3 авторских свидетельства о регистрации программ.

Структура и объем работы. Диссертационная работа состоит из введения, пяти разделов и заключения, изложенных на 206 страницах, содержит 93 рисунка, 21 таблицу, 105 наименований библиографии и 60 страниц приложений.

Содержание работы

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

В первом разделе проводится анализ состава и структуры современных средств построения трансляторов (СПТ) - генераторов компиляторов и выявляются их нетос-татки при решении проблемы разработки прикладных СТ пользователем Принцип

4

работы ГК заключается в генерации по заданной пользователем грамматике входного языка II. исходного кода синтаксического анализатора Т(И) на одном из языков программирования Далее пользователю, решающему прикладную задачу трансляции, необходимо реализовать в полученном анализаторе действия по генерации выходного текста на языке 01 и скомпилировать полученный код транслятора с помощью соответствующих инструментальных средств. В данном случае от пользователя, разрабатывающего собственный транслятор, требуется не только знание специального языка описания грамматик, с помощью которого задается грамматика входного языка //.. но и знание одного из алгоритмических языков и соответствующих инструментальных средств для дальнейшего ввода действий по генерации текста 01 Такой подход к построению трансляторов эффективен при е1 о использовании специалистами в области программирования и синтаксического анализа и компиляции, однако неприемлем в случае работы с СПТ пользователя Таким образом, из результатов анализа следует, что генераторы компиляторов (ГК) не обеспечивают эффективного решения отмеченной проблемы.

В качестве альтернативы ГК предлагается построение инструментальных средств многоязыковой трансляции (СМТ), основанных на разработанных в ТРТУ идеях мио-

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

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

- простота пользователю способа записи правил трансляции'

- возможность синтеза правил трансляции по исходному тексту на основе примеров с целью упрощения процедуры ввода правил трансляции пользователем;

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

Рисунок 1 - Схема трансляции с использованием СМТ

Правила перевода 11->01. описанные пользователем

^Текст на выходном языке 01

гоязыковой трансляции. Организация СМ Г предполагает наличие ядра трансляции, предоставляемого СМТ, и правил трансляции, описываемых пользователем (рисунок 1). Задачей пользователя при создании транслятора с помощью СМТ является описание правил трансля-

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

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

Во втором рашеле рассматриваются вопросы организации УЯТ и реализации в нем метода разбора входного текста. Универсальное ядро трансляции преобразовыва-С1 исходный текст 1Р(И), написанный на языке ¡1 в текст 0Р(01) на языке ОЬ в соответствии с описанной пользователем системой правил трансляции (продукционных правил) Р(11,01)\

,01)

Наличие в СМТ универсального ядра трансляции предоставляет возможность использования одного и того же механизм разбора текста во всех создаваемых пользователем с помощью СМТ трансляторах. При этом технические вопросы трансляции, как например, построение лексического и синтаксического анализатора, чтение входного и генерация выходного текста, реализованные в УЯТ, скрыты от пользователя и не требуют его участия.

С учетом того, что УЯТ в СМТ может использоваться пользователем для разбора самых разнообразных формальных (контекстно-свободных) входных языков, при его реализации необходимо выбрать наиболее универсальный метод синтаксическою разбора На основе литературных источников и результатов ранее проводимых на кафедре ВТ ТРТУ исследований в работе был выбран к использованию левосторонний нисходящий разбор с возвратами ЬЦВаскиаск), отличающийся гибкостью, отсутствием многих ограничений при описании грамматик и интуитивной понятностью пользователю. Его основными преимуществами являются: более свободная форма записи грамматик в связи с возможностью возвратов в дереве поиска, отсутствие кон-фтиктов операции сдвига'свергки, характерных для Ы1(к)-методов, отсутствие операции левой факторизации, характерной для ЬЬ(к)-методов, возможность применения опциональных ветвей разбора.

Однако, вследствие своей универсальности данный метод имеет недостатки, а именно необходимость в последовательном выполнении стадий трансляций и низкую скорость синтаксического разбора Как правило, современные трансляторы выполняют разбор входного текста 1Р(Щ и генерацию выходного ОР(ОЬ) в параллельном режиме - одновременно с лексическим анализом выполняется синтаксический анализ и следует выполнение соответствующих действий. Однако использование

LL(Backtrack) делает невозможным одновременное выполнение действий в продукциях вследствие возможных возвратов по дереву. Последовательный способ разбора влечет за собой создание дополнительных структур данных для представления промежуточных результатов, что означает дополнительное использование оперативной памяти и замедление разбора Для устранения этого недостатка в работе был разработан алгоритм сегментации входного текста и списка действий. Он основан на определении вершин грамматического дерева, откат из которых не возможен. В момент прохождения такой вершины производится выполнение действий из списка действий и его удаление, а также удаление всех элементов лексического списка, кроме последнего (текущего). Алгоритм основывается на том, что если любой левый раскрывающийся терминал в правиле представлен в единственном числе, то откат в поисках другого маршрута при прохождении через данный терминал не имеет смысла, то есть- при

обработке а е Т, Л -> а, откат из А невозможен, если {а}П FIRST(al)[~\FIRST(a2)f\ — C\FlRST(aN) - 0 где а - текущая лексема из входного потока, А-текущее правило, а, - очередная правая часть правила А (А —» or,, / = 1 N). /V - количество правых частей, FIRST - функция выборки множества левых терминалов.

Проведенный в работе анализ современных алгоритмических языков показал, что LL-грамматики, не прошедшие процедуру левой факторизации, обычно содержат в правилах от 40 до 50% левых уникальных в пределах правила терминалов, из чего был сделан вывод, что при условии нормального распределения лексем во входном 1ексте каждая вторая будет «безоткатной». Это означает, что алгоритм сегментации практически приводит 1.ЦВаск1гаск)-анализ к режиму параллельного выполнения.

С целью оптимизации использования оперативной памяти был разработан и исследован алюритм, заменяющий рекурсивные конструкции языка при обработке процедурой анализа на циклы, что не только экономит стековое пространство, но и сокращает время выполнения. Проведенный анализ современных алгоритмических языков показал, что в среднем в каждом языке содержится от 20 до 30% конструкций, организованных на основе рекурсий. В общем случае, грамматика, представляющая собой рекурсивный список, может быть представлена в виде 5 —> aiSql, 0 <= i <~ N , где at - предваряющая ветвь правил для каждой альтернативы правила S, qt - разделяющая ветвь, определяющая правила ограничения списка. Причем существуют еле-д\ ющие ограничения

VielOJV)3f,=0: Vie(0.JV) Se0„Sear

При обработке рекурсивной грамматики с учетом выполнения указанных условий оптимизатору необходимо организовать цикл по разбору выражений at Д до тех пор, пока не будет найден qt * 0 . В качестве критерия оценки эффективности работы алгоритма использовался максимальный достигаемый уровень вложенности процедуры разбора при обработке рекурсивных конструкций. Полученные экспериментальные результаты показали снижение этого уровня в 2 раза при использовании разработанного алгоритма оптимизации рекурсий.

Универсальность Backtiack-анализа приводит к тому, что временная характеристика его работы составляет с'1"1, где и- - входная цепочка, с - некоторая константа, в то время как менее универсальные безвозвратные методы разбора работают в зависимости c[wj. Для повышения скорости разбора был разработан и исследован алгоритм

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

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

функция IV(Р) = W(P) +-— , где Р, -очередная ветвь дерева, ЩРJ -

+1

приоритет ветви Р,.

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

В качестве метода оптимизации процесса поиска по дереву был разработан алгоритм представления множества терминалов в виде единого терминала для правил, состоящих только из набора терминалов В данном случае набор терминалов заменяется виртуальным терминалом с переопределенным оператором сравнения входной лексемы. Виртуальный терминал представляет собой набор всех терминалов, упорядоченных с помощью хеш-функции, что обеспечивает поиск любого из них с временной сложностью Ü(log2(n)), где п - количество терминалов При этом время разбора сокращается с X * п до X + log2 (п) * х, где .¥ - время, затрачиваемое на проверку одного терминала, а х • усредненное значение времени поиска элемента в хеш-таблице. Проведенные эксперименты с использованием грамматик современных алгоритмических языков, содержащих от 100 до 200 правил, показали, что ускорение процесса разбора с использованием данного алгоритма оптимизации составляет в среднем 2%. Для небольших грамматик данный показатель может быть увеличен на порядок.

В качестве дополнительного метода оптимизации, относящегося не к Васкйаск-анализу. а к вопросу построения универсального ядра трансляции, был предложен алгоритм сохранения образа грамматического дерева на носителе с последующим его быстрым восстановлением в оперативной памяти. Вследствие того, что универсальное ядро разбора существует отдельно от конечных трансляционных модулей (ТМ). при их запуске на инициализацию УЯТ требуется определенное время В процесс инициализации входит передача УЯТ грамматики /I. построение в ОЗУ синтаксического дерева разбора инициализация алгоритмов оптимизации и прочее Исключение выполнения указанных действий при каждом старте ТМ может повысить скорость их выпочнения Для опенки производительности алгоритма было предложено соотно-

время инициа ипсщии, сек шение —-------, определяющее процент времени, потраченный на

об шее время работы сек

инициализацию от общей продолжительности разбора. Результаты экспериментов показали, что с использованием данного алгоритма время инициализации может быть сокращено до 80%. что при трансляции небольших текстов (до 10 Кб) составляет 50% от общего времени трансляции.

Одновременное применение всех разработанных алгоритмов позволяет добиться высокой скорости работы ЬЦВасМгаск)-анализа без ввода дополнительных ограничений на способы описания грамматик. По результатам экспериментов было определено, что минимальное увеличение производительности работы 1Х(ВасЙгаск)-анализэ при использовании разработанных алгоритмов оптимизации составляет 2.6 раза В зависимости от формы входной грамматики увеличение скорости разбора может дос-т и гать порядка В таблице 1 представлены результаты сравнения скорости разбора текста на языке С размером 200 тыс. символов с помощью оптимизированного и не-оптимизированного ЬЬ (В ас к (г ас к) - а н ал и з а, а также безвозвратного метода 1Л(1).

Таблица 1 Результаты экспериментов по сравнению скорости работы оптимизированного ЬЬ(ВаскТгаск)-анализа с его неоптимизированной формой и с ЬЯ( 1 )-анализом

С ,01 s ж s н о s а. о s* а. я CQ X О а о о s VC e S S 2 3 bon S! 5 5 S S g 2. « В ir u с Œ >C О Время разбор с применением методов оптимизации, с 1 Коэффициент ускорения, раз ■ с S , 0 А с —. » £ л о J S ю 2 3 2 Î 3 в S J а, э а 14 3 « 2- о °ч d Ä i 1 œ - а л* « a- J

Intel Pentium IV, 1Г7ц 18 70 2.90 6.45 24 18.09 '

-, AMD Athlon 800 МГц 20.73 3.0 6.91 2 46 18.11

3 Intel Pentium III. 733 МГц 35.51 4.67 7.60 3.37 18.20

4 Intel Celeron. ^00 МГц 48.21 5 30 9.09 4.32 18.49

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

В третьем разделе исследуются возможности и способы выполнения синтеза грамматик (СГ) по исходным текстам, что позволяет упростить процедуру ввода пользователем в СМТ правил трансляции.

Пробпема задачи синтеза грамматик состоит в невозможности вывода грамматики языка только на основе набора имеющихся текстов, независимо от их количества Как указано в литературе, для выполнения синтеза грамматики С(Ц должен существовать конечный набор примеров, принадлежащих языку I. (положительные примеры), и другой конечный набор примеров не принадлежащих I (отрицательные примеры). Для СМТ отсутствует возможность получения отрицательных примеров, поэтому в работе были рассмотрены способы выполнения СГ только на основе V Было определено, что ограничение класса грамматик алгоритмическими языками и языками описания моделей и структур данных (АМСД). для которых обычно применяются СМТ. и знание особенностей данного класса языков позволяют решить задачу СГ.

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

1) статистический анализ лексем входного текста и составление на его основе списка ключевых слов с помощью алгоритма индуктивного вывода ключевых слов (ИВКС);

2) применение хранимых в базе данных СМТ грамматик для трансляции входного текста, выявление максимальных соответствий и формирование на основе выявленных соответствий частичной искомой грамматики с помощью алгоритма поиска соответствий грамматических конструкций (ПСГК);

3) выявление иерархических структур в нераспознанных алгоритмом ПСГК фрагментах текста с помощью алгоритма образования иерархической структуры (ОИС).

Алгоритм ИВКС предназначен для вывода на основе статистических данных списка ключевых слов. В общем случае лексический состав языка может быть определен как

цо) = /слт, т, т, шу,

где СИТ- набор констант, Ю - набор идентификаторов, Л/, - набор разделителей, Ш) - набор ключевых слов. В совокупности с разделителями (такими, как точка, запятая, скобки и прочее) ключевые слова образуют основу любой граммагики, поэтому знание ключевых слов является необходимым условием для образования структуры языка. Однако в то время как разделители всегда определены, набор ключевых слов заранее не известен и требует наличия процедуры их выделения. Основная проблема выделения ключевых слов состоит в том, что к общем случае, согласно правилам лексического анализа, Ш) е Ю . Таким образом, задача ИВКС сводится к выделению из множества Ю подмножества IVО. При этом алгоритм ИВКС базируется на следующих положениях:

- ключевое слово достаточно устойчиво появляется во всех предоставленных входных текстах, причем в общем случае К¡, —> 1 при N -х , где Кр - коэффициент устойчивости отдельно взятого ключевого слова, N - колгптество входных текстов,

- ключевое слово занимает в структуре документа определенную позицию, что отражается на виде лексем, отстоящих справа и слева от него и на позиции самого слова относительно начала и конца строки.

Результат работы ИВКС выражается в виде назначения каждому найденному уникальному ID коэффициента вероятности К его принадлежности к классу WD При этом данный коэффициент является суммарным результатом нескольких параметров

К=К,,+ KR,+ KRk+Kc

где K¡> - коэффициент устойчивости /£> относительно различных входных текстов, /^-коэффициент устойчивости расположения в строке, KR¡, KRF - коэффициенты устойчивости смежных символов.

Для разработанного алгоритма ИВКС была проведена серия экспериментов с применением исходных текстов различных языков, а именно С, Modélica, Object Pascal Во всех случаях am оритм показал эффективные результаты работы: были выделены все имеющиеся в исходных текстах ключевые слова.

Как показали исследования, грамматики различных АМСД языков часто имеют схожие или даже идентичные конструкции. Также не все грамматические конструкции могут быть корректно синтезированы на основе анализа текста, так как в синтаксическую структуру закладываются элементы семантики (например, приоритет выполнения операций в арифметическом выражении определяется синтаксической структурой) Поэтому перед выполнением синтеза грамматики имеет смысл произвести подбор известных грамматических конструкций из других языков на предмет их соответствия исходному тексту. Для поиска соответствий исходного текста с определенными грамматическими конструкциями, хранящимися в базе данных СМТ, быт разработан алгоритм ПСГК. Основная задача алгоритма заключается в юм, как оптимально соотнести грамматическую конструкцию из другого языка (или языков) к определенному фрагменту входного текста. В результате анализа задача ПСГК была декомпозирована на три подзадачи:

1)определение размеров и положения фрагментов текста для поиска соответствующих им фрагментов грамматики;

2)определение наиболее подходящих фрагментов грамматики к фрагментам текста;

3) импорт частей грамматики, удовлетворяющей выделенным фрагментам текста

Для решения первой задачи были исследованы возможности выделения фрагментов текста на основе найденных алгоритмом ИВКС ключевых слов и разделителей Была сформулирована стратегия образования фрагментов текстов, и на ее основе был разработан алгоритм выбора фрагментов текста.

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

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

В работе были проведены экспериментальные исследования алгоритма ПСГК, подтвердившие, что он успешно находит и импортирует готовые грамматические конструкции из имеющихся в базе данных СМТ грамматик-

Посте обработки входного текста алгоритмом ПСГК возможны остаточные фрагменты текста, не опознанные ни одной грамматикой В данном случае необходимо выполнить индуктивное образование синтаксической структуры для вывода данной цепочки 'ексем. Для этих целей в работе быт разработан алгоритм образования иерархической структуры (ОИС). С учетом проблемы синтеза грамматик на основе только положительных примеров в работе были предложены следующие принципы ! ингеза грамматик АМСД-языков:

- 1рамматика языка представляет собой набор циклических конструкций С„ ¡-О \г вложенных друг в друга в определенном порядке Корневое правило грамматики представляет собой цикл верхнего уровня, включающий р себя набор вложенных циклов В общем случае для языка I. {З^ ¡-О Л'грамматика 0(Ц имеет вид

вО.)- Д/,^. .. 15«/, (1)

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

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

На основе изложенных принципов был разработан и теоретически исследован алгоритм ОИС.

Результаты экспериментов с использованием алгоритмов ИВКС, ПСГК и ОИС подтвердили возможность построения процедур синтеза грамматик на основе исходных текстов.

В четвертом разделе приводятся результаты разработки и исследования языка описания продукций (ЯОП) и про/раммной инструментальной среды «Мультитранс-лятор».

Язык описания продукций (ЯОП) состоит из двух частей: языка описания грамматик (ЯОГ) и языка описания действий (ЯОД). ЯОГ представляет каждое правило грамматики как поименованный блок символов (терминалов и нетерминалов). Символы внутри правила могут разделяться между собой на группы, называемые вариантами или альтернативами. Таким образом, грамматику, описанную с помощью ЯОГ, можно выразить как

ОЩ = ({/?}.Я,); Л, V?

где И - правило, К - вариант, Т - символ (терминал и нетерминал).

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

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

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

При разработке трансляторов с помощью СМТ возникает необходимость предоставления возможности трансляции с языка Я, одновременно на несколько выходные языков С1Л,а, ОЬ^ Создание нового трансляционного модуля (ТМ) путем копирования грамматики 0(11.) из имеющегося ТМ является неэффективным решением, так как в случае внесения изменения в 0(1!.) необходимо выполнить модификацию и компиляцию N ТМ. Для решения этой задачи в ЯОГ был разработан специальный механизм для сопоставления в едином трансляционной модуле нескольких направлений трансляции с языка И. При описании действий в каждом правиле с помощью специальных обозначений указывается, к какому направлению разбора эти действия относятся. При компиляции ТМ с несколькими направлениями трансляции компилятор запрашивает, для какого конкретно направления необходимо выполнить сборку модуля.

Одновременно с задачей сопоставления одному входному языку нескольких выходных возникает и противоположная задача, заключающаяся в трансляции нескольких входных языков в один выходной язык 01. Наиболее часто данная задача встречается при трансляции языка II, имеющего несколько диалектов. С данной целыо в ЯОГ были введены средства описания нескольких входных языков. В данном случае грамматика языка расширяется до трехмерного представления, где в качестве третьего измерения выступает список версий входного языка Каждый новый входной язык выделяется в отдельный слой дерева. Разрешаются переходы между слоями, например, правило из второго слоя может ссылаться на правила и 5 первого слоя. Эта возможность является основополагающей в данном случае, так как проблема трансляции с нескольких диалектов языков состоит именно в различии отдельных фрагментов дерева при сохранении неизменного вида его основных ветвей.

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

Для исследования разработанного ЯОП, алгоритмов оптимизации и синтеза грамматик была разработана программная реализация инструментальной среды многоязыковой трансляции «Мультитрансляторл. В данную среду были включены универсальное ядро трансляции (УЯ Г) с реализованными алгоритмами оптимизации синтаксического разбора, компилятор ЯОП, виртуальная машина для выполнения ТМ, отладчик грамматик и действий, система синтеза грамматик и связанная с ней система хранения известных грамматик в СУБД, а также интегрированная оболочка, объединяющая все перечисленные компоненты Экранная форма интегрированной оболочки представлена на рисунке 2.

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

метальные замеры скорости работы УЯТ показали, что по эффективности рабош оптимизированный ЬЦВас1агаск)-анализ не уступает другим, менее универсальным, но более быстродействующим безвозвратным (Щ1),1.11(1) и т.д) методам синтаксического анализа.

rfe»"шат. i^&jfmmf % •

" -»»

-j ■ ¿1VS.Í ГГ --j »»mtc^COei^

O CW1 '

■»»»«• n¡r Менеджер правил

, м»л

трансляции

'PArwwiw gy71 ^wasj

-v1«ai dMcr»bcí ш " '" ' ~~

"lotoí «utcnrti* V »ji*«n

-.j latafixBtxrf

~ч> "btíCCOun C,'

-V "Ьй »«"atlM" -_> tft-tarítion rf vmW

3Í ^IJVIT

*¡f foíidi-d

Sd lemriií 'я de <J

ríw¡¡Jm/"íw ?J Окна сообщений компилятора,

romJtldlewMl

Fuwjie^ аи j5ioc*«fl"Tíi отчетов транслятора и проч

MAXftfiVAL аэМетяг* ]o< duoün <rd кют í/.' ín^isiS W desoí*« wJ eeotu Дет SJCB ' ^

aütwser .

"i -c;

Рисунок 2 - Экранная форма интегрированной оболочки инструментального средства «Мультитранслятор»

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

Разработка в составе инструментального средства «Мультитранслятор» отладчика грамматик и действий позволяет пользователю контролировать процесс трансляции на всех этапах.

В составе среды «Мультитранслятор» были также реализованы алгоритмы синтеза. Экспериментальные исследования, проводимые с использованием реализованных алгоритмов синтеза, подтвердили их работоспособность и эффективность.

Таким образом, по результатам работы был сделан вывод, что полученная реати-зация среды многоязыковой трансляции позволила решить все задачи, поставленные в главе 1, и таким образом, решить отмеченную проблему

В пятом разделе рассмотрены трансляционные модули, разработанные в инструментальной среде мноюязыковой трансляции «Мультитранслятор» для перевода текстов моделей между различными системами моделирования Разработка ТМ проводи-

лась на кафелры ВТ ТРТУ в рамках научно-исспедовательской работы. В результа!е было разработано 5 трансляционных модулей' ACSL—> С+4-. \CSL-»XML, Modélica-> XML, ModélicaC+--1-, SML-» ANSI С Приведены результаты применения средств синтеза грамматик на основе исходных текстов ACSL-программ, обеспечивающих автоматизацию ввода грамматики ACSL Описаны результаты применения протраммной инструментальной среды «Мультитранслятор» при создании языка описания разметки тегов и разработки компилятора для него на предприятии ООО НПП «Спецстрой-Связь», г Таганрог. Приведены примеры использования инструментального средст ва «Мультитранслятор» в учебном процессе

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

В приложениях приведены использованные при проведении экспериментов входные и выходные тексты программ на различных языках, описание ЯОП и результаты применения инструментального средства многоязыковой трансляции «Мультитранслятор» при решении практических задач. *

Основные результаты работы

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

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

- исследованы способы описания в одном трансляционном модуле схем сопоставления одному входному языку нескольких выходных и наоборот;

- разработаны методы оптимизации LL(Backtrack)-aHaiH3a, повышающие скорость его работы без сокращения функциональных возможностей, что позволяет более эффективно по сравнению с другими видами синтаксического анализа использовать LL(Backtrack) в СМТ;

- разработаны и исследованы алгоритмы синтеза грамматик по исходному тек-ciy. позволяющие автоматизировать процесс ввода в СМТ правил трансляции.

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

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

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

бавлять свои расширения функциональных возможностей СМТ Так. в частности, в виде подобных расширений были разработаны кодогенераторы исходных текстов трансляционных модулей для языков Гг^и Object Pascal

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

По теме диссертации опубликованы следующие работы: 1. Гузик В.Ф., Чернухин Ю.В., Поленов М.Ю, Фадеев Р В. Авюрское свидетельство об официальной регистрации программы «Интерактивная среда трансляции программы, написанных на различных алгоритмических языках (Мультитранслятор)», N2002610826,27 мая 2002 г.

2 Чернухин Ю.В., Фадеев Р.В. Методология построения гибкосвязных программных систем //Сборник трэдов пятой Всероссийской научной конференции с международным участием молодых ученых и аспирантов. - Таганрог: Изд-во ООО «Антон», 2002, с 164-165.

3 Чернухин Ю.В., Гузик В.Ф., Поленов М.Ю, Кравцов В.В, Фадеев Р.В. Авторское свидетельство об официальной регистрации программы «Сетевая версия интерактивной среды многоязыковой трансляции программ (Сетевой мультитранслятор)», N2003610431, 17 февраля 2003 г.

4 Чернухин Ю В., Поленов М.Ю , Фадеев Р.В. Интерактивная среда мультиязыковой транстяции сложных программных моделей // Межвузовский сборник научных грудов «Анализ и моделирование развивающихся интеллектуальных систем» Выпуск 4. Ростов н/Д: Изд-во СКНЦ ВШ, 2003, с 10-20.

5 Чернухин Ю.В., Гузик В Ф , Поленов М.Ю , Фадеев Р В. Методы оптимизации процедур мультиязыковой трансляции //Труды Международных научно-технических конференций «Интеллектуальные системы (IEEE AIS'03)» и «Интеллектуальные САПР» М : Изд-во Физико-математической литературы, 2003, с. 523-528.

6. Чернухин Ю.В., Фадеев РВ. Проблемы парсинга в системах мультитрансляции /'Тезисы докладов Всероссийской научной конференции молодых ученых и аспирантов «Информационные технологии, системный анализ и управление». Таганрог: Изд-во ТРТУ, 2003, с. 6-9.

7 Чернухин Ю В , Гузик В Ф., Поленов М Ю. Фадеев Р.В. Авторское свидетельство об официальной регистрации программы -'Инструментальная среда многоязыковой трансляции программных моделей виртуальных моделирующих систем». N2004611561,5 мая 2004 г.

8 Чернухин Ю В . Фадеев Р.В К вопросу автоматического синтеза грамматик по исходным текстам В книге «Искусственный интеллект Интеллектуальные и многопроцессорные системы - 2004». Материалы Международной научной конференции. Т.2 Tai анрог: изд-во ТРТУ, 2004, с 37-40.

В работах написанных в соавторстве, личный вклад автора состоит в сле-лующ^м- в [1.3,7] представлена реализация фрагментов системы многоязыковой трансляции, в [4] разработана структура инструментальных средств многоязыковой трансляции, в [5] рассмотрены методы оптимизации L! (Backtrack) поиска, в [8] предложены методы организации автомагического синтеза грамматик

Подписано в печать $ 0(/.%£>04 Формат Тираж 110 экз._ Заказ 1ЪЗ

Типография Таганрогского государственного радиотехническою университета.

«-6493

РНБ Русский фонд

2006-4 4708

f

i

ВВЕДЕНИЕ.

1 АНАЛИТИЧЕСКИЙ ОБЗОР МЕТОДОВ ПОСТРОЕНИЯ

ИНСТРУМЕНТАЛЬНЫХ СРЕДСТВ МНОГОЯЗЫКОВОЙ ТРАНСЛЯЦИИ.

1.1 Сравнительный анализ инструментальных средств многоязыковой трансляции и существующих современных средств трансляции.

1.2 Известные проблемы средств многоязыковой трансляции и предлагаемые способы их решения.

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

1.2.2 Организация универсального механизма разбора входного текста.

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

1.3 Анализ имеющихся инструментальных средств, соответствующих средствам многоязыковой трансляции.

1.4 Выводы.

2 РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ И СРЕДСТВ АНАЛИЗА ТЕКСТА В ИНСТРУМЕНТАЛЬНЫХ СРЕДСТВАХ МНОГОЯЗЫКОВОЙ ТРАНСЛЯЦИИ.

2.1 Организация универсального ядра трансляции.

2.2 Выбор метода синтаксического анализа для организации средств многоязыковой трансляции.

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

2.3.1 Анализ возможностей оптимизации процесса трансляции.

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

2.3.3 Алгоритм разложения рекурсивных грамматических конструкций в циклы.

2.3.4 Алгоритм свертки ИЛИ-вершин.

2.3.5 Алгоритм предсказания правильной ветви на основе хеширования.

2.3.6 Алгоритм предсказания правильной ветви на основе статистических данных.

2.3.7 Алгоритм замены множества терминалов виртуальным терминалом.

2.3.8 Алгоритм создания снимков состояния дерева разбора.

2.3.9 Экспериментальные исследования алгоритмов оптимизации.

2.4 Исследование возможностей распараллеливания процесса трансляции для повышения быстродействия его работы в средствах многоязыковой трансляции

2.5 Выводы.

3 РАЗРАБОТКА И ИССЛЕДОВАНИЕ АЛГОРИТМОВ СИНТЕЗА ГРАММАТИК НА ОСНОВЕ ИСХОДНЫХ ТЕКСТОВ ДЛЯ ИНСТРУМЕНТАЛЬНЫХ СРЕДСТВ МНОГОЯЗЫКОВОЙ ТРАНСЛЯЦИИ.

3.1 Исследование возможностей синтеза грамматик на основе исходных текстов.

3.2 Разработка и исследование алгоритма индуктивного вывода ключевых слов

3.3 Разработка и исследование алгоритма поиска соответствий грамматических конструкций.

3.4 Разработка и исследование алгоритма образования иерархической структуры текста.

3.5 Разработка и исследование алгоритма поиска операторных скобок для повышения качества работы системы синтеза грамматик.

3.6 Выводы.

4 РАЗРАБОТКА И ИССЛЕДОВАНИЕ ЯЗЫКА ОПИСАНИЯ ПРОДУКЦИЙ И ИНСТРУМЕНТАЛЬНОЙ СРЕДЫ МНОГОЯЗЫКОВОЙ ТРАНСЛЯЦИИ.

4.1 Разработка языка описания продукций.

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

4.3 Расширение мерности грамматического дерева для трансляции текстов схожих языков или различных версий языка.

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

4.5 Разработка инструментальной среды «Мультитранслятор».

4.6 Экспериментальные исследования алгоритмов синтеза грамматик на основе разработанной инструментальной среды «Мультитранслятор».

4.7 Применение открытой архитектуры инструментальной среды для внедрения в нее дополнительных специализированных модулей.

4.8 Выводы.

5 ПРАКТИЧЕСКОЕ ИСПОЛЬЗОВАНИЕ РАЗРАБОТАННЫХ ИНСТРУМЕНТАЛЬНЫХ СРЕДСТВ МНОГОЯЗЫКОВОЙ ТРАНСЛЯЦИИ.

5.1 Синтез грамматики языка ACSL на основе набора исходных текстов с помощью инструментальной среды «Мультитранслятор».

5.2 Трансляция ACSL-программ в программы на языке С++ и Object Pascal с помощью инструментальной среды «Мультитранслятор».

5.3 Применение инструментальной среды «Мультитранслятор» для выполнения многоязыковой трансляции.

5.4 Применение инструментальной среды «Мультитранслятор» при разработке грамматики языка для решения задач в области цифровой связи.

5.5 Применение инструментальной среды «Мультитранслятор» в учебном процессе.

5.6 Выводы.

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

Используемые в настоящее время программные средства трансляции (СТ) позволяют автоматически выполнять заданный перевод. Однако известные СТ, как правило, являются завершенными продуктами [1-5], в то время как при решении некоторых современных прикладных задач с их применением возникает необходимость в оперативной корректировке алгоритмов их работы или даже в самостоятельной разработке СТ пользователем. Например, современное разнообразие диалектов языков программирования [11, 12, 14] приводит к необходимости адаптации существующих СТ под определенный диалект [1, 10], а развитие систем моделирования постоянно требует увеличения количества различных средств трансляции для переноса разработанных моделей между системами. Указанные прикладные задачи могут быть решены с помощью самостоятельной разработки СТ пользователем при наличии соответствующих инструментальных средств (ИС).

Несмотря на то, что для разработки средств трансляции в настоящее время применяются специальные программные ИС - генераторы компиляторов, позволяющие автоматизировать значительную часть выполняемых разработчиками СТ действий [26, 27, 28, 29], они не предоставляют возможности организации СТ пользователем. Данные ИС ориентированы на специалистов в области синтаксического перевода и компиляции (СПиК) и программирования. Известно [5, 6], что задача построения трансляторов всегда определялась как высокотехнологичная и времяемкая, которая может быть решена только соответствующими специалистами. Это препятствует массовой разработке СТ, так как в прикладных областях разработка СТ для выполнения специфических трансляций может оказаться нерентабельной с учетом стоимости ее выполнения группой специалистов. Технические детали организации трансляторов, незнание пользователем языков программирования и отсутствие у него профессиональных знаний в области СПиК исключают возможность создания и последующей модификации им средств трансляции для решения возникающих прикладных задач. В связи с эти возникает проблема разработки инструментальных средств организации трансляции, предоставляющих возможности создания и модификации трансляторов, предназначенных для решения прикладных задач, конечным пользователем без участия специалистов [7-9].

Несмотря на актуальность отмеченной проблемы, исследования в области трансляции в настоящее время сосредоточены на дальнейшей разработке генераторов компиляторов (ГК) [29-37]. Однако данные средства ориентированы в основном на автоматизацию процесса разработки законченных средств трансляции специалистами и не предоставляют возможностей организации СТ пользователями.

В связи с этим представляет интерес новый класс средств построения СТ -средства многоязыковой трансляции (СМТ), предложенный на кафедре Вычислительной техники Таганрогского Радиотехнического Университета. Данные средства отличаются от традиционных ГК новым уровнем абстракции задачи трансляции за счет отделения описания правил трансляции от технических вопросов ее организации, что предоставляет возможность пользователям самостоятельно создавать и редактировать правила трансляции. При использовании СМТ задача создания трансляторов сводится не к разработке их как отдельных программных продуктов, а к формальному описанию правил трансляции, интерпретируемых в дальнейшем средствами СМТ. Это позволяет упростить и автоматизировать процесс создания трансляторов, а также исключить необходимость применения дополнительных языков программирования для кодирования трансляторов и, соответственно, применения любых дополнительных инструментальных средств, связанных с этими языками. В результате этого задача разработки и модификации правил трансляции и их дальнейшего использования решается интегрированно в пределах СМТ и становится доступной пользователю.

Указанные возможности СМТ позволяют применять их для решения отмеченной проблемы разработки прикладных средств трансляции пользователем. Данная работа посвящена исследованию и разработке инструментальных средств, реализующих изложенные в работах [38, 39] идеи многоязыковой трансляции.

ЦЕЛЬ И ЗАДАЧИ РАБОТЫ. Целью диссертационной работы является разработка и исследование инструментальных средств многоязыковой трансляции

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

Для достижения поставленных целей работы решаются следующие задачи:

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

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

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

- создание и исследование программной реализации инструментальных СМТ, позволяющих пользователю создавать и редактировать правила многоязыковой трансляции;

Работа выполнена в соответствии с пунктами 3.3 («.Принципы создания языков данных, языков манипулирования данными, языков запросов.»), 3.5 («Разработка и исследование моделей и алгоритмов анализа данных. методов и алгоритмов анализа текста.») паспорта специальности 05.13.17 и пунктом 3.2 («Синтаксис и семантика языков программирования, построение и оптимизация трансляторов, создание и реализация языков программирования») паспорта специальности 05.13.11.

МЕТОДЫ ИССЛЕДОВАНИЯ. Для решения поставленных задач используются методы теории синтаксического анализа, перевода и компиляции, теории множеств, регулярных выражений и элементы теории искусственного интеллекта. Для экспериментального исследования предложенных методов организации СМТ была разработана программная инструментальная среда «Мультитранслятор» с использованием инструментальных средств Microsoft Visual С++, Borland Delphi и СУБД Interbase. Для проведения экспериментов использовались исходные тексты программ на языках C/C++, Pascal/Object Pascal, ACSL, Modelica.

ОСНОВНЫЕ ПОЛОЖЕНИЯ, ВЫНОСИМЫЕ НА ЗАЩИТУ. На защиту выносятся следующие положения и результаты:

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

- алгоритмы оптимизации метода синтаксического анализа LL(Backtrack), повышающие эффективность работы СМТ при обработке входных текстов;

- алгоритмы синтеза грамматик по исходному тексту, позволяющие автоматизировать процесс формирования правил трансляции. НАУЧНАЯ НОВИЗНА. Предложен подход к решению проблемы построения прикладных СТ пользователем с помощью инструментальных средств многоязыковой трансляции на базе интегрированной среды, универсального ядра трансляции и специального языка описания правил трансляции. С целью повышения эффективности работы СМТ разработаны алгоритмы оптимизации используемого в них в качестве универсального механизма разбора метода синтаксического анализа LL(Backtrack), позволяющие достичь высокой скорости разбора входного текста и обеспечить простой и универсальный способ задания правил трансляции пользователем. В качестве метода автоматизации процесса формирования пользователем правил трансляции предложен синтез грамматик по исходному тексту и разработаны алгоритмы его выполнения, позволяющие упростить и ускорить процедуру ввода правил трансляции пользователем. ОСНОВНЫЕ НАУЧНЫЕ РЕЗУЛЬТАТЫ:

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

- исследованы способы описания в одном трансляционном модуле схем сопоставления одному входному языку нескольких выходных и наоборот;

- разработаны и исследованы методы оптимизации 1Х(Васк1таск)-анализа, повышающие скорость его работы без сокращения функциональных возможностей, что позволяет более эффективно по сравнению с другими видами синтаксического анализа [96,97] использовать LL(Backtrack) в СМТ;

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

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ РАБОТЫ. На основе теоретических результатов, полученных в данной работе, можно выделить следующие практические результаты:

- разработана программная инструментальная среда многоязыковой трансляции «Мультитранслятор» [99, 101, 102, 103], реализующая все необходимые пользователю операции с правилами трансляции: создание, редактирование, хранение, компиляцию, выполнение и отладку;

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

- в инструментальной среде «Мультитранслятор» применена открытая архитектура построения программных систем [87], позволяющая сторонним разработчикам добавлять свои расширения функциональных возможностей СМТ. Так в частности, в виде подобных расширений были разработаны кодогенераторы исходных текстов трансляционных модулей для языков С++ и Object Pascal.

В настоящее время на основе разработанной инструментальной среды многоязыковой трансляции «Мультитранслятор» на кафедре вычислительной техники Таганрогского радиотехнического университета (ВТ ТРТУ) ведутся работы по организации комплекса распределенной многоязыковой трансляции с помощью сети Internet [104].

ИСПОЛЬЗОВАНИЕ РЕЗУЛЬТАТОВ РАБОТЫ. Теоретические и практические результаты диссертационной работы использовались на кафедре ВТ ТРТУ при выполнении научных исследований совместно с Университетом штата Южная Каролина. Результаты диссертационной работы применены в ООО НПП «Спецстрой-Связь», г. Таганрог при разработке языка описания конфигураций цифровых автоматических телефонных станций. Разработанная программная инструментальная среда многоязыковой трансляции «Мультитранслятор» использована на кафедре ВТ ТРТУ при организации лабораторного практикума «Исследование продукционных систем принятия решений» по курсу «Системы искусственного интеллекта и нейрокомпьютеры». Применения результатов диссертационной работы подтверждены соответствующими актами о внедрении. Программный комплекс «Мультитранслятор» демонстрировался в музее ТРТУ в номинации «Достижения в информационных технологиях» в 2002 г.

АПРОБАЦИЯ РАБОТЫ. Основные результаты работы докладывались и обсуждались на:

- V Всероссийской научной конференции с международным участием молодых ученых и аспирантов «Новые информационные технологии. Разработка и аспекты применения» (г. Таганрог, 2002 г.);

- Международной научно-технической конференции «Интеллектуальные системы (IEEE AIS'03)» ( п. Дивноморское, 2003 г.);

- Всероссийской научной конференции молодых ученых и аспирантов (г. Таганрог, 2003 г.);

- Международной научно-технической конференции «Интеллектуальные и многопроцессорные системы (ИМС 2004)» (г. Таганрог, 2004 г.);

- Научно-технических конференциях профессорско-преподавательского состава, аспирантов и сотрудников ТРТУ (г. Таганрог, 2000 - 2004гг.). ПУБЛИКАЦИИ. По результатам диссертационной работы опубликовано 5 печатных работ и получено 3 авторских свидетельства о регистрации программ.

СТРУКТУРА И ОБЪЕМ РАБОТЫ. Диссертационная работа состоит из введения, пяти разделов и заключения, изложенных на 206 страницах, содержит 93

5.6 Выводы

В разделе рассмотрены прикладные задачи трансляции, в которых применение инструментального средства «Мультитранслятор» позволяет ускорить и автоматизировать процесс их решения и уменьшить трудозатраты пользователя.

Инструментальное средство «Мультитранслятор» было применено при составлении грамматики языка ACSL на основе имеющихся примеров исходных текстов. В разделе было проведено сравнение скорости разработки грамматики языка ACSL пользователем вручную и с помощью системы синтеза грамматик на основе исходных текстов, входящей в «Мультитранслятор».

Инструментальное средство «Мультитранслятор» использовалось на кафедре ВТ ТРТУ при решении задач переноса моделей между различными системами моделирования. Для переноса задач между системами ACSL, Modelica, VTB, Paragon и SML специалистами кафедры ВТ было создано 5 трансляционных модулей: ACSL —» С++, ACSL —» XML, Modelica—» XML, Modelica—» С++, SML —»ANSI С. Использование инструментального средства

Мультитранслятор» позволило специалистам кафедры ВТ ТРТУ реализовать, протестировать и применить необходимые трансляционные модули в короткие сроки без использования дополнительных языков и инструментальных средств.

Инструментальное средство «Мультитранслятор» использовалось в качестве средства для создания и отладки грамматики при разработке языка разметки тегов (ЯРТ), применяемого при описании конфигурации цифровых АТС на предприятии ООО НЛП «Спецстрой-Связь», г. Таганрог. Кроме возможностей отладчика и редактора правил трансляции, в процессе разработки грамматики ЯРТ была использована система синтеза грамматик, позволившая импортировать часть правил из грамматики языка Pascal. Импорт отдельных грамматических правил позволил автоматизировать и ускорить процесс разработки грамматики ЯРТ. На основе разработанной грамматики был построен компилятор ЯРТ. При его разработке использовались модули кодогенерации, с помощью которых семантический анализ и построение модели конфигурации АТС в компиляторе ЯРТ были реализованы на языке Object Pascal, так как на этом языке уже имелись специализированные библиотеки для работы с ЦАТС. Лексический и синтаксический анализ в разработанном компиляторе выполнялся с помощью универсального ядра трансляции (УЯТ), являющегося частью «Мультитранслятора», что позволило исключить необходимость разработки лексических и синтаксических анализаторов и таким образом сократить время разработки компилятора ЯРТ. При этом скорость синтаксического разбора текста универсальным ядром трансляции, построенного на основе оптимизированного ЬЦВаск{гаск)-анализа, была сравнима со скоростью специализированных трансляторов, что позволило применять УЯТ без снижения производительности работы компилятора ЯРТ.

Использование «Мультитранслятора» в цикле лабораторных работ по курсу «Системы искусственного интеллекта и нейрокомпьютеры» показало возможность его практического применения в учебном процессе для изучения теории синтаксического анализа и принятия решений.

ЗАКЛЮЧЕНИЕ

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

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

- исследованы способы описания в одном трансляционном модуле схем сопоставления одному входному языку нескольких выходных и наоборот;

- разработаны методы оптимизации ЬЦВаск1гаск)-анализа, повышающие скорость его работы без сокращения функциональных возможностей, что позволяет более эффективно по сравнению с другими видами синтаксического анализа использовать LL(Backtrack) в СМТ;

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

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

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

- в инструментальной среде «Мультитранслятор» применена открытая архитектура построения программных систем, позволяющая сторонним разработчикам добавлять свои расширения функциональных возможностей СМТ. Так в частности, в виде подобных расширений были разработаны кодогенераторы исходных текстов трансляционных модулей для языков С++ и Object Pascal.

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

1. Axo А., Сети Р., Ульман Д. Компиляторы: принципы, технологии и инструменты. / Пер. с англ. М.: Вильяме, 2003. - 768с.

2. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. В 2т. / Пер. с англ. М.: Мир, 1978. - Т.1 : 612 е.; Т.2 : 487 с.

3. Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. / Пер. с англ. М.: Мир, 1979. - 656с.

4. Хантер Р. Проектирование и конструирование компиляторов. / Пер. с англ.: -М.: Финансы и статистика, 1984. 232 с.

5. Грис Д. Конструирование компиляторов для цифровых вычислительных машин / Пер. с англ. М.: Мир, 1975. - 544 с.

6. Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. -Новосибирск: Наука, 1986. 344 с.

7. Genillard С. SyntaxAnalyserG: A Multi-Language Syntax Analysis Package //Ada Letters. 1991. Vol. ll,№l.-pp. 57-69

8. Lee S., Johnson T. A., Eigenmann R. Cetus An Extensible Compiler Infrastructure for Source-to-Source Transformation // Languages and Compilers for Parallel Computing: 16th International Workshop. - College Station, TX, USA, 2004. - pp. 539-553.

9. Villarreal E.E. Automated Compiler Generation for Extensible Data Languages //Ph. D. Thesis, 1994.-214 p.

10. Легалов А.И. Основы разработки трансляторов. Электронный ресурс. -Режим доступа: http://www.softcraft.ru

11. Бен-Ари М. Языки программирования. Практический сравнительный анализ / Пер. с англ. М.: Мир, 2000. - 366 с.

12. Кауфман В. Ш. Языки программирования. Концепции и принципы. М.: Радио и связь, 1993. - 432 с.

13. Рейоурд-Смит В.Дж. Теория формальных языков. Вводный курс. / Пер. с англ. М.: Радио и связь, 1988.

14. Штайнер Г. HTML/ XML/ CSS: Справочник / Пер. с англ. М: Лаборатория Базовых Знаний, 2001. 512 с.

15. Hansen M.R., Rischel Н. Introduction to Programming Using Sml. Pearson Addison Wesley, 1999. - 355 p.

16. Modelica A Unified Object-Oriented Language for Physical Systems Modeling. Tutorial. Version 1.4 Electronic resource. / Modelica Association. - 2000. Mode of access: http://www.modelica.orR/documents/ModelicaTutorial 14.pdf

17. Advanced Continuous Simulation Language (ACSL). Reference Manual. MGA Software, 1991.-350 p.

18. Поляков A.K. Языки VHDL и Verilog в проектировании цифровой аппаратуры. М.: СОЛОН-Пресс, 2003. - 320 с.

19. Алиев В. Visual Basic. Полное руководство пользователя. М: СОЛОН - Р, 2002. - 384 с.

20. Керниган Б., Ритчи Д. Язык программирования Си / Пер. с англ. М.: Финансы и статистика, 1992. - 272с.

21. Страуструп Б. Язык программирования С++, 3-е изд. / Пер. с англ. СПб.; М.: "Невский Диалект" - "Издательство БИНОМ", 1999 г. - 991 с.

22. Cooper D. Standard Pascal Reference Manual. New York: Norton, 1983.

23. Inprise Corporation. Object Pascal Language Guide. Scotts Valley: Inprise Corporation, 1999.

24. Virtual Test Bench (VTB) Electronic resource. Mode of access: http://vtb. engr. sc. edu/

25. Маккиман У. и др. Генератор компиляторов / Пер. с англ. /Маккиман У., Хорнинг Дж.,Уортман Д. М.:Статистика, 1980. - 527 с

26. Terry P.D. Compilers and Compiler Generators: An Introduction With С++. -International Thomson Computer Press, 1997 580p.

27. Feldman J.A. A formal semantics for computer languages and its application in a compiler compiler. // CACM. 1966. - №9.

28. Bennett, J.P. Introduction to Compiling Techniques: a First Course using ANSI C, LEX and YACC. McGraw-Hill, London, 1990.

29. Levine, J.R., Mason, T. and Brown D. Lex and Yacc (2nd edn). O'Reilly and Associates, Sebastapol, CA., 1992.

30. Donnelly C., Stallman Richard. M. Bison: The Yacc-Compatible Parser Generator, 8th edition. Free Software Foundation, 2003.

31. Yacc++® and the Language Objects Library Electronic resource. / Compiler Resources, Inc. Mode of access: http://world.std.com/~compres/

32. Flex, version 2.5 Electronic resource. / The Regents of the University of California. Mode of access:http://www.cs.princeton.edU/~appel/modern/c/soltware/flex/flextoc.html

33. The GENTLE Compiler Construction System Electronic resource. / German National Research Center for Information Technology. Mode of access: http://www.first.gmd.de/gentle/

34. The AnaGram Parser Generator Electronic resource. / Parsifal Software Inc. Mode of access: http://www.parsifalsoft.com

35. Parsing with Sandstone's Visual Parse++ Electronic resource. / Sandstone Inc. Mode of access: http://www.sand-stone.com/pwvp.ZIP

36. ProGrammar Parser Development Toolkit Electronic resource. / NorKen Technologies Inc. Mode of access: www.programmar.com

37. Chomsky, N. On certain formal properties of grammars // Information and Control. 1959. №2.-pp. 137-167.

38. Knuth D. Top-down syntax analysis, Lecture Notes // Acta Informatica. 1971. №1. - pp. 79-110.

39. Elder, J. Compiler Construction: a recursive descent model. Prentice-Hall, 1994. -437 p.

40. Кнут Д. О переводе (трансляции) языков слева направо / Пер. с англ // Сб. «Языки и автоматы» М.: Мир, 1975. - с 9-42.

41. Люггер Д.Ф. Искусственный интеллект. Стратегии и методы решения сложных проблем /Пер. с англ.: М.: Издательский дом «Вильяме», 2003. 864 с.

42. Чернухин Ю.В. Искусственный интеллект и нейрокомпьютеры. Таганрог: Изд-во ТРТУ, 1997. - 273 с.

43. Фридл Дж. Регулярные выражения. / Пер. с англ. Спб.: Питер, 2003. - 464 с.

44. ANSI С grammar specification Electronic resource. Mode of access: http://www.vendian.org/mncharity/ccode/grammar/

45. ADA 95 grammar specification Electronic resource. Mode of access: http://www.cs.vu.nl/grammars/browsable/ada/

46. Cobol grammar specification Electronic resource. Mode of access: h ttp:// www.cs.vu.nl/grammars/browsabl e/cobol/

47. Pascal grammar specification Electronic resource. Mode of access: http://www.moorecad.com/standardpascal/

48. Modelica A Unified Object-Oriented Language for Physical Systems Modeling. Language Specification. Version 2.1. Electronic resource. / Modelica Association. -2004. Mode of access:http://www.modelica.org/documents/ModelicaSpec21 .pdf

49. С++ grammar specification Electronic resource. Mode of access: http://www.csci.csusb.edu/dick/c++std/cd2/gram.html

50. C# language specification Electronic resource. / Microsoft Corporation. Mode of access: http://msdn.microsoft.com/library/default.asp?url=/library/en-us/csspec/html/CSharpSpecStart.asp

51. Java grammar specification Electronic resource. Mode of access: http://www.csci.csusb.edu/dick/samples/java.syntax.html

52. Richter J. Programming Applications for Microsoft Windows, 4-th edition. -Redmond: Microsoft Press, 1999. 1200 p.

53. Кнут Д. Искусство для программирования для ЭВМ. ТЗ: Сортировка и поиск. / Пер. с англ.: М.: Мир, 1978. - 844 с.

54. Седжвик Р. Фундаментальные алгоритмы на С++. Т. 1-4: Анализ, Структуры данных, Сортировка, Поиск /Пер. с англ. К.: Издательство «ДиаСофт», 2001.-688 с.

55. Бакнелл Д. "Фундаментальные алгоритмы и структуры данных в Delphi". /Пер. с англ. : СПб.: ООО "ДиаСофтЮП", 2003. - 560 с.

56. Кормен Т., Лейзерсон Ч., Ривелт. Р. Алгоритмы: построение и анализ /Пер. с англ. М.: МЦНМО, 2001. - 960 с.

57. В.А. Вальковский. Распараллеливание алгоритмов и программ, структурный подход. М: Радио и Связь, 1989. - 176 с.

58. Turney P. The gap between abstract and concrete results in machine learning //Journal of Experimental and Theoretical Artificial Intelligence (JETAI). 1991. -№3. - pp. 179-190.

59. Higuera C. Current Trends in Grammatical Inference. Advances in Pattern Recognition, Joint IAPR International Workshops SSPR+SPR'2000, Lecture Notes in Computer Science, Vol. 1876, pp. 28-31, 2001.

60. Gold M. Language identification in the limit //Information and Control. 1967. -№ 10. - pp. 447-474.

61. Valiant L.G. A theory of the learnable // Communications of the ACM. 1984. -№27.-pp. 1134-1142.

62. Angluin D. On the complexity of minimum inference of regular sets II Information and Control. 1967. №39. - pp. 337-350.

63. Lankhorst Marc M. Genetic algorithms in data analysis //Ph. D. Thesis. Rijksuniversiteit Groningen. Printed by Universiteitsdrukkerij Groningen, 1996.-144 p.

64. Angluin D. Inductive Inference of Formal Languages from Positive Data. //Information and Control, 1980. pp. 117-135.

65. Ahonen H. Generating grammars for structured documents using grammatical inference methods. Department Of Computer Science, University of Helsinki. Report A-1996-4.

66. Ahonen H., Mannila H., Nikunen E. Forming grammars for structured documents: an application of grammatical inference. In Carrasco and Oncina. pp. 153-167.

67. Richetin M., Verdnadat F. Efficient regular grammatical inference for pattern recognition. Pattern Recognition, 1984. pp. 245-250.

68. Sakakibara, Y. Learning Context-Free Grammars from Structural Data in Polynomial Time. 18th Workshop on Computational Learning Theory. 1988.

69. Sakakibara, Y. Efficient learning of context-free grammars from positive structural examples. Information and Computation, 1992 . pp. 23-60.

70. Carrasco R. C., Forcada M. L., Santamaria L. Inferring stochastic regular grammars with recurrent neural networks. In Miclet and Higuera. pp. 274-281.

71. Fletcher P. Neural networks for learning grammars. In Lucas. pp. 15/1-15/8.

72. P. Dupont. Regular grammatical inference from positive and negative samples by genetic search: the GIG method. In Carrasco and Oncina. pp. 236-245.

73. Robert M. Losee Learning Syntactic Rules and Tags with Genetic Algorithms for Information Retrieval and Filtering: An Empirical Basis for Grammatical Rules Information Processing & Management, 32 (2), 1996. pp. 185-197.

74. T. Knuutila. Inductive inference from positive data: from heuristic to characterizing methods. In Miclet and Higuera. pp. 22-47.

75. J. A. Sanchez and J.-M. Benedi. Statistical inductive learning of regular formal languages. In Carrasco and Oncina. pp. 130-138.

76. S. J. Young and H.-H. Shih. Computer assisted grammar construction. In Carrasco and Oncina. pp. 282-290.

77. Pieter W. A., Knobbe A. J. EMILE: Learning Context-Free Grammars From Examples. IML. 1996.

78. Ahonen H. Finding all maximal frequent sequences in text. In Proc. of ICML 99 Workshop, 1999.

79. Craig G. Nevill-Manning, Ian H. Witten. Identifying hierarchical structure in sequences: a linear-time algorithm. Department of Computer Science, University of Waikato, Hamilton, New Zealand.

80. Nevill-Manning, C.G. Inferring sequential structure, Ph.D. thesis, Department of Computer Science, University of Waikato, New Zealand, 1996.

81. Nelson, Mark R. LZW Data Compression. Dr. Dobbs Journal, October 1989, pp. 29-36.

82. Ковязин A. H., Востриков С. M. Мир InterBase. Архитектура, администрирование и разработка приложений баз данных в InterBase/Firebird/Yaffil. М.: КУДИЦ-Образ, 2003. - 496 с.

83. Дейт К. Дж. Введение в системы баз данных, 6-е издание: Пер. с англ. -К.;М.;СПб.: Издательский дом «Вильяме», 2000. 848 с.

84. Трельсен Э. Модель СОМ и применение ATL 3.0. / Пер. с англ. СПб.: БХВ-Петербург, 2001.-928 с.

85. Бокс Д. Сущность технологии СОМ. Библиотека программиста. / Пер. с англ. -СПб.: Питер, 2001.-400 с.

86. Gudgin М. Essential IDL: Interface Design for COM. Redmond: Addison-Wesley Pub Co, 2000. - 353 p.

87. Вирт H. Систематическое программирование. Введение / Пер. с англ.: М.: Мир, 1977.

88. Гузик В.Ф., Чернухин Ю.В., Золотовский В.Е., Доугал Р.А. Система процедурно-структурного моделирования // Информационная математика, М: Физматлит, 2003. № 1. С. 87-102.

89. Chaudhary V., Francis М., Huang X., Mantooth Н. A., «PARAGON A mixed-signal behavioral modeling environment» //IEEE International Conference on Communications, Circuits and Systems (ICCCAS'2002), June 29-30, 2002, Chengdu, China.

90. Behavioral Modeling Group Electronic resource. /Mixed Signal Computer Aided Design Lab. Mode of access: http://mixedsignal.eleg.uark.edu/paragon.html

91. Ю.В.Чернухин, Фадеев P.B. Проблемы парсинга в системах мультитрансляции. В книге «Информационные технологии, системный анализ и управление», Материалы всероссийской научной конференции молодых ученых и аспирантов. Таганрог: Изд-во ТРТУ, 2003, с. 6-9.

92. Гузик В.Ф., Чернухин Ю.В., Поленов М.Ю, Фадеев Р.В. Авторское свидетельство об официальной регистрации программы «Интерактивная среда трансляции программы, написанных на различных алгоритмических языках (Мультитранслятор)», N2002610826, 27 мая 2002 г

93. Чернухин Ю.В., Гузик В.Ф., Поленов М.Ю, Фадеев Р.В. Авторское свидетельство об официальной регистрации программы «Инструментальная среда многоязыковой трансляции программных моделей виртуальных моделирующих систем», N2004611561, 5 мая 2004 г