Языки программирования
Формально язык программирования — это открытое для пополнения множество текстов, записанных с помощью некоторого набора символов — алфавита языка
. Содержательно, по основному своему назначению, язык программирования — это средство общения между человеком, или, как еще говорят, пользователем языка и вычислительной машиной (компьютером).
Применительно к знаковым системам, в частности к языкам программирования, говорят об их синтаксисе — правилах образования текстов, семантике — правилах истолкования текстов тем, кому они адресованы.
В случае языков программирования:
Синтаксис языков программирования — это совокупность требований, которым должна удовлетворять любая осмысленная программа
Семантика языка программирования — это правила, определяющие, какие операции и в какой последовательности должна исполнить машина, работая по произвольной заданной ей программе.
Простые значения — это числа, логические значения, литеры и ссылки. Типы простых значений часто называют простыми типами. В некоторых языках встречаются н другие простые типы.
Числа
Принято различать два основных типа чисел: целые и так называемые вещественные.
Целое – множество целых чисел в диапазоне разрядной сетки ЭВМ.
Характеристикой этого типа данных может быть длина, выражаемая максимальным объемом памяти (в байтах) или максимальным числом десятичных позиций для записи данных (в случае двоично-десятичного представления целых чисел).
Кроме арифметической операции сложения, вычитания, умножения и целочисленного деления над целыми числами выполняются такие операции, как вычисление по заданному модулю (нахождение остатка от деления), определение максимального и минимального числа среди нескольких чисел, возведения в целую степень, определение следующего или предыдущего по значению чисел.
Для хранения целого числа в памяти ЭВМ выделяется фиксированное количество двоичных позиций .
Используется в ЭВМ формат представления чисел с фиксированной точкой, при этом представляется, что точка фиксирована после самого младшего разряда числа.
Действительные числа – множество вещественных чисел в диапазоне их представления в разрядной сетке ЭВМ.
В ЭВМ точность представления действительного числа является ограниченной из-за конечности (ограниченности) разрядной сетки ЭВМ. Так, число 0.1 в ЭВМ представляется неточно, так как его двоичное представление является бесконечной дробью.
Типичные операции над действительными числами – сложение, вычитание, умножение, деление, вычисление тригонометрических функций, возведение в степень, извлечение квадратного корня, логарифмирование, нахождение минимального и максимального числа из некоторого конечного множества чисел и некоторые другие.
Вещественные числа хранятся и используются в операциях над ними в формате с плавающей точкой.
X = M * E P ,
где М- мантисса со знаком, /М/>1,
Е- фиксированное основание (для десятичных чисел Е= 10, в ЭВМ чаще используется основание 16, но может быть и 2 или 8, во всяком случае, кратное 2).
Для вещественных чисел точность исполнения даже самых простых операций не гарантируется, т. е. допускается, что результат любой операции может быть получен с некоторой погрешностью — ошибкой округления. Величина этой ошибки зависит от операции, значений операндов, диапазона, которому принадлежат эти значения, и, разумеется, от компьютера- на котором исполняется программа, поскольку вид компьютера, определяет способ представления чисел внутри каждого из допустимых диапазонов.
Опишем синтаксис обозначений, принятый в –«Паскале». Далее:
Логические значения
Следующий тип простых значений — это логические или булевы значения.
Тип логический или BOOLEAN характеризуется тем, что может принимать два значения “истина” или “ ложь”. В разных языках программирования эти два логических значения могут записываться по разному. Например, в Паскале это true и false.
Они служат для того, чтобы зафиксировать один из двух возможных ответов на некоторый вопрос, один из двух возможных исходов некоторой проверки, одно из двух состояний некоторого объекта.
Типовыми операциями над этими данными является конъюнкция (и), дизъюнкция (или), отрицание (не). Часто в языках программирования используются и более сложные логические операции: исключающее или, импликация, эквивалентность. Кроме того, логическое значение является результатом выполнения операций (<, £, >, ³, =, ¹) над целыми и вещественными числами, символьными и другими данными, над которыми эти операции имеют смысл.
Литеры и строки
Символьный тип (или данное типа строка) включает множество символов или литер, доступных в конкретной ЭВМ.
В ЭВМ символы представляются в двоичном коде. Эти коды упорядочены и для каждого символа может быть определен соответствующий ему порядковый номер.
В некоторых языках программирования, таких, как Паскаль, есть стандартные операции определения кода по соответствующему номеру символа и обратная операция, определяющая номера в последовательности по заданному символу. В этом же языке реализованы и такие операции над символами, как определение последующего символа относительно заданного.
Значения из доступного набора литер относятся к типу литерный. Это еще не тексты, а только знаки: из которых составляются тексты — конечные последовательности литер, называемые обычно строками или цепочками. Строки иногда причисляют к простым значениям (типа строковый}, иногда - к составным.
Ссылочный тип данных. Динамические объекты.
Тип указатель (или POINTER) представляет собой множество адресов данных в пределах объема памяти ОЗУ (количество адресуемых байтов, слов).
1. Природа динамических объектов и способы их реализации.
Все объекты, представляющие данные в программе и которые рассматривали до сих пор, были статические в том смысле, что все их параметры, размеры были известны до выполнения программы. Следовательно, ресурсы для них можно было заранее спланировать и выделить.
Существуют задачи, для которых характерно наличие данных: – фактическое появление которых возможно, но не обязательно; – время жизни этих объектов меньше времени исполнения программы. Такие объекты называют динамическими объектами.
Для работы со статическими объектами в языках программирования используется хорошо известный механизм имен. Однако, этот механизм вряд ли нам подходит для представления и манипуляции динамическими объектами. Дело в том, что имя должно быт известно до выполнения программы – это во-первых. Во вторых, порождение всякого именованного объекта связано с выделением памяти. Раз объекты возникают динамически, то заранее мы не знаем сколько их будет. Следовательно не можем заранее выделить нужное количество имен.
Каждый раз, когда порождается динамический объект ему выделяется место в памяти. Адрес начала выделенной области памяти полагается в качестве значения ссылочной переменной, представляющей динамический объект. При уничтожении динамического объекта занимаемая им память считается свободной, а соответствующая ссылочная переменная принимает специальное значение – нет объекта. Все действия над динамическими объектами в программе описываются как действия над значениями ссылочных переменных.
Связь указателя (ссылочной переменной) с объектом графически можно проиллюстрировать так:
Значение ссылочной переменной, соответствующее отсутствию динамического объекта – nil (зарезервированное слово).
Составные значения и их типы
В современных языках программирования могут использоваться значения сложной структуры, теоретически — сколь угодно сложной. Надо уметь задавать эту структуру, называемую также типом значения.
Структура данных – это совокупность элементов данных, между которыми существуют некоторые отношения, причем элементами данных могут быть простые данные и структуры данных.
Структуру данных можно определить, как
S=(D,R),
где D- множество элементов данных, R-множество отношений (связей) между элементами данных.
Массив – конечное упорядоченное множество простых данных или скаляров одного и того же типа. Элементы вектора находятся между собой в отношении непосредственного следования. В памяти ЭВМ элементы вектора представляются последовательностью одинаковых по длине участков памяти, как правило, расположенных в порядке следования элементов в группе. Важнейшая операция над вектором – доступ к заданному элементу. Кроме того, над вектором можно выполнять операции определения верхней и нижней границ индекса. По сути эти операции дают описание вектора.
Элементы вектора нумеруются целыми числами (индексами). Но, в отличие от векторов в алгебре, нумерация элементов не обязана начинаться с 1, Индексы могут быть и отрицательными. Их диапазон задается так, как было сказано в начале раздела, и часто называется граничной парой, состоящей из двух границ: нижней и верхней.
к-мерным массивом называется конечное упорядоченное множество (к-1) мерных массивов, все элементы которых принадлежат одному и тому же типу. При к=1 получаем вектор.
Записи
Следующий способ образования составных значений – это объединение некоторого фиксированного числа k значений, возможно, различных, но также фиксированных типов <тип1>,.,. , <тии2>, в одно. Такое объединение принято называть записью (реже структурой), а. объединяемые значения — полями этой записи. Чтобы можно было выделять из записи отдельные поля, они снабжаются индивидуальными наименованиями - идентификаторами полей, которые входят в обозначение типа записи:
<тип записи> ::= record <список полей> end
<список полей> ::= <идентификатор>:<тип>
| <список полей>; <идентификатор>:<тип>
Классический пример типа записи — тип комплексного числа, имеющий обозначение
record re : real; irn. : real endrec
Тип записи для календарной даты может быть таким:
record day : byte; month: string [8]: year : word endrec
Определения этих структур данных основаны на понятии списка или списковой структуры.
Списком называется линейно-упорядоченная последовательность элементов данных E(1),E(2)…E(n), где n>0,причем каждый элемент E(i) характеризуется одним и тем же набором полей. Такой список называют линейным списком из-за линейной упорядоченности элементов. Упорядоченность элементов списка может быть задана неявно путем последовательного расположения его элементов как в логической структуре, так и в памяти ЭВМ (т.е физической структуре данных). Список с таким неявным заданием упорядоченности в логической и физической структурах называют еще последовательным линейным списком. С другой стороны, упорядоченность может задаваться явно путем помещения в каждом элементе E(i) указателей или связок, в которых помещается адрес последующего или предыдущего элемента списка. Такие списки называют связными списками и о них мы буде мы говорить позже.
Полустатические структуры данных- это последовательные линейные списки с переменной длиной, ограниченной фиксированной максимальной величиной и с ограниченным доступом. К таким структурам относятся стеки и очереди. Есть еще деки, но они менее распространены и на них останавливаться не будем.
Стек – такой последовательный линейный список с переменной длиной, включение и исключение элементов из которого выполняется только с одного конца списка. Известно и другое название стека – магазин. Иногда стек называют еще очередью, функционирующей по принципу LIFO (Last- In-First- Out –последним пришел – первым вышел).
| Emax |
| En |
| En-1 |
| … |
| E1 |
|
|
|
|
Логическая структура стека
|
|
Физическая структура стека может быть изображена следующим образом:
| ST – имя стека |
| Адрес верхней границы |
| Указатель вершины |
| Адрес нижней границы |
| Описание элемента |
|
|
Для включения нового элемента в стек сначала изменяется значение указателя вершины стека на длину элемента стека, а затем по значению этого указателя помещается новый элемент стека. При исключении элемента стека сначала прочитывается информация из вершины стека по значению указателя, а затем значение указателя уменьшается на величину длины элемента стека.
Для хранения стека в памяти ЭВМ отводится сплошная область памяти ограниченного объема. Если в процессе заполнения стека указатель выходит за отведенные границы стека, то происходит переполнение стека и включение нового элемента становится невозможным.
Очередь – такой последовательный список с переменной длиной, включение элементов в который происходит с одной стороны, а исключение с другой стороны списка.
Очередь функционирует по принципу – FIFO (First-In-First-Out-первым пришел, первым вышел).
|
Для индикации начала и конца очереди организуются 2 указателя: схема простейшей очереди будет следующая:
| A1 | A2 | Amax |
|
Из схемы следует: для очереди выделяется фиксированный участок памяти ЭВМ, в котором, как правило, заняты в каждый момент времени лишь некоторые слоты. Указатель P1 является адресом первого (начального), слота очереди, P2 – адресом первого свободного слота очереди.
При включении в очередь вносится по адресу P2, затем значение указателя P2 изменяется (передвигается на 1 элемент очереди), т.е. значение P2 увеличивается на длину элемента очереди.
При исключении из очереди извлекается элемент, адресуемый указателем P1, и после этого указатель P1 перемещается к следующему слоту, т.е его значение увеличено на длину элемента очереди.
Динамическая структура имеет следующие основные признаки:
1. Непостоянство и непредсказуемость размера (числа элементов) структуры в процессе ее обработки.
2. Отсутствие физической смежности элементов структуры в физической памяти. Логическая последовательность элементов задается в явном виде с помощью одного или нескольких указателей или связок, хранящихся в самих элементах. Следовательно, память, занимаемая динамической структурой не является непрерывной и может быть хаотически разработана в области памяти.
Часто динамические структуры физически представляются в форме связных списков.
Связный список – такая структура, элементами которой служат записи с одним и тем же форматом, связанные друг с другом с помощью указателей, хранящихся в самих элементах списка.
В односвязном линейном списке каждый элемент состоит из двух различных по назначению полей: содержательного и поля указателя. Логическая структура может быть изображена так:
| Æ |
| данные |
| Указатель |
| данные |
| Указатель |
| данные |
Æ -пустой указатель, означает конец списка.
Физическая структура списка может быть такой :
Включение списка и исключения элемента из списка осуществляется путем корректировки указателей.
Схематично покажем включение в односвязный список нового элемента между двумя существующими элементами списка. Чаще всего местоположение нового элемента определяется по назначения ключа:
В этом случае значение L2 записывается в поле указателя включаемой записи значение поля указанной записи, после которого включается новый элемент, изменяется на LN ,Þ,окончательная логическая структура будет следующей:
Исключение из списка может быть так:
В этом случае поле указателя записи, после которого удаляется элемент изменяется на значение адреса, следующего за исключаемым элемента списка (L2®L3). Оконченная логическая структура обновленного списка:
Аппарат процедур позволяет дать обозначение некоторому оператору — телу процедуры, с тем, чтобы этот оператор мог быть исполнен как бы в том месте программы, где возникла потребность в описываемых им действиях, и где для этой цели содержится обращение к процедуре (в другой терминологии — ее вызов). Тело процедуры обычно содержит некоторые идентификаторы, называемые {формальными} параметрами процедуры. При обращении к процедуре, непосредственно перед исполнением ее тела, эти параметры либо получают значения соответствующих аргументов обращения (фактических параметров}, либо заменяются этими аргументами. Первый вариант называется вызовом параметров значением, второй — вызовом по имени.
Функции.
В отличие от процедур, функции – определяют правила вычисления значений. В отличие от процедур функция не определяет, что надо делать с полученным значением. Заметим, что значения, получаемые через функции, могут быть только простых типов.
Описание функции.
Для определения правила вычисления значения используется понятие <описание функции>. Это описание размещается в разделе процедур и функций того блока, где они используются.
<описание функции>::=<заголовок функции>;<блок>
<заголовок функции>::=function <имя функции>
[(<список формальных параметров>)] :<имя типа>.
Подобно процедурам функции могут быть без параметров, могут иметь параметры-значения и параметры-переменные. Имя типа в заголовке функции необходимо по двум причинам:
- для определения типа выражения, надо знать типы операндов;
- для контроля правильности использования функции в программе.
Подобно процедуре, тело функции – блок. Как же определить какой из результатов, получаемых в теле функции – значение функции? Для этого в теле функции обязательно должен быть хотя бы один выполняемый оператор присваивания вида <имя функции>:=<выражение>.
Похожие записи
No user прокомментировали сообщение
Оставить комментарий