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

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

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

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

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

003473534

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

003473534

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

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

доктор физико-математических наук,

профессор Баранов Сергей Николаевич

Официальные оппоненты: доктор технических наук,

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

кандидат технических наук,

доцент Дрожжин Владимир Васильевич

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

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

Защита состоится « 9» июля 2009 г. в_15.30__ час. на заседании

диссертационного Совета Д.002.199.01 Учреждения Российской академии наук Санкт-Петербургский институт информатики и автоматизации РАН по адресу:

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

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

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

Ученый секретарь

диссертационного совета Д.002.199.01

Ронжин Андрей Леонидович

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

боростроения (с 2009 г.) - в диссертации приложены 2 акта о внедрении.

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

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

Реализация результатов работы. Исследования, отраженные в диссертации, применялись при построении компилятора для языка 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 наименований.

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

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

ложение содержания по главам и основные положения работы, выносимые на защиту.

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

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

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

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

система для разработки языков и объект рассмотрения преобразований.

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

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

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

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

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

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

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

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

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

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

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

Определение 1. Обобщенной итерацией множеств слов Р и Q называется множество C = P#Q, состоящее из слов вида

х\У\х2У2-Уп-\хп ■ где е Р>i = П, у J eQ,j = l,...,n-l, an- положительное целое.

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

Определение 2. Регулярным выражением множества А называется слово г(А) над расширенным алфавитом W, где

W = Vu{#,*, ;,(,), г, 0}, и, если А = 0, то г(А) = 0, если А-е, то r(A) = е , если А = {а}, где а е V, ТО г(А) = а, если г(Р) = р и r{Q) = q

- регулярные выражения для множеств Р и Q. Тогда: r{A) = (p\q) для множестваP\jQ\ г(А) = (р,q), для множества PQ; г(А) = (р*), для множества Р*; г(А) = (р+), для множества Р+; r(A) = (p#q), для множества P#Q.

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

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

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

Формулируется понятие эквивалентности для регулярных выражений: Два регулярных выражения г{А) и г{В) из множества 91(F) будем считать эквивалентными, если они представляют одно и тоже регулярное множество слов над алфавитом V .

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

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

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

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

procedure_call: procedure_name,

("(",((formal_parameter, "=>";е),actual_parameter)# ")"; ),";" .

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

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

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

►тНЭтН ЬКЮтН

тг

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

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

Рис.4. Граф, регулярного выражения (('а,;,Ь'),51,",52,('а,;'Ь'),'аЬс,)#(53,",84)#'аЬс'.

р[осес1иге_са]1

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

с!иге_са11»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

вестных алгоритмов извлечения крайних рекурсий, в БулвТ реализован алгоритм прямого эквивалентного преобразования лево-(право)рекурсивного нетерминала с использованием операции обобщённой итерации.

Рассмотрим А -правило для нетерминала А вида

А:А,ги,А; А,гп; г21,А; гг2., (1)

где ги,гп,г2иг12-регулярные выражения над алфавитом А^иГиЕ.

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

где

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

А2 -фрагмент содержит левоорекурсивное вхождение нетерминала А;

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

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

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

Шаг1. Рассмотрим ^-фрагмент А -правила: А,ги,А. Используя данный фрагмент А -правила мы можем вывести строки

А,АгиА,АгиАгиА,... ,

Из определения операции # это множество строк совпадает с множеством строк, порождаемым регулярным выражением

Мги . (2)

Шаг 2. Рассмотрим фрагмент Л-правила: А,гп: Здесь мы можем вывести строки

Агп, Аг12гп, Агигпги, ... . (2.1)

Из определения унарной операции * следует, что множество

(2.1) порождается регулярным выражением

А,гп * . (2.2)

Подставив вместо А в выражении (2) -фрагмент А -правила

(2.2), получим регулярное выражение

(А,ги*)#ги . (3)

Шаг 3. Аналогично для праворекурсивного вхождения нетерминала А в А3 -фрагменте. Здесь мы выводим множество строк

гпА, г21г21А,г2]г2]г21А, ..., которые порождаются регулярным выражением г21*,Л. Сделав подстановку вместо вхождения нетерминала А в (3) выражения г21*,А , получим регулярное выражение

{г2*,А,г12*)#ги. (4)

Шаг 4. Окончательно, подставляя вместо вхождения нетерминала А в регулярное выражение (4) А4 - фрагмент г22, получим эквивалентное регулярное выражение

(г21*>/22''12*)#'п- (5)

Таким образом, правую часть Л-правила (1) можно заменить на регулярное выражение (5).

Если предварительно воспользоваться преобразованиями регулярных выражений и привести правило к такому виду, что множество Цгп) не содержит цепочек вида аА , множество 1(г21) не содержит цепочек вида Аа, а множество Цг22) не содержит цепочек вида Аа и вида аА, где а произвольная цепочка, тогда прямая левая и правая рекурсия для нетерминала А отсутствуют.

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

