На правах рукописи

Федорченко

Людмила Николаевна

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

НА ОСНОВЕ ЭКВИВАЛЕНТНЫХ ПРЕОБРАЗОВАНИЙ

СИНТАКСИЧЕСКИХ ГРАФ-СХЕМ

Специальность 05.13.11 – Математическое и программное обеспечение

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

АВТОРЕФЕРАТ

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

Санкт-Петербург 2009

Работа выполнена в Учреждении Российской академии наук СанктПетербургский институт информатики и автоматизации РАН

Научный руководитель:

доктор физико-математических наук, профессор Баранов Сергей Николаевич

Официальные оппоненты:

доктор технических наук, старший научный сотрудник Марлей Владимир Евгеньевич кандидат технических наук, доцент Дрожжин Владимир Васильевич

Ведущая организация:

Санкт-Петербургский Государственный Электротехнический университет «ЛЭТИ»

Защита состоится « 9» июля 2009 г. в 15.30_ час. на заседании диссертационного Совета Д.002.199.01 Учреждения Российской академии наук Санкт-Петербургский институт информатики и автоматизации РАН по адресу:

199178, Санкт-Петербург, Васильевский Остров, 14 Линия, д.39, телефон (812) 3283311.

С диссертацией можно ознакомиться в научной библиотеке

СПИИРАН

Автореферат разослан «_8_»_июня_2009 г.

Ученый секретарь диссертационного совета Д.002.199. Ронжин Андрей Леонидович

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

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

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

Положения, выносимые на защиту:

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

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

3. Экспериментальная реализация инструментального средства SynGT (Syntax Graph Transformations) в виде программного продукта на языке Паскаль в Delphi 7.0 объемом 619 009 байт основной модуль, подтверждающая теоретические результаты работы на ряде экспериментов по автоматической генерации анализаторов для нескольких представительных подмножеств языков Си, Паскаль, АЛГОЛ-68.

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

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

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

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

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

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

Разработанная автором инструментальная система SynGT используется в организациях НИЦ БТС МО РФ (с 2005 г.) и в СанктПетербургском государственном университете аэрокосмического приборостроения (с 2009 г.) – в диссертации приложены 2 акта о внедрении.

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

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

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

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

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

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

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

Даётся обзор литературы c 60-х годов прошлого столетия и до наших дней по существующим методам синтаксического разбора, подробно рассматриваются LL- и LR-разборы, перечисляются наиболее известные инструментальные системы построения компиляторов Lex/Yacc, Flex/Bison, Eli, Antlr, Форт-технология, ТК SYNTAX, приведена таблица с характеристиками доступных для проверок компиляторов линейки Flex/Bison. Оценивается влияние типа разбора на проблему эквивалентных преобразований. Из наиболее сложных спецификаций языка рассматриваются двухуровневые грамматики Ван Вейнгаардена и аффиксные грамматики Костера. Наиболее известным применением двухуровневых грамматик стали Алгол-68 и язык CDL-3. Общий вывод состоит в ограниченности применения в существующих системах автоматических средств для выполнения эквивалентных преобразований правил грамматики и в необходимости поиска новых подходов решения проблемы эквивалентных преобразований, основанных на использовании синтаксических граф-схем для спецификации трансляций и построения оптимального анализатора, применяя регуляризацию трансляционной грамматики для минимизации числа состояний управляющей таблицы.

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

В качестве модельного примера рассматривается линейка генераторов компиляторов Flex/Bison как типичная инструментальная система для разработки языков и объект рассмотрения преобразований.

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

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

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

Критический анализ существующих систем построения трансляторов (по информации из comp.compilers news group) позволяет отметить отсутствие полноценных методик, обеспечивающих продолжение анализа правил грамматики после обнаружения конфликтной ситуации (ошибки). Преобразование грамматики анализируемого языка проводится либо вручную, либо недостаточно полно, о приведении грамматики к такому виду, когда сгенерированный по ней анализатор минимален по числу состояний распознающего автомата, речи нет.

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

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

Во второй главе изложена математическая формализация ме-тода построения синтаксических распознавателей (анализаторов) по контекстно-свободным грамматикам в регулярной форме ( КСР грамматикам), правые части которых интерпретируются в виде регулярных выражений над терминальными, нетерминальными символами и семантиками грамматики. Отправной точкой в изложении метода послужила простая модель: регулярные выражения – как средство описания бесконечного языка, и конечный автомат – в качестве адекватного средства его распознавания. Обоснованием этой модели является теорема Клини (Stephen Cole Kleene) о том, что класс регулярных множеств является минимальным классом, содержащим все конечные множества, замкнутым относительно операций объединения, конкатенации и замыкания, и следствия из этой теоремы о возможности представления регулярных множеств (множеств, распознаваемых конечными автоматами) регулярными выражениями.

