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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

Лукичев Александр Сергеевич

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

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

05.13.17 — Теоретические основы информатики

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

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

Работа выполнена на кафедре информатики матсматико-мсханического факультета Санкт-Пегербургского государственного университета.

Научный руководитель: доктор физико-математических наук,

доцент Борис Константинович Мартыненко

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

профессор Виталий Алексеевич Тузов кандидат физико-математических наук, Вячеслав Алексеевич Кириллин

Ведущая организация: Санкт-Петербургский институт

информатики и автоматизации Российской Академии наук

Защита состоится '2? 2006 г. в ^час. на заседании диссертацион-

ного совета Д.212.232.51 по защите диссертаций на соискание ученой степени доктора наук при Санкт-Петербургском государственном университете по адресу: 198504, Санкт-Петербург. Старый Петергоф, Университетский пр., 28, математико-механический факультет.

С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., 7/9.

Автореферат разослан "2Г" 2006 г.

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

диссертационного Совета У //,_ цо

доктор физико-математических наук ЭДАМ^ - *

' Б.К. Мартыненко

Общая характеристика работы

Актуальность темы. Атрибутная техника была введена Д. Кнутом [9] с целью описания семантики языков, порождаемых классическими контекстно-свободными грамматиками Хомского [3J. Технически метод предполагает построение дерева разбора входного предложения языка в данной КС-грамматике, а затем вычисление значений атрибутов в каждой вершине этого дерева по правилам, связанным с правилами грамматики, участвующими в разборе. На практике данный подход был реализован в ряде систем, таких как, например, YACC [8] и Eli [6].

Начиная с конца 60-х годов, для определения синтаксиса КС-языков применяются также синтаксические диаграммы Вирта?[4] и RBNF-грамматики. Каждому нетерминалу соответствует одна компонента диаграммы или одно правило RBNF-грамматики, правая часть которого — регулярное выражение, относительно символов объединенного алфавита грамматики. Технологии, использующие явно RBNF-грамматики с атрибутами, обычно неявно преобразуют данную грамматику в эквивалентную однозначную КС-грамматику. Поэтому с теоретической и практической точек зрения интересно рассмотреть применение атрибутной техники непосредственно в RBNF-грамматиках.

За основу разработки темы была взята технология SYNTAX [5]. использующая граф-схемы (аналоги диаграмм Вирта) и RBNF-грамматики в качестве синтаксического базиса для определения трансляций.

Актуальность постановки данной темы следует из перечисленных ниже аргументов:

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

во-вторых, анализ на RBNF-грамматиках при линейном ограничении по времени относительно длины входной цепочки приводит к ограничениям на класс применяемых грамматик и, как следствие, на использование атрибутов. Данные ограничения следует определить с учетом используемого механизма анализа;

в-третьих, SYNTAX-тохнология позволяет задавать контекстно-зависимые языки. Это достигается введением резольверов — предикатов, ограничивающих выбор альтернатив при анализе в зависимости от котттекста. Атрибуты могут использоваться для задания этого контекста;

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

1 Иначе называемые синтаксические графы

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

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

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

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

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

При использовании атрибутов для параметризации резольверов они приобретают черты аффиксов [10, 11], параметризующих нетерминалы. Таким образом, атрибутная RBNF-грамматика становится двухуровневой [12]. Известными представителями этого класса грамматик, помимо аффиксных грамматик К. Костера, являются также грамматики А. ван Вейнгаардена [13]. Используемые на практике искусственные языки часто не являются контекстно-свободными. Применение двухуровневых грамматик, мощность которых достаточна для описания рекурсивных множеств, позволяет специфицировать синтаксис такого языка в рамках одного формализма.

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

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

В целом, можно выделить следующие основные этапы диссертационной работы:

• разработка теоретического подхода применения атрибутов в RBNF-грамматиках;

• выявление ограничений, накладываемых SYNTAX-технологией на применение атрибутов;

• построение прототипа версии технологического комплекса SYNTAX, расширенной атрибутами;

• иллюстрация применения атрибутной SYNTAX-технологии на примере ATSL — языка атрибутных спецификаций SYNTAX;

• прагматическая оценка применения атрибутного подхода в SYNTAX.

Основные результаты работы:

• разработан способ применения атрибутов в RBNF-грамматиках;

• дано формальное определение трансляции, задаваемой атрибутной спецификацией;

• выявлены ограничения, накладываемые на атрибуты для их использования в алгоритме сплайнового процессирования, применяемом в технологии SYNTAX;

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

• модифицирован алгоритм сплайнового процессирования, реализующий прямой и обратный просмотры п технологии SYNTAX;

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

Научная новизна. Впервые атрибутная техника применяется непосредственно в RBNF-rpa,MMaTiiKax для построения средств еинтаксичсски-управ-ляемой обработки данных в контексте следующих особенностей алгоритма трансляции: . .

• атрибуты вычисляются на не полностью построенном дереве вывода;

• само дерево вывода строится с учетом контекста, определяемого значениями атрибутов;

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

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

Апробация работы. Результаты диссертации докладывались на семинаре «Информатика и компьютерньгс технологии» СПИЙРАН (200G г., Санкт-Петербург) и девятом научно-практическом семинаре «Новые информационные технологии в автоматизированных системах» МГИЭМ, ИПМ (2006 г., Москва).

Предложенный подход был реализован в виде прототипа на основе технологического комплекса SYNTAX, разработанного в СПбГУ.

Публикации. По теме диссертации опубликованы работы [1, 2].

Структура и объем диссертации. Диссертация состоит из введения, 4 глав, заключения и приложения. Диссертационная работа изложена на 83 страницах, приложение — па 34 страницах. Список литературы содержит 27 наименований.

Содержание работы

Во ВВЕДЕНИИ обосновывается актуальность темы исследования, формулируются цели и перечисляются основные научные результаты.

В ПЕРВОЙ ГЛАВЕ описаны подходы к описанию контекстно-зависимых языков на основе двухуровневых грамматик (аффиксные грамматики [11],

W-грамматики [13]) и к спецификации трансляции (атрибутная техника в КС-грамматиках [9]). Атрибутная техника в SYNTAX используется для решения двух этих задач, а поэтому имеет черты рассмотренных подходов.

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

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

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

Интерпретация метода рекурсивного спуска в терминах множества конечных автоматов [5], взаимодействующих в общей операционной среде, дает ключ к пониманию подхода к теме исследования.

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

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

лизации семантик и резольверов через параметры.

Ограничения, накладываемые на RBNF-грамматики в технологии SYNTAX, допускают синтаксически неоднозначные грамматики при соблюдении локальной семантической однозначности относительно каждого просмотра с учетом детерминизма и безвозвратности процесса анализа. Последнее условие является критичным для минимизации сложности механизма учета контекста. С другой стороны, исполнение семантических действий и, таким образом, изменение контекста и выполнение трансляции происходит одновременно с анализом входного предложения. Возможна ситуация, когда выполнение некоторого семантического действии зависит от информации, целиком доступной только к моменту окончания прямого просмотра. В этом случае такое действие может быть также отложено до стадии обратного просмотра в виде вызова семантики обратного просмотра. На этом этапе происходит прохождение по состояниям прямого просмотра в обратном порядке, вызов семантик обратного просмотра, более точное определение синтаксической структуры входной цепочки с помощью резольверов обратного просмотра. Здесь, как и на прямом просмотре, атрибуты используются для параметризации семаитик и резольверов, спецификации порядка передачи контекстной информации между ними.

При выполнении «отложенных действий» важно восстановить контекст, в котором эти действия были отложены. Иными словами, необходимо обеспечить передачу контекстной информации из прямого просмотра в обратный. Для этого вводится особый класс атрибутов — «междупросмотровые атрибуты»2.

Во ВТОРОЙ ГЛАВЕ дано формальное определение трансляции, задаваемой SYNTAX-спецификацией с использованием атрибутов (случай прямого просмотра), описание алгоритма онлайнового процессирования, приведены ограничения, накладываемые на атрибуты для обеспечения возможности их применения в сплайновом процессоре. Кроме того, описывается алгоритм обратного просмотра с использованием атрибутов, обсуждается вопрос передачи контекстной информации между просмотрами.

В параграфе 2.1 обсуждается невозможность введения атрибутов на основе дерева разбора [9] и обосновывается способ введения, предложенный в первой главе. Дается формальное определение атрибутной трансляции.

Со всяким вхождением нетерминала в левые части правил связывается набор формальных атрибутов, а со всяким вхождением нетерминала, семантики или резольвера в правые части правил — набор фактических атрибутов. Формальные атрибуты делятся на наследуемые, синтезируемые и локальные. Фактические — па наследуемые и синтезируемые.

2Этот класс, получил паш.чп не двусторонние атрибуты.

Предлагаемое определение атрибутной трансляции по своей сути близко к алгоритму Эрли [7], применяемому для анализа произвольных КС-грамматик. Основными отличиями являются учет контекстных условий, задаваемых резольверами, исполнение семантических действий, задание правил грамматики с помощью регулярных выражений и применение атрибутов для передачи информации.

На основе алгоритма работы процессора прямого просмотра и определения атрибутной трансляции выявляются и формулируются ограничения па атрибутную спецификацию трансляции.

Можно выделить следующие группы ограничений:

• требования отсутствия неопределенных значений;

• требования синтаксической балансировки;

• требования семантической балансировки.

. Последние два класса требований восходят к одноименным ограничениям па ГШКР-грамматики, применяемым в ЗУМТАХ-техиологии для получения детерминированных сплайновых процессоров линейной сложности.

В параграфе 2.2 рассматривается вопрос использовании атрибутов на обратном просмотре. Атрибуты (как формальные, так и фактические) подразделяются на атрибуты прямого и обратного просмотра, а некоторые локальные атрибуты могут определяться как двусторонние. Значения двусторонних атрибутов вычисляются на прямом просмотре и могут быть использованы на обратном.

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

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

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

В ТРЕТЬЕЙ ГЛАВЕ рассматривается модификация представления управляющих таблиц и алгоритма сплайнового процессирования, описанных в [5], с целью реализации поддержки атрибутов.

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

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

• класс фактического атрибута4.

При создании очередного локального контекста или при формировании списка аргументов семантики или резольвера индексы определяют позицию значения используемого атрибута в текущем локальном контексте, а классы — направление передачи информации.

В параграфе 3.2 па примере спецификации анализатора модельного языка производится сравнение атрибутного подхода с использованием технологии SYNTAX бел атрибутов. Можно выделить следующие основные преимущества атрибутных спецификаций:

а) потоки данных задаются с использованием атрибутов независимо для

