Вопрос 12. Компиляция и связывание.

Вопрос 11. Понятие эффективности и сложности алгоритмов и программ.

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

Оценка сложности зависит от:

· времени, затраченного на выполнение алгоритма

· объема памяти, требуемой для хранения исходных данных задачи.

Временная сложность алгоритма – это время T, необходимое для его выполнения в зависимости от исходных данных. T = k·t, где:

· k – кол-во вычислительных действий,

· t – время выполнения одного действия.

· T(n) – зависимость времени от объема входных данных.

· n – это размерность задачи (для линейного массива – размер массива).

Поведение T при увеличении n называется теоретической сложностью – O(f(n)).

Сравнительная оценка сложности алгоритмов:

 

Сложность O(f(n))	Тип зависимости	Значение при n=210
O(n)	Линейная
O(n·log2n)	Логарифмическая
O(n2) O(n3)	Полиномиальная	» 106 » 109
O(2n)	Экспоненциальная	» 10300

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

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

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

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

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

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

1) высокая скорость выполнения готовой программы

2) независимость исполняемого кода от среды программирования

3) возможность распространять программы без исходных текстов

Основные фазы компиляции:

1) Процесс компиляции разбивается на несколько этапов (фаз), на каждом из которых решаются вполне независимые задачи

2) Входными данными для первой фазы является исходная программа

3) Результат работы каждой фазы является входными для последующих фаз

4) Результатом работы последней фазы является исполняемая программа

Этапы компиляции:

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

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

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

Основными атрибутами объектов являются:

1) Тип данных

2) Область видимости

Основные виды проверок:

1) Проверка соответствия типов

2) Проверка правильности употребления имен

3) Проверка передачи управления

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

Генерация промежуточного представления. Выполняется для упрощения последующих этапов.

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

Критерии оптимизации:

1) быстродействие

2) объем машинного кода

3) объем используемой памяти и т. п.

Глобальная оптимизация анализирует (и преобразовывает) структуру всей программы. Локальная оптимизация анализирует (и преобразовывает) небольшие фрагменты программы.