Основы программирования

Лекция 5 - Денотационная семантика
Индекс материала
Лекция 5
Метод таблиц решений
Операционная семантика
Денотационная семантика
Аксиоматическая семантика
Аксиоматическая семантика1
Все страницы

4.                  Денотационная семантика

 

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

Основные идеи денотационной семантики проиллюстрируем на более простом случае, когда система равенств (5.3) является системой языковых уравнений:

X1 = φ1,1  φ1,2  ...  φ1,k1,

X2 = φ2,1  φ2,2  ...  φ2,k2,

(4)         .....…………………………

Xn= φn,1  φn,2  ...  φn,kn,

причем i-ое уравнение при ki = 0 имеет вид

Xi = 

Как известно, формальный язык — это множество цепочек в некотором алфавите. Такую систему можно рассматривать как одну из интерпретаций набора правил некоторой грамматики, представленную в форме Бэкуса-Наура (каждое из приведенных уравнений является аналогом некоторой такой формулы). Пусть фиксирован некоторый алфавит A = {a1, a2, …, am} терминальных символов грамматики, из которых строятся цепочки, образующие используемые в системе (4) языки. Символы X1, X2, ..., Xn являются метапеременными грамматики, здесь будут рассматриваться как переменные, значениями которых являются языки (множества значений этих метапеременных). Символы φi,j, i = 1, ..., n, j = 1, ..., kj, обозначают цепочки в объединенном алфавите терминальных символов и метапеременных:

φi,j  (A | { X1, X2, ..., Xn})* .

Цепочка φi,j рассматривается как некоторое выражение, определяющее значение, являющееся языком (множеством цепочек в алфавите A). Такое выражение определяется следующим образом. Если значения X1, X2, ..., Xn заданы, то цепочка

φ = Z1 Z2 ... Zk, Zi(A | { X1, X2, ..., Xn }),

обозначает сцепление множеств Z1 Z2 ... Zk, причём вхождение в эту цепочку символа aj представляет множество из одного элемента {aj}. Это означает, что φ определяет множество цепочек

{ p1 p2 ... pk | pjZj, j = 1, ..., k},

причём цепочка

p1, p2, ..., pk

представляет собой последовательность выписанных друг за другом цепочек p1, p2, ..., pk. Таким образом, каждая правая часть уравнений системы (4) представляет собой объединение множеств цепочек.

Решением системы (4) является набор значений (языков)

L1, L2, ..., Ln

переменных X1, X2, ..., Xn, для которых все уравнения системы (4) превращаются в тождество.

Рассмотрим в качестве примера частный случай системы (4), состоящий из одного уравнения

X = a X  b X  c

с алфавитом A = {a, b, c}. Решением этого уравнения является язык

L = { φ c | φ{a, b}*}.

Система (4) может иметь несколько решений. Так в рассмотренном примере помимо L решениями являются также

L1 = L  {φ a | φ{a, b}*}

и

L2 = L  { φ b | φ{a, b}*}.

В соответствии с денотационной семантикой в качестве определяемого решения системы (4) принимается наименьшее. Решение (L1, L2, ..., Ln) системы (4) называется наименьшим, если для любого другого решения (L′1, L′2, ..., L′n) выполняется

L1  L′1, L2  L′2, ..., Ln  L′n.

Так в рассмотренном примере наименьшим (а значит, определяемым денотационной семантикой) является решение L.

В качестве метода решения систем уравнений (3) и (4) можно использовать метод последовательных приближений. Сущность этого метода для системы (4) заключается в следующем. Обозначим правые части уравнений системы (4) операторами Ti(X1, X2, ..., Xn). Тогда система (4) примет вид

X1 = T1(X1, X2, ..., Xn),

X2 = T2(X1, X2, ..., Xn),

(5)                 ………………………

Xn = Tn(X1, X2, ..., Xn).

 

В качестве начального приближения решения этой системы примем набор языков (L1[0], ..., Ln[0]) = (, , ..., ). Каждое следующее приближение определяется по формуле:

(L1[0], ..., Ln[0]) = (T1(L1[i–1], ..., Ln[i–1]), …………….. (Tn(L1[i–1], ..., Ln[i–1])).

Так как операции объединения и сцепления множеств являются монотонными функциями относительно отношения порядка Н, то этот процесс сходится к решению (L1, ..., Ln) системы (5), т.е.

(L1, ..., Ln)= (T1(L1, ..., Ln), ..., Tn(L1, ..., Ln))

и это решение является наименьшим. Это решение называют ещё наименьшей неподвижной точкой системы операторов

T1, T2, ..., Tn.

В рассмотренном примере этот процесс даёт следующую последовательность приближений:

L[0] = , L[1] = {c}, L[2]= {c, ac, bc},

L[3] = {c, ac, bc, aac, abc, bac, bbc},

…………………………………………

Этот процесс сходится к указанному выше наименьшему решению L.