Синтезируемый, наследуемый или локальный прямого или обратного просмотра, двусторонний 'Синтезируемый или наследуемый прямого или обратного просмотра

каждого правила, что обеспечивает естественное разбиение текста спецификации на логические элементы; ' . . ,

б) программисту-разработчику спецификации трансляции не приходится разрабатывать свой механизм для передачи данных между реализациями семаптик и резольверов: такой механизм предоставляется самим атрибутным алгоритмом трансляции;

в) реализации семаптик и резольверов получают и возвращают данные через параметры; ■ • . .■

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

В ЧЕТВЕРТОЙ ГЛАВЕ рассматриваются отдельные задачи, которые не решены.в прототипе системы, но, однако,, могут быть реализованы с применением описанного, атрибутного подхода: ...

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

2. Использование атрибутов у терминалов: выражение 'а'<Х>, где 'а.' — терминал, X — некий синтезируемый фактический атрибут, принимающий значение терминального символа, полученного с лексического уровня, может быть переписано в виде 1;окепУа1ие<Х>, 'а', где -ЬокепУа1ие специальная системная семантика, устанавливающая значение X в зависимости от информации, полученной с лексического уровня. Спецификации же такого рода рассмотрены в данной работе.

3. Передача информации между процессорами: наиболее распространенным случаем, когда необходима передача информации между процессорами является выделение уровней лексического и синтаксического анализа в отдельные спецификации. В таком'случае входная цепочка транслируется процессором лексического уровня, который является поставщиком лексем процессора синтаксического уровня. Минимальный набор информации, получаемой с лексического уровня, состоит из кода лексемы, используемого для вхождения в управляющие таблицы синтаксического процессора, и представления лексемы в виде строки символов. Кроме того, может возникнуть необходимость управлять состоянием лексического просмотра с уровня синтаксического просмотра. В

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

