Концепция данных в языке Паскаль

кардинальное число, т.е. мощность множества значений, которые может принимать переменная (экземпляр) этого типа; кардинальное число типа Т обычно обозначается как card(Т) и задает размер памяти, необходимой для размещения переменной;

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

Очевидно, что первое свойство позволяет однозначно представить в памяти переменные каждого определенного типа. Второе свойство обусловлено тем, что при обработке данных каждая операция или функция требуют аргументов определенного типа и возвращают результат определенного типа. Так, например, аргументом и результатом вычисления функции n! могут быть только переменные типа integer. Попытка вычисления этой функции для вещественного аргумента является ошибочной. Следовательно, виртуальная машина может использовать информацию о типах для проверки вычислимости и корректности различных конструкций языка высокого уровня. С этой точки зрения Паскаль относится к строго типизированным языкам, при разработке которого преследовались цели исключения ошибок, связанных с некорректным применением типов данных, т.е. возможностью их обнаружения как на стадии трансляции программы, так и в процессе ее выполнения.

Концепция типов данных, принятая в Стандарте языка предполагает следующее.

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

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

Очевидным методом, позволяющим описать (определить) значения простого типа, является перечисление. Так, например, в программе, связанной с обработкой нотных текстов, можно описать простой тип нота, значения которого задаются именами до, ре, ми, фа, соль, ля, си, а в программе, связанной с обработкой плоских геометрических фигур тип фигура (прямоугольник, квадрат, круг, эллипс). Кардинальное число, соответствующее типу, в этом случае можно определить прямым подсчетом. Для приведенных примеров это число соответственно равно 7 и 4. Достаточно просто решаются в этом случае и вопросы представления значений перечисляемого типа в памяти машины. Значения могут кодироваться числами, например до - 1, ре - 2, и т.д.

Однако такое описание простого типа крайне неудобно, если его кардинальное число велико. Например, попытка описать тип целых чисел в диапазоне от -32768 до +32767 (диапазон представления в шестнадцатиразрядной ячейке памяти) с помощью перечисления может привести к чисто техническим затруднениям.

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

Поэтому кроме типов, задаваемых перечислением, в средствах языка нужно иметь некоторые предварительно определенные (встроенные) или стандартные типы, для которых кардинальное число и множество допустимых операций будет заранее оговорено. Предварительное описание таких типов не требуется, так как виртуальная машина их "знает", т. е. они "встроены" в транслятор.

Если значения некоторого типа упорядочены, то такой тип называют скалярным. В Паскале предполагается, что все простые типы - скалярные и при определении перечисляемого типа порядок значений соответствует порядку их описания, что поддерживается соответствующим числовым кодированием значений для представления в памяти ЭВМ.

На основе простых типов можно строить структурированные типы произвольной сложности. Однако, для этого в средствах языка должны быть предусмотрены некоторые механизмы или правила структурирования. Разнообразие таких механизмов, присущее языку, в значительной степени определяет его изобразительную мощность. В частности, средства языка Паскаль позволяют строить следующие структуры данных: регулярную (массив, array), комбинированную (запись, record), множество (set) и последовательность (file). Более сложные структуры в Паскале не описываются как статические типы, т.е. типы с известным кардинальным числом, а "динамически" создаются с помощью специально предназначенных для этого средств во время выполнения программы, причем их размер и вид могут изменяться. К таким структурам относятся списки, кольца, деревья и, в общем случае, произвольные конечные графы.

Ранее отмечалось, что с типом данных должно быть связано некоторое фиксированное множество операций. Это множество должно быть заранее задано, если язык не обеспечивает возможность их явной спецификации. В языке Паскаль такими операциями являются сравнение и присваивание, т. е. "проверка равенства" (или порядка в случае упорядоченных типов) и "установка равенства". Принципиальное различие этих двух операций выражается четким различием их обозначений в тексте программ: проверка равенства обозначается как x=y (при чтении здесь всегда присутствует интонация вопроса). Установка равенства (присваивание) обозначается как x := y.

Эти основные операции определены фактически для всех типов данных. Однако для данных, которые имеют большой объем и сложную структуру, выполнение этих операций может сопровождаться сложными вычислениями.

Кроме проверки равенства и присваивания имеется еще один класс основных операций - так называемых операций преобразования, которые "скрыты" от пользователя. Эти операции отображают одни типы данных в другие и особенно важны для структурированных типов.

Под преобразованием здесь понимается представление данных, принадлежащих определенному типу, в памяти ЭВМ и "возврат" от этого представления к виду, предусмотренному спецификацией типа или, иными словами, выделение в машинном представлении данных отдельных компонент.

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

Описание типов данных осуществляется в разделе типов. Раздел описания типов данных определяется следующими правилами грамматики:

<раздел типов> ::= type <список описаний типов>

<список описаний типов> ::= <описание типа>

<список описаний типов>;

<описание типа>

<описание типа> ::= <имя типа>=<тип>