Если ги, гп, г21, г22 регулярные выражения, не содержащие вхождений нетерминала А , то нетерминал А и правило для него можно удалить из грамматики С, а все его вхождения заменить на выражение (г21*,г22,гп*)#ги.

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

1. Г, (Л) - подстановка вместо нетерминала А его порождения.

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

3. Т3(А) - объединение общих префиксов в графе для нетерминала А .

4. Т4(А) - удаление повторяющихся альтернатив для нетерминала

А

5. Т5(А) - удаление крайних рекурсий для самовложенных нетерминалов.

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

7. Г7 ~ удаление лишних правил.

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

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

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

- ГёШ

ш&ю! ....... • ■ ■ - ' •' ...... : : . •• . .. ; • 1 • : •• ! . . " ■•■: ; й!

^тЕЕтп

чз>

ра;а.т>„!кг Ц

гЧ3>

Рис. 8. Рабочее поле системы БупСТ

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

Эффективность метода построения анализатора достигается в результате предварительного этапа обработки входной КСР-

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

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

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

Статьи, опубликованные в изданиях, определённых ВАК РФ

1. Федорченко Л.Н. О регуляризации контекстно-свободных грамматик. / Изв. вузов. Приборостроение, 2006. Т.49, №11. С.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 - С. 146-155.

5. Федорченко Л.Н., Мартыненко Б.К. Эквивалентные преобразования КСР грамматик в регулярной форме в практике построения языковых процессоров. Часть первая. Определение и распознавание КСР-языков посредством синтаксических граф-схем. - Ленинград, 1983. -Ленинградский Научно-исследовательский Вычислительный Центр,- С.55

6. Федорченко Л.Н. О числе состояний распознавателя, порождаемого с помощью КС-грамматик в регулярной форме: сб. Научных трудов "Информационные и вычислительные проблемы в научных исследованиях"/ М: Наука, 1983 - С. 69-73

7. Федорченко Л.Н. Алгоритм синтаксического анализа языков, порождаемых R-грамматиками - "Aigorithms and Systems of the Automation Research and Designing", Наука, M„ 1983. C. 15-20

8. Федорченко Л.Н., Юсупов P.M, и др. (всего 9 авторов), Инструментальная система для решения задач планирования и оптимизации вычислений в распределенной среде на основе графовых трансформаций. - Отчет по проекту Миннауки, Глава1, §§ 1-6, ВИНИТИ, шифр проекта 295.61,1998 г. 70с.

9. Федорченко Л.Н., Баранов С.Н., Кутузов М. Грамматика языка Си - //раздел отчета по совместному с INRIA (Франция) и Франко-российским институтом им. А.М. Ляпунова (МГУ) проекту №9 "ОСС-открытый компилятор языка Си "-Франко-российский институт им. А.М. Ляпунова, 1998 С.5

10. Федорченко Л.Н., Баранов С.Н и др. Усовершенствованный алгоритм экранного размещения синтаксической граф-схемы в системе SynGT (Syntax Graph Transformation) версии 3.1. - раздел отчета по совместному с INRIA (Франция) и Фран-

г

V -i 20

ко-российским институтом им. А.М.Ляпунова (МГУ) проекту №14 "ОСС-открытый компилятор языка Си для цифровых сигнальных процессоров", - Франко-российский институт им. A.M. Ляпунова, МГУ, 1999, с.45-46.

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

12. Федорченко Л.Н."Специализированный редактор для обработки контекстно-свободных грамматик в регулярной форме", - СПИИРАН, Труды 6-й международной конференции "Региональная информатика-98" (RI-98), Санкт-Петербург, 1999. С.56-57

