Теория программирования. Теория программирования
 Скачать 195.28 Kb.
|
|
Теория программирования  Голиков В.А. Теория программирования. / Московская финансово-промышленная академия. – М., 48 с. © Голиков В.А. © Московский финансово-промышленный университет «Синергия» Содержание ВВЕДЕНИЕ Том Сойер рисует на заборе Сид выполняет команды Тема 1. Устройство компьютера. Оперативная память, процессор, регистры процессора. Аппаратный стек 1.1. Устройство компьютера 1.2. Оперативная память 1.3. Процессор 1.4. Алгоритм работы компьютера 1.5. Аппаратный стек 1.6. Команды вызова подпрограммы и возврата Тема 2. Языки программирования 2.1. Первые языки программирования 2.2. Области применения языков программирования 2.3. Парадигмы программирования 2.4. Состав языка программирования 2.5. Стандартизация языков программирования 2.6. Среда проектирования 2.7. Трансляторы 2.8. Процесс трансляции Тема 3. Общее понятие алгоритма. Управляющие конструкции алгоритмического языка. 3.1. Общее понятие алгоритма 3.2. Управляющие конструкции алгоритмического языка 3.3. Язык схем 3.4. Основные структуры алгоритмов 3.5. Понятие переменной Тема 4. Типы переменных. Целые и вещественные переменные, представление целых и вещественных чисел в компьютере 4.1. Типы переменных 4.2. Целочисленные переменные 4.3. Вещественные переменные 4.4. Символьные переменные 4.5. Логические переменные и выражения 4.6. Массивы 4.7. Текстовые строки 1. ВВЕДЕНИЕ 1.1. Том Сойер рисует на заборе «Том появился на тротуаре с ведром извёстки и длинной кистью в руках. Он оглядел забор, и всякая радость отлетела от него, а дух погрузился в глубочайшую тоску. Тридцать ярдов дощатого забора в девять футов вышиной! Жизнь показалась ему пустой, а существование – тяжким бременем». Марк Твен, «Приключения Тома Сойера» Память компьютера похожа на длинный-предлинный забор, правда, покрашенный совсем не так, как хотелось бы тетушке Полли. Представим себе, что Том со своими дружками покрыли известкой не все доски забора, а, скажем, только первую, вторую, четвертую, седьмую... и т.д.: 1 1 0 1 0 0 1 0 1 1 0 0 1 1 1 0 1 1 0 0 1 1 0 0 Поступая так, Том Сойер и его команда, конечно же, не подозревали, что полосатый забор можно рассматривать как двоичный код, в котором единице соответствует светлая, а нулю – темная, непокрашенная доска. Каждая доска может быть только в двух состояниях, следовательно, она способна нести один бит информации. Число различных состояний двух идущих подряд досок уже равно четырем, поскольку каждому из двух состояний первой доски соответствуют два состояния второй. Легко понять, что восемь идущих подряд досок можно выкрасить 2 ´ 2 ´ 2 ´ 2 ´ 2 ´ 2 ´ 2 ´ 2 = 28 = 256 способами. Иными словами, в восьми битах можно уместить 256 разных чисел (от 0 до 255, например), а этого вполне достаточно, чтобы закодировать любую букву. Поскольку «забор» в нашем примере состоит из 24 досок (цифр), он пригоден для того, чтобы закодировать сразу три буквы. Какие же буквы показаны на заборе? Ответ на этот вопрос зависит от договоренности: какому числу соответствует та или иная буква. Первое число (11010010) на заборе равно (в привычном нам десятичном представлении) 210, второе (11001110) – это 206, третье (11001100) равно 204. И вся эта тройка соответствует в операционной системе Windows, скорее всего установленной у вас на компьютере, слову «ТОМ». 1.2. Сид выполняет команды Цифра 8 возникла в нашем шуточном примере не случайно. Ведь восемь битов (досок в заборе тетушки Полли) составляют байт – ячейку памяти минимального размера, к которой имеет доступ компьютер. Можно сказать, что память компьютера состоит из последовательности идущих друг за другом ячеек – байтов. В этих ячейках хранятся нули и единицы, которые могут быть чем угодно: буквами, цифрами или выполняемыми компьютером командами. Представим себе, что компьютерная программа написана на заборе, а роль процессора играет образцовый брат Тома – Сид. Том сидит на бочке и жует яблоко, а Сид отправляется к тому месту забора, где записана первая команда. Стоит еще раз подчеркнуть: в памяти компьютера, как и на заборе, хранятся последовательности нулей и единиц. Поэтому нужно заранее знать, с какой ячейки (байта)[1] начинается программа, чтобы не перепутать команды процессора и данные. Итак, предположим, что команда начинается с 31-го байта, то есть с 241-й доски забора. Подойдя к ней, Сид ищет число, там записанное, в специальной справочной таблице, которую вынужден носить с собой. Из этой таблицы он узнает, что делать дальше. Может, например, оказаться, что прочитанный Сидом байт – лишь часть команды процессора, и чтобы выполнить ее, необходимо знать содержимое нескольких следующих ячеек. Команды, выполняемые Сидом, весьма разнообразны. Простейшая команда просто велит ему перейти к другой ячейке. Если ее номер равен 20, Сиду нужно будет сделать несколько шагов к началу забора, а если это 10000-й байт – ему придется мчаться к самому его концу. Команда перехода может быть условной, например, Сид перейдет к ячейке 20 лишь в том случае, если число, хранящееся в пятнадцатом байте, больше нуля. Представим себе, что перед выполнением программы в пятнадцатой ячейке хранится число 10. Раз оно больше нуля, Сид перейдет к двадцатому байту, выполнит команды, записанные в ячейках с номерами 21¸30, и, если содержимое 15-й ячейки не изменилось, 31-й байт вновь отошлет его назад, и так он будет крутиться, пока хватит сил. Если же команды, хранящиеся в байтах 21¸30, после многих пробежек Сида запишут нуль в ячейку 15, тот вместо двадцатого байта перейдет к следующей команде, начало которой хранится в ячейке 32. Иными словами, Сид будет выполнять команды последовательно, одну за другой, пока ему не прикажут перейти к иной ячейке, и после очередной пробежки вдоль забора он снова начнет выполнять команды последовательно. И так будет продолжаться до тех пор, пока он не наткнется на команду «Стоп». Впрочем, еще раньше он может встретить число, которого нет в его таблице, или же предписание перейти к 1000000-й доске забора, в то время как в нем их всего 100000. И тогда Сид застынет в недоумении или побежит жаловаться Тому. А когда такое случается с настоящим компьютером, на экране возникает сообщение: «Программа выполнила недопустимую операцию и будет закрыта». Тема 1. Устройство компьютера. Оперативная память, процессор, регистры процессора. Аппаратный стек 1.1. Устройство компьютера Компьютер - это универсальный исполнитель, который умеет управлять другими исполнителями и обладает собственной внутренней памятью. Запись алгоритма для компьютера называется программой. Все современные компьютеры построены по так называемой фон-Неймановской архитектуре: программа хранится в памяти компьютера, так же как и данные. Компьютер построен из следующих составных частей: · процессор - это основа любого компьютера, его мозг. Процессор производит все вычисления и отдает команды всем остальным компонентам компьютера; · оперативная память также является обязательной составной частью любого компьютера. Оперативная память (RAM - Random Access Memory) хранит как программу, так и данные (т.е. значения переменных). Часть памяти может быть защищена от записи и хранится в специальной микросхеме (ПЗУ - постоянное запоминающее устройство или ROM - Read Only Memory). Обычно в ПЗУ лежит программа первоначальной загрузки и базовая система ввода-вывода (BIOS); · шина - это канал передачи команд и данных между всеми составными частями компьютера. В компьютере могут быть одна или несколько шин. Все устройства подключаются к шине параллельно, т.е. порядок подключения не важен, а количество проводов не зависит от количества подключенных устройств. Порядок передачи команд и данных определяется протоколом работы шины, т.е. четко описанным набором соглашений, принятым, как правило, в виде международного стандарта. Каждое устройство подключается к шине с помощью контроллера, который осуществляет перевод с языка сигналов, передаваемых по шине, на язык команд конкретного устройства; · внешние устройства подключаются к шине компьютера. Наиболее распространенные внешние устройства - это жесткий диск, клавиатура, монитор, сетевая карта, модем и т.п. Ни одно из них не является обязательным, как показывает пример компьютера, управляющего автомобильным двигателем со впрыском топлива. Но какие-то внешние устройства всегда присутствуют, поскольку через них осуществляется связь компьютера с внешним миром. Рассмотрим каждую из составляющих частей компьютера более подробно. 1.2. Оперативная память Элементарной единицей памяти всех современных компьютеров является байт, состоящий из восьми двоичных разрядов. Каждый байт имеет свой адрес. Память, с логической точки зрения, можно рассматривать как массив байтов: можно прочесть или записать байт с заданным адресом. Содержимое байта трактуется либо как неотрицательное целое число в диапазоне от 0 до255, либо как число со знаком в диапазоне от -128 до 127. Однако физически при работе с памятью по шине передаются не отдельные байты, а машинные слова. В 32-разрядной архитектуре машинное слово — это четыре подряд идущих байта, при этом адрес младшего байта кратен четырем. (В 64-разрядной архитектуре машинное слово состоит из восьми байтов.) Машинное слово — это наиболее естественный элемент данных для процессора. Машинное слово содержит целое число, которое можно рассматривать либо как беззнаковое в диапазоне от 0 до 232 - 1, либо как знаковое в диапазоне от -2 31 до 231 - 1. Адрес памяти также представляет собой машинное слово. Принято нумеровать биты внутри машинного слова (как и внутри байта) справа налево, начиная с нуля и кончая 31. Младший бит имеет нулевой номер, старший, или знаковый, бит — номер 31 . Младшие биты числа находятся в младших битах машинного слова. Существуют два способа нумеровать байты внутри машинного слова. В соответствии с этим все процессоры разделяются на два типа: · Big Endian - байты внутри машинного слова нумеруются слева направо. Таковы процессоры Motorola, Power PC. Байты в архитектуре Big Endian удобно представлять записанными слева направо. При этом старшие биты целого числа располагаются в байте с младшим адресом. · Little Endian - байты внутри машинного слова нумеруются справа налево. Таковы процессоры Intel 80x86, Alpha, VAX и др. Байты в архитектуре Little Endian следует представлять записанными справа налево. При этом старшие биты целого числа располагаются в байте со старшим адресом. Архитектура Big Endian была популярна в середине XX века. К концу 70-х годов программисты осознали, что Little Endian-архитектура гораздо удобнее. Например, один из аргументов в пользу Little Endian заключается в том, что целое число, занимающее машинное слово с адресом n, и байт с тем же адресом содержат одно и то же значение (конечно, если оно не превышает 255). В случае Big Endian это не так: например, если целое число с адресом n содержит число 17, то байт с адресом n содержит 0; или если целое число содержит отрицательное значение -77, то байт с адресом n содержит отрицательное значение -1. При небрежном программировании это порождает массу ошибок. Поэтому большинство современных процессоров построены по архитектуре Little Endian. Тем не менее многие компьютерные протоколы ориентируются на Big Endian, поскольку они были приняты достаточно давно. Например, все протоколы сети Internet передают данные в формате Big Endian, т.к. они были разработаны в 70-х годах XX века. На машинах с архитектурой Little Endian приходится переставлять байты внутри слова перед отправкой IP-пакета в сеть или при получении IP-пакета из сети. 1.3. Процессор Процессор является основой любого компьютера. Это большая микросхема, содержащая внутри себя сотни тысяч или даже миллионы элементов. Современные процессоры чрезвычайно сложны и могут содержать несколько уровней построения и описания. Так, можно различать внешние команды процессора в том виде, в котором они используются в программах и записываются в оперативной памяти, и внутренний микрокод, применяемый для реализации внешних команд. Процессор может содержать внутри себя устройства, предназначенные для ускорения работы, — конвейер команд, устройство опережающей выборки из памяти, кеш-память и т.п. Рассмотрим лишь самые общие принципы построения и работы процессора, которые одинаковы как для примитивных, так и для самых современных процессоров. Любой процессор имеет устройство, выполняющее команды, и собственную внутреннюю память, реализованную внутри микросхемы процессора. Она называется регистрами процессора. Имеется 3 типа регистров: · общие регистры хранят целые числа или адреса. Размер общего регистра совпадает с размером машинного слова и в 32-разрядной архитектуре равен четырем байтам. Число общих регистров и их назначение зависит от конкретного процессора. В большинстве Ассемблеров к ним можно обращаться по именам R0, R1, R2, ...Среди общих регистров имеются регистры специального назначения: указатель стека SP (Stack Pointer), счетчик команд PC (Program Counter) и др.; · регистр флагов содержит биты, которые устанавливаются в единицу или в ноль в зависимости от результата выполнения последней команды. Так, бит Z устанавливается в единицу, если результат равен нулю (Zero), бит N — если результат отрицательный (Negative), бит V — если произошло переполнение (oVerflow), бит С - если произошел перенос единицы из старшего или младшего разряда (Carry), например, при сложении двух целых чисел или при сдвиге. Значения битов в регистре флагов используются в командах условных переходов; · плавающие регистры содержат вещественные числа. В простых процессорах аппаратная поддержка арифметики вещественных чисел может отсутствовать. В этом случае плавающих регистров нет, а операции с вещественными числами реализуются программным путем. Команды, или инструкции, процессора состоят из кода операции и операндов. Команда может вообще не иметь операндов или иметь один, два, три операнда. Команды с числом операндов большим трех встречаются лишь в процессорах специального назначения (служащих, например, для обработки сигналов) и в обычных архитектурах не используются. Чаще всего применяются двухадресные и трехадресные архитектуры: к двухадресным относятся, к примеру, все процессоры серии Intel 80x86, к трехадресным — серии Motorola 68000. В двухадресной архитектуре команда сложения выглядит следующим образом: add X, Y что означает X = X + Y, т.е. один из аргументов команды является одновременно и ее результатом. Этот аргумент называется получателем (destination). Аргумент, который не меняется в результате выполнения команды, называется источником (source). Среди программистов нет единого мнения о том, в каком порядке записывать аргументы при использовании Ассемблера, т.е. в символической записи машинных команд. Например, в Ассемблере "masm" фирмы IBM для процессоров Intel 80x86 получатель всегда записывается первым, а источник вторым. Ассемблер "masm" используется в операционных системах MS DOS и Windows. В Ассемблере "as", который входит в состав компилятора "gcc" и используется в системах типа Unix (Linux и т.п.), получатель всегда является последним аргументом. Та же команда сложения записывается в "as" как add Y, X что означает сложить Y и X и результат записать в X. В трехадресной архитектуре команда сложения имеет 3 операнда: add X, Y, Z Получателем в трехадресной архитектуре обычно является третий аргумент, т.е. в данном случае сумма X+Y записывается в Z. Операндами команды могут быть регистры или элементы памяти. В действительности, конечно, процессор всегда сначала копирует слово из памяти в регистр, который может быть либо явно указан в команде, либо использоваться неявно. Операция всегда выполняется с содержимым регистров. После этого результат может быть записан в память либо оставлен в регистре. Например, при выполнении команды увеличения целого числа на единицу int X в случае, когда операнд X является словом оперативной памяти, содержимое слова X сначала неявно копируется во внутренний регистр процессора, затем выполняется его увеличение на единицу, и после этого увеличенное значение записывается обратно в память. Имеется несколько способов задания операнда, находящегося в оперативной памяти, они называются режимами адресации. Это · абсолютная адресация - когда в команде указывается константа, равная адресу аргумента; · косвенная адресация - когда в команде указывается регистр, содержащий адрес аргумента; · относительная адресация - адрес аргумента равен сумме содержимого регистра и константы, задающей смещение; · индексная адресация с масштабированием - адрес аргумента равен сумме содержимого базового регистра, константы, задающей смещение, а также содержимого индексного регистра, умноженного на масштабирующий множитель. Масштабирующий множитель может принимать значения 1, 2, 4, 8. Этот режим удобен для обращения к элементу массива. Бывают и другие, более изощренные, режимы адресации, когда, например, адрес аргумента содержится в слове, адрес которого содержится в регистре (так называемая двойная косвенность). 1.4. Алгоритм работы компьютера Среди всех регистров процессора в любой архитектуре всегда имеется два выделенных регистра: это регистр PC, что означает Program Counter, по-русски его называют счетчикомкоманд, и регистр SP — Stack Pointer, т.е. указатель стека. Иногда регистр PC обозначают как IP, что означает Instruction Pointer, указатель инструкции. (Команды процессора часто называют инструкциями.) В фон-Неймановской архитектуре, по которой построены все современные компьютеры, программа, состоящая из машинных команд, содержится в оперативной памяти. Регистр PC всегда содержит адрес команды, которая будет выполняться на следующем шаге. Алгоритм работы процессора выглядит следующим образом: цикл до бесконечности выполнять | прочесть команду с адресом PC из оперативной памяти; | увеличить содержимое PC на длину прочитанной команды; | выполнить прочитанную команду; конец цикла В простейшем случае, когда выполняется линейный участок программы, команды выбираются из памяти и выполняются последовательно, а содержимое регистра PC монотонно возрастает. Выполнение команды, однако, может приводить к изменению регистра PC. Таким образом организуются безусловные и условные переходы в программе, нарушающие последовательный порядок выполнения команд. С помощью команд условных и безусловных переходов реализуются конструкции ветвления и цикла. Команда перехода представляет собой либо прибавление константы к содержимому PC (константа может быть положительной или отрицательной), либо загрузку в PC адреса элемента памяти со всеми возможными режимами адресации. Первый способ используется для реализации переходов внутри подпрограммы (внутри функции в терминах языка Си), второй – для перехода к подпрограмме. Впрочем, гораздо чаще в последнем случае используется команда вызова подпрограммы, которая дополнительно запоминает точку возврата в регистре или в аппаратном стеке. 1.5. Аппаратный стек Стек – это запоминающее устройство, из которого элементы извлекаются в порядке, обратном их помещению в стек. Стек можно представить как стопку листов бумаги, на каждом из которых записан один из сохраняемых элементов. На вершине стека находится последний запомненный элемент. Стек можно представить в виде трубки с запаянным дном, помещенной вертикально. Верхний конец трубки открыт, в него можно добавлять, или, как говорят, заталкивать элементы. Общепринятые английские термины в этом плане очень красочны, операция добавления элемента в стек обозначается push, в переводе «затолкнуть, запихнуть». Новый добавляемый элемент проталкивает элементы, помещенные в стек ранее, на одну позицию вниз. При извлечении элементов из стека они как бы выталкиваются вверх, по-английски pop («выстреливают»). Аппаратный стек реализуется на базе оперативной памяти. Элементы стека расположены в оперативной памяти, каждый из них занимает одно слово. Регистр SP в любой момент времени хранит адрес элемента в вершине стека. Стек растет в сторону уменьшения адресов: элемент, расположенный непосредственно под вершиной стека, имеет адрес SP + 4 (при условии, что размер слова равен четырем байтам), следующий SP + 8 и т.д. 1.6. Команды вызова подпрограммы и возврата Одно из главных назначений аппаратного стека — поддержка вызовов подпрограмм. При вызове подпрограммы надо сохранить адрес возврата, чтобы подпрограмма могла по окончанию своей работы вернуть управление вызвавшей ее программе. В старых архитектурах, в которых аппаратный стек отсутствовал (например, в компьютерах IBM 360/370), точки возврата сохранялись в фиксированных ячейках памяти для каждой подпрограммы. Это делало невозможнойрекурсию, т.е. повторный вызов той же подпрограммы непосредственно из ее текста или через цепочку промежуточных вызовов, поскольку при повторном вызове старое содержимое ячейки, хранившей адрес возврата, терялось Во всех современных архитектурах точка возврата сохраняется в аппаратном стеке, что делает возможным рекурсию, а также параллельное выполнение нескольких легковесных процессов (нитей). Методические указания: § читать учебное пособие |