4794

Концепция данных в программировании

Лекция

Информатика, кибернетика и программирование

Концепция данных Элементарные конструкции языка программирования: алфавит, данные, имена. Типы данных. Вычислительные структуры (многосортные алгебры) как формальные средства описания данных. Носители и сигнатуры, формы записи. Термы. Интерпретации ...

Русский

2012-11-27

80.5 KB

24 чел.

Концепция данных

Элементарные конструкции языка программирования: алфавит, данные, имена. Типы данных. Вычислительные структуры (многосортные алгебры) как формальные средства описания данных. Носители и сигнатуры, формы записи. Термы. Интерпретации как семантика вычислительных структур.

Алфавит языка Паскаль

В языке используются:

1.Латинские буквы (большие и маленькие), знак подчеркивания ’_’

2.Цифры 0,...,9

3.Математические символы +, -, *, /, <, >, =

4.Разделители: ; , “ ‘ . : ^

5.Скобки ( ) [ ] { }

6.Другие символы (используемые для печати): буквы национальных алфавитов, !, ?, \, |, ...

В различных версиях могут использоваться различные наборы символов. Сейчас широко используется набор символов кода ASCII (American Standard Code for Information Interchange). Этот код предусматривает расширения для национальных алфавитов, символов псевдографики, которые могут меняться от версии к версии.

Данные

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

В языке Паскаль представляются числа и строки.

Целые числа записываются в десятичной системе счисления: 137, -56, +26 .

Вещественные числа используют также десятичную нотацию, причем целая часть отделяется от дробной не запятой, а точкой. Для обозначения порядка числа в качестве разделителя используется буква Е. Например, -5.1Е14 означает -5.1, умноженное на 10 в степени 14 (-5,1*1014). Степени чисел могут быть и отрицательными: 6.74Е-8, -56.89Е-10.

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

‘ строка из символов ‘, ‘ апостроф ‘’ в слове ‘

Имена

Именем в языке Паскаль называется последовательность (латинских) букв, знака подчеркивания ‘_’ и цифр, начинающаяся с буквы либо со знака подчеркивания. Хотя имена могут быть сколь угодно длинными, в реализации количество значащих символов в имени может быть ограничено. В стандарте языка имена различаются по первым восьми символам. Это означает, что имена VeryLongNumber, VeryLongCardinal в стандарте языка обозначают (именуют) один и тот же объект.  Кроме того, язык не различает больших и маленьких букв. Поэтому имена Sin, SIN, sin неразличимы.

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

Pi, Сonstant - имена констант; x, y1, y2, Counter - имена переменных;

Integral, MaxMin - имена процедур; Man, Color, WeekDay - имена типов;

Некоторые имена предопределены заранее. Например:

Sin - имя для обозначения функции синус;  Read - имя для обозначения процедуры чтения;

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

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

Стандартные простые типы данных языка Паскаль

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

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

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

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

Integer,  Real, Char,  Boolean

Простые типы, определяемые программистом 

Перечисляемый тип, Скалярный тип

Структурные типы данных  

Регулярный тип,  комбинированный тип, множественный тип,  файловый тип, ссылочный тип

В языке Паскаль определены 4 стандартных простых типа данных:

Integer   (целый);

Real   (вещественный);

Char   (символьный).

Boolean  (логический);

Для полного описания каждого типа данных, используемых в языке программирования, необходимо знать:

  1.  множество допустимых значений для данных этого типа;
  2.  допустимые операции над данными этого типа;
  3.  функции, определенные на данных этого типа или принимающие значения в этом типе;
  4.  допустимые отношения на данных этого типа.

Тип данных Integer

Значениями целого типа являются элементы зависящего от реализации подмножества (отрезка) целых чисел. Это означает, что существует стандартная константа с именем MaxInt, такая что для любого данного X типа Integer

-MaxInt < X < MaxInt

Наиболее распространенное для 16 разрядных ПЭВМ значение

MaxInt = 215 - 1 = 32767.

Операции:

* - умножение; div -  целочисленное деление; mod - остаток от целочисленного деления; + -  сложение;   -   -  вычитание;

Функции:

Abs(x) - х ;

Sqr(x) - х2;

Trunc(x) - отбрасывание дробной  части от вещественного х;

Round(x) - округление вещественного x;

Succ(x) - х + 1;

Pred(x) - х - 1;