13. Федорченко Л.Н. Извлечение крайней рекурсии из КСР грамматики в системе SynGT. Труды СПИИРАН/-Вып.1, т. 1. — СПб: СПИИРАН, 2002.-С.350-359.

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

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

16. Федорченко Л.Н., Маньков Е.В. Современное состояние и классификация систем построения компиляторов- Материалы IX Санкт-Петербургской международной конференции "Региональная информатика-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. Федорченко Л.Н. О регуляризации контекстно-свободных грамматик.// IX Санкт-Петербургская международная конференция "Региональная информатика-2004 (РИ-2004)". Труды конференции - СПб: 2005. - С. 89-95.

20. Федорченко Л.Н. Метод регуляризации грамматик в системах трансляции языков. //VI Юбилейная международная научная конференция "Инновации в науке и образова-нии-2008," посвященная 50-летию пребывания КГТУ на Калининградской земле. Труды конференции в 3-х частях, часть 2 - Калининград: 2008 - С. 305. ISBN 978-5-94826217-8. С.294-297.

Основные обозначения и сокращения.

Введение.

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

Глава 1. ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ ГРАММАТИК В СОВРЕМЕННЫХ СИСТЕМАХ ПОСТРОЕНИЯ ТРАНСЛЯТОРОВ

1.1. Обзор основных методов синтаксического анализа.

1.2. Способы задания синтаксических структур.

1.3. Эквивалентные преобразования грамматик в инструментальных средствах Уасс/Вгёоп.

1.4. Эквивалентность как отношение подобия на синтаксических структурах.

Выводы по главе 1.

Глава 2. ОПРЕДЕЛЕНИЕ И РАСПОЗНАВАНИЕ КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ

С ПОМОЩЬЮ СИНТАКСИЧЕСКИХ ГРАФ-СХЕМ.

2.1. Основные понятия.

2.2. Контекстно-свободные грамматики в регулярной форме.

2.3. Выводимость в КСР-грамматике.

2.4. Синтаксическая граф-схема.

2.5. Рекуррентный алгоритм построения синтаксической граф-схемы.

2.6. Достижимые вершины в синтаксической граф-схеме.

2.7. Синтез распознающих автоматов для КСР -грамматик.

2.8. Свойства синтаксической граф-схемы.

2.9. Леммы о существовании состояний распознавателя в синтаксической граф-схеме.

2.10. Основная теорема о языке.

Выводы по главе 2.

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

3.1. Синтаксическая модель языка.

3.2. Этап предварительной подготовки грамматики.

3.3.Этапы обработки исходного текста грамматики.

3.4. Рекурсивные нетерминалы.

3.4.1. Левая и правая рекурсии.

3.4.2. Свойство 'самовложенности.

3.5. Подстановка нетерминала.

3.6. Исключение рекурсивных нетерминалов.

3.7. Число состояний распознавателя, синтезируемого по КСР-грамматике.

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

Выводы по главе 3.

Глава 4. ИНСТРУМЕНТАЛЬНАЯ СИСТЕМА ЭКВИВАЛЕНТНЫХ

ПРЕОБРАЗОВАНИЙ БулвТ

4.1. Описание, спецификации и дизайн системы.

4.2. Экранное размещение синтаксической граф-схемы.

4.3. Интерфейс пользователя.

4.4. Генерация тестов в системе ЭупОТ.

4.6.Пример преобразования рекурсивного нетерминала.

Выводы по главе 4.

При построении синтаксического анализатора как составной части транслятора необходимо проводить эквивалентные преобразования грамматики реализуемого языка. Сейчас языковые технологии активно включаются в различные сферы нашей жизни, что привело к развитию современных транслирующих систем, ориентированных на разнообразный ассортимент вычислительных устройств во многих предметных областях. При этом наиболее остро проявилась проблема быстрой настройки (преобразования) синтаксического определения языка на ту форму, которая допускает автоматическую или ручную реализацию, а также проблема учёта ограничений выбранного метода синтаксического анализа. Первая проблема обусловлена разнообразием спецификаций реализуемых языков, диапазон которых простирается от обычной формы Бэкуса-Наура (БНФ) и языка разметки 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 раза.

Заключение

1. Ахо А. В., Сети Р., Ульман Д. Д. Компиляторы: принципы, технологии и инструменты. М.: Вильяме, 2001.

