Программа как математический объект: Методические указания для самостоятельного изучения темы и выполнения РГР, страница 5

1.6.2  Типы данных

Тип данных – это множество объектов, в котором объединяются 1) множество операций, 2) множество тестов  и 3) множество символов. Например, целое ³ 0 является типом данных с операциями +, *, тестов =, >, и множеством символов в виде десятичных или двоичных цифровых строк. Спецификация типа данных обозначается ключевым словом type, которое определяет имя типа и таблицу операций и тестов.

Когда тип данных имеет общеизвестное определение, содержание таблицы операций и тестов следует из имени типа или ссылки к последнему. Например,

type целое ³ 0

предполагает таблицу операций и тестов, начало которой имеет вид

целое³0	целое³0	+	*	=	>
0	0	0	0	истина	ложь
0	1	1	0	ложь	ложь
1	0	1	0	ложь	истина
0	2	2	0	ложь	ложь
1	1	2	1	истина	ложь
2	0	2	0	ложь	истина
.	.	.	.	.	.
.	.	.	.	.	.
.	.	.	.	.	.

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

Существует два вида определений типов данных: перечислением и указанием интервала, каждое из которых предполагает соответствующий способ обработки данных. Определение типа данных перечислением представляет собой запись последовательности символов; например

                     type днинедели = {Пн, Вт, Ср, Чт, Пт, Сб, Вс}

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

          type рабочиедни = {Пн...Пт}

где тип "рабочие дни" имеет элементы Пн, Вт, Ср, Чт, Пт

Описания типов данных внутреннего синтаксиса могут приписываться к описаниям данных внешнего синтаксиса. Например, в выражении

          scalar a, b : целый

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

1.7  Примеры

1.7.1  Задача1: преобразовать в обратную польскую запись заданное простое выражение. Простое выражение задается следующей грамматикой в форме Бэкуса - Наура:

<простое_выражение> ::=<терм>({+, -}< терм >)*

<терм> ::= <множитель>( * < множитель >)*

<множител>ь::= < идентификатор>|(простое - выражение)

        <идентификатор> ::= буква

Проект решения задачи на языке PDL:

sequence input :text

queue output : text

stack  S : char

scalar a, c : char, op: string

proc польская запись (alt output, fix input)

top(S) := ‘#’ [символ дна стека должен иметь самый низкий приоритет]

while input ¹ empty

do a := next(input)

     case  a  of

part ( +, -, *)

   op:= ‘ знак’

part ( (, ) )

   op:= ‘ скобки’

else op:= ‘ операнд’ esac

case op of

part( операнд )

end ( output) := a

part ( знак)[ работа со стеком]

c := top(S)

if приоритет(a)  > приоритета (с)

then top(S) := c; top(S) := a fi

else do

while

 приоритет(a)  £ приоритета (с)

do end (output) := c

   c := top(S)

od; top(S) := c ; top(S) := a

     od

fi

part( скобки)

if a= ‘(‘ then top(S) := a

        else do c := top(S)

while c ¹ ‘(‘

do end(output) := c

od

fi

esac

od

[последовательность на входе пуста, необходимо очистит стек]

while S ¹ empty do

end (output) := top(S) od

corp

1.7.2    Задача 2. Постройте распознаватель для языка

L = {xyy^R |x, y ÎI*,|y| ³ 1},где y^R реверс цепочки y.