С некоторыми другими функциями мы познакомимся позже - при определении других типов данных.

Отношения:

 < - меньше     <= - меньше или равно

 > - больше      >= - больше или равно

 = - равно       <> - неравно

Тип данных Real

Значениями вещественного типа являются элементы зависящего от реализации подмножества вещественных чисел. В TP-6 диапазон типа Real [ 2.9*10 -39 ... 1.7*10 38 ]

Операции:

*  - умножение;      /   - деление;

+  - сложение;        -   - вычитание;

Функции:

Abs(x) - модуль х;

Sqr(x) - х в квадрате;

Sqrt(x) - корень из х.

Sin(x) - sin х;

Cos(x)- cos х;

Arctan(x)- arctg х;

Ln(x)  - ln х;

Exp(x) - e х;

Отношения: такие же, как и для типа Integer.

Числовые типы Integer и Real совместимы. Это означает, что данные типа Integer могут обрабатываться как вещественные числа и результат будет иметь тип Real.

Тип данных Сhar

Значениями символьного типа являются элементы конечного и упорядоченного множества символов. Символы этого множества определяются реализацией. Они должны быть и на вводных, и на выводных устройствах. Большинство ПЭВМ поддерживает ASCII - код, поэтому в реализациях языка множество значений типа Char совпадает с некоторым расширением ASCII - символов. ASCII код каждому символу, определенному в нем, ставит в соответствие один байт.

Вне зависимости от реализации множество символов включает:

A,  B, C, ... , Z, _  (знак подчеркивания)

 1, ... , 9 - (десятичные цифры)

 Символ пробела.

Функции:

 Ord(x) - порядковый номер x.

Chr(n)- символ с порядковым номером N.

 Pred(x)- символ, предшедствующий x.   

Succ(x) - символ, следующий за x.

Отношения.

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

= , <> , > , < , >= , <= .

Порядок на множестве букв латинского алфавита согласован с алфавитным, а на множестве цифр - с числовым.

Логический тип данных Boolean будет описан ниже - когда мы будем изучать понятие условия.

Тип данных Boolean 

Условия используются в программах для организации ветвлений и повторяющихся действий. Условием в языке является логическое выражение - выражение типа Boolean. Булевские значения - это логические истинностные значения: True (истина) и False (ложь).

Этот тип данных, как и другие простые типы данных, упорядочен. На нем определены функции Ord, Succ, Pred.

Таким образом , имеют место следующие соотношения :

False < True ,

Ord (False)=0,  Ord (True)=1,

Succ (False)=True,  Pred (True)=False.

На множестве < True, False > определены логические операции

Операции:

 And - логическая коньюнкция ( и )

  Or - логическая дизньюнкция ( или )

Not - логическое отрицание ( не )

Эти операции определяются следующими таблицами истинности:

                                     

And

False

True

Or

False

True

x

Not (x)

False

False

False

False

False

True

False

True

True

False

True

True

True

True

True

False

Отношения, определенные ранее для простых стандартных типов являются операциями, результат которых имеет логический тип. Иными словами, булевское значение дает любая из операций отношений :  =, < > , <= , < , > , >= , in.

Для типа Boolean определены стандартные функции, принимающие значения этого типа (логические значения):

Odd(Х) { Odd(Х) = True, если Х - целое нечетное число

 Odd(Х) = False, если Х - целое четное число}

Eoln(F) { конец строки в текстовом файле}

Eof(F) { конец файла}

Функции Eoln(F) и Eof(F) будут определены при описании файлов.

Условия можно классифицировать как простые и сложные.

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

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

Приведем примеры простых и сложных выражений типа Boolean (условий).

Простые выражения типа Boolean (условия) :

Sin(2*x) > Ѕ, (X + Y) mod Prime = 0,

b*b > 4*a*c ,

Number div Modulo = 2, Odd(A*P + B),

Flag ;

Сложные выражения типа Boolean (условия) :

а) (а + i > в) or ( х [Index] = с )

{ Здесь а, в, с - переменные типа Real, х - массив вещественных чисел , Index - переменная типа Integer }

б) Odd (n) And (n < 10е4)

в) Eof(f) Or (f^.data = 0)            {f - файл действительных чисел}

г) Not(beta) And (gamma)   {beta и gamma - переменные типа Boolean}

д) (A > B) = (C > D)