2. Ахо А. В., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т.1. Синтаксический анализ, 612 с. Т.2. Компиляция, 487 е., М.:Мир,1978.

3. Баранов С.Н. Реализация системы символьных вычислений МИНИСАК на языке Форт. / Л.: Наука, Математич. методы постр. и анализа алг., 1990. С.3—15.

4. Баранов С.Н. Система символьных вычислений МИНИСАК// Программирование, 3, 1993. С.62-73.

5. Глушков В.М. Синтез цифровых автоматов. Физматгиз. 1962.

6. Иванищев В.В., Марлей В.Е. Введение в теорию алгоритмических сетей. СПб: Изд. СПбГТУб 2000,179 с.

7. Издательство журнала «Открытые системы» Электронный ресурс. URL:http://www.osp.ru/os/2009/03/8158133/

8. Клини С. Представление событий в нервных сетях. / В кн.: Автоматы. М.:ИЛ,1956,с.15-67.

9. Кнут Д.О. О переводе (трансляции) языков слева направо// Сб. «Языки и автоматы»- М.:Мир. 1975. С.9-42.

10. Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. М.:Мир. 1979.

11. Марлей В.Е. Алгебра алгоритмических сетей. //Теоретические основы и прикладные задачи интеллектуальных информационных технологий. СПб.: Изд. «Анатолия», 1998.С.200-207.'.'.;-■■■ .••.-. 138 •■■

12. Марлей В.Е., Морозов В.П. Интерпретация алгоритмических сетей как языковых конструкций. //Проблемы автоматизации в научных и производственных процессах М::Наука, 1985.-С.37-46.

13. Мартыненко: Б.К. Синтаксически управляемая обработка;данных. СПб, СПбГУ, 1997. 362 с.15: Опалева Э;А., Самойленко В.П., Семенова О.Н. Формальные методы описания перевода: Учеб. пособие. СПб.: СПбГЭТУ., 2000.

14. Пересмотренное сообщение об Алголе 68. / Под ред. А. ван Вейнгаар-ден. Пер. с англ. М.: Мир, 1979. 533 с.

15. Федорченко Л.Н, Извлечение крайней рекурсии из КСР-грамматики в системе SynGT, Труды СПИИРАН, вып.1,т. 1. — СПб: СПИИРАН, 2002, с.350-359 ; .

16. Федорченко:Л;Н., Заболотский В.П. Лингвистический инструментарийш задачах обеспечения информационной безопасности. СПб.: Изд-во Политехи^ ун-та, журнал «Проблемы информационной безопасности. Компьютерные системы» № 4, 2008 г., С. 60-68

17. Федорченко Л.Н., О регуляризации контекстно-свободных грамматик. Изв. вузов. Приборостроение, 2006. Т.49, №11, с.50-54.

18. Федорченко Л.Н. Об одном алгоритме синтаксического анализа языков, порождаемых R-грамматиками. / В сб. «Алгоритмы и системы автоматизации научных исследований и проектирования». М.: Наука, 1980.

19. Федорченко Л.Н. «О числе состояний распознавателя, синтезированного по контекстно-свободной грамматике в регулярной форме». В сб. «Информационно-вычислительные проблемы автоматизации, научных исследований». М.: Наукам983.

20. Aho A.V. and Johnson S.C. LR parsing / Computing. Surveys 6:2,1974 P.99-124

21. Aho, A.V. and Ullman, J.D. A technique for speeding up LR(k) parsers / SIAM J. Computing 2:2, 1973, pp 106-127.

22. Anderson Т., Eve J. and Horning J. J. Efficient LR(1) parsers/ Acta Informática 2:1, 1973, pp' 12-39.

23. B.W.Kernigan, D.M.Ritchie. The С Programming Language. Second Edition. Prentice Hall, 1988.

24. Baranov S.N. and Lavarenne C. Open С Compiler in Forth. // EuroForth'95 Conf.Proc. 27-29 Oct. 1995 Schl.Dagstuhl, Germany.

25. Bochman G.V. and Ward P. Compiler writing system for attribute grammars / Computer J. 21:2, 1978, pp 144-148.

26. Charles Donnelly and Richard Stallman, Bison, The YACC-compatible Parser Generator Электронный' ресурс.: http://dinosaur.compilertools.net/#bison

