Введение к работе
Актуальность темы диссертации. При построении синтаксического анализатора как составной части транслятора необходимо проводить эквивалентные преобразования грамматики реализуемого языка. Сейчас языковые технологии активно включаются в различные сферы нашей жизни, что привело к развитию современных транслирующих систем, ориентированных на разнообразный ассортимент вычислительных устройств во многих предметных областях. При этом наиболее остро проявилась проблема быстрой настройки (преобразования) синтаксического определения языка на ту форму, которая допускает автоматическую или ручную реализацию, а также проблема учёта ограничений выбранного метода синтаксического анализа. Первая проблема обусловлена разнообразием спецификаций реализуемых языков, диапазон которых простирается от обычной формы Бэкуса-Наура (БНФ) и языка разметки HTML, до двухуровневых и других видов грамматик. Вторая - ведёт либо к языковой неоднозначности, либо к недетерминированности распознающего автомата. Решение этих проблем связано с корректным отображением транслируемого языка во внутреннее машинное представление. Для этого следует эффективно использовать информацию о языке, определяя его синтаксис и статическую семантику в виде специальной КС-грамматикой (трансляционной), которая помимо основной своей функции порождения цепочек языка позволяет задавать трансляции, необходимые разработчикам.
Существующие подходы к реализации языков и обширный набор средств автоматического построения трансляторов как правило используют встроенные в инструментальные системы разработки эквивалентные преобразования, часть из которых выполняются в ходе построения анализатора, а часть вручную, что существенно замедляет процесс разработки и приводит к большому числу ошибочных итераций. Стало очевидным, что необходимо выполнять предварительную обработку (препроцессинг) по приведению синтаксических определений языка к нужной форме с помощью автономного инструментария, позволяющего заранее сформировать синтаксис языка и оптимизировать анализатор, применением процедуры регуляризации исходной трансляционной грамматики с помощью эквивалентных преобразований. Такой инструмент должен иметь удобный интерфейс и должен обладать достаточным набором функций по выполнению преобразований. Исследование этих преобразований и их применения их в технологиях разработки трансляторов является актуальной темой исследования, поскольку ведёт к разрешению проблем языко-
4 вой неоднозначности и недетерминированности при автоматическом построении анализатора.
Цель работы и задачи исследования. Основной целью диссертационной работы является разработка методики и алгоритмов эквивалентных преобразований трансляционной грамматики при обработке языка в системах построения трансляторов, позволяющих повысить эффективность их разработки.
Для достижения поставленной цели в диссертационной работе поставлены следующие задачи:
Анализ существующих подходов и методов синтаксического разбора при построении анализатора языка с целью определения текущей картины в области применения эквивалентных преобразований и определения возможностей для её улучшения.
Построение модели определения и распознавания языка на основе синтаксической граф-схемы с целью проверки свойств и ограничений на входную трансляционную грамматику для автоматического синтеза распознавателя языка.
Разработка алгоритма регуляризации грамматики языка на основе эквивалентных преобразований синтаксической граф-схемы, позволяющего оптимизировать построенный анализатор.
Построение экспериментальной инструментальной программной системы, реализующей разработанные алгоритмы, для практической проверки на практике предложенных новых методов на известных эталонных примерах.
В соответствии с целью и перечисленными выше задачами объектом исследования являются КСР-грамматики, а предметом исследования - эквивалентные преобразования КСР-грамматик, их свойства и ограничения при построении эффективных распознавателей языков.
Методы исследования. Для решения поставленных задач в работе используются методы теории формальных языков и автоматов, теории графов и методы объектно-ориентированного программирования.
Положения, выносимые на защиту:
Новый алгоритм регуляризации трансляционных контекстно-свободных грамматик с помощью их эквивалентных преобразований, позволяющий аппроксимировать входной язык регулярными множествами слов, применимость которого показана на фрагментах реальных языков программирования, обеспечивающая высокий процент повышения эффективности, по сравнению с известными методами в системах построения трансляторов Flex/Bison, Antlr.
Новый способ задания модели реализуемого языка с использованием формального понятия синтаксической граф-схемы
грамматики, повышающий наглядность её представления, по сравнению с традиционными текстовыми формами записи в виде регулярных выражений.
3. Экспериментальная реализация инструментального средства SynGT (Syntax Graph Transformations) в виде программного продукта на языке Паскаль в Delphi 7.0 объемом 619 009 байт основной модуль, подтверждающая теоретические результаты работы на ряде экспериментов по автоматической генерации анализаторов для нескольких представительных подмножеств языков Си, Паскаль, АЛ-ГОЛ-68.
Научной новизной обладают следующие результаты выполненных исследований:
Впервые сформулирована и доказана теорема об адекватности распознающего автомата, построенного на основе синтаксической граф-схемы и подкласса /ССР-грамматик. (Совпадение порождаемых и распознаваемых языков).
Разработан и исследован алгоритм регуляризации трансляционной грамматики на основе синтаксической граф-схемы с целью получения минимального по числу состояний синтаксического анализатора.
Разработана инструментальная система SynGT (Syntax Graph Transformation), позволяющая выполнять основные алгоритмы эквивалентных преобразований и алгоритм регуляризации КСР-грамматики.
Обоснованность и достоверность научных положений, основных выводов и рекомендаций, содержащихся в диссертации обеспечивается анализом состояния исследований в области технологий построения трансляторов (рассмотрены практически все технологии, начиная с 60-х годов прошлого века), корректным применением методов исследований, корректностью формулировок и строгим построением доказательств утверждений и следствий, а также подтверждаются реализацией предложенных алгоритмов в инструментальной системе SynGT и результатами ее экспериментального применения на фрагментах реальных языков программирования. Практическая ценность результатов работы. Разработанные модели и алгоритмы направлены на разрешение проблемы эквивалентных преобразований и регуляризации трансляционных грамматик, которые представлены в виде экспериментальной программной системы, позволяющей, по сравнению с известными подходами, повысить скорость подготовки спецификации реализуемого языка в 3-4 раза и точнее определить разработчику языкового процессора необходимые затраты экономических, временных и кадровых ресурсов. Разработанная автором инструментальная система SynGT используется в организациях НИЦ БТС МО РФ (с 2005 г.) и в Санкт-
6 Петербургском государственном университете аэрокосмического приборостроения (с 2009 г.) - в диссертации приложены 2 акта о внедрении.
Разработанный алгоритм регуляризации /ССР-грамматики позволяет проверить, является ли порождаемый ею язык регулярным, и тем самым оптимизировать синтезируемый языковой процессор.
Разработанный способ спецификации языка с использованием синтаксической граф-схемы может быть применён для тестирования корректной работы анализатора. Алгоритмы для генерации множества тестовых предложений языка могут быть использованы при проведении тестирования и в других подобных действующих системах построения трансляторов.
Реализация результатов работы. Исследования, отраженные в диссертации, применялись при построении компилятора для языка ANSI Си в совместном с INRIA (Франция) и институтом A.M. Ляпунова (МГУ) проектах «ОСС- Открытый компилятор языка Си», проект № 14 и в проекте «Компилятор языка Си для цифровых процессоров». Результаты диссертационного исследования были получены в рамках исследований, выполнявшихся во время стажировки в Будапештском институте Вычислительной техники Венгерской Академии Наук, при выполнении НИР по созданию транслятора языка Алгол-68, выполнявшейся в Ленинградском государственном университете. Апробация результатов работы. Результаты диссертационного исследования докладывались на международном семинаре "Computer Networks" в Венгерской Академии наук, международных конференциях в Польше (2001, 2002, 2003), в Калининградском государственном университете (2008), серии международных конференций "Региональная информатика" в 1998, 2000, 2002, 2004, 2006, 2008 годах, серии Санкт-Петербургских межрегиональных конференциях "Информационная безопасность регионов России (ИБРР - 2005, 2007)". Публикации. Основные результаты и выводы диссертационной работы опубликованы в 20 научных публикациях, две - из списка ВАК. Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, трёх приложений, списка использованной литературы и двух актов внедрения результатов диссертации. Объем диссертационной работы составляет более 110 страниц машинописного текста, содержит 23 рисунка, 6 таблиц и приложения. Список литературы включает 78 наименований.
