Этапы обработки программы на компьютере

Трансляция

Редактирование

Загрузка

Выполнение

текст маш.код отн.адреса абс.адреса

 

ИМ ОМ ЗМ память

 

результаты

 

периферия

Терминология

Исходные модули (ИМ) – тексты программы на алгоритмическом языке.

Объектные модули (ОМ) – оттранслированные тексты программы на машинном языке в относительных адресах.

Загрузочный модуль (ЗМ) – единая готовая к выполнению программа, по-прежнему, в относительных адресах.

Рассмотрим более подробно каждый этап.

Трансляция

В целях снижения уровня сложности разработки большинство программ разбивается на отдельные части, выполняющие одну или более функций. Эти части называют модулями. Каждый модуль может транслироваться отдельно, независимо от других модулей программы. Это позволяет выполнять процесс разработки поэтапно. Модуль до трансляции называют исходным, после трансляции – объектным. Каждый модуль может состоять из одной или более процедур. В любой программе существует процедура, в которой начинается выполнение и в которой в большинстве случаев работа программы заканчивается. Такую процедуру называют главной ( main ).

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

main (главная процедура)

процедура

процедура

процедура

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

Для обозначения объектов программы на алгоритмическом языке используется понятие имя.

Пример. Возможные имена.

x matrix Height Copy1 Sum

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

ИМ: имя   ОМ: адрес

Область памяти

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

Наиболее распространенными языками программирования являются: FORTRAN ( Formula Translator – переводчик формул), PL/1 ( Programming Language/1 – язык программирования 1), C, С# и C++, Pascal, BASIC ( Beginner's All-purpose Symbolic Instruction Code – универсальный язык символического кодирования для начинающих), Java.

Редактирование связей (компоновка)

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

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

Загрузка

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

- определение и выделение необходимой памяти под программу и данные;

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

- передача управления первой инструкции главной процедуры.

Выполнение

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

Типы вычислительных процессов

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

Следование

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

Пример.

y=a+b z=2*y*y+a*y+b print(z)

Развилка

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

если < условие> то

< действие 1>

[ иначе

< действие 2> ]

Конец если

Как < действие 1>, так и < действие 2> могут являться комбинацией всех 3 базовых структур, поэтому с помощью данной структуры можно организовать более двух ветвей алгоритма. Квадратные скобки вокруг альтернативы иначе означают необязательность этой ветви.

Пример. Найти x =max( a, b ), y =min( a, b ).

Вариант 1.

Вариант 2.

если a> b то

x=a

y=b

Иначе

x=b

y=a

Конец если

x=a

y=b

если a< b то

x=b

y=a

Конец если

Цикл

Это последовательность действий, повторяющаяся до тех пор, пока выполняется некоторое условие. Цикл, в общем случае, состоит из 4 блоков: инициализации цикла; логического блока, содержащего условие продолжения или окончания цикла; тела цикла – последовательности инструкций, выполняемых при каждом повторении, и блока, в котором производится изменение условия продолжения (или окончания) цикла. В зависимости от того, как расположен блок условия по отношению к телу цикла, различают цикл с предусловием (условие проверяется до выполнения тела цикла) и цикл с постусловием (условие проверяется после выполнения тела цикла). В первом случае тело цикла может ни разу не выполниться, во втором – оно выполнится хотя бы 1 раз. На рисунке показаны обобщенные блок-схемы цикла каждого вида. В некоторых частных случаях отдельные блоки могут отсутствовать.

инициализация

инициализация

тело цикла

тело цикла

изменение условия (параметра цикла)

изменение условия (параметра цикла)

Цикл с предусловиемЦикл с постусловием

Пример. Сортировка массива методом " пузырька" {a_i}, i=1...n.

k=1 Исходный массив: {24, -12, 0, 123, -2, 57}

пока k> 0 делать Результат: {-12, -2, 0, 24, 57, 123}

k=0

для i от 1 до n-1 выполнить

если a_i > a_i+1 то

b=a_i

a_i=a_i+1

a_i+1=b

k=1

Конец если

Конец для

Конец пока

Данные

Данные – это информация, обрабатываемая программой.

Системы счисления

