Поскольку деревьев вывода, вообще говоря,

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

Отметим, что этот метод определения семантики обладает такой же мощностью, как и всякий другой возможный метод, в том смысле, что значение любого атрибута в любом узле может произвольным образом зависеть от структуры всего дерева. Предположим, например, что в КС грамматике всем символам, кроме S, приписано по два унаследованных атрибута: l ("положение") и t ("дерево"), а всем нетерминалам, кроме того, по одному синтезированному атрибуту s ("поддерево"). Значениями l будут конечные последовательности положительных целых чисел

, определяющие местонахождение узла в дереве в соответствии с системой обозначения Дьюи. Атрибуты t и s представляют собой множество упорядоченных пар (l, X), где l - положение узла, а X - символ грамматики, обозначающий метку узла с положением l. Семантическими правилами для каждого синтаксического правила (пример 2.1) служат

(2.4)

Следовательно, для дерева (рис. 1.2), например, мы имеем

s(N) = {(1, L), (2, ?), (3, L), (1.1, L), (1.2, B), (3.1, L), (3.2, B), (1.1.1, L), (1.1.2, B), (1.2.1, 1), (3.1.1, B), (3.2.1, 1), (1.1.1.1, L), (1.1.1.2, B), (1.1.2.1, 0), (3.1.1.1, 0), (1.1.1.1.1, B), (1.1.1.2.1, 1), (1.1.1.1.2.1, 1)}.

Ясно, что эта запись содержит всю информацию о дереве вывода. Согласно семантическим правилам (2.4), атрибут t во всех узлах (кроме корня) представляет собой множество, характеризующее всe дерево вывода; атрибут l определяет местонахождение этих узлов. Отсюда сразу следует, что любая мыслимая функция, определ_нная на дереве вывода, может быть представлена как атрибут произвольного узла, поскольку эта функция имеет вид f(t, l), для некоторого f. Аналогично, можно показать, что для определения значения, связанного с произвольным деревом вывода, достаточно только синтезированных атрибутов, поскольку синтезированный атрибут w, вычисляемый по формуле

Содержание Назад Вперед

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