<имя типа> ::= <идентификатор>

<тип> ::= <простой тип>

<простой структурный тип>

<ссылочный тип>

Простые типы данных

Конструкция, задающая альтернативы для простого типа выглядит так:

<простой тип> ::= <перечисляемый тип>

<предопределенный тип>

<ограниченный тип>

Иными словами, данные простого типа в языке Паскаль могут быть описаны как данные перечисляемого типа (иногда его называют собственным типом пользователя), предопределенного или стандартного типа (этот тип не нужно описывать в разделе типов) и ограниченного типа (отрезка типа). При этом следует помнить, что все эти типы являются скалярными, т. е. их значения определенным образом упорядочены.

Перечисляемый тип

При формулировке многих алгоритмов в виде текста программ целые числа используются в том случае, когда их собственно числовое значение несущественно и число указывает только на выбор значения из небольшого множества возможных вариантов. Так, например дни недели можно закодировать таким образом: понедельник - 1, вторник - 2, и т.д. Однако над этими числами нельзя выполнять никаких операций, кроме проверки на равенство или присваивания. Попытка сложить эти числа приведет к бессмыслице. Для дальнейшего использования в программе таких данных желательно определить их тип как перечисляемый. Это позволит:

сделать текст программы удобным для чтения и избавить программиста от необходимости самому кодировать значения;

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

при условии, что кардинальное число типа меньше или равно 256, разместить эти данные в одном байте, т.е. экономить память.

Конструкция, определяющая правило описания перечисляемого типа имеет вид:

<перечисляемый тип> ::= (<список значений>)

<список значений> ::= <значение>

<список значений>,<значение>

<значение> ::= <идентификатор>

<целое >

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

Пример раздела типов с такими описаниями:

type

Day = ( mo, tu, we, th, fr, sa, su ); {card(day)=7}

Notation= ( do_, re, mi, fa, sol, la, si ); {card(notation)=7}

Тогда, при описании переменных MyDday и MyNota в разделе переменных:

var

MyDay : Day ;

MyNota : Notation;

можно, например, использовать такие операторы присваивания:

MyDay := sa;

MyNota := fa;

Поскольку предопределенный тип является скалярным, для него полезно определить функции, которые возвращают предшествующее и последующее значения для своего аргумента. В языке Паскаль такими функциями являются соответственно Pred(x) и Succ(x). Так, в результате выполнения оператора MyDay:=Pred(sa) переменной MyDay будет присвоено значение fr, а выполнение оператора MyNota :=Succ(do_) присвоит переменной MyNota значение re. Очевидно, что эти функции не определены на соответственно "первом" и "последнем" значениях, т.е. обращения вида Pred(do_) или Succ(si) вызовут сообщение об ошибке. Кроме того, существенным недостатком перечисляемого типа является отсутствие поддержки вывода его значений в подавляющем большинстве существующих систем программирования, что заставляет использовать для вывода, например, такой фрагмент текста программы:

. . . if MyDay = mo then Write (`mo');

if MyDay = tu then Write (`tu');

. . .

Стандартные простые типы

Стандартные или предопределенные простые типы - это типы, которые "встроены" в большинство современных языков программирования. К ним обычно относят данные, множеством значений которых являются целые и вещественные числа, логические значения и некоторое множество символов. Предварительное определение первых трех типов связано, в первую очередь, с расширением множества допустимых над ними операций.

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

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

Конструкцию <предопределенный тип> для языка Паскаль задает следующее правило.

<предопределенный тип> ::= Integer Rreal Boolean Char

Целый тип (Integer). Значения типа Integer принадлежат подмножеству целых чисел, размер которого может быть различным для различных ЭВМ. Однако, в большинстве случаев, его кардинальное число соответствует диапазону представления чисел с фиксированной точкой в 16-разрядной ячейке (двум байтам), т. е. целые числа представлены в интервале [-32768,+32767]. Максимальному значению типа соответствует предопределенная константа MaxInt.

Над переменными этого типа, кроме операций проверки на равенство и присваивания, допустимы арифметические операции: сложение (+), вычитание (-), умножение (*) и деление(div). Последнее дает целый результат, опуская возможный остаток так, что для любых m и n m-n < (m div n)* n m. Кроме того к целому типу применима операция взятия остатка mod, которая определяется с помощью деления из уравнения (m div n)*n +(m mod n)= m. Таким образом, m div n - это целое от деления m на n, а m mod n - остаток от деления.

Предполагается, что все действия с данными этого типа:

являются точными (результат является целым числом) и выполняются по обычным правилам арифметики;

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

Вещественный тип (Real). Строго говоря, вещественный тип не может иметь кардинального числа, поскольку любой отрезок числовой оси содержит бесконечное количество вещественных чисел. Но при этом нужно учесть, что вещественные числа представляются в ячейке с определенным количеством разрядов в нормальной форме (форме с плавающей точкой). Такая форма имеет диапазон представления и, следовательно, можно говорить о кардинальном числе типа Real, которое зависит от конкретной реализации. Таким образом, типу Real соответствует подмножество вещественных чисел.

Несмотря на то, что вещественный тип относится к скалярным, из-за ошибок округления это верно не в любом контексте. Так, переменные типа real нельзя использовать в качестве параметра цикла for, базового типа множества и при индексации массивов. Кроме того, на этом типе не определены функции pred и succ.

Над переменными вещественного типа можно выполнять те же арифметические операции, что и над переменными целого типа. Поэтому целый и вещественный типы иногда называют арифметическими. Однако эти операции имеют некоторые отличия. В то время как арифметические действия с целыми числами всегда дают точный результат, при тех же действиях со значениями типа real допускается погрешность в пределах ошибок округления. Последнее связано с тем, что форма их представления допускает возможность округления результата. Кроме того, деление вещественных чисел, дающее вещественный результат обозначается наклонной чертой (/), а операция mod для вещественного типа не определена. Если в арифметической операции участвуют операнды целого и вещественного типов, что допускается правилами языка, то результат должен быть обязательно вещественного типа. Более подробно эта тема обсуждается в разделе, посвященном проблеме совместимости типов.

Булевский тип (Boolean). Значения типа Boolean - это логические истинностные значения false (ложь) и true (истина). Таким образом, кардинальное число типа равно двум. Тип упорядочен так, что false соответствует Pred(true).

Над переменными типа Boolean допустимы логические операции, возвращающие булевское значение. К таким операциям относятся отрицание, конъюнкция и дизъюнкция. При вычислении логических выражений старшинство операций соответствует порядку их перечисления. Логическое отрицание обозначается символом not, конъюнкция - and и дизъюнкция - or. Сущность этих операций поясняет таблица 3.1.

Таблица 3.1. Логические операции

Булевское значение дает и любая из операций отношения, т.е. равно(=), не равно(<>), меньше(<), меньше равно(<=), больше(>), больше равно(>=). Следовательно, результат сравнения можно присваивать булевской переменной или использовать в качестве операнда в логических (булевских) выражениях. Например, во фрагменте текста программы:

var

P,Q : Boolean;

X,Y,Z : Integer;

begin

X :=3;

Y := 5;

Z := 8;

P :=X=Y;

Q:=(X<Y) and (Y<=Z);

. . .

в результате выполнения двух последних операторов переменной P будет присвоено значение false, а переменной Q - значение true.

Символьный тип

Значениями символьного типа (Char) являются элементы конечного и упорядоченного множества символов. К сожалению, и сегодня не существует общего стандартного множества символов, принятого для всех виртуальных машин. Наиболее часто в качестве такого множества используется множество символов, определенное Международной организацией по стандартизации (ISO), и особенно его американская версия ASCII (американский стандартный код для обмена информацией). Таблица символов ASCII (см. приложения) включает 95 печатаемых и 33 управляющих символа, которые используются в основном для передачи данных и управления печатью.

При описании алгоритмов, обрабатывающих символьную информацию (значения типа char), можно независимо от машины определить некоторые свойства множества символов, делающие его связным.

тип содержит 26 латинских букв, 10 арабских цифр и некоторое количество других графических символов, например, знаков препинания;

подмножества букв и цифр упорядочены и связны, т.е.

(`A' x) and (x `Z') x - буква,

(`0' x) and (x `9') x - цифра;

тип Char содержит не печатаемый символ (пробел), который может использоваться как разделитель.

Символ, заключенный в апострофы (одиночные кавычки), означает константу символьнoго типа (понятие константы можно определить как конкретное значение, принадлежащее типу, в то время как переменная может принимать любое из таких значений). Например: `.' `A' `4' `Z' (для представления самого апострофа его записывают дважды, т.е. `"').

Для прямого и обратного отображения множества символов в подмножество целых чисел, которые называют порядковыми номерами символов, определены две стандартные функции преобразования Ord(X) и Chr(I): Ord(X) возвращает порядковый номер символа X в упорядоченном множестве символов, а Chr(I) - символьное значение с порядковым номером i. Очевидно, что функции обратны по отношению друг к другу, т. е. Chr(Ord(X))=X и Ord(Chr(I))=I.

Для аргументов символьного типа стандартные функции pred и succ могут быть определены так: Pred(X)=Chr(Ord(X)-1) и Succ(X)= Chr(Ord(X)+1).

Предшествующий или последующий символ по отношению к заданному зависит от используемого множества символов. Поэтому результат функции может быть не определен, если такого символа в множестве нет.

Ограниченный тип (отрезок типа). Часто бывает так, что переменная должна принимать значение некоторого базового типа только в определенном интервале. Это можно выразить, определив тип переменной в соответствии с правилами:

<ограниченный тип> ::= <минимальное значение> .

<максимальное значение>

<минимальное значение> ::= <константа базового типа>

<максимальное значение> ::= <константа базового типа>

На семантическом уровне константа базового типа определяется следующим образом. Это значение простого типа, точнее перечисляемого типа, типа integer или char. Действительно, тип boolean слишком "короткий" для определения отрезка, а для типа real не определены функции pred и succ, т.е. нельзя заранее установить, какое количество значений принадлежит отрезку. При этом базовый тип, если он является перечисляемым, должен быть обязательно определен.

Операции, допустимые над переменными ограниченного типа соответствуют операциям над переменными базового типа. Ограниченный тип данных, присущий далеко не всем языкам высокого уровня, является крайне полезным типом, так как позволяет "застраховать" пользователя от неочевидных ошибок времени выполнения программы и (или) ошибок в данных. Например, во фрагменте программы:

type

Day=(mo,tu,we,th,fr,su,sa);

Year=1900 .. 2000;

WorkDay=mo ..fr;

var

MyYear : Year;

MyDay : WorkDay;

begin

MyYear :=1995;

MyDay :=su;

. . .

первый оператор правильный (год принадлежит типу year), а второй вызовет сообщение об ошибке (значение su не принадлежит типу workday).

Простой тип (расширение конструкций) По отношению к простым типам в Borland Pascal вводится понятие порядковые типы. Последние представляют собой подмножество простых типов. Все простые типы, отличные от вещественных типов, считаются порядковыми и характеризуются следующим. Все возможные значения данного порядкового типа представляют собой упорядоченное множество, и каждое возможное значение связано с порядковым номером, который представляет собой целочисленное значение. За исключением значений целочисленного типа, первое значение любого порядкового типа имеет порядковый номер 0, следующее значение имеет порядковый номер 1 и так далее для каждого значения в этом порядковом типе. Порядковым номером значения целочисленного типа является само это значение. В любом порядковом типе каждому значению, кроме первого, предшествует другое значение, и после каждого значения, кроме последнего, следует другое значение в соответствии с упорядоченностью типа.

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

К любому значению порядкового типа можно применить стандартную функцию Pred, возвращающую предшествующее этому значению значение. Если эта функция применяется к первому значению в этом порядковом типе, то выдается сообщение об ошибке.

К любому значению порядкового типа можно применить стандартную функцию Succ, возвращающую следующее за этим значением значение. Если эта функция применяется к последнему значению в этом порядковом типе, то выдается сообщение об ошибке.

К любому значению порядкового типа и к ссылке на переменную порядкового типа (см раздел 7) можно применить стандартную функцию Low, возвращающую наименьшее значение в диапазоне данного порядкового типа.

К любому значению порядкового типа и к ссылке на переменную порядкового типа можно применить стандартную функцию High, возвращающую наибольшее значение в диапазоне данного порядкового типа.

В этом случае представляется возможным определить базовый тип для отрезка типа как порядковый тип. Кроме того версии Borland Pascal допускают расширенный перечень стандартных типов. Соответствующая этому расширению конструкция может быть определена следующим образом:

<предопределенный тип> ::= <подмножество целых типов >

<подмножество вещественных типов >

<подмножество булевских типов >

char

Подмножество целых типов включает типы Integer (целое) ShortInt (короткое целое), LongInt (длинное целое), Byte (длиной в байт) и Word (длиной в слово). Тип Integer в этом перечне полностью соответствует Стандарту. Остальные типы характеризуются только другим кардинальным числом (диапазон представления для них иллюстрирует таблица 3.2).

Таблица 3.2. Диапазон представления целых типов

В соответствии с таблицей типы Byte и Word используются для представления только положительных чисел. Операции, допустимые над переменными этих типов, ничем не отличаются от операций, допустимых над типом Integer. Введение дополнительных типов позволяет расширить область вычислений с использованием точной "целочисленной арифметики", экономно расходуя при этом ресурсы памяти, и, при необходимости, обеспечивает совместимость с другими языками по представлению данных.

Подмножество вещественных типов включает пять видов вещественных типов: соответствующий Стандарту вещественный (Real), с одинарной точностью (Single), с двойной точностью (Double), с повышенной точностью (Extended) и сложный (Comp). Действия над типами с одинарной, двойной и повышенной точностью, а также над сложным типом могут выполняться только при наличии сопроцессора 8087.

Borland Pascal обеспечивает программную и аппаратную поддержку выполнения операций над числами с плавающей точкой. Выбор типа поддержки осуществляется с помощью директивы компилятора $N, которая устанавливается по умолчанию, как $N-. Из-за возможного снижения скорости выполнения программы и увеличения размера машинного кода в этом состоянии допускаются только действия над переменными типа real. Любая попытка протранслировать операторы, выполняющие действия над переменными, принадлежащими типам с одинарной, двойной и повышенной точностью, а также над сложными типами, вызовет сообщение об ошибке. Директива $N+ позволяет использовать все пять вещественных типов при наличии сопроцессора 8087. Для "подключения" программы-эмулятора сопроцессора 80x87 можно использовать директиву компилятора $E, если система программирования используется на платформе DOS и сопроцессор 80х87 отсутствует. Платформой Windows директива $E в этом случае игнорируется. Более подробно с настройкой транслятора можно ознакомиться в разделе 8. В противном случае либо не следует отклоняться от Стандарта, либо не следует "обижаться" на ошибки.

Таблица 3.3 Диапазон представления вещественных типов

Сложный тип содержит только целочисленные значения в диапазоне от -2 ⁶³⁺¹ до 2 ^63-1, что приблизительно равно -9.210 ¹⁸ и 9.210 ¹⁸.

Подмножество булевских типов содержит тип Boolean, определенный Стандартом, а также типы ByteBool (булевский, размером в один байт), WordBool (булевский - 2 байта), LongBool ("длинный" булевский тип - 4 байта).

Типы ByteBool, WordBool и LongBool введены в язык для того, чтобы обеспечить совместимость с другими языками, а также платформой Windows. Как уже упоминалось, переменные типа boolean представлены в машине порядковыми значениями 0 (false) и 1 (true). Для переменных типа ByteBool, WordBool и LongBool значению true могжет соответствовать любое нену-левое значение содержимого ячейки памяти, в том числе и 1.

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

type

Color = (red, green, blue);

Scale = (X - Y) * 2 .. (X + Y) * 2;

Согласно синтаксису Стандарта, если определение типа начинается с круглой скобки, то это перечислимый тип (такой как Color). Однако Scale предназначен для определения отрезка типа. Неоднозначность можно устранить, переупорядочив первое выражение, например:

type

Scale = 2 * (X - Y) .. (X + Y);

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

Уточнение конструкций

Переменные и константы. Под переменной всегда понимается экземпляр типа, в том числе и составного (см. ниже), которому можно присвоить значение. Понятие константы используется двояко и обычно определяется контекстом. Так под константой иногда понимают конкретное значение, принадлежащее некоторому типу данных, называя, например, число 25 константой целого типа (уместнее было бы называть его просто значением). Во втором случае под константой понимают то, что и следует понимать в соответствии с синтаксисом языка, т. е. некоторые данные, описанные в соответствующем разделе программы и не изменяющие своего значения в процессе ее выполнения. Таким разделом является раздел констант:

<раздел констант> ::= const<список описаний констант>

<список описаний констант> ::=<описание константы>

<список описаний констант>;

<описание константы>

<описание константы> ::=< имя>=<константа>

<константа> ::=<число><имя константы><строка>

Эту конструкцию, по-видимому, можно отнести к немногим "спорно удачным" конструкциям языка. Действительно, зачем нужно описывать те величины , которые не изменяют своего значения, в отдельном разделе, если они могут быть описаны как обычные переменные и проинициализированы в начале раздела операторов (в крайнем случае их можно снабдить соответствующим комментарием). Кроме того, здесь возникает семантическая неоднозначность, которая в Сообщении не поясняется. Эта неоднозначность заключается в отсутствии ответа на вопрос, к какому типу может принадлежать сопоставленное с константой значение. Однако, при отказе от описания констант теряется возможность контроля попытки случайного изменения их значений, а это достаточно сильный аргумент в пользу применения соответствующего раздела.

Расширенный синтаксис языка Borland Pascal предусматривает совершенно новый вид константы - константу-переменную (у математика это вызовет естественное раздражение. Синтаксис константы переменной определяется следующим правилом:

< константа-переменная> ::=< имя>:<тип>=<константа>

Условие. В предшествующих разделах конструкция <условие> определялась следующим образом:

<условие> :: = <выражение>

<выражение><операция отношения> <выражение>

Определение булевского и арифметических типов позволяет уточнить как эту конструкцию так и конструкцию <выражение> в целом, выделив <арифметическое выражение> и <логическое выражение> (в Сообщении такое разделение не предусмотрено) :

<арифметическое выражение> ::= <терм >

+<терм>

-<терм>

<арифметическое выражение>

<аддитивная операция>

<терм>

<терм> ::= <операнд>

<терм>

<мультипликативная операция>

<операнд>

<операнд> ::= <переменная>

<константа без знака>

(<арифметическое выражение>)

<переменная> ::= <имя переменной>

<константа без знака> ::= <число без знака>

<аддитивная операция> ::= +-

<мультипликативная операция> ::= /divmod

Особенностью правила теперь является то, что результатом вычисления выражения может быть только значение типа Integer или Real, поскольку из правил, определяющих мультипликативную и аддитивную операцию, исключены логические операции not, or и and.

<логическое выражение> ::= <логический терм>

not <логический терм>

<логическое выражение> or

<логический терм>

<логический терм> ::= <логический множитель>

<логический терм> and

<логический множитель>

<логический множитель> ::= <логическая переменная>

(<логическое выражение>)

<логическая переменная> ::= <имя переменной>

(<арифметическое выражение>

<операция отношения>

<арифметическое выражение>)

Теперь выражение и условие можно определить как

<выражение> ::= <арифметическое выражение>

<логическое выражение>

<условие> :: = <логическое выражение>

К сожалению, уточненные правила требуют комментария, поскольку при определении конструкций обоих выражений не достаточно строго сформулированы правила <переменная> и <логическая переменная>. Первое из них будет еще раз в дальнейшем уточняться. Относительно второго следует заметить, что средствами БНФ практически невозможно разделить понятия переменных различного типа. Однако при разработке трансляторов такая возможность все же существует. Контроль за принадлежностью имен переменных к определенному типу может осуществляться на основании их описания в разделе переменных, а тип выражения (но не во всех случаях) можно определить по множеству используемых операций.

Константы Являясь расширением стандартного Паскаля, Borland Pascal позволяет использовать выражения-константы. Выражение-константа представляет собой выражение, которое может вычисляться компилятором без необходимости выполнения программы. Приведем примеры выражений-констант:

100

'A'

256 - 1

(2.5 + 1) / (2.5 - 1)

'Borland' + '' + 'Pascal'

Chr(32)

Ord('Z') - Ord('A') + 1

Простейший случай выражения-константы представляет собой простая константа, например 100 или 'A'. В стандартном Паскале допускается использовать только простые константы. В Borland Pascal разрешено использование выражений-констант.

Поскольку компилятор должен иметь возможность полностью вычислить выражение-константу во время компиляции, в качестве выражений-констант не допускается использовать следующие конструкции:

- вызовы функций (кроме тех, которые отмечены далее);

- оператор получения адреса @

За исключением этих ограничений для выражений-констант соблюдаются те же синтаксические правила, что и для обычных выражений (описанных в Главе 6 "Выражения").

В выражениях-константах допускается использовать следующие стандартные функции:

Abs, Chr, Hi, High, Length, Lo, Low, Odd, Ord, Pred, Ptr, Round, SizeOf, Succ, Swap, Trunc.

Приведем некоторые примеры использования выражений-констант в описаниях констант:

const Min = 0;

Max = 100;

Center = (Max - Min) div 2;

Beta = Chr(255);

NumChars = Ord('Z') - Ord('A') + 1;

Message = 'Out of memory';

ErrStr = 'Error:' + Message + '.';

ErrPos = 80 - Length(Error) div 2;

ErrAttr = Blink + Red * 16 + White;

Ln10 = 2.302585092994095684;

Ln10R = 1 / Ln10;

Numeric = ['0'..'9'];

Alpha = ['A'..'Z','a'..'z'];

AlphaNum = Alpha + Numeric;

Еще в большей степени оспариваемо расширение этой синтаксической конструкции в системах программирования Borland Pascal, где

<описание константы> ::=< имя>=<константа>

< имя>:< тип>=<константа>

Расширение представлено второй альтернативой в конструкции <описание константы>. В этом случае константа, описанная, например, как B: Integer=23 , называется типизированной константой. Типизированные константы, по сути, являются переменными, которым в разделе констант присвоено начальное значение, т. е. они проинициализированы в разделе констант (зачем?). Здесь же уместно заметить, что, например, у математика понятие "переменная константа" может вызвать раздражение.

Простые структурированные типы

Обобщенные методы структурирования данных являются предметом теории структур данных. Прикладные аспекты этой теории распространяются на ряд предметных областей и, в том числе, на исследование и создание соответствующих средств, включаемых в языки программирования. Необходимость структурирования данных очевидна, поскольку в окружающем нас мире только небольшое количество объектов может быть описано с помощью одной характеристики или, что то же самое, отображаться данными простого типа. Например, человеку свойственны имя, место жительства, возраст, рост, вес и т.п., причем все эти характеристики должны быть связаны вместе, т.е. отражены в некоторой структуре данных.

В теории структур данных для этих целей чаще всего используется понятие массив, которое определяется как абстракция некоторого объекта, отражающая совокупность принимаемых во внимание свойств. Для представления этих свойств используется запись. Запись состоит из полей, каждое из которых характеризует отдельное свойство, а значения этих полей отражают конкретную меру свойств. Массив является статической структурой данных, которая не видоизменяется в процессе ее обработки.

Различают однородные и неоднородные массивы. Массив называется однородным в том случае, когда все поля в записи однотипны. В противном случае массив считается неоднородным. Очевидно, что неоднородный массив всегда можно сделать однородным при условии соответствующего кодирования значений свойств. Подобные преобразования сокращают множество средств, необходимых для структуривания данных, но могут потребовать существенного увеличения объема хранилища информации.

Поэтому в развитых языках программирования существуют средства, позволяющие отображать как однородные, так и неоднородные массивы. В частности, язык Паскаль располагает такими средствами и, кроме того позволяет организовать структуру данных типа "множество".

Простой структурированный тип в языке Паскаль задается правилом:

<простой структурированный тип> ::= < тип array >

< тип record >

< тип set >

< тип file >

Используя буквальный перевод английских терминов, в литературе эти типы часто называют типом массива, записи, множества и файла соответственно. Три последних термина не приводят к разночтению. Первый (тип массива) не соответствует определениям, которые были приведены выше. Поэтому, если не будет примечаний, в дальнейшем под массивом будет пониматься структура данных или переменная типа array. В качестве синонима можно использовать другой (применяемый в линейной алгебре) термин - вектор.

Тип array

Тип array - это регулярная структура, предназначенная для представления однородных информационных объектов. Ее компоненты имеют один и тот же тип, который называют базовым. Кроме того, это структура с так называемым случайным или прямым доступом: все ее компоненты могут выбираться произвольно и одинаково доступны. Для обозначения отдельной компоненты в этом случае нужно указать только ее порядковый номер в структуре - индекс. Таким образом, для описания типа необходимо задать тип индексов, что определит количество компонент, и базовый тип, т.е. тип компонент:

<тип array> ::= array [<тип индексов>] of <тип компонент>

<тип компонент> ::= <тип>

Согласно правилу, тип индексов задается в квадратных скобках. Естественно, что типом индексов может быть только скалярный тип, точнее перечисляемый тип или отрезок типа, поскольку другие разновидности скалярного типа не позволят однозначно задать количество компонент. Типом компонент может быть любой тип, в том числе и простой структурированный, за исключением типа файла. Примером описания типа array в разделе типов будет:

type

Index1 = 1 .. 80;

Iindex2 = (jan, feb, mar. apr, may, jun, jul, aug, sep, oct, nov, dec);

Vector1= array [index1] of Real;

Vector2= array [index2] of Char;

Vector3= array [Index1] of Vector2;

С именем Vector1 связано описание структурированного типа array, тип индексов для которого задан отрезком типа Index1 = 1 .. 80, т. е. вектор состоит из 80-ти компонент. Тип компонент в свою очередь определен как real. У вектора Vector2 двенадцать компонент, которые индексируются значениями, определенными перечисляемым типом, а тип компонент - символьный. В последней строке описан тип Vector3, компоненты которого определены как компоненты структурированного типа Vector2.

Если предположить, что существует описание type Т= array [I] of Т₀ , где I является типом индексов (I=1 .. n), Т₀ - типом компонент и в разделе переменных описана переменная W : Т типа Т, то составное значение W с компонентами w₁, ..., w_n может задаваться с помощью конструктора. Конструктор распределит память под переменную-вектор W и позволит в дальнейшем присваивать ее как единое целое, т. е. присваивать значение одного экземпляра типа (переменной-вектора) другому.

Последнее допустимо не во всех версиях систем программирования. В таких случаях говорят, что конструктор вырожден.

Для распределения памяти под вектор конструктор свяжет с именем переменной некоторый адрес w_o и зарезервирует необходимое для размещения всех компонент количество ячеек памяти с учетом размерности компонент. Размещение структуры типа array в памяти ЭВМ иллюстрируется рисунком (Рис.3.1).

Операция, которая позволяет обращаться к отдельным компонентам вектора, это селектор. Для этого вместе с именем соответствующей переменной в квадратных скобках задается порядковый номер (индекс) компоненты, например, W[I]. Селектор вычисляет адрес этой компоненты с помощью сложения с w_o значения индекса i, обеспечивая тем самым прямой доступ к самой компоненте.

Рис.3.1. Размещение вектора w в памяти ЭВМ

Синтаксис языка допускает и другую форму описания типа:

type

Vector1= array [1 .. 80] of Real;

Vector2=array[(jan,feb,mar,apr,may,jun,jul,aug,sep,oct,nov,dec)] of Char;

Vector3=array[1 .. 80] of

array[(jan,feb,mar,apr,may,jun,jul,aug,sep,oct,nov,dec)] of Char;

Такая форма возможна потому, что согласно правилу вектор должен быть определен с помощью типа индексов и типа компонент, а тип и в первом и во втором случае может быть задан либо именем типа, либо его непосредственным описанием. В общем случае такой формы описания следует избегать по двум причинам. Во-первых текст программы тяжелее читать. И, во вторых, что особенно важно, со структурой данных нужно "работать", т.е. обращаться к ее компонентам с помощью селектора. В качестве селектора необходимо использовать переменную, тип которой должен быть определен так же, как тип индексов структуры array. В первом случае такой тип уже определен (имеет имя), а во втором его придется повторять при описании переменной-селектора.

Еще "хуже" описывать структурированный тип непосредственно в разделе переменных, например:

W1 : array [1 .. 80] of real;

W2 : array [(jan, feb, mar, apr, may, jun, jul, aug, sep, oct, nov, dec)] of char;

W3 : array [1 .. 80] of array [(jan, feb, mar, apr, may, jun, jul,

aug, sep,oct, nov, dec)] of char;

При таком описании тип также оказывается не "поименованым", а это в некоторых случаях может нарушить соглашения об отношениях между типами. Обычно составной тип данных воспринимается двойственно. С одной стороны это переменная, например, вектор, если это структура типа array. С другой стороны составной тип рассматривается как совокупность отдельных компонент.

В первом случае можно говорить о кардинальном числе составного типа, которое равно произведению кардинальных чисел всех его компонент. Для структуры array кардинальное число равно (card(T₀))ⁿ, где n=card(I). Отсюда следует, что изменение значения одной из компонент приводит к новому значению всей переменной. Определение кардинального числа составного типа используется при распределении памяти под соответствующие переменные, а с позиций пользователя необходимо для оценки емкостной сложности алгоритмов.

Во втором случае следует оценить возможности обращения к отдельным компонентам структуры. То, что индексы вектора, т.е. "имена" его компонент, могут быть отрезком типа integer, позволяет применять к ним операции целочисленной арифметики, т. е. вычислять значения индексов. Иными словами, вместо индексной константы в селекторе можно использовать индексное выражение. Например, обращение к компоненте W[(A+B)*A div 2] при a равном 3 и b равном 5 равносильно обращению W[12]. Здесь особое значение приобретает контроль типа индексов, поскольку такой компоненты в векторе может и не быть, а это ошибка времени выполнения программы.

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

Формирование вектора и вывод значений его компонент на экран в этом случае могут быть описаны следующим фрагментом программы:

type

Index = 1 .. 100;

Vector= array [index] of Real;

var

I,N : Index;

W : Vector;

begin

Write (`Введите размерность вектора N= '); { N 100 }

Readln (N);

Write (`Введите ',N,' компонент вектора');

for I :=1 to N do

Read (W[I]);

. . . {обработка вектора}

WriteLn (`Результирующий вектор имеет вид');

for I :=1 to N do

Write (W[I])

end.

С каждой структурой данных обычно связан некоторый типичный для нее набор операций или, точнее, действий, связанных с ее обработкой . По отношению к структуре типа array это просмотр массива, поиск компонент с заданными значениями и модификация структуры, т.е. вставка дополнительных и удаление "лишних" компонент. Поиск компонент с заданными значениями или определение индекса такой компоненты в массивах большой размерности мало эффективен, если массив предварительно не упорядочен, Например, поиск слова в обычном, но не упорядоченном по алфавиту словаре, который состоит всего из пяти-шести тысяч слов может продлиться достаточно долго. Процедура упорядочивания структур данных по некоторому признаку или ключу называется сортировкой. Типичные задачи, связанные с сортировкой структур данных более подробно рассматриваются в разделе 5.

Примеры программ, иллюстрирующих просмотр с целью поиска компонент с заданным значением в структурах данных типа array, приведены ниже. Первая из них реализует алгоритм поиска наименьшего числа в неупорядоченной последовательности вещественных чисел.

program Prim3_1;

type

Index = 1 .. 10;

Vector= array [Index] of Real;

var

I,K,N : Index;

Buf : Real;

W : Vector;

begin

Write (`Введите размерность вектора N= ');

ReadLn (n);

Write (`Введите ',N,' компонент вектора');

for I :=1 to N do

Read (W[I]);

WriteLn;

K := 1;

Buf :=W[1];

for I :=2 to N do

if W[I] < Buf then

begin

Buf := W[I];

K := I

end;

WriteLn ('минимальное значение в последовательности равно `,W[K])

end. {Prim3_1}

Цель следующей программы - определить наименьший индекс I компоненты вектора со значением A.

program Prim3_2;

type

Index = 1 .. 10;

Vector = array [Index] of Real;

var

I,N : Index;

A : Real;

W : Vector;

begin

Write (`Введите размерность вектора N= ');

ReaDln (n);

Write (`Введите ',N,' компонент вектора');

for I :=1 to N do

Read (W[I]);

WriteLn;

Write (`Введите значение искомой компоненты A= ');

ReadLn (A);

I := 0;

repeat

I := I+1

until ((W[I]=A) or (I=N));

if W[I] = A then

WriteLn ('значение ', A ,' находится в `, I ,'-ой компоненте')

else

WriteLn ('в векторе нет такой компоненты`)

end. {Prim3_2}

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

program Prim3_3;

type

Index= 1 .. 11;

Vector= array [Index] of Real;

var

I,N : iIndex;

A : Real;

W : Vector;

begin

Write (`Введите размерность вектора N= ');

ReadLn (N);

WriteLn (`Введите ',n,' компонент вектора');

for I :=1 to N do

Read (W[I]);

WriteLn;

Write (`Введите значение искомой компоненты A= ');

ReadLn (A);

I := 0;

W [N+1] := A;

repeat

I := I+1

until w[i]=a;

if I <> N+1 then

WriteLn ('значение ', A ,' находится в `, I ,'-ой компоненте')

else

WriteLn ('в векторе нет такой компоненты`)