Любое число x в десятичной системе счисления может быть представлено в виде: xà D_m-1*10^m-1+D_m-2*10^m-2+...+D₁*10+D₀+D_-1*10^-1+D_-2*10^-2+... _, где D_m-1, D_m-2, D_1, D₀, D_-1, D_-2 – цифры, составляющие число.

Пример.

125.478 = 1*100+2*10+5+4*10^-1+7*10^-2+8*10^-3

Число различных цифр, образующих систему, называется ее основанием. Любое число может быть записано в системе счисления с основанием, отличным от 10, причем между целыми числами, записанными в различных системах с целыми положительными основаниями, существует взаимно однозначное соответствие. Следовательно, перевод целого числа из одной системы счисления в другую осуществляется точно, без погрешности. Ниже приведена таблица первых 16 целых чисел для систем с основаниями 10, 2, 8, 16, которые применяются в вычислительной технике.

10: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

-------------------------------------------------------------------------------------------------

2: 0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111

-------------------------------------------------------------------------------------------------

8: 0 1 2 3 4 5 6 7 10 11 12 13 14 15 16 17

-------------------------------------------------------------------------------------------------

16: 0 1 2 3 4 5 6 7 8 9 A B C D E F

-------------------------------------------------------------------------------------------------

Перевод целого числа в другую систему счисления выполняется последовательным делением на ее основание. Наиболее удобно использовать для этого основание 8. Заменив в полученном значении каждую 8-ричную цифру ее двоичным представлением, получим то же самое целое число в двоичной системе.

Пример. 459₁₀ = 713₈ = 111 001 011₂

459|8

------------

40 |57|8

------------

59 56 7 à 713

56 1

----

3

Обратный перевод показан ниже.

111 001 011₂ à 713₈ à 7*64+1*8+3=448+8+3=459₁₀

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

0.15 0.00(1001)

------ 1/8+1/64+1/128+...à 0.1250+0.0156+0.0078+...»0.1484

0.3

------.

0.6

-----

1.2-1

-----

0.4

-----

0.8

-----

1.6

-----

Типы и совокупности данных

Скалярная переменная – это переменная, имеющая в текущий момент времени 1 значение.

Тип переменной – это множество значений, которые может принимать переменная во время выполнения программы.

Остановимся на наиболее распространенных типах данных.

Целые

Диапазон представления определяется разрядностью процессора. Обычно используются 2 модификации целых размером в 32 бита – диапазон представления: | x |< 2³¹ (чуть больше 9 десятичных цифр) и 16 бит – диапазон: | x |< 2¹⁵=32768. Все операции над целыми выполняются без погрешности.

Вещественные

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

Данные хранятся в памяти в форме с плавающей точкой. Число имеет вид:

x = m * B^e,

где m – мантисса,

B – основание системы счисления (10|2|8|16),

e – порядок.

Пример.

-2.73*10^-15=-273*10^-17

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

0.1< =| m |< 1 или 1< =| m |< 10

Логические

Эти данные могут принимать только 2 значения: True – истина или False – ложь и используются для записи условий. Например, выражение a< b при a=3, b=5 принимает значение True, а при a=7, b=0 значение False.

Строки

Представляют собой последовательности символов фиксированной или переменной длины.

Пример.

" hard disk" " Привет всем! "

Совокупности данных

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

Пример. Система линейных алгебраических уравнений.

a₁₁x₁+a₁₂x₂=b₁

a₂₁x₁+a₂₂x₂=b₂

{a_ij, i, j=1, 2} – массив коэффициентов, {x_k, k=1, 2} – массив корней, {b_m, m=1, 2} – массив свободных членов.

Количество индексов определяет размерность массива. Массивы с размерностью более 1 называют многомерными. Расположение в памяти элементов многомерного массива может быть разным: a₁₁, a₁₂, a₂₁, a₂₂ – лексикографическое (по строкам) в большинстве языков, a₁₁, a₂₁, a₁₂, a₂₂ - по столбцам ( Fortran ).

В тексте программы доступ к элементам массива осуществляется с помощью переменной с индексами.

Пример.

a_i+1, _j-1. При i=2, j=4 это будет элемент a₃, ₃.