4. Использование атрибутов во вспомогательных понятиях: вспомогательные понятия [5] в спецификациях на языке TSL применяются для макроподстановок на этапе построения граф-схемы. Использование атрибутов в спецификациях, таким образом, должно отразиться и на применении вспомогательных понятий. Предлагается способ решения этой проблемы на этапе применения макроподстановки с помощью переименования атрибутов.

5. Контроль типов значений атрибутов: предлагаемое в данной работе решение проблемы передачи информации с помощью атрибутов пе затрагивает вопросов контроля типов значений атрибутов. Контроль типов, однако, может быть реализован на этапе построения управляющих таблиц. Кроме того, возможно осуществлять дополнительный контроль во время исполнения алгоритма трансляции, применяя револьверы. Важно отметить, что контроль времени исполнения не возможен в случае классического подхода [9].

6. Оптимизация атрибутных процессоров. Описанный в [5] алгоритм оптимизации челночных процессоров базируется па вычислении отношения эквивалентности для различных элементов конечного управления процессора. Это отношение может быть модифицировано с учетом введения атрибутов. Сами алгоритмы оптимизации при этом не изменяются.

В ЗАКЛЮЧЕНИИ сформулированы основные результаты и выводы:

1. Разработан способ применения атрибутов в RBNF-грамматиках и, в частности, в SYNTAX-спсцификациях. Описана мотивация использования такого подхода. В рамках предложенного подхода рассмотрено применение атрибутов на прямом и обратном просмотрах, выявлены ограничения, накладываемые па атрибуты, разработан механизм передачи контекстной информации между просмотрами.