Логические выражения преобразуются по законам логики высказываний. Например,

Not((A > 0) And (B <> 0))  <==>  Not(A > 0) Or Not(B <> 0)  <==>   (A <= 0) Or (B = 0)

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

Вычислительные структуры как формальные средства описания данных

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

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

Проектирование и реализация структур данных осуществляется в терминах АТД и ВС сверху-вниз, а описания – снизу вверх.

Рисунок иллюстрирует методологию проектирования и реализации структур данных для некоторой предметной области в терминах вычислительной структуры ЯП.

Задача: Построить систему визуализации хода решения задачи на построения с помощью циркуля и линейки

Пример АТД Планиметрия (лекция 1)

Примитивные типы объектов:    точка, прямая, окружность.

Имена типов (Паскаль)       Point,      Line,         Circle

Примитивные операции и заголовки функций и процедур (Паскаль):

Line: (точка, точка)  прямая

Procedure DoLine (A, B: Point; var p: Line)

Circle: (точка, точка)  окружность

Procedure DoCircle (A, B: Point; var c: Circle)

CircleRad: (точка, точка, точка)  окружность

Procedure DoCirRad (A, B, C: Point; var c: Circle)

Аналогично определяются процедуры для:

IntersectLines(прямая, прямая) точка

IntersectCircles(окружность, окружность) (точка, точка)

IntersectLineCircle(прямая, окружность) (точка, точка)

Математические определения:   Данные

Точка     (X, Y)     (X, Y)

Прямая     aX + bY = c    (a, b, c)  

Окружность  (x - X)2 + (y - Y)2 = R2 ((X, Y), R)

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

Type Point = Record

      X, Y:Real

  End;

Circle = Record

      C: Point;

      R: Real

   End;

Circle = Record

      a, b, c: Real

        End;

Семейство отображений как множество определяется сигнатурой вычислительной структуры, которая содержит в качестве элементов описания вида

<имя отображения>: <список имен типов аргументов> <тип результата>

Например:

Trunc : Real Integer   >= : Real, Real Boolean

 

Наглядную иллюстрацию элемента сигнатуры дают рисунки.

Каждому элементу сигнатуры в ЯП предписана форма записи (префиксная скобочная или бесскобочная, инфиксная, постфиксная)

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

Термы. Интерпретации как семантика вычислительных структур.

Понятие терма

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

Именно:

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

Sqr(sin(X)) + Sqr(cos(X)) = 1   Trunc(Abs(B - A)) + 1

Формы записи

Префиксная форма записи формулы атомарного терма имеет вид

<имя функции>(<список аргументов >)

 Например:  Sin(X),   Log(a, X),    GCD(A, B)

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

A + B  вместо  Add(A, B)    A or B  вместо  or(A, B)

