для т
.pdfr^ := sqr(r^) + i^ - 17;
Разумеется, совершенно недопустим оператор
r := sqr(r^) + i^ - 17;
так как указателю R нельзя присвоить значение вещественного выражения. Точно так же недопустим оператор
r^ := sqr(r);
поскольку значением указателя R является адрес, и его (в отличие от того значения, которое размещено по этому адресу) нельзя возводить в квадрат. Ошибочным будет и такое присваивание:
r^ := i;
так как вещественным данным, на которые указывает R, нельзя присвоить значение указателя (адрес).
Динамическую память можно не только забирать из кучи, но и возвращать обратно. Для этого используется процедура DISPOSE. Например, операторы
dispose(r);
dispose(i);
вернут в кучу 8 байт, которые ранее были выделены указателям I и R.
Отметим, что процедура DISPOSE(PTR) не изменяет значения указателя PTR, а лишь возвращает в кучу память, ранее связанную с этим указателем. Однако повторное применение процедуры к свободному указателю приведет к возникновению ошибки периода исполнения. Освободившийся указатель программист может пометить зарезервированным словом NIL. Помечен ли какой-либо указатель или нет, можно проверить следующим образом:
const
р: ^real = NIL;
begin
. . . . .
if р = NIL then
new(p);
. . . . .
dispose(p);
p := NIL;
. . . . .
end.
Никакие другие операции сравнения над указателями не разрешены. Приведенный выше фрагмент иллюстрирует предпочтительный способ объявления указателя в виде типизированной константы с одновременным присвоением ему значения NIL. Следует учесть, что начальное значение указателя (при его объявлении в разделе переменных) может быть произвольным. Использование указателей, которым не присвоено значение процедурой NEW или другим способом, не контролируется системой и может привести к непредсказуемым результатам. Чередование обращений к процедурам NEW и DISPOSE обычно приводит к ╚ячеистой╩ структуре памяти. Дело в том, что все операции с ней выполняются под управлением особой подпрограммы, которая называется администратором кучи. Она автоматически пристыковывается к нашей программе компоновщиком Турбо Паскаля и ведет учет всех сводных фрагментов в куче. При очередном обращении к процедуре NEW эта подпрограмма отыскивает наименьший свободный фрагмент, в котором еще может разместиться требуемая переменная. Адрес начала найденного фрагмента возвращается в указателе, а сам фрагмент или его часть нужной длины помечается как занятая часть кучи.
Другая возможность состоит в освобождении целого фрагмента кучи. С этой целью перед началом выделения динамической памяти текущее значение указателя HEAPPTR запоминается в переменной-указателе с ющью процедуры MARK. Теперь можно в любой момент освободить фрагмент кучи, начиная от того адреса, который запомнила процедура MARК, и до конца динамической памяти. Для этого используется процедура RELEASE. Например:
var
p,p1,p2,р3,р4,р5: ^integer;
begin
new(p1);
new(p2);
mark(p);
new(p3);
new(p4);
new(p5);
. . . . .
release(p);
end.
В этом примере процедурой MARK(P) в указатель Р было помещено тукущее значение HEAPPTR, однако память под переменную не резервировалась. Обращение RELEASE(P) освободило динамическую память от помеченного места до конца кучи. Пирведенный ниже рисунок иллюстрирует механизм работы процедур NEW-DISPOSE и NEW-MARK-RELEASE для рассмотренного примера и для случая, когда вмемто оператора RELEASE(P) используется, например, DISPOSE(P3).
а) |
б) |
в) |
Состояние динамической памяти:
а) перед освобождением; б) после Dispose(p3); в) после Release(p)Следует учесть, что вызов RELEASE уничтожает список свободных фрагментов в куче, созданных до этого
процедурой DISPOSE, поэтому совместное использование обоих механизмов освобождения памяти в рамках одной программы не рекомендуется.
22. язык программирования алфавит, синтаксис ,лексема, семантика.Комментарии , пространство имен,ключевые слова. Основными элементами любого языка программирования являются его алфавит, синтаксис и семантика. Алфавит – совокупность символов, отображаемых на устройствах печати и экранах и/или вводимых с клавиатуры терминала. Лексика – совокупность правил образования цепочек символов (лексем), образующих идентификаторы (переменные и метки), операторы, операции и другие лексические компоненты языка. Сюда же включаются зарезервированные (запрещенные, ключевые) слова языка программирования, предназначенные для обозначения операторов, встроенных функций и пр. Иногда эквивалентные лексемы, в зависимости от языка программирования, могут обозначаться как одним символом алфавита, так и несколькими. Например, операция присваивания значения в языке Си обозначается как «=», а в языке Паскаль – «:=». Операторные скобки в языке Си задаются символами «{» и «}», а в языке Паскаль – begin и end. Граница между лексикой и алфавитом, таким образом, является весьма условной, тем более что компилятор обычно на фазе лексического анализа заменяет распознанные ключевые слова внутренним кодом (например, begin – 512, end – 513) и в дальнейшем рассматривает их как отдельные символы. Синтаксис – совокупность правил образования языковых конструкций, или предложений языка программирования – блоков, процедур, составных операторов, условных операторов, операторов цикла и пр. Особенностью синтаксиса является принцип вложенности (рекурсивность) правил построения конструкций. Это значит, что элемент синтаксиса языка в своем определении прямо или косвенно в одной из его частей содержит сам себя. Например, в определении оператора цикла телом цикла является оператор, частным случаем которого является все тот же оператор цикла.Необходимо строгое соблюдение правил правописания (синтаксиса) программы. В частности, в Паскале однозначно определено назначение знаков пунктуации. Точка с запятой (;) ставится в конце заголовка программы, в конце раздела описания переменных, после каждого оператора. Перед словом End точку с запятой можно не ставить. Запятая (,) является разделителем элементов во всевозможных списках: списке переменных в разделе описания, списке вводимых и выводимых величин.В БНФ(формула Бекуса – Наура) всякое синтаксическое понятие описывается в виде формулы, состоящей из правой и левой части, соединенных знаком ::=, смысл которого эквивалентен словам «по определению есть». Слева от знака ::= записывается имя определяемого понятия (метапеременная), которое заключается в угловые скобки <>, а в правой части записывается формула или диаграмма, определяющая все множество значений, которые может принимать метапеременная. Синтаксис языка описывается путем последовательного усложнения понятий: сначала определяются простейшие (базовые), затем все более сложные, включающие в себя предыдущие понятия в качестве составляющих.
В записях метаформул приняты определенные соглашения. Например, формула БНФ, определяющая понятие «двоичная цифра», выглядит следующим образом: <двоичная
цифра>::=0|1 Значок «|» эквивалентен слову «или».В диаграммах стрелки указывают на последовательность расположения элементов синтаксической конструкции; кружками обводятся символы, присутствующие в конструкции.Понятие «двоичный код» как непустую последовательность двоичных цифр БНФ описывает так:<двоичный код>::=<двоичная цифра>| <двоичныйкод><двоичная цифра>Определение, в котором некоторое понятие определяется само через себя, называется рекурсивным. Рекурсивные определения характерны для БНФ.Возвратная стрелка обозначает возможность многократного повторения. Очевидно, что диаграмма более наглядна, чем БНФ.Синтаксические диаграммы были введены Н. Виртом и использованы для описания созданного им языка Паскаль.Семантика – смысловое содержание конструкций, предложений языка, семантический анализ – это проверка смысловой правильности конструкции. Например, если мы в выражении используем переменную, то она должна быть определена ранее по тексту программы, а из этого определения может быть получен ее тип. Исходя из типа переменной, можно говорить о допустимости операции с данной переменной. Семантические ошибки возникают при недопустимом использовании операций, массивов, функций, операторов и пр. Пространство имён — некоторое множество, под которым подразумевается модель, абстрактное хранилище или окружение, созданное для логической группировки уникальных идентификаторов (то есть имён). Идентификатор,
определенный в пространстве имён, ассоциируется с этим пространством. Один и тот же идентификатор может быть независимо определён в нескольких пространствах. Таким образом, значение, связанное с идентификатором, определённым в одном пространстве имён, может иметь (или не иметь) такое же значение, как и такой же идентификатор, определённый в другом пространстве. Языки с поддержкой пространств имён определяют правила, указывающие, к какому пространству имён принадлежит идентификатор (то есть его определение).
Например, Андрей работает в компании X, а ID (сокр. от англ. Identifier — идентификатор) его как работника равен 123. Олег работает в компании Y, а его ID также равен 123. Единственное (с точки зрения некой системы учёта), благодаря чему Андрей и Олег могут быть различимы при совпадающих ID, это их принадлежность к разным компаниям. Различие компаний в этом случае представляет собой систему различных пространств имён (одна компания — одно пространство). Наличие двух работников в компании с одинаковыми ID представляет большие проблемы при их использовании, например, по платёжному чеку, в котором будет указан работник с ID 123, будет весьма затруднительно определить работника, которому этот чек предназначается.
В больших базах данных могут существовать сотни и тысячи идентификаторов. Пространства имён (или схожие структуры) реализуют механизм для сокрытия локальных идентификаторов. Их смысл заключается в группировке логически связанных идентификаторов в соответствующих пространствах имён, таким образом делая систему модульной.
Ограничение видимости переменных может также производиться путём задания класса её памяти. Операционные системы, многие современные языки программирования обеспечивают поддержку своей модели пространств имён: используют каталоги (или папки) как модель пространства имён. Это позволяет существовать двум файлам с одинаковыми именами (пока они находятся в разных каталогах). В некоторых языках программирования (например, C++, Python) идентификаторы имён пространств сами ассоциированы с соответствующими пространствами. Поэтому в этих языках пространства имён могут вкладываться друг в друга, формируя дерево пространств имён. Корень такого дерева называется глобальным пространством имён.
4)Линейный алгоритм
Изучение алгоритмических конструкций начнем с линейного алгоритма. В учебниках иногда используется термин «следование».
Алгоритм назовем линейным, если:1) выполняется каждый его шаг, и 2) только один раз.
Такого определения вполне достаточно. В некоторых учебниках используются слова «шаги выполняются последовательно, друг за другом», но эти слова означают наличие некоторого порядка. А порядков имеется два!
Одним из свойств алгоритма является, что его можно использовать двояко: либо исполнить, либо записать по определенным правилам. Таким образом первый порядок – порядок исполнения команд, второй – порядок написания. Эти порядки могут не совпадать.
На рисунке слева – случай, когда порядок написания и порядок исполнения совпадают, справа – эти порядки различны. Может показаться, что на рисунке справа алгоритм не линеен, так как команды выполняются не «друг за другом», а сначала вторая, потом первая. Но если определить линейный алгоритм как указано выше - Алгоритм линейный, если выполняется каждый его шаг, и только один раз – то эта проблема снимается.
Линеен алгоритм обмена, алгоритмы деления угла или отрезка пополам и многие другие.
Ветвление неполное
Вернемся к нашему определению линейного алгоритма и попытаемся определить остальные алгоритмические структуры.
Для начала, откажемся от требования 1), обязательности выполнения каждого шага алгоритма.
Имеем алгоритм, в котором некоторые шаги могут не выполняться.
Получившаяся структура алгоритма называется. НЕПОЛНОЕ ВЕТВЛЕНИЕ
Согласно принципу детерминированности алгоритмов, исполнитель должен знать, выполнять отмеченный шаг или нет. Приходится ввести понятие «условие», то есть предложение, значение которого либо «истина», либо «ложь».
Если условие истинно – шаг алгоритма выполняется, иначе – нет.
Всевозможные условия являются объектом работы, то есть ДАННЫМИ, которые могут иметь либо значение истина, либо значение ложь. Образуются эти значения при сравнении двух переменных или выражений одного типа.
A=B;A<>B;X<>5;A>5;B<3;C<=A+B
Значения этих выражений «истинно» (true) или «ложно» (false) зависит от значений используемых переменных.
На языке блок-схем блок ветвления обозначается ромбом, имеет один вход и два выхода. Однако любой алгоритм должен обладать свойством результативности, то есть у него должен быть конец и только один. Обе ветви, для достижения конца соединяются, место соединения называется УЗЕЛ и на блок-схеме отмечается кружком.
Наличие двух выходов так же представляет собой проблему. Выходы должны быть разными. Поэтому они маркируются словами «да» и «нет» или знаками «+» и «-». Согласно первому выходу алгоритм продолжаем при истинности условия, которое вписывается в ромб, иначе – продолжаем согласно второму выходу. Лентяи просто ставят около выхода «да» точку. Этого достаточно для однозначного определения дальнейших шагов алгоритма.
Цикл
Ветвление - один из случаев нарушения линейности алгоритма.
Как уже отмечалось, на блок-схеме ветвление обозначается ромбом, внутри которого указывается условие. Блок ветвления имеет один вход и два выхода. Обе ветви, для достижения конца соединяются в узле.
Однако ветви могут соединиться и перед блоком условия!
Возможна ситуация, когда команды блока выполняются несколько раз подряд. Алгоритм тоже нелинейный.
Такая организация алгоритма называется ЦИКЛ.
Шаги, которые могут выполняться несколько раз подряд образуют ТЕЛО цикла. Выполнять или нет тело еще раз решает УСЛОВИЕ цикла.
Итак, любой цикл имеет ТЕЛО и УСЛОВИЕ ВЫХОДА.
Снова вспоминаем свойство алгоритма, что его можно исполнить и его можно записать.
Две составных части цикла – тело и условие – можно записать по разному: либо сначала условие, потом тело, либо сначала тело, потом условие.
В первом случае цикл называется циклом типа «пока», во втором – циклом типа «до».
Так выглядит оформление цикла с предусловием (цикла «пока») в разных языках программирования.
b |
pa |
C |
asc
si |
al |
c |
|
1
0 if
<
ус
л.
>
th en 40 2 0 <т ел
о
ц
ик
ла
"П
О
К
А"
>
3
0 go to 10 4 0
w hil e <у сл
.>
<
те
ло
ц
ик
ла
"П
О
К
А"
>
w en d
А
так
вы
гля
ди
т
оф
ор
мл
ен
ие
ци
кла
с
пос
тус
ло
ви
ем
(ци
кла
«д
о»)
в
яз
ык
ах
пр
огр
ам
ми
ро |
|
|
|
|
ва |
|
|
|
|
ни |
|
|
|
|
я. |
|
|
|
|
bas |
|
|
|
|
ic |
|
|
|
|
|
|
|
|
|
10 |
|
re |
|
d |
re |
|
p |
|
o |
m |
|
ea |
|
{< |
нач |
|
t |
|
|
|
|
те |
||
ал |
|
|
|
|
|
< |
|
л |
|
о |
|
|
||
|
те |
|
о |
|
ци |
|
|
||
|
л |
|
ц |
|
кла |
|
|
||
|
о |
|
ик |
|
20 |
|
|
||
|
ц |
|
ла |
|
<те |
|
|
||
|
ик |
|
" |
|
ло |
|
|
||
|
ла |
|
Д |
|
ци |
|
|
||
|
" |
|
О |
|
кла |
|
|
||
|
Д |
|
"> |
|
«Д |
|
|
||
|
О |
|
} |
|
О» |
|
|
||
|
"> |
|
|
|
> |
|
|
w |
|
|
|
|
||
|
|
|
|
|
50 |
|
u |
|
hil |
|
nt |
|
e |
|
if |
|
|
||
|
il |
|
<у |
|
<ус |
|
|
||
|
<у |
|
сл |
|
ло |
|
|
||
|
сл |
|
.> |
|
ви |
|
|
||
|
.>; |
|
|
|
е> |
|
|
|
|
|
|
|
|
|
the |
|
|
|
|
n |
|
|
|
|
10 |
|
|
|
|
|
|
|
|
|
Основным различием циклов ДО и ПОКА является то, что в цикле ДО тело цикла один раз выполняется обязательно, а в цикле ПОКА возможна ситуация, когда тело цикла не выполнится ни разу.Изменив условие, для цикла ПОКА можно добиться выполнения цикла один (первый) раз, цикл будет работать как и цикл ДО.Запретить выполнение первого раза тела цикла типа ДО невозможно.Так как из цикла ПОКА можно получить цикл ДО, цикл ПОКА является более универсальным.
Попытки определить тип цикла по семантическому значению слов «до» и «пока» в русском языке обречены на неудачу.
Фразы:
Тело цикла выполняется до тех пор ПОКА позволяет условие
И Тело цикла выполняется ДО тех пор пока позволяет условие
Различаются только акцентом.
Как видим, задача может быть решена как использованием цикла «пока», так и использованием цикла «до».
Довольно часто выбор типа цикла несущественен.
Но встречаются случаи, когда только одна из этих разновидностей цикла наилучшим образом подходит к конкретной задаче.
Например, если вы собираетесь удалить пробелы, стоящие в начале строки, то, скорее всего, выберете цикл с предусловием, потому что надо сначала убедиться, что пробел имеется, и только затем его удалять (глупо поступать наоборот - сначала удалять, а потом проверять, стоило ли это делать). Зато ввод текста до точки трудно построить иначе как с постусловием, поскольку сначала требуется ввести очередной символ и только потом сравнивать его с точкой.
Для цикла ПОКА принято организовывать выход при значении условия "ложно", а для цикла ДО принято организовывать выход при значении условия "истина". Это следует знать, если вы работаете, скажем, на паскале.
Однако, Вы можете разработать свой язык программирования, где все будет наоборот. Требование придерживаться этих условий при работе с блок-схемами мне кажется неправильным.
При некорректной организации некоторых циклов может возникнуть эффект так называемого "зацикливания", когда действия внутри цикла не могут создать условия, требующиеся для его завершения. Следует всячески избегать подобных ситуаций путем тщательного анализа условий работы цикла.
7. Понятие выражения, операции, операнда.
При выполнении программы осуществляется обработка данных, в ходе которой с помощью выражений вычисляются и используются различные
значения. Выражение представляет собой конструкцию, определяющую состав данных, операции и порядок выполнения операций над данными. Выражение состоит из операндов, знаков операций и круглых скобок. В простейшем случае выражение может состоять из одной переменной или константы. Тип значения выражения определяется типом операндов и составом выполняемых операций. Операнды представляют собой данные, над которыми выполняются действия. В качестве операндов могут использоваться константы, переменные, элементы массивов и функции.
Операции – это действия, которые выполняются над операндами. Операции бываю унарными и бинарными. Унарная операция относится к одному операнду, и ее знак
записывается перед операндом, например, - x. Бинарная операция выражает отношение между двумя операндами, и знак ее записывается между операндами, например, x + y.
Круглые скобки используются для указания порядка выполнения операций. Если в операциях используется несколько данных, то их типы должны быть либо идентичными, либо