2. Дано формальное определение трансляции, осуществляемой на прямом просмотре с использованием атрибутов в технологии SYNTAX. На основе

описанных в [5] алгоритмов процессирования и построения управляющих таблиц построены модифицированные алгоритмы, поддерживающие атрибутные спецификации.

3. Реализован прототип системы на языке Pascal. В качестве основы для данной реализации был взят код технологического комплекса SYNTAX, разработанного в СПбГУ. Описаны изменения, внесенные в представление и алгоритмы построения управляющих таблиц, процедуру процессирования.

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

• применение предлагаемого подхода улучшает условия разработки семантической части спецификации трансляции, избавляя разработчика от необходимости реализации своего метода передачи контекстной информации, согласованного с синтаксическим механизмом;

• использование семаптик и резольверов с параметрами делает структуру семантической части спецификации более прозрачной и модульной;

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

В ПРИЛОЖЕНИИ представлена спецификация трансляции с языка ATSL (TSL [5] с атрибутами) в линейное представление граф-схем, принятое в ТК SYNTAX. Спецификация выполнена на языке ATSL, семантика реализована на языке Pascal.

Публикации по теме диссертации

1. Лукичев A.C. Использование атрибутов в технологии SYNTAX // Вест.

С.-Петерб. ун-та. Сер. 1. Вып. 2. СПб, 2005. С. 64-73.

2. Лукичев A.C. Реализация атрибутов в RBNF-грамматиках системы

SYNTAX // Новые информационные технологии: материалы девятого

научно-практического семинара. Моск. гос. ин-т электроники и математики. М., 2006 (февраль). С. 243-255.

Литература

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

