Содержание к диссертации
Введение
Глава 1. Введение атрибутов 8
Глава 2. Построение трансляции 20
2.1. Введение атрибутов на прямом просмотре 20
2.2. Введение атрибутов на обратном просмотре 38
Глава 3. Применение атрибутных спецификаций 48
3.1. Алгоритмы процессирования и построения атрибутных процессоров 48
3.2. Применение атрибутных RBNF-грамматик в технологии SYNTAX 60
Глава 4. Дополнительные возможности применения атрибутных специ фикаций 70
Заключение 79
Список литературы
- Введение атрибутов на прямом просмотре
- Введение атрибутов на обратном просмотре
- Алгоритмы процессирования и построения атрибутных процессоров
- Применение атрибутных RBNF-грамматик в технологии SYNTAX
Введение к работе
Актуальность темы. Атрибутная техника была введена Д. Кнутом [9] с целью описания семантики языков, порождаемых классическими контекстно-свободными грамматиками Хомского [3]. Технически метод предполагает построение дерева разбора входного предложения языка в данной КС-грамматике, а затем вычисление значений атрибутов в каждой вершине этого дерева по правилам, связанным с правилами грамматики, участвующими в разборе. На практике данный подход был реализован в ряде систем, таких как, например, 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-грамматиках для построения средств синтаксически-управляемой обработки данных в контексте следующих особенностей алгоритма трансляции:
атрибуты вычисляются на не полностью построенном дереве вывода;
само дерево вывода строится с учетом контекста, определяемого значениями атрибутов;
атрибуты применяются для контекстно-зависимого разрешения синтаксической неоднозначности спецификации трансляции.
Практическая и теоретическая ценность. Полученные результаты развивают технологию синтаксически-управляемой обработки данных SYNTAX, улучшая условия разработки и надежность информационных систем, создаваемых с ее использованием. Основной теоретический результат: показано, что использование атрибутов в SYNTAX-спецификациях равнозначно параметризации контекстных символов.
Апробация работы. Результаты диссертации докладывались на семинаре «Информатика и компьютерные технологии» СПИИРАН (2006 г., Санкт-Петербург) и девятом научно-практическом семинаре «Новые информационные технологии в автоматизированных системах» МГИЭМ, ИПМ (2006 г., Москва).
Предложенный подход был реализован в виде прототипа на основе технологического комплекса SYNTAX, разработанного в СПбГУ.
Публикации. По теме диссертации опубликованы работы [1, 2].
Структура и объем диссертации. Диссертация состоит из введения, 4 глав, заключения и приложения. Диссертационная работа изложена на 83 страницах, приложение — на 34 страницах. Список литературы содержит 27 наименований.
Введение атрибутов на прямом просмотре
При описании введения атрибутов в технологию SYNTAX будем опираться на ее изложение в монографии [4]. Управляющая RBNF-грамматика определяется как формальная система G = (Удг, Vj, Ж, Е, Р, S), где V/v и Vp — множества нетерминалов и терминалов соответственно, Н и — множества резольверов и семантик, S Є VN — начальный нетерминал, а Р — множество правил вида N : Ду, где N Є VJV, a RN — регулярное выражение над объединенным алфавитом V = VJV U Vy U 9 U . Значение такого регулярного выражения //(і?) определяется следующим образом: {а}, если R = а, а Є V U{e} H(R) = { U /i(Hi)fc, если R = R\ fc=0 n(Ri)n(R2), если R = Ді, 7 //(Лі) U /х(Лг), если Л = і?і; .
При изучении свойств RBNF-грамматик и построении сплайновых процессоров удобно бывает рассматривать представление RBNF-грамматики в виде граф-схемы. Граф-схема представляет собой направленный граф, вершины которого помечены символами из VNUVT, а дуги — цепочками из 91 и Е . Каждому регулярному выражению в правой части правила RBNF-грамматики можно сопоставить компоненту граф-схемы, пользуясь таблицей 1. Каждая компонента имеет выделенные начальную и конечную вершины.
Рассмотрим классический [15] способ введения атрибутов. Здесь наборы атрибутов связываются с вхождениями грамматических символов (нетерминалов и терминалов) в правила КС-грамматики, а правила вычислений зна чений атрибутов связываются с самими правилами грамматики. Так, правилу грамматики А - В\В2, где А имеет синтезируемый атрибут с\, а В і и В2 — наследуемые атрибуты с2 и Сз, соответственно, можно сопоставить правило вычисления атрибута с\ := /(с2,сз). Важно отметить, что атрибуты здесь характеризуются не только своим именем, но и вхождением связанного с ними грамматического символа в правило. Так, в правиле А — В В атрибуты, связанные с вхождениями нетерминалов В будут различны, поскольку различны эти вхождения. То есть правило для вычисления с\, атрибута А, будет выглядеть как с\ := /(сг, сз), где сг и сз — атрибуты первого и второго вхождений В, соответственно. Если рассматривать соответствующий узел в дереве разбора как запись с полями для хранения информации, то атрибут грамматического символа можно считать именем поля [2].
Рассмотрим возможность применения аналогичного подхода к RBNF-грамматикам [4]. Взяв в качестве примера правило А : В+ RBNF-грамматики и применив предложенную выше схему введения атрибутов, можно связать, например, атрибут с\ с вхождением А, а атрибут с2 — с вхождением В и задать правило вычисления с\ как с\ := f(c2). Однако, в таком случае вычисление С\ не будет зависеть от того, какому из предложений В, ВВ, ВВВ и т.д. соответствует разбираемая но данному правилу синтаксическая конструкция.
Одним из подходов к решению проблемы связи атрибутов с операндами регулярных выражений в правых частях правил является введение специальных операций над атрибутами, соответствующих операциям над операндами [12]. Тогда с каждым нетерминалом в левой части правила связывается не просто объявление атрибута и его тина (наследуемый, синтезируемый), но также и операция, которая должна быть применена. Такие спецификации близки по организации генерируемых трансляторов к классическим.
В данной работе, в силу особенностей алгоритма сплайнового процесси-рования, предлагается вычислять значения атрибутов итеративно в процессе анализа входной цепочки по соответствующему правилу грамматики. То есть в данном примере можно некоторым образом задать правило с\ := д{с\,с2), которое исполняется всякий раз при разборе очередной подконструкции входной цепочки, соответствующей очередному вхождению В. Таким образом, в случае, если разбираемая синтаксическая конструкция соответствует ВВВ, то значение атрибута с\ будет вычисляться в данном случае по правилу с\ := f(C0,ChC2,C3), где f(x0,xi,x2,x3) = д(д{д{х0,хі),х2),хз), Ch С2, С3 — значения синтезируемых атрибутов для каждого вхождения В в цепочку ВВВ, Со — начальное значение с\, задаваемое при инициализации. Со — константа, поэтому значение с\ в данном случае зависит от трех параметров — значений синтезируемых атрибутов вхождений В.
Реализовать итеративное вычисление значений атрибутов можно с помощью описанного в главе 1 способа введения атрибутов в технологию SYNTAX. Для реализации такого подхода рассмотрим следующую схему: со всяким вхождением нетерминала в левые части правил свяжем набор формальных атрибутов, а со всяким вхождением нетерминала, семантики или резольвера в правые части правил свяжем набор фактических атрибутов.
Введение атрибутов на обратном просмотре
Обратный просмотр, как и прямой, реализуется онлайновым процессором. При этом входной язык этого процессора состоит из цепочек состояний прямого просмотра. Как было показано в главе 1 применение атрибутов на обратном просмотре так же целесообразно, как и на прямом. В качестве механизма, реализующего атрибутную трансляцию на обратном просмотре, можно использовать атрибутный сплайновый процессор, описанный в параграфе 2.1. Остается только показать взаимосвязь такого механизма и соответствующего ему описания трансляции.
Согласно [4] помещение очередного магазинного символа в маїязин этого процессора происходит при прохождении правой границы порождения некоторого нетерминала. При этом в магазин процессора помещается символ, содержащий вершину граф-схемы, помеченную этим нетерминалом. Снятие символа с вершины магазина на обратном просмотре происходит при достижении левой границы порождения нетерминала, являющегося меткой одной из вершин, составляющих верхний магазинный символ. Таким образом, так же, как и в случае прямого просмотра, элементы магазина контекстов (то есть контексты) сплайнового процессора можно связать с правилами грамматики.
Выделим в каждом из трех классов формальных атрибутов атрибуты прямого и обратного просмотра. Каждая семантика и резольвер в SYNTAX может использоваться только на одном из просмотров. Поэтому атрибуты прямого просмотра могут использоваться как фактические атрибуты только семантик и резольверов прямого просмотра, а атрибуты обратного просмотра — только семантик и резольверов обратного просмотра. Вхождение в граф-схему вершины, помеченной нетерминалом, одинаково приводит к созданию нового контекста и на прямом, и на обратном просмотрах, поэтому нетерминалы могут быть помечены наборами фактических атрибутов, состоящими из атрибутов обоих просмотров.
Можно построить соответствие между контекстами прямого и обратно го просмотров через правила грамматики, следовательно, можно специфицировать передачу контекстной информации между просмотрами на уровне грамматики.
Для передачи информации из некоторого контекста на прямом просмотре в соответствующий контекст на обратном используется специальный тип локальных атрибутов — двусторонние атрибуты. Двусторонний атрибут, с точки зрения разработчика спецификации, присутствует как на прямом, так и на обратном просмотре. Причем значение, полученное им на прямом просмотре, не теряется после окончания просмотра.
Технически это может быть реализовано следующим образом. На прямом просмотре два следующих события происходят одновременно: достижение считывающей головкой правой границы порождения нетерминала А и переход процессора в возвратное состояние, состоящее из вершин, множество меток которых содержит А. На обратном просмотре первое событие приводит к помещению магазинного символа в магазин и формированию нового контекста на вершине магазина контекстов. На прямом просмотре второе событие связано со снятием текущего контекста с вершины магазина контекстов. Это означает, что данные, полученные в двусторонних атрибутах к этому времени, должны быть сохранены для того, чтобы быть восстановленными на обратном просмотре. Входным предложением обратного просмотра является последовательность состояний, которые прошел процессор прямого просмотра, взятая в обратном порядке. Таким образом, процессор прямого просмотра при переходе в новое состояние должен добавлять номер этого состояния к формируемому входу процессора обратного просмотра. Поскольку снятие контекста связано с переходом в возвратное состояние, вычисленные значения двусторонних атрибутов сохраняются вместе с номером этого состояния.
Алгоритмы процессирования и построения атрибутных процессоров
Рассмотрим подробнее работу алгоритма детерминированного сплайнового процессора:
1) Выбор очередной лексемы (входного символа). По состоянию q и очередной лексеме а осуществляется обращение к таблице лексических входов и выбирается множество резольверных цепочек, соответствующих этой паре. Если множество выбранных резольверных цепочек пусто, то по паре (q, а) выбирается запись в таблице управляющих элементов. Если в состоянии q прием а невозможен, то осуществляется проверка на возможность «пустого» движения. Данной ситуации также соответствует либо непустое множество резольверных цепочек, либо указатель на управляющий элемент. Если «пустое» движение невозможно, то процессор переходит в состояние бесконтекстной ошибки.
2) Если на шаге 1 было выбрано пустое множество резольверных цепочек, то осуществляется переход к шагу 3, иначе значение каждой цепочки вычисляется в контексте текущего состояния операционной среды. Если количество цепочек, значение которых истинно, отлично от 1, то это индицирует контекстную ошибку. В противном случае по единственной цепочке с истинным значением выбирается управляющий элемент.
3) В результате выполнения предыдущих шагов был выбран управляющий элемент. Если выполнялось «непустое» движение, то данный элемент является тройкой, содержащей: - номер следующего (переходного) состояния; - цепочку семантик; - цепочку магазинных символов.
В результате его интерпретации в магазин помещается указанная цепочка магазинных символов, исполняются семантики, некоторым образом модифицирующие состояние операционной среды, процессор осуществляет переход в следующее состояние.
Если выполнялось «пустое» движение, то управляющий элемент содержит: - вход в таблицу возвратных состояний; - цепочку семантик; - цепочку магазинных символов. Интерпретация цепочек семантик и магазинных символов аналогична случаю «непустого» движения. Таблица возвратных состояний используется для отображения верхнего символа магазина в одно из возвратных состояний. При этом верхний символ магазина снимается, а процессор переходит в возвратное состояние.
На рисунке 7 представлена схема работы онлайнового процессора без атрибутов.
В случае использования атрибутов помимо собственно магазина онлайнового процессора, содержащего магазинные символы, используется магазин контекстов. Элементами магазина контекстов являются конечные последовательности значений атрибутов. Сравнивая алгоритм выполнения перехода между конфигурациями, описанный в [4], с алгоритмом, приведенным в п.2.1, можно отметить следующее: во-первых, вместо элементов множеств К, Е и Г в атрибутном алгоритме используются соответствующие элементы множеств И, S и Г; во-вторых, в изменении нуждаются только следующие операции, используемые в алгоритме процессирования: вызов семантики; вычисление резольвера; помещение/снятие символа магазина.
Вызов семантики заключается в вызове процедуры, ассоциированной с данным грамматическим символом-семантикой. В случае семантики без атрибутов данная процедура осуществляет преобразование операционной среды. В случае использования атрибутов процедура имеет параметры, соответствующие атрибутам.
Применение атрибутных RBNF-грамматик в технологии SYNTAX
Описанный в главах 1-3 подход был реализован в виде ирототипа на основе существующего технологического комплекса SYNTAX. Однако в прототипе некоторые проблемы остались не решены. Ниже представлены некоторые такие задачи, имеющие практическое значение, и способы сведения их решения к предложенному подходу.
Проверка требований отсутствия неопределенных значений атрибутов. Представленные в главе 2 ограничения задают алгоритм проверки таких условий на уровне граф-схем:
5А) Если формальный атрибут прямого просмотра используется как наследуемый фактический атрибут, то
а) либо на всяком пути в компоненте граф-схемы из начальной вер шины в данную соответствующий формальный атрибут хотя бы однажды использовался как синтезируемый фактический атрибут прямого просмотра;
б) либо соответствующий формальный атрибут является формаль ным наследуемым атрибутом нетерминала, соответствующего дай ной компоненте.
5Б) Если формальный атрибут обратного просмотра используется как наследуемый фактический атрибут, то
а) либо на всяком пути в компоненте граф-схемы из данной вершины вершины в конечную соответствующий формальный атрибут хотя бы однажды использовался как синтезируемый фактический атрибут обратного просмотра;
б) либо соответствующий формальный атрибут является формаль ным наследуемым атрибутом нетерминала, соответствующего дан ной компоненте; в) либо соответствующий формальный атрибут является двусторон ним атрибутом.
6А) Для всякого синтезируемого формального атрибута прямого просмотра нетерминала, соответствующего данной компоненте, на всяком пути в компоненте граф-схемы из начальной вершины в конечную существует вершина, у которой данный формальный атрибут используется как синтезируемый фактический атрибут прямого просмотра.
6Б) Для всякого синтезируемого формального атрибута обратного просмотра нетерминала, соответствующего данной компоненте, на всяком пути в компоненте граф-схемы из начальной вершины в конечную существует вершина, у которой данный формальный атрибут используется как синтезируемый фактический атрибут обратного просмотра.
6В) Для всякого двустороннего формального атрибута нетерминала, соответствующего данной компоненте, на всяком пути в компоненте граф-схемы из начальной вершины в конечную существует вершина, у которой данный формальный атрибут используется как синтезируемый фактический атрибут прямого просмотра.
В силу того, что в процессе анализа входной цепочки вычисление резоль-веров происходит до вычисления семантик, независимо от порядка, в котором они следуют в спецификации, предполагается, что в пометках дуг резольверы прямого просмотра предшествуют семантикам прямого просмотра, а резоль-веры обратного просмотра следуют за семантиками обратного просмотра.
Использование атрибутов у терминалов. Одним из введенных в главе 2 ограничений было условие отсутствия атрибутов у терминалов. Тем не менее, информация о терминале может потребоваться не только для синтаксической компоненты (для входа в управляющую таблицу), но и для реализации семантических действий (например, представление лексемы). В реализации технологического комплекса SYNTAX элементы входной цепочки последовательно поставляются «поставщиком лексем», который модифицирует состояние операционной среды таким образом, чтобы дополнительная, контекстная, информация об очередной лексеме могла быть получена в реализации семантического действия. Далее эта информация может быть использована как значение какого-либо атрибута. Применение атрибутов терминальных символов может снять необходимость явного обращения к операционной среде для получения дополнительной информации о входном символе.
С точки зрения «поставщика лексем» нет различия в поставляемых им входных символах, поэтому все терминалы должны быть помечены одинаковыми (по типам) наборами фактических атрибутов. Например, если «поставщик лексем» производит дополнительно только информацию о представлении лексемы, то все терминалы должны быть помечены цепочкой, состоящей из одного фактического синтезируемого атрибута: Variable declaration $out name, type : Type type , identifier name . Type $out type : identifier type . На этапе построения граф-схемы атрибутные пометки терминалов могут преобразовываться в вызовы семантик прямого просмотра: Variable declaration $out name, type : Type type , setRepresentation name , identifier . Type $out type : setRepresentation type , identifier .
Обработка полученной таким образом граф-схемы описана в главе 3. Помимо условия однообразности наборов фактических атрибутов терминальных символов, описанное преобразование в силу ограничения 8Б влечет следующее ограничение:
Терминальные вершины, объединяемые в одно состояние прямого просмотра, должны иметь эквивалентные наборы фактических атрибутов.
Передача информации между синтаксическими процессорами.
Весьма распространенной в анализе языков программирования является ситуация, когда входная цепочка одного процессора является входным символом другого. Типичным примером является разделение лексического и синтаксического анализа. Входная цепочка разбивается на участки, каждый из которых является предложением языка, распознаваемого лексическим процессором. Все множество таких предложений разбивается на конечное множество классов, каждый из которых соответствует терминальному символу синтаксического процессора. Задача лексического процессора в таком случае — не только распознать предложение своего языка, но и определить его лексический класс.
И синтаксический, и лексический процессоры могут быть заданы в виде ATSL спецификаций. При этом множества лексем часто являются регулярными. Регулярный язык можно задать с помощью однокомпонентной граф-схемы.
