Содержание к диссертации
Введение
Глава 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
Введение к работе
Одной из типичных задач в информатике является синтаксически-упраи-ляемая обработка данных. Процесс обработки данных в таком случае управляется синтаксической структурой этих данных. Примером такой задачи может служить трансляция программ» Более общим приложением является трансляция вообще и ее построение. Трансляцией называется отображение из некоторого входного языка в выходной. На практике часто результатом трансляции является изменение состояния программы, реализующей трансляцию, что может заключаться и в генерации предложения на выходном языке.
Для решения задачи построения трансляции используются системы построения трансляторов, наиболее распространенными из которых являются средства, основанные на применении грамматик для описания входного языка. С правилами таких грамматик связываются семантические правила, служащие для вычисления результата трансляции. Для передачи данных между семантическими правилами могут использоваться атрибуты, введенные Д. Кнутом [15. ТехЕтчески этот метод предполагает построение дерева разбора входного предложения в данной КС-грамматике, а затем вычисление значений атрибутов в каждой вершине этого дерева по семантическим правилам, связанным с правилами грамматики, участвующими в разборе.
Начиная с конца 6U-X годов, для определения синтаксиса КС-языков применяются также синтаксические диаграммы (синтаксические графи) Вирта [3] и RBNF-грамматики. Каждому нетерминалу соответствует одна компонента диаграммы или одно правило RBNF-грамматики, правая часть которого — регулярное выражение относительно символов объединенного алфавита грамматики.
Возникает задача спецификации трансляции с использованием RBNF-грам-матик в качестве синтаксической основы. Технологии, использующие явно ItBNF-грамматики, обычно неявно преобразуют данную грамматику в эквивалентную однозначную КС-грамматику. В технологии SYNTAX [4], использующей грас! -схшы (аналоги диаграмм Вирта) и RBNF-грамматики в качестве синтаксического базиса, применяется другой подход. Здесь регулярные выражения в правых частях правил грамматики явно интерпретируются. Кроме того, данная технология позволяет задавать трансляции с контекстно-зависимых языков и использовать синтаксически-неоднозначные входные грамматики.
Передача данных между семантическими действиями в технологии SYNTAX не специфицируется на уровне грамматики. Задачей данной работы является реализация атрибутов в SYNTAX для обеспечения возможности задания потоков данных средствами атрибутных RBNF-грамматик.
Актуальность темы следует из перечисленных ниже аргументов:
во-первых, использование атрибутов в RBNF-грамматиках требует специального оформления правил грамматик и разработки метода применения атрибутов в механизме реализации трансляции;
во-вторых, анализ па JlBNF-грамматиках при линейном ограничении времени относительно длины входной цепочки приводит к ограничениям на класс применяемых грамматик и, как следствие, на использование атрибутов. Данные ограничения следует определить с учетом используемого механизма ана лиза;
в-третьих, SYNTAX позволяет задавать контекстно-зависимые языки. Это достишется введением резольверов — предикатов, огршшчивающих выбор альтернатив при анализе в зависимости от контекста- Атрибуты могут использоваться для задания этого контекста;
в-четвертых, ограничения, накладываемые на RBNF-грамматики в SYNTAX, позволяют использовать синтаксически-неоднозначные грамматики. Дли уточнения синтаксической структуры входного предложения может применяться обратный просмотр, где также могут использоваться атрибуты.
Выбор в качестве основы технологии SYNTAX определялся не только возможностью полисе раскрыть указанные теоретические аспекты, но и необходимостью устранения одного из серьезных, с точки зрения технологии программировании, недостатков SYNTAX: невозможности использования параметров у подпрограмм, реализующих семантические действия и резольиеры.
Цель работы заключается в разработке метода спецификации трансляций на атрибутных IlBNF-грамматиках и его использовании в технологии сиитаксически-управляемой обработки данных SYNTAX.
Научная новизна. Впервые атрибутная техника применяется непосредственно в RBNF-грамматиках для построения средств сиитаксически-управляемой обработки данных в контексте следующих особенностей алгоритма трансляции:
• атрибуты вычисляются на не полностью построенном дереве вывода;
• само дерево вывода строится с учетом контекста, определяемого значениями атрибутов;
• атрибуты применяются для контекстно-зависимого разрешения синтаксической неоднозначности грамматики относительно результата трансляции.
Основные результаты работы:
• разработан способ применения атрибутов в RBNF-грамматиках;
дано формальное определение трансляции, задаваемой атрибутной спе-цификацией;
• выявлены ограничения, накладываемые на атрибуты для их использования в алгоритме сплайпового процессирования, применяемом в технологии SYNTAX;
• модифицированы алгоритмы построения управляющих таблиц сплайпового челночного процессора для реализации поддержки атрибутов;
• модифицирован алгоритм онлайнового ироцсссировалия, реализующий прямой и обратный просмотры в технологии SYNTAX;
• разработан механизм передачи контекстной информации между просмотрами с использованием атрибутов.
Построение диссертации. Основное содержание диссертации изложено в 4 главах.
В ПЕРВОЙ ГЛАВЕ описаны подходы к описанию контекстно-зависимых языков на основе двухуровневых грамматик (аффиксные грамматики [17, W-грамматики [2GJ) и к спецификации трансляции (атрибутная техника в КС-і рамматиках [15]). Неформально в RBNF-спецификации системы SYNTAX вводятся атрибуты-
Во ВТОРОЙ ГЛАВЕ дано формальное определение трансляции, задаваемой SYNTAX-спецификацией с использованием атрибутов (случай прямого просмотра), описание алгоритма сплайпового процессирования, приведены ограничения, накладываемые па атрибуты для обеспечения возможности их применения в сплайповом процессоре. Кроме того, описывается алгоритм обратного просмотра с использованием атрибутов, обсуждается вопрос передачи контекстной информации между просмотрами.
В ТРЕТЬЕЙ ГЛАВЕ описывается модификация представления управляющих таблиц и алгоритма сплайпового процессировашш, описанных в [4], с целью введения поддержки атрибутов. Рассмотрспы примеры использования атрибутного подхода.
В ЧЕТВЕРТОЙ ГЛАВЕ рассматриваются отдельные вопросы, которые не реализованы в разработанном прототипе системы, но, однако, могут быть реализованы с применением описанного атрибутного подхода,
В ЗАКЛЮЧЕНИИ сформулированы основные выводы, полученные по результатам выполненных в диссертации исследований.
Введение атрибутов на прямом просмотре
При описании введения атрибутов в технологию SYNTAX будем опираться на се изложение в монографии [4]. Управляющая RBNF-гралшатика определяется как формальная система G — (VV7 VT, Я, Е, Л 5), где Vjv и Vj- — множества нетерминалов и терминалов соответственно, Ш и 2 — множества резольвсров и селмштив, 5 Є Kv — начальный нетерминал, а Р — множество правил вида N : 7?я где N Є V/v, з, Я# — регулярное выражение над объединенным алфавитом Vr = VjvUVrU9lUS. Значение такого регулярного выражения fi(R) определяется следующим образом: {а}, если R = а, а Є V U {є} U a(Ri)\ если Я = ЯЇ №) = /і(Яі)/і(Я2), если Я = /?ь Й2 /х(Яі)и/ №), еслиЯ = Яі;Я2
При изучении свойств RBNF-грамматик и построении сплайновых процессоров удобно бывает рассматривать представление RBNF-грамматики в виде граф-схемы. Граф-схема представляет собой направленный граф, вер-шины которого помечены символами из VjvUlr, а дуги — цепочками изїИ и . Каждому регулярному выражению в правой части правила RBNF-грамматики можно сопоставить компоненту граф-схемы, пользуясь таблицей 1. Каждая компонента имеет выделенные начальную и конечную вершины.
Рассмотрим классический [15] способ введения атрибутов. Здесь наборы атрибутов связываются с вхождениями грамматических символов (нетерминалов и терминалов) в правила КС-грамматики, а правила вычислений зиа чепий атрибутов связываются с самими правилами грамматики. Так, правилу грамматики А — В\В2. где А имеет синтезируемый атрибут С\, a By и В2 — наследуемые атрибуты С2 и сз, соответственно, можно сопоставить правило вычисления атрибута с\ := /(с2 сз)- Важно отметить, что атрибуты здесь характеризуются не только своим именем, ко и вхождением связанного с ними грамматического символа в правило. Так, в правиле А — В В атрибуты, связанные с вхождениями нетерминалов В будут различны, поскольку различны эти вхождения. То есть правило для вычисления с\у атрибут А} будет выглядеть как с\:— /(с2, с$), где с% и с% — атрибуты первого и второго вхождений В, соответственно» Если рассматривать соответствующий узел в дереве разбора как запись с полями для хранения информации, то атрибут грамматического символа можно считать именем поля [2.
Рассмотрим возможность применения аналогичного подхода к RBNF-грамматикам [4]. Взяв в качестве примера правило A : В+ RBNF-грамматики и применив предложенную выше схему введения атрибутов, можно связать, например, атрибут Сі с вхождением А, а атрибут сг — с вхождением В и задать правило вычисления сі как с\ := f(c2). Однако, в таком случае вычисление С\ не будет зависеть от того, какому из предложений В, ВВ, ВВВ и т.д. соответствует разбираемая по данному правилу синтаксическая конструкция.
Одним из подходов к решению проблемы связи атрибутов а операндами регулярных выражений в правых частях правил является введение специальных операций над атрибутами, соответствующих операциям над операндами [12]. Тогда с каждым нетерминалом в левой части правила связывается не просто объявление атрибута и его тина (наследуемый, синтезируемый), по также и операция, которая должна быть применена. Такие спецификации близки по организации генерируемых трансляторов к классическим.
В данной работе, в силу особенностей алгоритма сплаґшового процесси-рования, предлагается вычислять значения атрибутов итеративно в процессе анализа входной цепочки по соответствующему правилу грамматики. То есть в данном примере можно некоторым образом задать правило с := g(ci,c-2), которое исполняется всякий раз при разборе очередной подконструкции входной цепочки, соответствующей очередному вхождению В. Таким образом, в случае, если разбираемая синтаксическая конструкция соответствует ВВВ, то значение атрибута а будет вычисляться в данном случае по правилу Pi := /(Со,Сх,С2}Съ), где J{XQ,XUX2,XZ) = 5(5(5( 0, 1), 2)1 3), Си C2l 73 — значения синтезируемых атрибутов для каждого вхождения В в цепочку ВВВ, Со — начальное значение Сі, задаваемое при инициализации. Со — константа, поэтому значение с\ в данном случае зависит от трех параметров — значений синтезируемых атрибутов вхождений В,
Введение атрибутов на обратном просмотре
Обратный просмотр, как и прямой, реализуется онлайновым процессором. При этом входной язык этого процессора состоит из цепочек состояний прямого просмотра. Как было показано в главе 1 применение атрибутов на обратном просмотре так же целесообразно, как и па прямом, В качестве механизма, реализующего атрибутную трансляцию на обратном просмотре, можно использовать атрибутный сплайновый процессор, описанный в параграфе 2.1. Остается только показать взаимосвязь такого механизма и соответствующего ему описания трансляции.
Согласно [4] помещение очередного магазинного символа в магазин этого процессора происходит при прохождении правой границы порождения некоторого нетерминала. При этом в магазин процессора помещается символ, содержащий вершину граф-схемы, помеченную этим нетерминалом. Снятие символа с вершины магазина на обратном просмотре происходит при достижении левой границы порождения нетерминала, являющегося меткой одной из вершин, составляющих верхний магазинный символ. Таким образом, так же, как и в случае прямого просмотра, элементы магазина контекстов (то есть контексти) сплайнового процессора можно связать с правилами грамматики.
Выделим в каждом из трех классов формальных атрибутов атрибуты прямого и обратного просмотра. Каждая семантика и резольвер в SYNTAX может использоваться только па одном из просмотров. Поэтому атрибуты прямою просмотра могут использоваться как фактические атрибуты только семантик и резольверов прямого просмотра, а атрибуты обратного просмотра — только семантик и резольверов обратного просмотра. Вхождение в граф-схему вершины, помеченной нетерминалом, одинаково приводит к созданию нового контекста и на прямом, и на обратном просмотрах, поэтому нетерминалы могут быть помечены наборами фактических атрибутов, состоящими из атрибутов обоих просмотров.
Можно построить соответствие между контекстами прямого и обратно го просмотров через правила грамматики, следовательно, можно специфицировать передачу контекстной информации между просмотрами па уровне грамматики.
Для передачи информации из некоторого контекста на прямом просмотре в соответствующий контекст на обратном используется специальный тип локальных атрибутов — двустороппие атрибуты. Двусторонний атрибут, с точки зрении разработчика спецификации, присутствует как на прямом, так и на обратном просмотре. Причем значение, полученное им на прямом просмотре, не теряется после окончания просмотра.
Технически это может быть реализовано следующим образом. На прямом просмотре дна следующих события происходят одновременно: достижение считывающей головкой правой границы порождения нетерминала А и переход процессора в возвратное состояние, сосюящее из вершин, множество меток которых содержит А. На обратном просмотре первое событие приводит к помещению магазинного символа в магазин и формированию нового контекста на вершине магазина контекстов. На прямом просмотре второе событие связано со снятием текущего контекста с вершины магазина коп-текстов. Это означает, что данные, полученные в двусторонних атрибутах к этому времени, должны быть сохранены для того, чтобы быть восстановленными на обратном просмотре. Входным предложением обратного просмотра является последовательность состояний, которые прошел процессор прямого просмотра, взятая в обратном порядке. Таким образом, процессор прямого просмотра при переходе в повое состояние должен добавлять помер этого состояния к формируемому входу процессора обратного просмотра. Поскольку снятие контекста связано с переходом в возвратное состояние, вычисленные значения двусторонних атрибутов сохраняются вместе е номером этого состояния.
Алгоритмы процесснрования и построения атрибутных про цессоров
За основу реализации прототипа атрибутной системы был принят технологический комплекс SYNTAX, разрабатываемый в СПбГУ. Введение атрибутов потребовало изменений: структур хранения данных (управляющих таблиц онлайнового процессора); алгоритмов генерации управляющих таблиц; алгоритма процессирования (анализа входной цепочки). Модификация алгоритма процессирования. Рассмотрим подробнее работу алгоритма детерминированного онлайнового процессора:
1) Выбор очередной лексемы (входного символа). По состоянию q и очередной лексеме а осуществляется обращение к таблице лексических входов и выбирается множество резольвериых цепочек, соответствующих этой паре. Если множество выбранных резольвериых цепочек пусто, то по nape (q a) выбирается запись в таблице управляющих элементов. Если в состоянии q прием а невозможен, то осуществляется проверка на возможность «пустого» движения. Данной ситуации также соответствует либо непустое множество резольвериых цепочек, либо указатель на управляющий элемент. Если «пустое» движение невозможно, то процессор переходит в состояние бесконтекстной ошибки.
2) Если на шаге 1 было выбрано пустое множество резолызорных цепочек, то осуществляется переход к шагу 3, иначе значение каждой цепочки вычисляется в контекста текущего состояния операционной среды. Если количество цепочек, значение которых истинно, отлично от 1, то это индицирует контекстную ошибку. В противном случае по единственной цепочке с истинным значением выбирается управляющий элемент.
3) В результате выполнения предыдущих шагов был выбран управляющий элемент. Если выполнялось шепустоез движение, то данный элемент является тройкой, содержащей: - номер следующего (переходного) состояния; - цепочку семантик; - цепочку магазинных символов.
В результате его интерпретации в магазин помещается указанная цепочка магазинных символов, исполняются семантики, некоторым образом модифицирующие состояние операционной среды, процессор осуществляет переход в следующее состояние.
Если выполнялось «пустое движение, то управляющий элемент содержит: - вход в таблицу возвратных состояний; - цепочку семантик; - цепочку магазинных символов. Интерпретация цепочек семалтик и магазинных символов аналогична случаю «непустого» движения. Таблица возвратных состояний используется для отображения верхнего символа магазина в одно из возвратных состояний. При этом верхний символ магазина снимается, а процессор переходит в возвратное состояние. На рисунке 7 представлена схема работы онлайнового процессора баз атрибутов.
В случае использования атрибутов помимо собственно магазина онлайнового процессора, содержащего магазинные символы, используется магазин контекстов. Элементами магазина контекстов являются конечные последовательности значений атрибутов. Сравнивая алгоритм выполнения перехода между конфигурациями, описанный в [4], с алгоритмом, приведенным в п 2.1, можно отметить следующее: во-первых, вместо элементов множеств Я, Е и Г в атрибутном алгоритме используются соответствующие элементы множеств Я, Е и Г; во-вторых, в изменении нуждаются только следующие операции, используемые в алгоритме процессироваиия: вызов семантики; вычисление револьвера; помещение/снятие символа магазина.
Вызов семантики заключается в вызове процедуры, ассоциированной с данным грамматическим символом-семантикой, В случае семантики без атрибутов данная процедура осуществляет преобразование операционной среды.
Применение атрибутных RBNF-грамматик в технологии SYNTAX
Разработка спецификации. В качестве примера применения предложенного подхода рассмотрим следующую задачу.
Задача. Пусть предложение некоторого языка состоит из замкнутого предложения — заключенной в скобки последовательности операторов, описаний переменных и определений функций, разделенных точками с запятой. Описание переменной выглядит, как, например, deel numeric а, где deel — ключевое слово, numeric — тип, а — идентификатор, имя переменной. Определение функции выглядит, как, например, ргос f (numeric х) ; numeric = closed sentctnee, где т&іом функции является замкнутое предложение — dosed sentence. Оператором является вызов функции (например, f (х)). Все идентификаторы, используемые и вызовах функций, должны быть описаны как переменные или определены как функции в текущем замкнутом предложении или объемлющих. При этом определение или описание может встречаться текстуально как до, так и после использования.
Ниже представлена спецификация на языке ATSL, осуществляющая распознавание описанного выше языка. program : body, body $revdir aecset : initdecset decset , closed sentence decset . Телом программы (body) является замкнутое предложение (closed sentence). Входным атрибутом этого нетерминала является множество символов, определенных на данном уровне (decset). В данном примере реальным значением этого атрибута является ссылка на само множество определенных символов. В начале анализа это множество инициализируется с помощью семантики initdecset, значением выходного атрибута которой является ссылка на инициализированный объект. closed sentence $in indecset, Srevdir decset : copydecs indecset» decset , (\ (phrase decset, decset ) # ; , )
Замкнутое предложение состоит из фраз (phrase), разделенных точками с запятой и заключенных в скобки. Каждому замкнутому предложению соответствует множество символов, определенных в нем. Ссылка на это множество сохраняется в двустороннем атрибуте decset. phrase $in indecset, $revin decset : declaration indecset, decset ; procedure definition indecset, decset ; statement indecset, decset .
Фразой является либо определение переменной, либо описание процедуры, либо оператор (statement). Входным атрибутом прямого просмотра являемся ссылка на множество определенных символов текущего замкнутою предложения. При анализе синтаксической компоненты, соответствующей данной фразе, на прямом просмотре это множество может пополняться. Входным атрибутом обратного просмотра также является ссылка на множество определенных символов текущего замкнутого предложения. Это множество сохраняется для каждого замкнутого предложения в соответствующем двустороннем атрибуте. statement $in indecset $revin decset : expression indecset, decset . expression $in indecset» $revin decset, Srevdir symbol : declared symbol 3ymbQl , blookupsymbol decset3 symbol , actual parameter list indecset, decset .
Оператором является выражение (expression). Выражение — вызов функции или взятие значения переменной. Проверка того, что функция определена в в данном замкнутом предложении или объемлющих, выполняется на обратном просмотре. Для этого вызывается рсзольвер обратнош просмотра blookupsymbol, который получает1 2 параметра — множество определенных символов и сам символ, идентифицирующий функцию. Значение этого идентификатора сохраняется в двустороннем атрибуте symbol.
