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

При построении синтаксического анализатора как составной части транслятора необходимо проводить эквивалентные преобразования грамматики реализуемого языка. Сейчас языковые технологии активно включаются в различные сферы нашей жизни, что привело к развитию современных транслирующих систем, ориентированных на разнообразный ассортимент вычислительных устройств во многих предметных областях. При этом наиболее остро проявилась проблема быстрой настройки (преобразования) синтаксического определения языка на ту форму, которая допускает автоматическую или ручную реализацию, а также проблема учёта ограничений выбранного метода синтаксического анализа. Первая проблема обусловлена разнообразием спецификаций реализуемых языков, диапазон которых простирается от обычной формы Бэкуса-Наура (БНФ) и языка разметки HTML, до двухуровневых и других видов грамматик. Вторая — ведёт либо к языковой неоднозначности, либо к недетерминированности распознающего автомата. Решение этих проблем связано с корректным отображением транслируемого языка во внутреннее машинное представление. Для этого следует эффективно использовать информацию о языке, определяя его синтаксис и статическую семантику в виде специальной КС-грамматикой (трансляционной), которая помимо основной своей функции порождения цепочек языка позволяет задавать трансляции, необходимые разработчикам.

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

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

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

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

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

2. Построение модели определения и распознавания языка на основе синтаксической граф-схемы с целью проверки свойств и ограничений* на входную трансляционную грамматику для автоматического синтеза распознавателя языка.

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

4. Построение экспериментальной инструментальной программной1 системы, реализующей разработанные алгоритмы, для практической проверки на" практике предложенных новых методов на известных эталонных примерах.

В соответствии с целью и перечисленными^выше задачами’объектом исследования являются КСР-грамматики, а предметом исследования — эквивалентные преобразования КСР-грамматик, их свойства и ограничения при построении эффективных распознавателей языков.

Методы исследования. Для решения поставленных задач в работе используются методы теории формальных языков и автоматов, теории графов и методы объектно-ориентированного программирования.

Научной новизной обладают следующие результаты выполненных исследований:

1. Впервые сформулирована и доказана теорема об адекватности распознающего автомата, построенного на основе синтаксической графсхемы и подкласса КСР-грамматик. (Совпадение, порождаемых и распознаваемых’языков).

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

3. Разработана инструментальная система? SynGT (Syntax Graph Transformation), позволяющая выполнять основные алгоритмы эквивалентных преобразований и алгоритм регуляризации’КСР^-грамматики.

Обоснованность и достоверность научных положений, основных" выводов w рекомендаций^ содержащихся в диссертации обеспечиваются* анализом состояния’исследований в области технологий"построения трансляторов (рассмотрены практически все технологии? начиная с 60-х^ годов прошлого века), корректным’применением!методов-исследований? корректностью формулировок и строгим построением^доказательств утверждений «и следствийа также подтверждаются реализацией предложенных алгоритмов в инструментальной* системе SynGT и результатами ее экспериментального применения на^фрагментах реальных языков>программирования.

Практическая* ценность результатов, работы. Разработанные модели и алгоритмы направлены на^ разрешение проблемы эквивалентных преобразований^{регуляризации} трансляционных грамматик ипредставлены в виде экспериментальной программной системы, позволяющейпо сравнению с известными-подходами, повысить скорость подготовки специ фикации реализуемого языка в 3−4 раза, а также точнее определить разработчику языкового процессора необходимые затраты экономических, временных и кадровых ресурсов. Разработанная автором инструментальная система SynGT используется в организациях НИЦ БТС МО РФ (с 2005 г.) и в Санкт-Петербургском государственном университете аэрокосмического приборостроения (с 2009 г.) — в диссертации приложены 2 акта о внедрении.

Разработанный алгоритм регуляризации /ССР-грамматики^ позволяет проверить, является ли порождаемый ею язык регулярным? и, тем самыми оптимизировать синтезируемый>языковой процессор.

Разработанный способ спецификации5 языка с использованием синтаксической граф-схемы может быть применён-для тестированиякорректной работы анализатора. Алгоритмы для генерациимножества* тестовых предложений языка могут быть использованы при проведении-тестирования и в других подобных действующих системах построения трансляторов.