Пример. Структура – cтрока ведомости по зарплате.

таб.номер фамилия и.о. сумма вычеты

236 Иванов П.А. 37605.00 5264.70

 

ЭЛЕМЕНТЫ ЯЗЫКА

История языков С и Basic

Язык C был разработан в 1972 г. Д.Ритчи в AT& T Bell Laboratories на основе языков BCPL (автор -М. Ричардсон) и B (автор - К. Томпсон). В него вошли понятия ранее созданных языков PL/1, Fortran и некоторых других. Целью было создание компактного универсального языка программирования, который бы включал как средства для написания управляющих программ (драйверов) периферийных устройств компьютера, так и для представления абстрактных понятий, характерных для алгоритмических языков высокого уровня. Дальнейшее развитие язык C получил в той же компании Bell Labs, где в 1980 г. Б. Страуструп разработал язык, который он назвал C с классами, основным нововведением которого стало добавление понятий класса и объекта. Принятый сейчас в мире термин C++ ввел в 1983 г. Р. Маскити. Язык C++ положил начало развитию нового направления в программировании – объектно-ориентированному подходу (ООП). В настоящее время наиболее распространенными средами для разработки программ для этих языков являются Borland C++, Visual Studio и Turbo C++.

Язык Basic был создан в 1965 г. сотрудниками Дартмутского колледжа под руководством Дж. Кемени и Т. Курца для пользователей-непрофессионалов. В связи с переходом на персональные компьютеры в 1975 г. фирмой MicroSoft была разработана новая версия этого языка. В настоящее время в состав языка Basic включены средства для реализации визуального объектно-ориентированного программирования, и этот язык уже никак нельзя назвать языком для начинающих. Тем не менее он более прост для изучения, чем языки C и C++. В настоящее время существует несколько версий языка Basic. В данном курсе за основу взята версия MS Visual Basic, разработанная для платформы MS.NET Framework и реализованная в средах разработки MS Visual Studio 2008 Express Edition и MS Visual Studio 2010 Professional.

Алфавит

Алфавит языков C и Basic составляют латинские буквы, арабские цифры и спецсимволы. Все символы алфавита кодируются целыми значениями в диапазоне от 0 до 127 в соответствии с международной таблицей ASCII ( American Standard Code for Information Interchange – американская стандартная кодировочная таблица для печатных символов и некоторых специальных кодов). Существуют также таблицы локальных кодировок, включающие буквы национальных алфавитов. Символы этих таблиц имеют коды в диапазоне от 128 до 255. Буквы национальных алфавитов могут использоваться только в данных и в комментариях к программе, но не при обозначении объектов программы. Существуют и русифицированные среды разработки, например, Visual Basic for Applications (VBA), который входит в состав пакета MS Office, но это скорее исключение, чем правило.

В языке C прописные и строчные буквы считаются разными символами, в языке Basic они не различаются.

Идентификаторы

Идентификатор: = < имя> |< ключевое слово>

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

Правило (формат) записи имени:

{< буква> |_}[< буква> |< цифра> |_]...

Для усвоения метаобозначений дадим словесное определение этому правилу. Имя – первый символ: < буква> или знак подчеркивания, последующие (если они есть): < буква> или < цифра> или знак подчеркивания.

Пример.

STEP Kod A1 player NextStep For While

Замечание. Не рекомендуется использовать имена, начинающиеся с _ или __, поскольку транслятор применяет некоторые из таких в качестве служебных.

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

С

Стандарт языка не ограничивает длину идентификатора, но используются только первые 32 или 64 символа имени. Ключевые слова записываются строчными буквами.

Basic

Максимальная длина имени – 1023 символа. В языке Visual Basic не различаются строчные и прописные буквы.

Знаки разрядки

Применяются для удобочитаемости текста программы. К ним относят: пробел, табуляцию (клавиша Tab ), переход на новую строку (клавиша Enter ). Могут ставиться везде, но не внутри идентификаторов и знаков составных операторов.

Комментарии

Комментарии позволяют ввести пояснения к фрагменту программы.

С

12345678910Следующая ⇒

Поделиться: