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

• Автор: Фадеев, Роман Викторович
• Шифр специальности: 05.13.17, 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Таганрог
• Количество страниц: 266 с. : ил.

ВВЕДЕНИЕ
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 Синтез грамматики языка на основе набора исходных текстов с помощью инструментальной среды Мультитранслятор
5.2 Трансляция программ в программы на языке и с помощью инструментальной среды Мультитранслятор
5.3 Применение инструментальной среды Мулыитранслягор для выполнения многоязыковой трансляции.
5.4 Применение инструментальной среды Мультитранслятор при разработке грамматики языка для решения задач в области цифровой связи
5.5 Применение инструментальной среды Мультитранслятор в учебном процессе.
5.6 Выводы.
ЗАКЛЮЧЕНИЕ.
СПИСОК СОКРАЩЕНИЙ
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ


Наличие универсальной среды трансляции решает для пользователя проблему разработки собственных трансляторов, изучения языков программирования для их написания и углубления в теорию синтаксическою анализа, однако попрежнему трудоемкой задачей для пользователя остается ввод продукционных правил в СМТ при создании нового направления трансляции, в связи с чем возникает необходимость в разработке средств автоматизации этого процесса. В случае если грамматика входного языка имеется, но она представлена в формате, отличном от формата СМТ, средства многоязыковой трансляции должны предоставлять возможности импорта грамматик, причем данные возможности должны быть расширяемыми, то есть должен существовать способ для пользователя описывать новые форматы и затем выполнять импорт грамматик из них в СМТ. Однако в некоторых случаях грамматика входного языка может быть недоступна, что требует ее ручного восстановления с последующей проверкой на контрольных примерах. Данная задача может быть формализована, и грамматика может быть синтезирована на основе входного текста. Проблема состоит в том, что согласно классической формализации задачи СГ, известной как идентификация языка в пределе iiii i ii , не существует возможности вывести грамматику языка, исходя только из набора имеющихся текстов, независимо от их количества. Согласно , существует конечный набор строк, принадлежащих некоторому языку положительные примеры, и, возможно, другой конечный набор строк . Язык является идентифицируемым в пределе, если существует процедура для поиска грамматики , такая что 1. Как утверждается в , , обучение для контекстносвободных языков может проводиться только с помощью пары . Таким образом, данное утверждение теоретически отвергает возможность синтеза КСграмматик на основе только положительных примеров. Однако в большинстве практических задач, и тем более в СМТ, отрицательные примеры не доступны. Кроме того, согласно , обнаружение наименьшего конечного автомата, совместимого с данными положительными и отрицательными наборами, является полной задачей . Были предприняты попытки решить задачу синтеза i рамматик, используя различные методы решения, такие как применение нейронных сетей , , генетических алгоритмов , , эвристик на основе статистических данных ,. Однако любой из предложенных методов имеет ряд серьезных ограничений. Как указано в , большинство исследовательских работ в области синтеза грамматик сфокусировано на регулярных языках, являющихся лишь подмножеством КС . Более того, большинство предложенных алгоритмов решения до настоящего времени не нашли своего практического применения . Из попыток практического применения методов синтеза можно выделить работу , из действующих моделей известна лишь система I , позволяющая выводить грамматику натурального языка, основываясь на коротких предложениях. Вес это указывает на достаточную сложность и неформализуемость задачи СГ. Однако, учитывая область применения СМТ, можно рассматривать способ решения проблемы синтеза грамматик за счет ограничения класса задач не с точки зрения синтаксической структуры языка, а области его применения семантики. Например, знание того, что обрабатываемый КСязык принадлежит к классу алгоритмических языков или языков описания данных, может дать определенную информацию о его структуре. Наличие такой информации позволит использовать определенные методы обработки входного текста, характерные именно для данного класса языков. Наличие систем синтеза в средствах многоязыковой трансляции позволит автоматизировать процесс ввода грамматик, что выгодно отличит СМТ от существующих средств построения СТ. Данное свойство открывает новые возможности в повышении эффективности применения СМТ пользователем. Идеи многоязыковой трансляции были формально определены в работах , . Однако и до этого формального изложения проблемы на практике неоднократно предпринимались попытки в той или иной форме разработать удобную и эффективную среду для построения трансляторов, предоставляющую возможность минимизации труда пользователя. Был разработан и в настоящее время успешно эксплуатируется ряд программных комплексов, которые можно отнести к средствам организации трансляции с возможностью применения различных СПП. Ниже приведен их анализ с целью определения необходимости разработки СМТ.