27. Cremers А В , and Ginsburg S., Context-free grammar forms /J Comput SystScI 11 (1975), 86-117.

28. De Remer F. and Penello T. Efficient computation of LALR(1) look-ahead sets / TOPLAS 4:4, 1982. P. 615-649.

29. De Remer F. Simple LR(k) grammars / Comm ACM 14:7, 1971, pp 453460.

30. Dick Grune and Ceriel Jacobs Parsing Techniques. A Practical Guide , Ellis Horwood, Chichester, England (1990), p.322.

31. Dick Grune Two Level grammars are more expressive than Type 0 grammars or are they?, Dept. of Mathematics and Computer Science Vrije Uni-versiteit, De Boelelaan 1081, HV Amsterdam. Электронный ресурс.: dick@cs.vu.nl

32. Early J. Ambiguity and precedence in syntax description / Acta Informática 4:2, 1975, pp 183-192.

33. Floyd R.W. Syntactic analysis and operator precedence / JACM, 10, (July 1963), 316p.

34. Foster, J.M. A syntax improving program / Computer J.11:1, 1968. P. 3134.

35. Ginsburg S. A survey of grammar forms / Acta Cybernetica, 3(4):269-280, 1977.

36. Ginsburg S., Harrison Michael A.: Bracketed context free languages. (2005)

37. Graham S. L. On Bounded Right Context Languages and Grammars / SIAM J. Comput. 3(1974), 224-254.

38. Graham S.L. Extended precedence, bounded right context languages, and deterministic languages (extended abstract)// Proc. Symp. on Switching and Automata Theory, Oct. 1970, pp. 175-180.

39. Gray J. N. and Harrison M. A., On the covering and. reduction problems for context free grammars. Journal of the. ACM 19, 675-698. 1972.

40. Harrison M. A., and Havel I. M. Strict Deterministic Grammars,, Journal of Computer and Systems Science, Vol. 7 pp. 237-277, 1973.

41. Hotz G. Normal-form transformations of context-free grammars / Acta Cybernetica, 4(1):65-84, 1978.

42. HTML Материал из электронной энциклопедии Википедия Электронный ресурс. URL:http://ru.Wikipedia.org/wiki/HTML

43. Hunt III Н. В. and Rosenkrantz D. J., Complexity of grammatical similarity relations // In: Procs of a Conf. on Theoretical Computer Science Waterloo 1977, 139-145.

44. Johnson S.C. YACC Yet Another Compiler-Compiler. // Сотр. Sci. Tech. Rep.39. Bell Telephone Laboratories. 1975. New Jersey: Murray Hill. Электронный ресурс. URL: http://www.usc.edu/~ram1335/yacc.doc

45. Kenichi Taniguchi, Tadao Kasami: A Result on the Equivalence Problem for Deterministic Pushdown Automata/J. Comput. Syst. Sci. 13(1): 38-50 (1976)

46. KnuthDonald E. Backus Normal Form vs. Backus Naur Form // Communications of the ACM 7 (12),1964: p. 735-736.

47. Korenjak A. J. and Hopcroft J. E. Simple deterministic languages // IEEE Conf. Record.of 7th Annual Symposium on Switching and Automata Theory, 1966, pp.36^16.

48. Koster C.H.A. et all. CDL3 manual- Электронный ресурс. URL: http:www.es. ru.nl/~kees/vbcourse/ivbstuff/ cdl3.pdf.

49. Koster C.H.A. Two-level Grammars// Budapest. Seminar on Automata and Mathematical Linguistics, Mathematisch Instituut, May 1970.

50. Krai J. and Demner J.: Semi-top-down syntactic analysis//Report UVT 6/73/M Institute of Computation Technique. August 1973.

51. Kral J., Demner J.: Almost Top-Down Analysis for generalized LR(k) Grammars. Methods of Algorithmic Language Implementation 1975: 149-172

52. Lewis P., Rozenkrantz D., Stearns R. Attributed Translations/ J. Computer and System Sciences 9(3) (1974) 279-307.

53. Lewis P.M. Compiler Design Theory. Addison-Wesley. 1996.

54. M.Sintzoff, "Existence of a van Wijngaarden syntax, for every recursively enumerable set", Annales de la Societe Scientifique de Bruxelles 81(11), pp.115-118 (1967).