4. Вирт. Н. Алгоритмы+структуры данных=программы. Пер. с англ. — М., 1984 г.

5. Мартыненко Б.^. Синтаксически управляемая обработка данных. Изд. 2-е. - СПб, 2004 г.

6. Gray R. W., Heuring V.P., Levi S.P. et al. Eli: a complete, flexible compiler construction system // Communications of ACM, Vol. 35, Num. 2, 1992, pp. 121-130.

7. Early J. An Efficient Context-Free Parsing Algorithm // Communications of the ACM, Vol. 13, Num. 2, 1970, pp. 94-102.

8. Johnson S.C. Yacc — yet another compiler compiler. Computer Science Technical Report'32. AT&T Bell Laboratories, Murray Hill, N.J., 1975.

9. Knuth D.E. Semantics of context-free languages /,/ Mathematical Systems Theory 2:2.' 1968, pp. 127-145.

10. Koster C.H.A. On the Construction of ALGOL-Procedures for Generating, Analyzing and Translating Sentences in Natural Languages. Report MR72, Mathematisch Centrum, Amsterdam, 1965.

11. Köster C.H.A. Affix Grammars // In: Proceedings of IFIP Conference on ALGOL 68 Implementation. 1970. Munich, pp. 95-109.

12. Köster C.H.A. Affix Grammars for Programming Languages // In: Attribute Grammars, Applications and Systems. International Summer School SAGA. 1991. Prague.

13. van Wijngaarden A. Orthogonal Design and Description of a Formal Language. Report MR76, Mathematisch Centrum, Amsterdam, 1965.

Подписано в печать 16.06.2006. Формат бумаги 60 х 84 1/16. Бумага офсетная. Печать ризографическая. Усл. печ. л. 1,0. Тираж 100 экз. Заказ 3797.

Отпечатано в отделе оперативной полиграфии НИИХ СПбГУ. 198504, Санкт-Петербург, Старый Петергоф, Университетский пр.26

Введение.

Глава 1. Введение атрибутов.

Глава 2. Построение трансляции.

2.1. Введение атрибутов на прямом просмотре.

2.2. Введение атрибутов на обратном просмотре.

Глава 3. Применение атрибутных спецификаций.

3.1. Алгоритмы процессирования и построения атрибутных процессоров

3.2. Применение атрибутных RBNF-грамматик в технологии SYNTAX

Глава 4. Дополнительные возможности применения атрибутных спецификаций

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

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

Начиная с конца 60-х годов, для определения синтаксиса КС-языков применяются также синтаксические диаграммы (синтаксические графы) Вирта [3] и ШШР-грамматики. Каждому нетерминалу соответствует одна компонента диаграммы или одно правило 11ЕШР-грамматики, правая часть которого — регулярное выражение относительно символов объединенного алфавита грамматики.

Возникает задача спецификации трансляции с использованием RBNF-грам-матик в качестве синтаксической основы. Технологии, использующие явно RBNF-грамматики, обычно неявно преобразуют данную грамматику в эквивалентную однозначную КС-грамматику. В технологии SYNTAX [4], использующей граф-схемы (аналоги диаграмм Вирта) и RBNF-грамматики в качестве синтаксического базиса, применяется другой подход. Здесь регулярные выражения в правых частях правил грамматики явно интерпретируются. Кроме того, данная технология позволяет задавать трансляции с контекстно-зависимых языков и использовать синтаксически-неоднозначные входные грамматики.