A + B+C вместо (A+B)+C   A+B*C вместо A+(B*C

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


Правила вычисления значений термов в языке Паскаль

Наибольший приоритет имеют функции и логическая операция not, далее следуют мультипликативные операции, аддитивные операции и отношения.

Таблица приоритетов

Функции  not.

Мультипликативные операции:  *    /    div    mod     and

Аддитивные операции:     +    -   or

Отношения:     =   <>   >   <   >=   <=    in

Операции одного приоритета вычисляются слева направо. Это соответствует группировке скобок в бесскобочном терме влево.

a + b + c = (a + b) + c,               a * b * c = (a * b) * c

Вычисление значения терма дает промежуточные результаты - данные некоторого типа, точно определенного знаком терма типами операндов (аргументов).

Любое несоответствие типа значения операнда приведет к ошибке, выявляемой компилятором при синтаксическом анализе.  

Примеры несоответствий типов

A/B div 10  (A + 1) or (B > 0)

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

Примеры неопределенностей

A/(B - B) + B  Sqrt(-1)

Точные определения семантики термов включают области определения атомарных термов

Пример

Семантика атомарных термов описывается соотношениями

Sqr(X) = X*X    Sqr(Sqrt(X)) = X  Sqrt(Sqr(X)) = Abs(X)


Выражение

  Отношение

Выражение

Логическая функция

огическое значение

Простое

условие

Абстрактные типы данных

предметной области

Составные (структурные) типы данных

языка программирования

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

языка программирования

Вычислительные структуры ЯП

Real

Integer

Trunc

Real

Real

>=

Boolean


 

А также другие работы, которые могут Вас заинтересовать

29374. Фазы трансляции программ 32.5 KB
  На вход лексического анализатора подаётся последовательность символов входного языка. ЛА выделяет в этой последовательности простейшие конструкции языка которые называют лексическими единицами лексемами. Генератор каждому символу действия поступающему на его вход ставит в соответствие одну или несколько команд выходного языка. В качестве выходного языка могут быть использованы команды устройства команды ассемблера либо операторы какоголибо другого языка.
29375. Основные функции сканера 34 KB
  Лексический анализ программ – один из основных этапов фаз трансляции программ – выделение в исходной программе элементарных единиц языка таких как идентификаторы константы ключевые слова символы операций разделители и др. Лексический анализ завершается преобразованием выделенных единиц языка в некоторую унифицированную форму обычно числовую.Часть транслятора которая выполняет лексический анализ называется сканером лексический анализатор. Лексический анализатор сканер должен распознать идентификаторы константы ключевые слова...
29376. Принципы работы сканера 95.5 KB
  Синтаксис целых констант представляется: целое ::=цифра знак цифра целое цифра знак ::= Для представления грамматики состояния целых констант диаграмма имеет вид:Вершины соответствуют состояниям автомата и определяются нетерминальными символами. Построим диаграмму состояний для автомата который распознает лексемы трех типов: целые константы десятичные константы идентификаторы идентр ::=буква идентр буква идентр цифра десятичная константа: дес.число цифра смеше число цифра смеше число ::= целое целое ::=цифра знак цифра целое цифра...
29377. Нисходящий грамматический разбор с возвратами 83 KB
  Суть данного метода можно представить в виде следующей последовательности шагов выполнение которых повторяется в процессе чтения входной цепи символов. Если активная вершина помечена а T то сравнить его с очередным символом входной цепочки. Сравниваемые символы совпали тогда сделать активной вершиной дерева лист правее а и перейти к следующим символам входной цепочки. Символы не совпали то выполним возврат к предыдущему уровню дерева разбора и соответствующему символу входной цепочки.
29378. Грамматический разбор методом операторного предшествования 68.5 KB
  Метод операторного предшествованияДанный метод относится к классу восходящих методов синтаксического анализа.Дерево разбора:Идея метода: входная цепочка символов просматривается слева направо пока не будет найдено подвыражение имеющее более высокий уровень предшествования чем соседние операторы. Для реализации метода необходимо установить отношение предшествования между всеми парами операторов грамматики.
29379. Основные функции и построение семантического анализатора программ 43 KB
  При работе семантических программ широко используется набор данных с организацией в виде стека. Операнды переписываются в выходную строку а операторы заносятся в стек. В зависимости от приоритета операторов при записи в стек оператор может вытолкнуть из стека другой оператор который последовательно записывается в выходную строку. Работа со стеком организуется так:1.
29380. Семантическое дерево как форма представления программ в языковых процессорах САПР 38 KB
  Семантическое дерево 2 польская запись 3 список тетрад. Семантическое дерево СД – модифицированное дерево грамматического разбора из которого исключили вершины соответствующие нетерминальным символам.Пример: E→ET TT→TM MM→E a b cabcДерево разбора:При построении СД скобки не требуются т.
29381. Польская запись как форма представления программ в языковых процессорах САПР 24 KB
  операнды следуют в том же порядке что и в исходной записи.Пример: 1 ab – инфиксная форма записи; ab – польская запись постфиксная.2 abc – инфиксная форма записи abc – польская запись.Формально построение польской записи описывается следующим грамматическим правилом: операнд ::= константа идентификатор операнд операнд оператор оператор ::= – Если должны быть учтены операторы с одним операндом то грамматическое правило должно быть расширено с учётом введения таких операторов добавляется бинарный и унарный оператор.
29382. Качества полноценного навыка чтения и пути их формирования 44 KB
  Качества полноценного навыка чтения и пути их формирования Овладение учащимися полноценным навыком чтения является важнейшим условием успешного обучения в школе по всем предметам. Навык чтения – это автоматизированное умение по озвучиванию печатного текста предполагающее осознание идеи воспринимаемого произведения и выработку собственного отношения к читаемому. В методике наряду с термином навык чтения употребляется термин техника чтения. Техника чтения обозначает все три компонента процесса чтения: восприятие произнесение понимание.