Содержание к диссертации
Введение
1 Аналитический обзор методов построения инструментальных средств многоязыковой трансляции 13
1.1 Сравнительный анализ инструментальных средств многоязыковой трансляции и существующих современных средств трансляции 13
1.2 Известные проблемы средств многоязыковой трансляции и предлагаемые способы их решения 19
2.1 Способ организации систем продукционных правил и формат их
описания пользователем 19
1.2.2 Организация универсального механизма разбора входного текста 21
1.2.3 Возможности применения в средствах многоязыковой трансляции способов автоматизации процесса ввода продукционных правил 22
1.3 Анализ имеющихся инструментальных средств, соответствующих средствам многоязыковой трансляции 24
1.4 Выводы 29
2 Разработка и исследование методов и средств анализа текста в инструментальных средствах мног оязыковой трансляции 31
2.1 Организация универсального ядра трансляции 31
2.2 Выбор метода синтаксического анализа для организации средств многоязыковой трансляции 32
2.3 Исследование и разработка алгоритмов оптимизации процесса трансляции текста для повышения производительности работы универсального ядра трансляции 37
2.3.1 Анализ возможностей оптимизации процесса трансляции 37
2.3.2 Алгоритм сегментации списков 39
2.3.3 Алгоритм разложения рекурсивных грамматических конструкций в циклы 43
2.3.4 Алгоритм свертки ИЛИ-вершин 47
2.3.5 Алгоритм предсказания правильной ветви на основе хеширования 50
2.3.6 Алгоритм предсказания правильной ветви на основе статистических данных 54
2.3.7 Алгоритм замены множества терминалов виртуальным терминалом 62
2.3.8 Алгоритм создания снимков состояния дерева разбора 65
2.3.9 Экспериментальные исследования алгоритмов оптимизации 68
2.4 Исследование возможностей распараллеливания процесса трансляции для повышения быстродействия его работы в средствах многоязыковой трансляции .70
2.5 Выводы 76
3 Разработка и исследование алгоритмов синтеза грамматик на основе исходных текстов для инструментальных средств многоязыковой трансляции 79
3.1 Исследование возможностей синтеза грамматик на основе исходных текстов... 79
3.2 Разработка и исследование алгоритма индуктивного вывода ключевых слов 82
3.3 Разработка и исследование алгоритма поиска соответствий грамматических конструкций 91
3.4 Разработка и исследование алгоритма образования иерархической структуры текста 104
3.5 Разработка и исследование алгоритма поиска операторных скобок для повышения качества работы системы синтеза грамматик 1 13
3.6 Выводы 116
4 Разработка и исследование языка описания продукций и инструментальной среды многоязыковой трансляции 119
4.1 Разработка языка описания продукций 119
4.2 Разработка и исследование процедуры сопоставления входному языку нескольких выходных языков в одном трансляционном модуле 130
4.3 Расширение мерности грамматического дерева для трансляции текстов схожих языков или различных версий языка 132
4.4 Разработка универсального ядра трансляции, компилятора языка описания продукций и виртуальной машины для выполнения конечных трансляционных модулей... 135
4.5 Разработка инструментальной среды «Мультитранслятор» 142
4.6 Экспериментальные исследования алгоритмов синтеза грамматик на основе разработанной инструментальной среды «Мультитранслятор» 150
4.7 Применение открытой архитектуры инструментальной среды для внедрения в нее дополнительных специализированных модулей 164
4.8 Выводы 169
5 Практическое использование разработанных инструментальных средств многоязыковой трансляции 172
5.1 Синтез грамматики языка ACSL на основе набора исходных текстов с помощью инструментальной среды «Мультитранслятор» 172
5.2 Трансляция ACSL-npoграмм в программы на языке C++ и Object Pascal с помощью инструментальной среды «Мультитранслятор» 177
5.3 Применение инструментальной среды «Мультитранслятор» для выполнения многоязыковой трансляции 185
5.4 Применение инструментальной среды «Мультитранслятор» при разработке грамматики языка для решения задач в области цифровой связи 187
5.5 Применение инструментальной среды «Мультитранслятор» в учебном процессе 192
5.6 Выводы 193
Заключение 195
Список сокращений 197
Список использованной литературы
- Известные проблемы средств многоязыковой трансляции и предлагаемые способы их решения
- Исследование и разработка алгоритмов оптимизации процесса трансляции текста для повышения производительности работы универсального ядра трансляции
- Разработка и исследование алгоритма индуктивного вывода ключевых слов
- Расширение мерности грамматического дерева для трансляции текстов схожих языков или различных версий языка
Введение к работе
В условиях широкого применения современной вычислительной техники во всех областях человеческой деятельности остро востребованными являются задачи трансляции текстовых данных.
Используемые в настоящее время программные средства трансляции (СТ) позволяют автоматически выполнять заданный перевод. Однако известные СТ, как правило, являются завершенными продуктами [1-5], в то время как при решении некоторых современных прикладных задач с их применением возникает необходимость в оперативной корректировке алгоритмов их работы или даже в самостоятельной разработке СТ пользователем. Например, современное разнообразие диалектов языков программирования [11, 12, 14] приводит к необходимости адаптации существующих СТ под определенный диалект [1, 10], а развитие систем моделирования постоянно требует увеличения количества различных средств трансляции для переноса разработанных моделей между системами. Указанные прикладные задачи могут быть решены с помощью самостоятельной разработки СТ пользователем при наличии соответствующих инструментальных средств (ИС).
Несмотря на то, что для разработки средств трансляции в настоящее время применяются специальные программные ИС - генераторы компиляторов, позволяющие автоматизировать значительную часть выполняемых разработчиками СТ действий [26, 27, 28, 29], они не предоставляют возможности организации СТ пользователем. Данные ИС ориентированы на специалистов в области синтаксического перевода и компиляции (СПиК) и программирования. Известно [5, 6], что задача построения трансляторов всегда определялась как высокотехнологичная и времяемкая, которая может быть решена только соответствующими специалистами. Это препятствует массовой разработке СТ, так как в прикладных областях разработка СТ для выполнения специфических трансляций может оказаться нерентабельной с учетом стоимости ее выполнения группой специалистов. Технические детали организации трансляторов, незнание пользователем языков программирования и отсутствие у него профессиональных знаний в области СПиК исключают возможность создания и последующей
модификации им средств трансляции для решения возникающих прикладных задач. В связи с эти возникает проблема разработки инструментальных средств организации трансляции, предоставляющих возможности создания и модификации трансляторов, предназначенных для решения прикладных задач, конечным пользователем без участия специалистов [7-9].
Несмотря на актуальность отмеченной проблемы, исследования в области трансляции в настоящее время сосредоточены на дальнейшей разработке генераторов компиляторов (ГК) [29-37]. Однако данные средства ориентированы в основном на автоматизацию процесса разработки законченных средств трансляции специалистами и не предоставляют возможностей организации СТ пользователями.
В связи с этим представляет интерес новый класс средств построения СТ -средства многоязыковой трансляции (СМТ), предложенный на кафедре Вычислительной техники Таганрогского Радиотехнического Университета. Данные средства отличаются от традиционных ГК новым уровнем абстракции задачи трансляции за счет отделения описания правил трансляции от технических вопросов ее организации, что предоставляет возможность пользователям самостоятельно создавать и редактировать правила трансляции. При использовании СМТ задача создания трансляторов сводится не к разработке их как отдельных программных продуктов, а к формальному описанию правил трансляции, интерпретируемых в дальнейшем средствами СМТ. Это позволяет упростить и автоматизировать процесс создания трансляторов, а также исключить необходимость применения дополнительных языков программирования для кодирования трансляторов и, соответственно, применения любых дополнительных инструментальных средств, связанных с этими языками. В результате этого задача разработки и модификации правил трансляции и их дальнейшего использования решается интегрированно в пределах СМТ и становится доступной пользователю.
Указанные возможности СМТ позволяют применять их для решения отмеченной проблемы разработки прикладных средств трансляции пользователем. Данная работа посвящена исследованию и разработке инструментальных средств, реализующих изложенные в работах [38, 39] идеи многоязыковой трансляции.
ЦЕЛЬ И ЗАДАЧИ РАБОТЫ. Целью диссертационной работы является разработка и исследование инструментальных средств многоязыковой трансляции
7 (СМТ), позволяющих организовать интегрированный процесс создания, редактирования, отладки и применения правил трансляции (ПТ) пользователем и таким образом решить проблему построения прикладных трансляторов. При этом ставится цель разделения процесса описания ПТ и технической организации процесса трансляции, а также автоматизации процесса создания и модификации ПТ, что позволяет пользователю, решающему прикладные задачи трансляции с помощью СМТ, обходиться без профессиональных знаний и навыков в области синтаксического перевода и компиляции.
Для достижения поставленных целей работы решаются следующие задачи:
анализ особенностей организации инструментальных средств многоязыковой трансляции, исследование существующих методов трансляции, определение возможности их использования при построении СМТ, а также исследование вопросов оптимизации выбранных методов для повышения эффективности работы СМТ;
разработка и исследование специальных языков описания правил многоязыковой трансляции, позволяющих определять грамматику исходного языка для разбора входного текста и действия по формированию выходного текста;
разработка и исследование способов автоматизации процесса описания правил многоязыковой трансляции и разработка алгоритмов синтеза грамматик по исходным текстам.
создание и исследование программной реализации инструментальных СМТ, позволяющих пользователю создавать и редактировать правила многоязыковой трансляции;
Работа выполнена в соответствии с пунктами 3.3 («...Принципы создания языков данных, языков манипулирования данными, языков запросов...»), 3.5 («Разработка и исследование моделей и алгоритмов анализа данных... методов и алгоритмов анализа текста...») паспорта специальности 05.13.17 и пунктом 3.2 («Синтаксис и семантика языков программирования, построение и оптимизация трансляторов, создание и реализация языков программирования») паспорта специальности 05.13.11.
МЕТОДЫ ИССЛЕДОВАНИЯ. Для решения поставленных задач используются методы теории синтаксического анализа, перевода и компиляции,
8 теории множеств, регулярных выражений и элементы теории искусственного интеллекта. Для экспериментального исследования предложенных методов организации СМТ была разработана программная инструментальная среда «Мультитранслятор» с использованием инструментальных средств Microsoft Visual C++, 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], позволяющая сторонним разработчикам добавлять свои расширения функциональных возможностей СМТ. Так в частности, в виде подобных расширений были разработаны кодогенераторы исходных текстов трансляционных модулей для языков C++ и Object Pascal.
В настоящее время на основе разработанной инструментальной среды многоязыковой трансляции «Мультитранслятор» на кафедре вычислительной техники Таганрогского радиотехнического университета (ВТ ТРТУ) ведутся
10 работы по организации комплекса распределенной многоязыковой трансляции с помощью сети Internet [104].
ИСПОЛЬЗОВАНИЕ РЕЗУЛЬТАТОВ РАБОТЫ. Теоретические и практические результаты диссертационной работы использовались на кафедре ВТ ТРТУ при выполнении научных исследований совместно с Университетом штата Южная Каролина. Результаты диссертационной работы применены в ООО НПП «Спецстрой-Связь», г. Таганрог при разработке языка описания конфигураций цифровых автоматических телефонных станций. Разработанная программная инструментальная среда многоязыковой трансляции «Мультитранслятор» использована на кафедре ВТ ТРТУ при организации лабораторного практикума «Исследование продукционных систем принятия решений» по курсу «Системы искусственного интеллекта и нейрокомпьютеры». Применения результатов диссертационной работы подтверждены соответствующими актами о внедрении. Программный комплекс «Мультитранслятор» демонстрировался в музее ТРТУ в номинации «Достижения в информационных технологиях» в 2002 г.
АПРОБАЦИЯ РАБОТЫ. Основные результаты работы докладывались и обсуждались на:
V Всероссийской научной конференции с международным участием молодых ученых и аспирантов «Новые информационные технологии. Разработка и аспекты применения» (г. Таганрог, 2002 г.);
Международной научно-технической конференции «Интеллектуальные системы (IEEE AIS'03)» ( п. Дивноморское, 2003 г.);
Всероссийской научной конференции молодых ученых и аспирантов (г. Таганрог, 2003 г.);
Международной научно-технической конференции «Интеллектуальные и многопроцессорные системы (ИМС 2004)» (г. Таганрог, 2004 г.);
Научно-технических конференциях профессорско-преподавательского состава, аспирантов и сотрудников ТРТУ (г. Таганрог, 2000 - 2004гг.). ПУБЛИКАЦИИ. По результатам диссертационной работы опубликовано 5
печатных работ и получено 3 авторских свидетельства о регистрации программ.
СТРУКТУРА И ОБЪЕМ РАБОТЫ. Диссертационная работа состоит из введения, пяти разделов и заключения, изложенных на 206 страницах, содержит 93
рисунка, 21 таблицу, 105 наименований библиографии и 60 страниц приложений, всего 266 страниц.
В ПЕРВОМ РАЗДЕЛЕ проводится анализ состава и структуры современных СТ, выявляются особенности организации СМТ, отличающих их от имеющихся современных средств организации трансляции. Приводится анализ современных программных средств построения СТ, реализующих некоторые функциональные возможности СМТ, и определяются их недостатки. По результатам анализа делается вывод об отсутствии инструментальных средств, способных решить указанную в диссертации проблему организации прикладных СТ пользователем, и необходимости разработки и исследования инструментальных средств на базе СМТ. Производится анализ задач, возникающих при разработке СМТ, формулируются требования к разрабатываемым инструментальным средствам многоязыковой трансляции, приводятся основные этапы работы СМТ и описывается их структура.
ВО ВТОРОМ РАЗДЕЛЕ обосновывается выбор метода обработки входного текста и рассматриваются его преимущества. На основе метода синтаксического анализа LL(Backtrack) рассматриваются вопросы организации процедуры разбора входного текста и производится анализ эффективности ее работы. Исследуются способы оптимизации LL(Backtrack)-aHanH3a, позволяющие ускорить процесс трансляции. На основании предложенных способов разрабатываются алгоритмы оптимизации и приводятся результаты экспериментов. Проводится сравнение эффективности полученной процедуры разбора входного текста с современными быстродействующими специализированными способами разбора. Анализируются возможности распараллеливания процесса трансляции на многопроцессорных системах в качестве способа повышения производительности СМТ.
В ТРЕТЬЕМ РАЗДЕЛЕ исследуются возможности и способы выполнения синтеза грамматик языков по исходным текстам. Определяется класс языков, подлежащих процедуре синтеза в условиях ее применения в средствах многоязыковой трансляции. Приводится разбиение задачи синтеза на подзадачи и для каждой из них разрабатывается алгоритм решения. Полученные алгоритмы экспериментально исследуются для выявления их возможностей и ограничений.
В ЧЕТВЕРТОМ РАЗДЕЛЕ производятся разработка и исследование программного инструментального средства многоязыковой трансляции
12 «Мультитранслятор». Разрабатывается язык описания правил трансляции и исследуются его функциональные возможности. Исследуются вопросы расширения функциональности конечных трансляционных модулей для поддержки нескольких версий входного языка, приводятся способы трансляции текста с одного языка в несколько других с использованием одного трансляционного модуля. Приводится описание составных частей разработанного программного инструментального средства «Мультитранслятор»: универсального ядра трансляции, компилятора правил трансляции, виртуальной машины, отладчика, интегрированной среды. Рассматриваются вопросы разработки платформо-независимых трансляционных модулей на основе разработанной виртуальной машины. Изучаются возможности отладки правил перевода на основе встроенного отладчика. Рассматриваются средства импорта, экспорта и визуализации грамматик на основе диаграмм Вирта. Приводится практическая реализация алгоритмов синтеза грамматик на основе исходных текстов и экспериментальные показания скорости их работы. Разрабатывается схема построения средств многоязыковой трансляции на основе открытой архитектуры и приводятся примеры расширения СМТ внешними модулями при решении специфичных прикладных задач с помощью программного комплекса «Мультитранслятор».
В ПЯТОМ РАЗДЕЛЕ рассматриваются примеры построения трансляционных модулей СМТ для перевода текстов программ, написанных на языках ACSL и Modelica, в языки XML и C++ их дальнейшего использования в системе виртуального моделирования (Virtual Test Bench, VTB) в рамках научно-исследовательских работ кафедры ВТ ТРТУ совместно с Университетом штата Южной Каролины. Приводятся результаты применения средств синтеза грамматик на основе исходных текстов ACSL-программ, а также описываются результаты применения программной инструментальной среды «Мультитранслятор» при создании языка описания разметки тегов на предприятии ООО НПП «Спецстрой-Связь», г. Таганрог. Приводятся результаты применения инструментальной среды многоязыковой трансляции «Мультитранслятор» в учебном процессе кафедры ВТ ТРТУ.
В ЗАКЛЮЧЕНИИ формулируются основные выводы и результаты диссертационной работы.
Известные проблемы средств многоязыковой трансляции и предлагаемые способы их решения
Согласно проведенному в подразделе 1.1 анализу средства многоязыковой трансляции (СМТ) предоставляют возможность ведения и пополнения базы данных СПП, что обеспечивает пользователей постоянно расширяющимся набором готовых решений. Следует рассмотреть вопрос организации СПП. Стандартный способ представления СПП представляется в виде отношений {SIL}: {A0L} s 1:1, то есть одной грамматике входного языка IL соответствует один набор действий по генерации выходного представления OL). Однако можно предложить расширенный вариант хранения продукционных правил в СПП. Так как в системе продукционных правил хранится как левая, так и правая часть продукций, то ее можно организовать в иерархической форме - каждой левой части СПП может быть сопоставлено несколько правых частей, что позволяет использовать одну входную грамматику и несколько вариантов по генерации выходного текста. Например, если необходимо выполнять преобразование C++- SmallTalk и C++- Object Pascal, то СПП можно представить так, как показано на рисунке 1.5.
Подобная структура хранения продукций позволяет оптимизировать работу пользователя с ними. Например, для рассматриваемого случая задача модернизации грамматики C++ потребует изменения только одной СПП, несмотря на то что фактически существует два транслятора, связанных с грамматикой C++ (C++ SmaHTalk и C++- -Object Pascal).
Аналогично можно организовывать обратные схемы: нескольким входным грамматикам сопоставлена общая правая часть продукций, Такие схемы позволяют эффективно выполнять трансляцию не с одного языка IL в OL, а с группы языков /Z/..ЛД являющихся диалектом языка 1L.
Важным вопросом при организации СМТ является способ представления продукционных правил для их ввода пользователем в СМТ. Можно рассматривать 2 основных подхода: задание СПП в графической форме и в текстовой форме с помощью специального языка. Графический способ удобен для описания {S }, так как грамматики языков представляют собой граф отношений синтаксических единиц. Для описания {SiL}, например, можно применять диаграммы Вирта [10,91]. Однако графический способ неприемлем для описания действий по формированию выходного текста на языке OL. Для описания действий оптимальным способом является использование текстовой формы с применением специального языка. С учетом указанных обстоятельств оптимальным способом і OL] if-І является использование текстового формата для задания {S } и {А } как наиболее универсального способа представления информации. Однако в качестве способа ввода грамматик можно рассматривать и графический метод, так как он является более демонстративным. Более того, графически заданную грамматику всегда можно преобразовать к текстовому описанию и наоборот, что позволяет использовать оба метода одновременно.
Исследование и разработка языка описания продукций, способов представления грамматик в графическом виде, а также методов иерархической организации СПП приведены в разделе 4 данной работы.
Возможность формирования пользователем {SILj для разнообразных формальных языков ставит перед СМТ задачу построения такого ядра трансляции, которое бы позволило обрабатывать входной текст инвариантно относительно входного языка JL. Различные классы формальных языков обычно описываются с помощью грамматик различных классов и обрабатываются разными методами синтаксического анализа [1-5]. У каждого из этих методов существуют свои преимущества и недостатки. Преимущества, как правило, заключаются в высокой скорости разбора текста, недостатки - в вводимых ограничениях на синтаксическую структуру языков, за счет которых и достигается высокая скорость работьг. С учетом синтаксических особенностей языков и класса решаемых задач, разработчик специализированного транслятора может выбрать наиболее оптимальный для него способ синтаксического анализа и программно реализовать на его основе процедуру разбора.
С учетом того, что одной из задач инструментальных средств многоязыковой трансляции является сокрытие от пользователя технических особенностей организации процесса трансляции и синтаксический разбор осуществляется с помощью универсального ядра трансляции, входящего в состав СМТ, задача обеспечения синтаксического разбора текстов любых формальных языков должна быть решена средствами СМТ без участия пользователя. Это означает, что при построении СМТ необходимо выбрать такой метод синтаксического анализа, который позволяет обрабатывать любые формальные языки.
Исследование и разработка алгоритмов оптимизации процесса трансляции текста для повышения производительности работы универсального ядра трансляции
В настоящее время LL(Backtrack)-анализ применяется достаточно редко [1]. Как правило, современные трансляторы используют вариации LL(1)-анализа, характеризующегося использованием направляющих терминалов [1-6, 10]. Этот способ разбора является более быстродействующим, чем Backtrack.
Причины его эффективности заключаются в особенностях построения Щ1) -грамматики, которая составляется таким образом, чтобы при обработке символа а- во входной цепочке а,а,...а„ обеспечивался однозначный выбор правила. Следствием подобной организации процесса разбора является тот факт , что анализатор никогда не возвращается к элементу д(_( ,х є {1,/-1}, находясь в позиции / и, следовательно, анализатор не сохраняет историю состояний маркера входного текста при продвижении по синтаксическому дереву. При Backtrack - разборе возвраты производятся для альтернативных правил, начинающихся с одинаковых подцепочек. В этом случае откат из правила ведет к восстановлению маркера в лексическом анализаторе па позицию, соответствующую вершине дерева, до которой производится откат [2]. Данная особенность Backtrack - анализа существенно замедляет синтаксический разбор [3]. Временная характеристика его работы составляет с" !, где - входная цепочка, с - некоторая константа, в то время как безвозвратные методы разбора (например, LL(1)) работают в зависимости c\w\. Низкая скорость трансляции не всегда приемлема, поэтому в данной работе ставится задача разработать методы оптимизации Backtrack-анализа, чтобы повысить его эффективность и сохранить универсальность и простоту использования.
Проведенный анализ показывает, что для синтаксического разбора с возвратами характерны следующие три ресурсоемкие операции:
1) необходимость накапливать цепочку действий по мере выполнения синтаксического анализа, что ведет к созданию временных структур данных для хранения промежуточных результатов;
2) использование частых «холостых» рекурсивных вызовов процедуры перемещения по синтаксическому дереву.
3) необходимость вести стек состояний цепочки лексического анализатора для каждой вершины дерева и выполнять откаты в случае неудачно разобранной ветви;
Очевидных способов избежать использования данных операций не существует, однако можно оптимизировать их работу. Для увеличения эффективности процесса трансляции необходимо снизить следующие показатели Backtrack-анализа:
1) объем оперативной памяти, используемой для хранения промежуточных результатов между процессами разбора текста и выполнения действий;
2) количество рекурсивных вызовов основной процедуры разбора (оптимизация рекурсий);
3) количество промахов при выборе одной из нескольких ветвей разбора (алгоритм предсказания правильной ветви).
В следующих разделах исследуются алгоритмы, позволяющие повысить эффективность работы 1Х(Васкп аск:)-анализа.
Как правило, современные трансляторы выполняют разбор входного текста IP(IL) и генерацию выходного OP(OL) в параллельном режиме - на каждом таге синтаксического анализа следует выполнение соответствующих, согласно системе продукций, действий [4, 5]. Однако использование подхода с возвратами существенно изменяет стандартную процедуру, так как применение параллельного режима в сочетании с Backtrack делает невозможным выполнение действий в продукциях одновременно с разбором. Для разбора с возвратами характерно использование раздельных стадий трансляции: сначала производится разбор текста, а затем выполнение действий.
Последовательный способ разбора неизменно влечет за собой создание дополнительных структур данных для представления промежуточных результатов. Так, лексический анализатор должен иметь готовый список лексем для возможности перемещения по нему назад и вперед, синтаксический анализатор должен предоставить цепочку пройденных вершин для дальнейшего выполнения действий. И если выполнение лексического анализа в параллельном режиме с синтаксическим еще можно организовать, хотя и с большими потерями производительности, то параллельное выполнение синтаксического анализа и действий невозможно в принципе.
Разработка и исследование алгоритма индуктивного вывода ключевых слов
Одной из особенностей алгоритмических языков и языков описания данных является наличие ключевых слов, определяющих ту или иную грамматическую конструкцию. В общем случае лексический состав языка может быть определен как множество {CNT, Ю, DL, WD}, где CNT- набор констант, ID - набор идентификаторов, DL - набор разделителей, WD - набор ключевых слов.
В совокупности с разделителями (такими, как точка, запятая, кавычка, дефис, скобки и прочее) ключевые слова образуют основу любой грамматики, поэтому знание ключевых слов является необходимым условием при выполнении синтеза грамматики. Однако в то время как разделители заранее известны и могут быть обработаны лексическим анализатором, набор ключевых слов заранее не известен и требует наличия процедуры их выделения. Основная проблема выделения ключевых слов в алфавите языка состоит в том, что в общем случае, согласно правилам лексического анализа, {WD} с {ID}. Таким образом, задача обнаружения ключевых слов сводится к построению алгоритма выделения из множества ID подмножества WD на основе статистического анализа исходного текста. Простейшим анализом в данном случае можно считать подсчет соотношения идентичных ID в обработанном тексте к размеру всего множества обнаруженных ID, то есть
Несмотря на объемное описание алгоритма, его суть достаточно проста и может быть изложена следующим образом. При принятии решении о принадлежности лексемы к ключевым словам необходимо исходить из следующих положений: - ключевое слово достаточно устойчиво появляется во всех предоставленных входных текстах, причем чем больше набор входных текстов, тем равномернее будет коэффициент устойчивости ключевого слова, и, в общем случае, Кр - 1 при N -» х , где Кр- коэффициент устойчивости ключевого слова, N - количество входных текстов; - ключевое слово занимает в структуре документа определенную позицию, что отражается на виде лексем, отстоящих справа и слева от него: чем меньший набор лексем справа и слева встречается от указанного слова, тем больше вероятность того, что данное слово является ключевым; - ключевые слова всегда присутствуют в языках класса АМСД, поэтому при решении, принадлежит ли слово к набору ключевых слов, целесообразнее применять не абсолютный порог отсечения, а относительный, исходя из полученной максимальной оценки одним из слов (п. 9).
Смысл коэффициента / заключается в том, что все языки класса АМСД имеют склонность к размещению ключевых слов в начале строки или вообще на отдельной строке. Естественно, данное утверждение весьма условно, так как любую программу можно записать в виде одной строки, но, тем не менее, общепринятые правила форматирования текста следующие: - ключевое слово часто начинается с новой строки (например, слова program, procedure, function, var В языке Pascal [23] принято записывать с начала строки); - реже ключевое слово завершает строку; - если слово в строке единственное, то, скорее всего, оно ключевое, так как неключевые слова обычно образуют выражения и не имеют смысла в отдельном размещении. Обычно такие слова указывают на начало нового раздела в тексте (например, слова derivative, initial, end в языке ACSL [18] или слова interface, implementation в языке Pascal). Использование коэффициента Кс дает эффективные результаты для текстов, отформатированных согласно определенному стандарту. Более того, Л не оказывает отрицательного влияния на общий результат алгоритма, если текст не отформатирован или правила форматирования меняются от документа к документу. В этом случае Кс будет просто приближен к нулю.
В рассмотренном алгоритме ИВКС должны быть определены коэффициенты кь к2, к3. Коэффициенты kh к2, kj задают соотношение приоритетности трех видов расположения лексемы между собой. Значения этих коэффициентов определяют значение Кс, что в дальнейшем влияет на конечный коэффициент К. Завышение коэффициентов kr k3 приводит к чрезмерному влиянию коэффициента Кс на общий исход, занижение - к исключению К( из суммарного К. Как показали экспериментальные исследования, для всех языков АМСД коэффициенты k, k2, k3 можно принять равными 1.1, 1.2 и 1.3.
При выполнении п.1 алгоритма ИВКС можно ввести дополнительную проверку ИВКС 1 на минимальную длину ключевых слов: длина ключевого слова должна быть более одного символа. Дополнение ИВКС1 обусловлено тем обстоятельством, что современные языки класса АМСД используют в качестве ключевых слов осмысленные слова или слитные словосочетания из натуральных языков, что исключает использование слов из одной буквы или слов, содержащих цифры (существуют, конечно, такие однобуквенные слова, как «Г» или «я», но их процент настолько мал, а семантический смысл несущественен, что этим набором можно пренебречь). В ИВКС] можно включить и другие проверки, например, учет регистра букв в ключевых словах или проверка на отсутствие цифр, символа подчеркивания и других символов в ключевых словах. При этом ИВКС1 может конфигурироваться самостоятельно без участия пользователя. Для этого достаточно организовать двухпроходное выполнение
Расширение мерности грамматического дерева для трансляции текстов схожих языков или различных версий языка
В подразделе 4.2 была рассмотрена ситуация, когда один язык I.L транслируется в несколько выходных. Однако иногда возникает и противоположная задача: транслировать несколько входных языков в один выходной язык OL. Наиболее часто данная задача встречается при трансляции языка IL, имеющего несколько диалектов. Наличие диалектов характерно для каждого популярного современного языка, например, C/C++ или Basic. В основном, это связано с реализацией компиляторов для данных языков различными фирмами-разработчиками, а также применением этих языков в специализированных областях. Иногда также встречаются ситуации, когда поздние версии одного и того же языка несовместимы с более ранними (как, например, было в ранних версиях языка Modelica [17]). В подобных случаях выгодно разрабатывать один проект с поддержкой в нем нескольких входных языков.
С данной целью в ЯОГ были введены расширения для описания нескольких входных языков. Принцип описания использовался тот же, что и для трансляции в несколько выходных языков: в тексте модуля при описании грамматики применялись директивы IL, EIL для указания специфики языка.
Рассмотрим применение данного способа описания на примере ранее использовавшейся грамматики арифметического выражения (рисунок 4.2). Предположим, что существует версия грамматики, в которой арифметические операции обозначаются с помощью ключевых слов ADD, SUB, MUL и DIV. Чтобы совместить обе версии грамматики в одном модуле, необходимо описать правила так, как это показано на рисунке 4.11 (представлен фрагмент грамматики).
Полный листинг модуля трансляции арифметических выражений представлен в Приложении В.
Перед выполнением компиляции трансляционного модуля компилятор ЯОП запрашивает у пользователя, для какого конкретно входного языка необходимо создать транслятор. Однако, в отличие от случая с несколькими выходными языками, в данном случае пользователь может не знать заранее, с какой версией входного языка он будет в дальнейшем работать. Если при трансляции исходного текста заранее неизвестно, на какой из версий грамматик он написан, пользователю необходимо применять поочередно все версии транслятора до тех пор, пока он не определит подходящий. Однако подобного перебора можно избежать, если разместить в скомпилированном трансляционном модуле одновременно все версии грамматики входного языка. При этом необходимо хранить не отдельные грамматические деревья для каждой версии входного языка, а образовывать общее дерево. Такое грамматическое дерево расширяется до трехмерного представления, где в качестве третьего измерения выступает список версий входного языка. Таким образом, дерево разбора может быть представлено так, как это показано на рисунке 4.12.
Каждый новый входной язык выделяется в отдельный слой дерева. При такой модификации дерева синтаксический анализ выполняется в последовательности: - слева направо; - сверху вниз; - внутрь дополнительных слоев.
Разрешаются переходы между слоями, например, правило из второго слоя может ссылаться на правила из первого слоя. Эта возможность является основополагающей в данном случае. Ведь проблема диалектов языков состоит в различии лишь отдельных фрагментов дерева при сохранении неизменного вида его основных ветвей.
Таким образом, объединение в одном трансляционном модуле грамматик различных диалектов входного языка позволяет повысить функциональные возможности средств многоязыковой трансляции и упростить процесс разработки пользователем трансляционных модулей.
Создание высокоуровневого языка описания продукций, на основе которого предполагается построение трансляционных модулей в СМТ, приводит к необходимости разработки компилятора для данного языка, переводящего описание в объектный код транслятора. Учитывая тот факт, что средства многоязыковой трансляции должны иметь два ядра разбора текста - для компилятора ЯОП и для конечных трансляторов - было решено разработать единое универсальное ядро трансляции (УЯТ), позволяющее как компилировать программу на ЯОП, так и транслировать текст по указанной системе продукций. В результате схема работы программного комплекса СМТ может быть представлена так, как показано на рисунке 4.13.