Передача данных между семантическими действиями в технологии SYNTAX не специфицируется на уровне грамматики. Задачей данной работы является реализация атрибутов в SYNTAX для обеспечения возможности задания потоков данных средствами атрибутных RBNF-грамматик. Актуальность темы следует из перечисленных ниже аргументов: во-первых, использование атрибутов в RBNF-грамматиках требует специального оформления правил грамматик и разработки метода применения атрибутов в механизме реализации трансляции; во-вторых, анализ на RBNF-грамматиках при линейном ограничении времени относительно длины входной цепочки приводит к ограничениям на класс применяемых грамматик и, как следствие, на использование атрибутов. Данные ограничения следует определить с учетом используемого механизма анализа; в-третьих, SYNTAX позволяет задавать контекстно-зависимые языки. Это достигается введением резольверов — предикатов, ограничивающих выбор альтернатив при анализе в зависимости от контекста. Атрибуты могут использоваться для задания этого контекста; в-четвертых, ограничения, накладываемые на RBNF-грамматики в SYNTAX, позволяют использовать синтаксически-неоднозначные грамматики. Для уточнения синтаксической структуры входного предложения может применяться обратный просмотр, где также могут использоваться атрибуты.

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

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

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

• атрибуты вычисляются на не полностью построенном дереве вывода;

• само дерево вывода строится с учетом контекста, определяемого значениями атрибутов;

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

Основные результаты работы:

• разработан способ применения атрибутов в RBNF-грамматиках;

• дано формальное определение трансляции, задаваемой атрибутной спецификацией;

• выявлены ограничения, накладываемые на атрибуты для их использования в алгоритме сплайнового процессирования, применяемом в технологии SYNTAX;

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

• модифицирован алгоритм сплайнового процессирования, реализующий прямой и обратный просмотры в технологии SYNTAX;

• разработан механизм передачи контекстной информации между просмотрами с использованием атрибутов.

Построение диссертации. Основное содержание диссертации изложено в 4 главах.

В ПЕРВОЙ ГЛАВЕ описаны подходы к описанию контекстно-зависимых языков на основе двухуровневых грамматик (аффиксные грамматики [17], W-грамматики [26]) и к спецификации трансляции (атрибутная техника в КС-грамматиках [15]). Неформально в RBNF-спецификации системы SYNTAX вводятся атрибуты.

Во ВТОРОЙ ГЛАВЕ дано формальное определение трансляции, задаваемой SYNTAX-спецификацией с использованием атрибутов (случай прямого просмотра), описание алгоритма сплайнового процессирования, приведены ограничения, накладываемые на атрибуты для обеспечения возможности их применения в сплайновом процессоре. Кроме того, описывается алгоритм обратного просмотра с использованием атрибутов, обсуждается вопрос передачи контекстной информации между просмотрами.

В ТРЕТЬЕЙ ГЛАВЕ описывается модификация представления управляющих таблиц и алгоритма сплайнового процессирования, описанных в [4], с целью введения поддержки атрибутов. Рассмотрены примеры использования атрибутного подхода.

В ЧЕТВЕРТОЙ ГЛАВЕ рассматриваются отдельные вопросы, которые не реализованы в разработанном прототипе системы, но, однако, могут быть реализованы с применением описанного атрибутного подхода.

В ЗАКЛЮЧЕНИИ сформулированы основные выводы, полученные по результатам выполненных в диссертации исследований.

Заключение

В ходе выполнения работы были достигнуты все основные цели исследований, получены следующие результаты:

1. Разработан способ применения атрибутов в RBNF-грамматиках и, в частности, в SYNTAX-спецификациях. Описана мотивация использования такого подхода. В рамках предложенного подхода рассмотрено применение атрибутов на прямом и обратном просмотрах, выявлены ограничения, накладываемые на атрибуты, разработан механизм передачи контекстной информации между просмотрами.

2. Дано формальное определение трансляции, осуществляемой на прямом просмотре с использованием атрибутов в технологии SYNTAX. На основе описанных в [4] алгоритмов процессирования и построения управляющих таблиц построены модифицированные алгоритмы, поддерживающие атрибутные спецификации.

3. Реализован прототип системы на языке Pascal. В качестве основы для данной реализации был взят код технологического комплекса SYNTAX, разработанного в СПбГУ. Описаны изменения, внесенные в представление управляющих таблиц.

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

• применение предлагаемого подхода делает процесс разработки семантических действий более прозрачным, избавляя разработчика от необходимости реализации своего метода передачи контекстной информации, согласованного с синтаксическим механизмом;

