Конспект установочных лекций по комплексному курсу Информатика, Теория информации




Описание значений выражений


Как уже упоминалось, существенный интерес представляют два дополняющих описания значения ("семантики") ЯП:

(1) операционная, ориентированная на вычисление значения по форме описания, которая дает алгоритм для вычисления значения выражения;

(2)   функциональная форма описания, которая математическим образом каждому выражению ставит в соответствие математический элемент.

(3)   Форма (1) соответствует операционной семантике, а форма (2) - функциональной. Соответственно этому для выражения в аппликативном языке обе семантики определяются следующим образом:

(1)    семантика подстановки термов, которая представляется через алгоритм подстановок термов, приводящий выражение (при известных дополнительных условиях) в нормальную (примитивную) форму;

(2)    функция интерпретации I, которая отображает выражение ЯП на математические элементы.

При этом предполагается, что заданы "примитивная" вычислительная структура А с сигнатурой ? = (S, F), так что каждый носитель sА типа s в А содержит элемент 1, и система подстановки термов R над ?. В дальнейшем предполагается заданным множество ID идентификаторов. Оно соответствует формальному языку, который связан с синтаксической единицей <id>. Определяются множества D, FCT и Н.

D =def {а

sA:s
S}

FCT =def {(f:sA1

x...xsAn> sAn+1): n

 N ^ f строгая ^ (
i, 1<= i <=n + 1: si
S)}.

D представляет множество элементов данных, FCT - множество функций, а

Н =-def D ^ FCT

есть множество "семантических" элементов, состоящее из множества элементов данных и множества отображений между элементами данных. D есть область значений для семантической интерпретации выражений. Н есть область значений для применяемых позднее конкретизаций.

Для задания операционной семантики будет применяться семантика подстановки термов. К томy же предполагаются заданными правила подстановки термов для термов над сигнатурой примитивных вычислительных структур. Пусть для терма из wЕ определена система R, которая полностью корректна и каждый терм t (с подходящим образом определенной интерпретацией, т.е.


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