Использование этой модели возможно лишь в применении к регулярным языкам; например, на фазе лексического анализа в компиляторе.

Кроме того, всё множество регулярных выражений над фиксированным алфавитом также можно рассматривать как регулярный язык, который описывается контекстно-свободной мета-грамматикой с одним правилом, и тогда этот язык распознается конечным автоматом.который можно минимизировать и получить абсолютно оптимальный верификатор регулярных выражений. В системе SynGT, разработанной автором, такой конечный автомат реализован и используется для проверки правильности записи регулярных выражений в правилах грамматики.

В главе даётся вариант определения регулярных выражений, отличный от определений Клини, который позволяет частично решить задачу минимизации регулярных выражений и упростить их обработку. В соответствии с данными определениями множество в конечном алфавите V регулярно тогда и только тогда, когда оно либо, либо {}, либо {} для некоторого V, либо его можно получить из этих множеств, применяя конечное число раз операции объединения, конкатенации, унарной и бинарной итераций.

Определение обобщенной итерации (# ) (итерации с разделителем или итерации Цейтина) над множествами слов в алфавите V выглядит следующим образом. Пусть дан алфавит символов V = {a1, a 2,..., a n }. V * – множество всех слов в алфавите V.

Определение 1. Обобщенной итерацией множеств слов P и Q называется множество C = P # Q, состоящее из слов вида x1 y1 x 2 y 2... y n 1 x n, где x i P, i = 1,..., n, y j Q, j = 1,..., n 1, а n – положительное целое.

Для представления регулярного множества Клини ввел понятие регулярного выражения в алфавите V. Дадим определение регулярного выражения для расширенного набора операций над множествами слов.

Определение 2. Регулярным выражением множества A называется слово r ( A) над расширенным алфавитом W, где – регулярные выражения для множеств P и Q. Тогда: r ( A) = ( p; q ) для множества P Q ; r ( A) = ( p, q ), для множества PQ ; r ( A) = ( p*), для множества P * ; r ( A) = ( p + ), для множества P + ; r ( A) = ( p # q ), для множества P# Q.

Операция обобщенной итерации не расширяет множество регулярных слов и может быть определена через традиционную (унарную) операцию Клини (*) как P # Q = P, (Q, P) *, но она частично решает задачу минимизации регулярного выражения по числу вхождений символов из объединённого алфавита. Таким образом, в обобщённом регулярном выражении операции являются бинарными. Это удобно при построении обратной Польской формы записи регулярного выражения.

Для удаления из выражений лишних скобок опишем приоритеты операций: унарные операции {*} и { + } обладают наивысшим приоритетом, затем идет итерация с разделителем или обобщенная итерация {# }, затем конкатенация {, }, и далее объединение {; }. Например, регулярное выражение p*; q, p # q с учетом приоритетов означает (( p*); (q, ( p # q))).

Существенным различием между регулярным множеством слов и регулярным выражением является то, что регулярное выражение - это описание регулярного множества, а регулярное множество слов – это язык, порождаемый данным регулярным выражением, его значение.

Формулируется понятие эквивалентности для регулярных выражений:

Два регулярных выражения r ( A) и r (B ) из множества (V ) будем считать эквивалентными, если они представляют одно и тоже регулярное множество слов над алфавитом V.

Регулярные выражения, соответствующие одному и тому же регулярному множеству слов, могут быть получены друг из друга A, (; B # ( A; C ), A) ( A# ( B # C )). Отметим, что выражение в правой части эквивалентности содержит меньше операндов, а значит меньше вероятность появления конфликта Shift/Reduce при построении распознавателя.

Исходя из сформулированной цели регуляризации грамматик, следующим шагом на пути обобщения регулярной модели является определение контекстно-свободной грамматики в регулярной форме (КСР-грамматики), правила которой задаются в виде множества пар вида ( A, r ), где A – нетерминальный символ грамматики (нетерминал), а r – регулярное выражение, представляющее множество слов, являющихся значением данного регулярного выражения.

Из определения КСР-грамматики следует, что каждое правило традиционной KC -грамматики автоматически является правилом в KCP грамматике. Обратное неверно.

Например, правило для процедурного вызова в языке Ada может быть записано в следующем виде (символы терминального алфавита взяты в кавычки):

procedure_call: procedure_name, Чтобы представить то регулярное множество слов, которое порождается данным правилом, необходимо записать не одно, а несколько контекстно-свободных правил.

Принципиально новым качеством, отличающим КСР-грамматику от других подобных грамматик, является принятый в ней механизм вывода цепочек языка. Если в традиционной КС-грамматике на каждом шаге вывода происходит замена одной цепочки на другую, то в КСРграмматике цепочка заменяется значением регулярного выражения, языком L(A) – бесконечным множеством цепочек. Для представления этого множества цепочек используется понятие синтаксической граф-схемы (СГС), являющейся графовым аналогом КСР-правила, а вывод в грамматике заменяется более простой структурой – маршрутом (или путём) в СГС. Под синтаксической граф-схемой понимают набор конечных ориентированных графов с помеченными вершинами и дугами. Каждый граф соответствует одному правилу КСРграмматики и называется графом для нетерминала, определяющего КСР-правило. Две вершины графа Г A для нетерминала А являются входными и выходными с метками E А и FА. Внутренние вершины помечены терминальными и нетерминальными символами – операндами регулярного выражения правой части правила, определяющего нетерминал А, а дуги помечены контекстными символами (семантиками) – именами семантических процедур, которые должны исполняться по ходу синтаксического анализа.

На рисунках 1–3 показаны графические представления основных операций над элементарными регулярными выражениями, которые реализованы в программной системе эквивалентных преобразований SynGT:

Рис. 1. Конкатенация. Рис. 2. Объединение. Рис. 3. Итерация.

Так задаются базисные элементы, к которым рекурсивно сводятся более сложные случаи, например, такие как на рисунке 4–5.

(('a';'b'),S1,'',S2,('a';'b'),'abc')#(S3,'',S4)#'abc'.

Рис. 5. Граф, соответствующий правилу для нетерминала «Procedure_call»

Для порождения цепочек языка вводится отношение достижимости на вершинах СГС G, которое отражает возможную последовательность символов в порождаемой цепочке. Тогда маршрут x, определяющий процесс порождения цепочки x из языка LG, содержит последовательность вершин в G, первый и последний элементы которой являются входной и конечной вершинами в графе для начального нетерминала КСР-грамматики, причём, каждый элемент достижим из предыдущего (если таковой имеется), а соответствующая последовательность меток вершин представляет символы цепочки x.

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

являясь адекватным регулярному выражению (Лемма 2.2.), граф нагляднее отражает структуру КСР-грамматики и не вводит избыточную рекурсивность в KC -язык;

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

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

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

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

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

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

Разнообразные способы определения понятия состояния в СГС и переходного состояния позволяют промоделировать известные из литературы МП-преобразователи, лежащих в основе современных методов разбора (анализа).

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

Третья глава посвящена эквивалентным преобразованиям КСграмматик, используемых при трансляции языков, и описанию алгоритма регуляризации. Под регуляризацией КС-грамматики понимается процесс применения цепочки базисных эквивалентных преобразований исходной КС-грамматики G в новую КС-грамматику G1 в регулярной форме (КСР-грамматику), причем такую, что из нее иcключаются подстановками несамовставленные нетерминалы. Алгоритм исключения приводится в разделе 3.5. Если все нетерминалы КС-грамматики G не являются самовставленными, то их можно исключить из правых частей правил на начальном этапе обработки. Определяющие правила для этих нетерминалов исключаются также. В этом случае грамматика G преобразуется в грамматику G1 с одним правилом, правая часть которого является сложным по композиции операций регулярным выражением над терминалами и контекстными символами (семантиками). Значением этого регулярного выражения является регулярный язык L = L(G1 ) = L(G ).

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

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

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

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

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

3. Исключение лево- (право) рекурсивных нетерминалов из правил грамматики.

4. Выполнение операции глобальной подстановки вместо нетерминальных вершин их порождений.

5. Минимизация регулярных выражений в правых частях правил.

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

Для простоты изложения рассмотрим А -правило в КСР-грамматике, когда нетерминал А является одновременно и лево, и праворекурсивным, и рекурсия прямая. Хорошо известно, что косвенная рекурсия методом подстановок сводится к прямой. В отличие от всех известных алгоритмов извлечения крайних рекурсий, в SynGT реализован алгоритм прямого эквивалентного преобразования левоправо)рекурсивного нетерминала с использованием операции обобщённой итерации.

Рассмотрим А -правило для нетерминала A вида где r11, r12, r21, r22 - регулярные выражения над алфавитом N T.

Данное А правило (1) состоит из четырёх частей ( Ai – фрагментов), i = 1,2,3,4:

где A1 фрагмент содержит одновременно и лево, и праворекурсивное вхождение нетерминала A ;

A2 фрагмент содержит левоорекурсивное вхождение нетерминала A ;

A3 фрагмент содержит праворекурсивное вхождение нетерминала A ;

A4 фрагмент не содержит рекурсивных вхождений нетерминала A.

Рассмотрим, какие строки могут порождаться с помощью А правила (1).

Шаг 1. Рассмотрим A1 – фрагмент А -правила: A, r11, A. Используя данный фрагмент А -правила мы можем вывести строки Из определения операции # это множество строк совпадает с множеством строк, порождаемым регулярным выражением Шаг 2. Рассмотрим A2 – фрагмент А правила: A, r12.

Здесь мы можем вывести строки Из определения унарной операции * следует, что множество (2.1) порождается регулярным выражением Подставив вместо А в выражении (2) A2 –фрагмент A -правила (2.2), получим регулярное выражение Шаг 3. Аналогично для праворекурсивного вхождения нетерминала А в A3 –фрагменте. Здесь мы выводим множество строк r21 A, r21 r21 A, r21 r21 r21 A, K, которые порождаются регулярным выражением r21 *, A. Сделав подстановку вместо вхождения нетерминала A в (3) выражения r21 *, A, получим регулярное выражение Шаг 4. Окончательно, подставляя вместо вхождения нетерминала A в регулярное выражение (4) A4 - фрагмент r22, получим эквивалентное регулярное выражение Таким образом, правую часть A правила (1) можно заменить на регулярное выражение (5).

Если предварительно воспользоваться преобразованиями регулярных выражений и привести правило к такому виду, что множество L(r12 ) не содержит цепочек вида A, множество L(r21 ) не содержит цепочек вида A, а множество L(r22 ) не содержит цепочек вида A и вида A, где произвольная цепочка, тогда прямая левая и правая рекурсия для нетерминала A отсутствуют.

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

Если r11, r12, r21, r22 регулярные выражения, не содержащие вхождений нетерминала A, то нетерминал A и правило для него можно удалить из грамматики G, а все его вхождения заменить на выражение (r21 *, r22, r12 *)# r11.

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

1. T1 ( A) – подстановка вместо нетерминала A его порождения.

2. T2 ( A) – удаление вхождения леворекурсивного или праворекурсивного нетерминала A в правой части правила.

3. T3 ( A) – объединение общих префиксов в графе для нетерминала 4. T4 ( A) – удаление повторяющихся альтернатив для нетерминала 5. T5 ( A) – удаление крайних рекурсий для самовложенных нетерминалов.

6. T6 ( A) – сведение регулярного подвыражения в новый нетерминал в графе для A и создание нового правила в грамматике.

7. T7 – удаление лишних правил.

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

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

В качестве основных информационных компонент SynGT рассматриваются: SynGT – документ, рабочее поле (рисунок 8) с областями, синтаксическая граф-схема, подграф, дуга (семантика), нетерминальная, вспомогательная и терминальная вершины, правило КСРграмматики.

В SynGT – документе содержится информация о синтаксической граф-схеме, состоянии рабочего поля, соответствующей синтаксической граф-схеме КСР-грамматики, комментарии к текущему SynGT - документу в текстовой форме.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

Статьи, опубликованные в изданиях, определённых ВАК РФ 1. Федорченко Л.Н. О регуляризации контекстно-свободных грамматик. / Изв. вузов.

Приборостроение, 2006. Т.49, №11. C.50–-54.

2. Федорченко Л. Н., Заболотский В. П. Лингвистический инструментарий в задачах обеспечения информационной безопасности. / Ежеквартальный журнал изд-ва СПбГПУ «Проблемы информационной безопасности. Компьютерные системы», 2008, вып.4.

С.60–68.

Статьи, опубликованные в других изданиях 3. Федорченко Л.Н. Об алгоритме синтаксического анализа детерминированных языков. // Материалы совместного с Венгерской Академией Наук семинара "Computer Networks", Leningrad Computing Center of the Academy of Sciences and Computer and Automation Institute of Hungarian Academy of Sciences.– Budapest: 1978.–C.73–78.

4. Федорченко Л.Н. Об одном алгоритме синтаксического анализа языков, порождаемых R-грамматиками: сб. научных трудов ЛНИВЦ АН СССР, “Алгоритмы и системы автоматизации исследований и проектирования” / М: Наука, 1980 – C. 146–155.

5. Федорченко Л.Н., Мартыненко Б.К. Эквивалентные преобразования КСР грамматик в регулярной форме в практике построения языковых процессоров. Часть первая. Определение и распознавание КСР-языков посредством синтаксических графсхем. - Ленинград, 1983. – Ленинградский Научно-исследовательский Вычислительный Центр.– C. 6. Федорченко Л.Н. О числе состояний распознавателя, порождаемого с помощью КСграмматик в регулярной форме: cб. Научных трудов “Информационные и вычислительные проблемы в научных исследованиях” / M: Наука, 1983 – C. 69- 7. Федорченко Л.Н. Алгоритм синтаксического анализа языков, порождаемых Rграмматиками – "Algorithms and Systems of the Automation Research and Designing", Наука, M., 1983. С.15- 8. Федорченко Л.Н., Юсупов Р.М, и др. (всего 9 авторов), Инструментальная система для решения задач планирования и оптимизации вычислений в распределенной среде на основе графовых транcформаций. - Отчет по проекту Миннауки, Глава1, §§ 1–6, ВИНИТИ, шифр проекта 295.61,1998 г. 70с.

9. Федорченко Л.Н., Баранов С.Н., Кутузов М. Грамматика языка Си – //раздел отчета по совместному с INRIA (Франция) и Франко-российским институтом им. А.М. Ляпунова (МГУ) проекту №9 “OCC–открытый компилятор языка Си ” – Франко-российский институт им. А.М. Ляпунова, 1998 С. 10. Федорченко Л.Н., Баранов С.Н и др. Усовершенствованный алгоритм экранного размещения синтаксической граф-схемы в системе SynGT (Syntax Graph Transformation) версии 3.1. – раздел отчета по совместному с INRIA (Франция) и Франко-российским институтом им. А.М. Ляпунова (МГУ) проекту №14 “OCC–открытый компилятор языка Cи для цифровых сигнальных процессоров”, – Франко-российский институт им. А.М. Ляпунова, МГУ, 1999, с.45–46.

11. Федорченко Л.Н. и др. Средства визуализации синтаксических граф-схем – СПИИРАН, // Материалы VI Санкт-Петербургской международной конференции «Региональная информатика–98» (РИ–98), СПб, 2–4 июня 1998, Санкт-Петербург, 1999.

C.55– 12. Федорченко Л.Н.”Специализированный редактор для обработки контекстносвободных грамматик в регулярной форме”, – СПИИРАН, Труды 6-й международной конференции “Региональная информатика–98” (RI–98), Санкт-Петербург, 1999. C.56- 13. Федорченко Л.Н. Извлечение крайней рекурсии из КСР грамматики в системе SynGT. Труды СПИИРАН / –Вып.1, т.1. — СПб: СПИИРАН, 2002.–С.350–359.

14. Федорченко Л.Н., Соловьев С.В. Синтаксические преобразования в системе SynGT и их новые приложения. – Материалы VIII Санкт-Петербургской международной конференции “Региональная информатика–2002 (РИ–2002)” в 2-х частях, Санкт-Петербург, 26 – 28 ноября 2002г., часть 2, 180 с. СПОИСУ, 2002. С. 50.

15. Федорченко Л.Н. Извлечение крайней рекурсии из правил контекстно-свободной грамматики в регулярной форме. Труды VII Санкт-Петербургской международной конференции “Региональная информатика–2000” (РИ–2000) СПб, 2001, 428 с. СПОИСУ.

С. 243–258.

16. Федорченко Л.Н., Маньков Е.В. Современное состояние и классификация систем построения компиляторов– Материалы IХ Санкт-Петербургской международной конференции “Региональная информатика–2004 (РИ–2004)”, Санкт-Петербург, 22 – 24 июня 2004г., 442 с. СПОИСУ, 2004г., стр.66.

17. L. Fedorchenko, I. Naumov Syntax Graph Transformations in The System SynGT and Their New Applications, Procs of 10-th Multi-conference on Advanced Computer Systems (ACS–AIBITS 2003), October 22–24, Poland.

18. L. Fedorchenko, Syntax Graph Transformations in the System SynGT and Regularization of Grammars, Procs of Intern Multi-Conference on Advanced Computer Systems (ACS– CISIM 2004), 14–16 June, Elk, Poland [электронный ресурс] http://acs.wi.ps.pl/info.php 19. Федорченко Л.Н. О регуляризации контекстно-свободных грамматик. // IХ СанктПетербургская международная конференция “Региональная информатика–2004 (РИ– 2004)”. Труды конференции.– СПб: 2005. – C. 89–95.

20. Федорченко Л.Н. Метод регуляризации грамматик в системах трансляции языков.

// VI Юбилейная международная научная конференция “Инновации в науке и образовании–2008,” посвящённая 50-летию пребывания КГТУ на Калининградской земле. Труды конференции в 3-х частях, часть 2 – Калининград: 2008 – С. 305. ISBN 978–5–94826– 217–8. C.294–297.