• использование семантик и резольверов с параметрами делает структуру семантической части спецификации более прозрачной и модульной;

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

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

• использование атрибутов у терминальных символов;

• применение атрибутов для передачи контекстной информации между челночными процессорами;

• введение типизированных атрибутов;

• применение атрибутов при макроподстановке;

• оптимизация атрибутных синтаксических процессоров.

1. Алгол 68. Методы реализации. / Под. ред. Г.С. Цейтина. Изд. ЛГУ, J1. 1976

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

3. Вирт Я. Алгоритмы+структуры данных=программы. Пер. с англ. — М., 1984 г.

4. Мартыненко Б. К. Синтаксически управляемая обработка данных. Изд. 2-е. СПб, 2004 г.

5. Мартыненко Б.К. Языки и трансляции. СПб, 2004 г.

6. Chomsky N. On certain formal properties of grammars // Inf. Contr. 2,1959, pp. 137-167.

7. Farnum C. Pattern-based tree attribution // Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 1992, pp. 211-222.

8. Farrow R., Marlowe T.J., Yettin D.M. Composable Attribute Grammars: Support for Modularity in Translator Design and Implementation // Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 1992, pp. 223-234.

9. Gray R.W., Heuring V.P., Levi S.P. et al Eli: a complete, flexible compiler construction system // Communications of ACM, Vol. 35, No. 2, 1992, pp. 121-130.

10. Early J. An Efficient Context-Free Parsing Algorithm // Communications of the ACM, Vol. 13, No. 2, 1970, pp. 94-102.

11. Johnson S.C. Yacc — yet another compiler compiler. Computer Science Technical Report 32. AT&T Bell Laboratories, Murray Hill, N.J., 1975.

12. Jullig R.K., DeRemer F. Regular Right-Part Attribute Grammars // Proceedings of the ACM SIGPLAN '84 Symposium on Compiler Construction, SIGPLAN Notices Vol. 19, No. 6, 1984, pp. 171-178.

13. Kastens U., Hütt D., Zimmermann E. GAG: A Practical Compiler Generator // Lecture Notes in Computer Science, Vol. 141, 1982.

14. Knuth D.E. On the translation of languages from left to right // Inf. Contr. 8, Vol. 6, 1965, pp. 607-639.

15. Knuth D.E. Semantics of context-free languages // Mathematical Systems Theory 2:2, 1968, pp. 127-145.

16. Koster C.H.A. On the Construction of ALGOL-Procedures for Generating, Analyzing and Translating Sentences in Natural Languages. Report MR72, Mathematisch Centrum, Amsterdam, 1965.

17. Köster C.H.A. Affix Grammars 11 Proceedings of IFIP Conference on ALGOL 68 Implementation. 1970. Munich, pp. 95-109.

18. Köster C.H.A. Affix Grammars for Programming Languages // In: Attribute Grammars, Applications and Systems. International Summer School SAGA. 1991. Prague.

19. Koster C.H.A., Beney J.G. On the Borderline Between Grammars and Programs // Springer Lecture Notes in Computer Science 528,1991, pp. 219230.

20. Lee J.A.N., Dorocak J. Conditional Syntactic Specification // ACM '73: Proceedings of the annual conference, 1973, pp. 101-105.

21. Lewis P.M., Stearns R.E. Syntax-directed transduction // Journal of ACM, Vol. 15, No. 3, 1968, pp. 465-488.

22. Mejier H. The Project of Extended Affix Grammars at Nijmegen // Attribute Grammars and their Applications. Lecture Notes in Computer Science 461, Springer, 1990.

23. Odersky M. Defining Context-Dependent Syntax Without Using Contexts // ACM Transactions on Programming Languages and Systems, Vol. 15, No. 3, 1993, pp. 535-562.

24. Olsen D.R., Jr. Pushdown Automata for User Interface Management// ACM Transactions on Graphics, Vol. 3, No. 3, 1984, pp. 177-203.