Применяемая методика. 
Подход к реализации атрибутов в системе SynGT

Трансляция из языка L-/cZ^*b язык L^cl2* определяется как отношение х/_2[1 ]. На практике рассматривается обобщение этого определения, при котором трансляция определяет изменение состояния программы в зависимости от входного предложения.

В соответствии с требованиями [10], которым должно удовлетворять описание языка, способ спецификации трансляции должен давать следующее:

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

Привлекательность КС-грамматик для анализа языка, их простота (правила имеют вид А—>а, где — ацепочка символов из объединенного алфавита грамматики), позволяющая создавать эффективные анализаторы, породили огромное количество классов и подклассов грамматик, с различной степенью ограничений на языки. Наиболее сильные ограничения на языки (LL (k)), LR (k), LALR, SLR) [1] позволяют строить анализаторы, имеющие линейную сложность разбора в зависимости от длины входного предложения.

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

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

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

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

В общем случае в SynGT технологии используется синтаксический анализ типа top-down. Поэтому основным ограничением на класс грамматик является отсутствие леворекурсивных правил. Алгоритм удаления левой рекурсии в КСР-грамматиках подробно дан в ряде работ [19], [20].

Введение

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

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

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

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

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

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

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

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

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

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