55. Mc Naughton, R. The development of formal language theory since 1956 / Internat. J. Found. Comput. Sci. (1990), p. 355-368.

56. McNaughton R. The theory of automata. A survey in "Advances in Computers,". F. L. Alt, Ed., vol. II, pp. 379-421,. Academic Press, N.Y.

57. Nijholt A. and Soisalon-Soininen E. Ch(k) grammars: A characterization of LL(k) languages. ln:Mathematical Foundations of Computer Science, 8th Conf., J. Becvar (ed.), Springer-Verlag, Berlin, Lect. Notes in Comput. Sci. 74, 1979. P. 390-397.

58. Open С Compiler. SYNTAX ANALYZER. GRAMMAR REQUIREMENTS SPECIFICATIONS. File GRSRS.txt Совместный СПИИРАН и INRIA проект- 1995.

59. Paull M. and Unger S. Structural equivalence of context-free grammars / Jornal of Computer and System Sciences 2 (1968), 427-463.

60. Paull M.C., and Unger S.H. Structural Equivalence of LL-k Grammars// IEEE Conference Record of Ninth Annual Symposium on Switching and Automata Theory,1968 p. 160-175.

61. Prather R.E. Regular Expressions for Program Computations, American Mathematical Monthly, 104, No. 2, 1997.

62. Raiha K.-J., Saarinen M., Sarjakoski M., Sippu S., Soisalon-Soininen E. and Tienari M. // Revised report on the compiler writing system HLP78, Report A-1983-1, Dept. of Computer Science, University of Helsinki, 1983.

63. Reynolds J.C., and Haskell R. Grammatical coverings. Unpub. memorandum, Syracuse University, 1970. From ACM Transactions on Programming Languages and Systems (TOPLAS). V. 9 , Issue 4 (Oct 1987), pp.543-566 1987 ISSN:0164-0925.

64. Rozenkrantz D.J., Stearns R.E. Compiler Construction. An Advanced Course: Springer-Verlag, 2001.

65. Salomaa K. and Yu S. Decidability of structural equivalence of E0L grammars / Theoretical Computer Science 82 1991.

66. Soisalon-Soininen E. and Ukkonen E. A method for transforming grammars into LL(k) form / Acta Informatica 12, 1979. P. 339-369.

67. Stearns R.E. Deterministic top-down parsing // Proc. 5th Annual Princeton Conf. on Information Sciences and Systems, 1971. P. 182-188.

68. Linger S.H. A global parser for context-free phrase structure grammars, CACM, 11 (April 1968), 240-246; 11 (June 1968), 427c.

69. Vern Paxson Flex- a fast scanner generator, Электронный ресурс. URL:http://dinosaur.compilertools.net/.

70. Wirth N., Weber H.: Euler: A Generalization of Algol and Its Formal Definition / Comm. ACM 9(1): 11-23, and 9(2): 89-99, 1966.

71. Wirth Niklaus: What can we do about the unnecessary diversity of notation for syntactic definitions? CACM, Vol. 20, Issue 11, November 1977. P. 822823.

72. Wood D. The theory of left factored languages/ Computer J. 12:4, 1969, pp.349-356.1. ТЕРМИНЫ

73. Программное обеспечение (ПО) Software. в области вычислительной техники и программирования - это совокупность всей информации, данных и программ, которые обрабатываются компьютерными системами.

74. Языковым процессором language processor. называют ПО, которое транслирует язык программирования в машинный код.

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

76. Компиляция compilation. трансляция программы на язык, близкий к машинному. Трансляция программы, составленной на исходном языке, в объектный модуль (осуществляется компилятором)

77. Компилятор compiler. -1). Машинная программа, используемая для компиляции.2.. Программа (или техническое средство), выполняющая компиляцию.3.. Транслятор, выполняющий преобразование программы, составленной-на исходном языке, в объектный модуль.

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

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

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

81. Регуляризация КС-грамматики это процесс эквивалентного преобразования произвольной КС грамматики G в КС грамматику G1 в регулярной форме (КСР-грамматику), причем такой, что из нее исключаются все самовставленные нетерминальные символы.

82. Часть таких преобразований реализована в системе SynGT (Syntax Graph Transformations)^ ,22, 23.