Теория и реализация языков программирования



         

Формальные свойства - часть 3


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

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

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

l(X_{pj})= \left\{ \begin{aligned} &l(X_{p0})\cdot j , & \text{ если } & X_{p0}\neq S;\\ &j, & \text{ если } & X_{p0}= S;\\ \end{aligned} \right. \\l(X_{pj})= \left\{ \begin{aligned} &t(X_{p0}), & \text{ если } & X_{p0}\neq S;\\ &s(X_{p0}), & \text{ если } & X_{p0}= S;\\ \end{aligned} \right.

(2.4)

s(X_{p0})=\{(l(X_{p0}),X_{p0}) \mid\ X_{p0} \neq S \} \cup \bigcup\limits_{j=1}^{n_{p}}} \{S(X_{pj}) \mid X_{pj} \in N \}

Следовательно, для дерева (рис. 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, вычисляемый по формуле




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