Реализация результатов работы. Исследования, отраженные в диссертации, применялись при построении компилятора для языка ANSI Си в совместном с INRIA (Франция) и институтом A.M. Ляпунова (МГУ) проекте «ОССОткрытый компилятор языка Си», (проект № 14) и в проекте «Компилятор языка Си для цифровых процессоров» в 1995;98гг.

Результаты диссертационного исследования была использованы в рамках исследований, выполнявшихся во время стажировки в Будапештском институте Вычислительной техники Венгерской Академии Наук и при выполнении НИР по созданию транслятора языка Алгол-68, выполнявшейся в Ленинградском государственном университете.

Апробация результатов работы. Результаты диссертационного исследования докладывались на международном семинаре «Computer Networks» в Венгерской Академии наук, международных конференциях в Польше (2001, 2002, 2003), в Калининградском государственном университете (2008), серии международных конференций «Региональная информатика» в 1998, 2000, 2002, 2004, 2006, 2008 годах, серии Санкт-Петербургских межрегиональных конференциях «Информационная безопасность регионов^ России (ИБРР — 2005, 2007)» .

Публикации. Основные результаты и выводы диссертационной работы опубликованы в 20 научных публикациях, две публикации — из списка ВАК.

Структура и объем диссертации

Диссертация состоит из введения, четырех глав, заключения, трёх приложений, списка использованной литературы и двух актов внедрения результатов диссертации. Объем диссертационной работы составляет 160 страниц машинописного текста, содержит 66 рисунков, 6 таблиц и приложения.

Список литературы

включает 81 наименование.

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

— Разработаны и реализованы алгоритмы эквивалентных преобразований грамматик с целью построения компактных и эффективных анализаторов языков, с улучшенными на 10−15−20%, по сравнению с известными системами из семейства компиляторов GNU характеристиками по эффективности и объему памяти. На этих алгоритмах построена* схема регуляризации трансляционной грамматики языка. Эквивалентные преобразования и метод регуляризации на их основе являются единственным средством расширить область применимости метода синтаксического анализа языка, который фиксирован в системе построения-трансляторов.

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

— Разработана специальная инструментальная система эквивалентных преобразований КСР-грамматик SynGT, обеспечивающая автоматизированную настройку синтаксиса реализуемого языка в рамках простого метода синтаксического разбора. Система является автономной и может быть использована и в других технологиях разработки. В настоящий момент система БупСТ позволяет применять эквивалентные преобразования к правилам любой приведённой КС-грамматики в регулярной.форме. Класс трансляционных грамматик, удовлетворяющих методу синтаксического анализа, изложенному в главе 2, порождает детерминированные языки, определение которых дано Д.Кнутом.

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

— эффективностью разбора текста.(линейное время);

— достаточно широким классомдопустимых, грамматик с исчерпывающим определением его грамматических свойств (порождающие детерминированные языки).

— простым*набором базисных эквивалентных преобразований.

— Эффективность метода построения анализатора' достигается в реI зультате предварительного этапа-обработкивходной КСР-грамматики, в результате чего синтезируются таблицы состояний магазинного автомата. Если синтез таблиц заканчивается успешно (все состояния распознавателя существуют и конечны), то программа разбора, использующая построенные таблицы состояний, проводит разбор цепочки длины п за время Сп.

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

— Разработанная методика и алгоритмы эквивалентных преобразований трансляционной грамматики могут быть эффективно использованы в проектах различной направленности, связанных с реализацией языка для различных предметных областей, в том? числе на всех уровнях в системах обеспечения информационной безопасности, например, при обработке и анализе правил политик безопасности, определении поведенческих сценариев, проверке их на непротиворечивость, разработке тестов и тестовых процедур, поиске областей уязвимости кода приложений, решении задач обработки больших по объёму спецификаций требований программного проекта, документы для которых могут содержать сотни и тысячи пунктов требований, в задаче преобразования внутренних форматов данных, например, КОР-формата, описывающего ЮЕРО-диаграмму, к формату данных, описывающему иМ1-диаграмму, и многие другие.

— Алгоритм регуляризации грамматики может применяться для создания миниатюрных языковых процессоров во встраиваемое ПО.

— Достигнутый уровень автоматизации при использовании системы эквивалентных преобразований совместно с выбранной технологией автоматизации проектирования трансляторов составляет от 50% до 100% в зависимости от специфики проекта. Снижение трудозатрат — примерно в 3—4 раза.

Заключение

.