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

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

Первоначально в тексте исходной программы лексический анализатор выделяет последовательность символов, которая по его предположению должна быть словом в программе, т.е. лексемой. Может выделяться не вся последовательность, а только один символ, который считается началом лексемы. Это наиболее ответственная часть работы лексического анализатора. Более просто она реализуется для тех языков программирования, в которых слова в программе отделяются друг от друга специальными разделителями (например, пробелами), либо запрещено использование служебных слов в качестве переменных, либо классы лексем опознаются по вхождению первого (последнего) символа лексемы.

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

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

метод линейного списка;

метод упорядоченного списка;

метод расстановки и другие.

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

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

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

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

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

10 --- ключевое слово; 20 -- разделитель; 30 -- идентификатор; 40 -- константа.

Вход лексического анализатора имеет вид:

Program primer;

var x,y,z : real;

begin

x:=5;

y:=5;

z:=x+y;

end;

Внутренние таблицы лексического анализатора имеют вид:

Таблица ключевых слов

№ п/п	Ключевое слово
1	Program
2	Begin
3	End
4	For
5	Real
6	Var

Таблица идентификаторов

№ п/п	Идентификатор
1	Primer
2	x
3	y
4	z

Таблица разделителей

№ п/п	Разделитель
1	;
2	,
3	+
4	-
5	/
6	*
7 n	:
8	=
9	.

Таблица констант

№ п/п	Константа
1	5

Выходом лексического анализатора является следующий дескрипторный текст:

(10.1)(30,1) (20,1)

(10,6) (30,2) (20,2) (30,3) (20,2) (30,4) (20,7) (10,5) (20,1) (10,2)

(20,7) (20,8) (40,1) (20,1)

(20,7) (20,8) (40,1) (20,1)

(20,7) (20,8) (30,2) (20,3) (30,3) (20,1)

(10,3) (20,1).

Однако, основной задачей ЛА является не порождение лексических единиц, а их распознавание. Математической моделью процесса распознавания регулярного языка является вычислительное устройство, которое называется конечным автоматом (КА). Термин «конечный» подчеркивает то, что вычислительное устройство имеет фиксированный и конечный объем памяти и обрабатывает последовательность входных символов, принадлежащих некоторому конечному множеству. Существуют различные типы КА, если функцией выхода КА (результатом работы) является лишь указание на то, допустима или нет входная последовательность символов, такой КА называют конечным распознавателем. Именно этот тип КА в дальнейшем мы и будем рассматривать.

Конечный автомат описывается следующим образом:

А = <V, Q, 8, q₀, F>,

где V = {а₁, а₂,..., а_m} -- входной алфавит (конечное множество символов);

Q ⁼ { q₀, q₁,..., q_n-1} -- алфавит состояний (конечное множество символов);

8: Q х V -> Q -- функция переходов;

q₀ Q -- начальное состояние конечного автомата;

F Q -- множество заключительных состояний.

На содержательном уровне функционирование КА можно представить следующим образом.

Имеется бесконечная лента, разбитая на ячейки, в каждой из которых может находиться один символ из V. На ленте записана цепочка а V*. Ячейки слева и справа от цепочки не заполнены. Имеется конечное устройство управления (УУ) с читающей головкой, которое может последовательно считывать символы с ленты, передвигаясь вдоль ленты слева направо. При этом УУ может находиться в каком-либо одном состоянии из Q. Начинает свою работу УУ всегда в начальном состоянии q_o Q, а завершает в одном из заключительных состояний F. Каждый раз, переходя к новой ячейке на ленте, УУ переходит в соответствии с функцией переходов. Функцию переходов КА можно представить различными способами. Основные из них: совокупность команд; диаграмма состояний; матрица переходов.

Для КС-языков устройствами распознавания языка являются магазинные автоматы (или, иначе, автоматы с магазинной памятью, МП-автоматы).

Автомат имеет конечное множество состояний, конечное множество входных символов и неограниченную снизу вспомогательную ленту (называемую лентой магазинной памяти или магазинной памятью). «Дно» магазина (самый нижний символ) отмечается специальным символом, называемым маркером дна. Магазинная память определяется свойством «первым введен -- последним выведен». При записи символа в магазин, его содержимое сдвигается на одну ячейку «вниз», а на освободившееся место записывается требуемый символ. Обработку входной цепочки МП-автомат начинает в некотором выделенном состоянии при определенном содержимом магазина. Затем автомат выполняет операции, задаваемые его управляющим устройством. При этом выполняется либо завершение обработки, либо переход в новое состояние. Если синтаксический анализатор выполняется переход, то он дает новый верхний символ магазина, новый текущий символ, автомат переходит в новое состояние и цикл работы автомата повторяется. Итогом работы МП-автомата при обработке лексемы является ответ на вопрос: «принадлежит данная лексема данному языку или нет?». В общем виде может быть предложен следующий порядок конструирования ЛА:

Выделить во входном языке множество классов лексем.

Построить для каждого класса лексем грамматику.

Построить модель распознавателя.

Выбрать формат кодов лексем-дескрипторов.

2.4 Синтаксический анализ

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

Рассмотрим пример построения АСД для выражения: (a + b) * (c + d):



Размещено на http://www.allbest.ru/

Рисунок 2.1 - АСД для выражения (a + b) * (c + d)

Чаще в АСД, внутренние узлы соответствуют операциям, а листья - операндам. Листья связаны с записями в таблице идентификаторов.

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

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

Пример

Построим грамматику для целых десятичных чисел:

TF|TF - правило построения числа

F 0 |1 |2 |…| 9

F - цифра

Произвольная цепочка вывода будет выглядеть:

S-T-TF-TFF-FFF

Дерево вывода можно построить двумя способами: «сверху-вниз» и «снизу-вверх». Поскольку все известные языки программирования используют нотацию записи слева-направо, компилятор читает программу слева-направо и сверху-вниз.

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

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

Синтаксические деревья содержат информацию о взаимосвязи операций и операндов. Это машинно-независимая форма внутреннего представления программы, является сложной связной структурой. На следующем шаге, синтаксические деревья преобразуются в другие формы (тетрады, триады, ассемблерный код и др.)

Примеры представления синтаксического дерева в виде триады:

A = B * C + D - B * 10

1) * (B, C)

2) + (^1, D)

3) * (B, 10)

4) - (^2, ^3)

5) = (A, ^4)

Знак ^ означает ссылку операнда одной триады на результат другой.

Пример представления синтаксического дерева в виде триады.

1) * (B, C, T1 (результат))

2) + (T1, D, T2)

3) * (B, 10, T3)

4) - (T2, T3, T4)

5) = (T4, A)

2.5 Семантический анализ

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

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

- таблицы идентификаторов;

- результаты разбора синтаксических конструкций.

Каждый язык программирования имеет четко заданные семантические соглашения, например:

1) каждый идентификатор должен быть описан не более одного раза, должен быть описан до его условия;

2) типы переменных в выражениях должны быть согласованы;

3) при вызове процедуры функции, число и типы фактических параметров должны быть согласованы с числом и типом формальных параметров.

Например:

sum (int x, int y)

sum (2,3);

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

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

2.6 Распределение памяти

Синтез объектной программы начинается с распределения памяти для программных объектов. Исходными данными для распределения памяти является таблица идентификаторов. Размер памяти, выделяемый под лексические единицы базовых типов, зависит от вершин компилятора.

Размер базового типа int в языке СИ для архитектуры компьютеров на базе 16-ти разрядного процессора составляет 2 байта; 32-х разрядного - 4 байта. Глобальные статические переменные хранятся в области глобальных статических переменных. Память выделяется один раз при инициализации результирующей программы. Локальная область памяти выделяется в начале выполнения некоторого объекта (функции), и освобождается по завершению выполнения.

Статическая область памяти - область памяти, размер которой известен на этапе компиляции.

Динамическая область памяти - область памяти, размер которой на этапе компиляции неизвестен.

Динамические области памяти можно разделить на:

1) динамическая память, выделяемая пользователем;

2) динамическая память, выделяемая компилятором.

В 1-ом случае это осуществляется за счет использования специальных функций (new, delete).

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

Компилятор отвечает за порождение кода, своевременное выделение и освобождение памяти.

2.7 Генерация кода

Задачей генератора кода является построение эквивалентной машинной программы. На этом этапе происходит замена операторов языка высокого уровня инструкциями ассемблера, а затем машинными кодами. Как правило, компилятор осуществляет генерацию результирующего кода поэтапно: - выделяет синтаксическую конструкцию, порождает фрагмент кода. Чтобы компилятор мог построить результирующий код для синтаксической конструкции, используется метод, называемый СУ-переводом (синтаксически управляемый перевод): с каждой вершины абстрактно синтаксического дерева связывается цепочка результирующего кода.

Пример СУ-перевода АСД на язык ассемблера (таблица 2.1).

Таблица 2.1 - Формирование ассемблерного кода

Вид узла	Результирующий ассемблерный код	Примечание
	Mov ax, op2 Mov op1, ax	оp1, op2 - операнды
	Code (узел 2) Mov op1, ax	Code (узел2) - порождаемый код для нижележащего узла

2.8 Оптимизация кода программы

Оптимизация программы - обработка, связанная с переупорядочиванием и изменением операций компилируемой программы с целью получения более эффективной результирующей объектной программы. В качестве показателя эффективности используют 2 критерия:

1) объем необходимой памяти;

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

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

Например, выражение A||B||C||D нет необходимости вычислять, если значение A есть true (заранее известно, что оно истинно).

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

- удаление бесполезных присваиваний;

- исключение лишних операций;

- перестановка операций… и т.д.

Пример 1:

A=B*C;

D=B+C;

A=D*C;

Выражение A=B*C бессмысленно и может быть удалено из программы.

Пример 2:

For i:=1 to 10 do

вegin

D:=B*С;

A[i] :=D + A[i];

end; …

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

D:=B*С;

For i:=1 to 10 do

вegin

A[i] :=D + A[i];

end;...

После оптимизации, операция умножения B на C будет выполнена один раз, а не 10, как в первом случае.

Оптимизация процессов передачи параметров процедуры и функции

Рассмотрим пример распределения памяти при выполнении программы, функций программы.

...

int sum (int x, int y)

{return (x+y);}

int main () {

int x,y;

cout «введите x,y»;

cin >>x>>y;

Sum (x,y);

Return 0; }

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

Существует ряд методов оптимизации:

1) передача параметров через регистры процессора (register int x;). Данные обрабатываются быстрее, код становится меньше за счет исключения операций со стеком.

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

В СИ есть inline-функции, позволяющие реализовывать данный метод.

inline int sum (…) {…

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

Практически все компиляторы выполняют оптимизацию на этапе генерации кода. Различают 2 основных вида оптимизирующих преобразований:

1) преобразования, не зависящие от объектного языка, не зависящие от архитектуры, на которой будет выполнять программа;

2) преобразования, зависящие от свойств объектного языка, от архитектуры вычислительной машины.

Так, например, при оптимизации может учитываться объем кэш-памяти, методы организации конвейерных команд. Эти преобразования являются «ноу-хау» производителей компиляторов.

2.9 Компоновка программ

Многомодульные программы.

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

В Си (Си++) не существует специальных языковых конструкций, которые непосредственно в программе описывали бы ее общую структуру. Структура программы описывается специальными неязыковыми средствами. Межмодульные связи поддерживается специальными файлами. В процессе трансляции программы, исходный код переводится в объектный. Объектный модуль можно выполнять лишь после специальной обработки -> компоновки, которая осуществляется программой-компоновщиком (системной программой). Рассмотрим процесс компоновки:

1) программа строится из конструкций-операторов;

2) операторы включают выражения;

3) выражения состоят из операндов и операций;

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

5) в ходе трансляции устанавливается соответствие между операндами и адресами оперативной памяти.

Задачей компоновщика является согласование адресов во всех фрагментах кода: присвоение каждой программной секции адреса. Компоновщик также добавляет к компонуемой программе коды библиотечных функций. Преобразованная компоновщиком программа называется загрузочной или выполняемой программой.

Модульные программы обычно состоят из нескольких независимых частей кода (модули). Компилятор обрабатывает каждый модуль независимо, компоновщик объединяет полученные части для создания выполняемого файла.

Компоновка включает в себя следующие этапы:

1) сбор всех модулей из библиотек пользователя, системных библиотек;

2) установка ссылок между модулями;

3) построение загрузочного модуля.

2.10 Загрузчики

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

Список литературы

Основная

1. Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение / Учебник. Изд. С-Петербург, 2002.

2. Иванова Г.С. Программирование на СИ++ / Учебник. Изд. М.: МГТУ им. Н.Э. Баумана, 2002.

Дополнительная

1. Герхард Франкен, Сергей Молявко MS DOS для пользователя.- Киев, 1993.

2. Краковяк С. Основы организации и функционирования ОС ЭВМ.- М.: Мир, 1988.

3. Кейслер С. Проектирование операционных систем для малых ЭВМ.- М.: Мир, 1986.

4. Теренс Чан Системное программирование на СИ++ для Unix./Под ред. Коломыцева, Киев, 1997.

5. Немет Э., Снайдер Г. Unix. Руководство системного администратора.- Киев.: BHV, 1997.

6. Дегтярев Е.К. Введение в Unix.- М.: Память, 1992.

7. Свиридов С.В. Системные вызовы ОС UNIX.-М.:Память, 1992.

8. Страуструн Б. Язык программирования СИ++. Пер с англ.- М.:Радио и связь, 1991.

9. Дунаев С. UNIX-сервер. Настройка, конфигурирование, работа в операционной среде, Internet-возможности: в 2-х томах.Том 1.-М.:Диалог-МИФИ, 1999.

10. Дунаев С. UNIX-сервер. Настройка, конфигурирование, работа в операционной среде, Internet-возможности: в 2-х томах.Том 2.-М.:Диалог-МИФИ, 1999.

11. Шамер Л., Негус К. UNIX (серия «Без проблем»). Пер. с англ. -М.:Бином, 1998.

12. Кейлингерт П. Элементы операционных систем. Введение для пользователей. Пер. с англ. -М.:Мир, 1995.

13. Брой М. Информатика. Структуры систем и системное программирование: в 4-х ч. Пер. с англ.-М.:Диалог-МИФИ, 1996.

14. Персон Р. Windows 95 в подлиннике. Пер. с англ.-СПБ:BHV-Санкт-Петербург, 1996.

15. Такет Д., Барнет С. Специальное издание. Использование LINUX. Пер. с англ.-4-е изд.-К.:, Н.:, СПб.: Издательский дом «Вильямс», 1999.

Приложение А Пример выполнения курсовой работы по дисциплине "Системное программное обеспечение"

Волжский университет имени В.Н.Татищева

Факультет “Информатика и телекоммуникации”

Кафедра “Информатика и системы управления”

КУРСОВАЯ РАБОТА

по дисциплине: “Системное программное обеспечение”

Тема: “Оптимизация кода программы в процессе компиляции”

Тольятти

Волжский университет имени В.Н.Татищева

Факультет “Информатика и телекоммуникации”

Кафедра “Информатика и системы управления”

Специальность:

_____________________________________________________________

ЗАДАНИЕ

на курсовую работу по дисциплине

“Системное программное обеспечение”

Студенту_____________________________________________________

Группа ____________________

Тема курсовой работы______________________________________________________________________________________________________________________________

СОДЕРЖАНИЕ ЗАДАНИЯ

____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Руководитель курсовой работы ______________________ / Трубачева С.И. /

Студент ______________________ / ********* /

Дата выдачи: “ ____ “ __________ 20__ г.

СОДЕРЖАНИЕ

Введение

1 Теоретическая часть

1.1 Процесс компиляции, структура компилятора

1.2 Лексический анализ

1.3 Синтаксический анализ

1.4 Контекстный анализ

1.5 Обработка несовпадающих типов

1.6 Оптимизация кода для повышения эффективности8

1.7 Методы оптимизации кода

1.8 Генерация кода

2 Практическая часть

2.1 Постановка задачи

2.2 Разработка СИ программы

2.3 Разработка алгоритма

Заключение

Список использованных источников

Введение

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

Транслирующие программы делятся на две категории: интерпретаторы и компиляторы.

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

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

1 Теоретическая часть

1.1 Процесс компиляции, структура компилятора

Процесс компиляции разделяется на несколько этапов:

1. Препроцессор - исходная программа обрабатывается путём подстановки имеющихся макросов и заголовочных файлов;

2. Лексический, синтаксический и контекстный анализ - программа преобразовывается в цепочку лексем, а затем во внутреннее представление в виде дерева;

3. Контроль типов и обнаружение ошибок - поиск возникающих ошибок и несоответствия типов;

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

5. Генерация кода - внутреннее представление преобразовывается в блоки команд процессора, которые преобразовываются в ассемблеровский текст или в объектный код;

Рисунок 1.1 - Процесс компиляции программы

6. Ассемблирование - Если генерируется ассемблерный текст, производится его ассемблирование с целью получения объектного кода;

7. Сборка - сборщик соединяет несколько объектных файлов в исполняемый файл или библиотеку.

1.2 Лексический анализ

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

1.3 Синтаксический анализ

Основная задача синтаксического анализа - разбор структуры программы. Как правило, под структурой понимается дерево, соответствующее разбору в контекстно-свободной грамматике языка. В настоящее время чаще всего используется либо LL(1)- анализ (и его вариант - рекурсивный спуск), либо LR(1)-анализ и его варианты (LR(0), SLR(1), LALR(1) и другие). Рекурсивный спуск чаще используется при ручном программировании синтаксического анализатора, LR(1) - при использовании систем автоматизации построения синтаксических анализаторов. Результатом синтаксического анализа является синтаксическое дерево со ссылками на таблицу имен. В процессе синтаксического анализа также обнаруживаются ошибки, связанные со структурой программы.

1.4 Контекстный анализ

На этапе контекстного анализа выявляются зависимости между частями программы, которые не могут быть описаны контекстно-свободным синтаксисом. Это в основном связи "описание- использование", в частности анализ типов объектов, анализ областей видимости, соответствие параметров, метки и другие. В процессе контекстного анализа строится таблица символов, которую можно рассматривать как таблицу имен, пополненную информацией об описаниях (свойствах) объектов.

Основным формализмом, использующимся при контекстном анализе, являются атрибутные грамматики. Результатом работы фазы контекстного анализа является атрибутированное дерево программы. Информация об объектах может быть как рассредоточена в самом дереве, так и сосредоточена в отдельных таблицах символов. В процессе контекстного анализа также могут быть обнаружены ошибки, связанные с неправильным использованием объектов. Затем программа может быть переведена во внутреннее представление. Это делается для целей оптимизации и/или удобства генерации кода. Еще одной целью преобразования программы во внутреннее представление является желание иметь переносимый компилятор. Тогда только последняя фаза (генерация кода) является машинно-зависимой. В качестве внутреннего представления может использоваться префиксная или постфиксная запись, ориентированный граф, тройки, четверки и другие.

1.5 Обработка несовпадающих типов

Если типы сыновей одного отца не совпадают, то транслятор использует правило: позволяющее ему продолжить работу. Например, если один из сыновей имеет целый, а другой - вещественный тип, то такое правило может указывать, что отец должен иметь вещественный тип. Однако возможны неразрешимые сочетания типов. На рисунке показан случай, когда один сын имеет целый (I) тип, а второй литерный (C). Для такой комбинации типов не существует правила разрешения, и поэтому транслятор выдает программисту сообщение об ошибке. Контроль типов играет еще одну очень важную роль дает транслятору дополнительную информацию о лексемах, которая нужна при генерации кода.

1.6 Оптимизация кода для повышения эффективности

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

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

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

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

Оптимизирующие преобразования могут быть зависящими или независящими от архитектуры компьютера. Процесс компиляции компьютерной программы включает два основных действия: синтаксичесикй/семантический анализ и генерацию кода. Синтаксический/семантический анализ существенно зависит от грамматики и специфичен для языка. Генерация кода является общей и прекрасно может быть использована для поддержки первой стадии для любого количества языков программирования.

Исходный текст конкретного языка первым делом транслируется в общую промежуточную форму, которая последовательно обрабатывается для выработки на стадии генерации машинно-зависимого кода. Машинно-независимая оптимизация, такая как выделение общих подвыражений и вынесение инвариантного кода, применяется к промежуточному коду. Машинно-зависимая оптимизация применяется к результату стадии генерации кода и использует набор команд конкретного процессора. Эта оптимизация известна как "щелевая" оптимизация, потому что эти преобразования выполняются внутри маленького окна (5 - 10 инструкций машинного уровня). Типичные примеры щелевой оптимизации включают удаление излишних операций загрузки/сохранения регистров, удаление недостижимого кода, выпрямление передач управления, алгебраические упрощения, снижение мощности (команд) и использование команд, специфических для конкретного процессора.

1.7 Методы оптимизации кода

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

1. Размножение констант - при его применении любая ссылка на константное значение замещается самим значением. В следующем примере повышается эффективность благодаря удалению трех адресных ссылок и замене их константами:

x = 2;

if( a < x && b < x)

c = x;

переводится в

x = 2;

if(a < 2 && b < 2)

c = 2;

2. Размножение копий - в этом методе копируются переменные вместо константных значений. Например,

x = y;

if(a < x && b < x)

c = x;

переводится в

x = y;

if(a < y && b < y)

c = y;

3. Свертки констант (константная арифметика) - сводит выражения, которые содержат константные данные, к возможно простейшей форме. Константные данные обычно используются в программе либо непосредственно (как в случае чисел или цифр), либо косвенно (как в случае объявленных манифестных констант).

Свертка констант сводит следующий оператор:

#define TWO 2

a = 1 + TWO;

к его эквивалентной форме,

a = 3;

4. Алгебраические упрощения - есть вид свертки констант, который удаляет арифметичесике тождества. Код, сгенерированыый для таких операторов, как

x = y + 0;

x = y * 0;

x = y / 1.0;

x = y / 0;

должен быть простым константным присваиванием и не должен содержать команд для выполнения арифметических операций. Бдительный компилятор должен пометить последний оператор как ошибочный и не генерировать код для него;

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

Выражения y * 3 и a[y*3] являются общими подвыражениями в следующем тексте:

if( a[y*3] < 0 || b[y*3] > 10)

a[y*3] = 0;

Выделение этих выражений приводит к логически эквивалентному тексту:

T1 = y*3;

A1 = &a[T1];

A2 = &b[T1];

if( *A1 < 0 || *A2 > 10)

*A1 = 0;

6. Глубокое выделение общих подвыражений - является более сложным и перекрывает базовые блоки. Выделение общего подвыражения, y*3, в операторе:

 if(a == 0)

a = y * 3;

else

b = y * 3;

приводит к логическому эквиваленту:

T1 = y * 3;

if(a == 0)

a = T1;

else

b = T1;

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

8. Удаление недостижимого кода - еще один метод оптимизации. Недостижимый код - это некоторая последовательность инструкций программы, которая недостижима ни по одному пути в программе;

9. Удаление лишних присваиваний - включает нахождение промежутка жизни переменной и удаление присваиваний этой переменной, если эти присваивания не могут изменить логику программы;

10. Распределения переменных по регистрам - состоит в попытке обеспечить оптимальное назначение регистров путем сохранения часто используемых переменных в регистрах так долго, как это возможно, для того, чтобы исключить более медленный доступ к памяти. Количество регистров, доступных для использования, зависит от архитектуры процессора;

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

Если инвариантный код выносится из следующего цикла:

unsigned char i,j,k,v,x;

for (i = 0; i < v; i++)

x = i * (j+k);

его логический эквивалент будет:

T1 = j + k;

for(i = 0; i < v; i++)

x = i * T1;

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

13.

for(i=0;i<10;i++) //первый простой цикл

a=b+c; //вычисление

for(i=0;i<10;i++) //второй простой цикл

d=e+f; //вычисление

могут быть объединены в один цикл:

for(i=0;i<10;i++) //цикл при методе слияния циклов

{

a=b+c; //вычисление

d=e+f; }

1.8 Генерация кода

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

2 Практическая часть

2.1 Постановка задачи

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

2.2 Разработка СИ программы

Оптимизация исходного кода программы по методу «Размножение констант»

"Размножение констант"- при его применении любая ссылка на константное значение замещается самим значением:

#include<iostream.h>

#include<conio.h>//подключение библиотек

int main() {

int x=5,a,b,c;//объявление переменных

clrscr();

cout<<"а=";//вывод сообщения

cin>>a;//ввод данных

cout<<"b=";

cin>>b;

if ((a<x)&&(b<x))//условие

{c=x;

cout<<"c="<<c;}

else cout<<"error";

getch();

return 0;

}

Эффективность повышается благодаря удалению трех адресных ссылок и замене их константами. При этом удаляется лишнее присваивание:

#include<iostream.h>

#include<conio.h>//подключение библиотек

int main() {

int a,b,c;//объявление переменных

clrscr();

cout<<"a=";//вывод сообщения

cin>>a;//ввод данных

cout<<"b=";

cin>>b;

if ((a<5)&&(b<5))//условие

{c=5;

cout<<"c="<<c;}

else cout<<"error";

getch();

return 0; }

2.3 Разработка алгоритма

Детальный алгоритм работы компилятора представлен на рисунке 2.1.

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

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



Размещено на http://www.allbest.ru/

Рисунок 2.1 - Алгоритм компиляции

Размещено на http://www.allbest.ru/

Рисунок 2.1 -Алгоритм компиляции (продолжение)

Заключение

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

Был разработан алгоритм работы компилятора, позволяющий детально рассмотреть процесс оптимизации программного кода. При оптимизации программного кода был использован метод «Размножение констант». Изученный метод оптимизации позволил оптимизировать код программы и сократить время на компиляцию программы, уменьшить объем исходного кода, время на выполнение.

операционный трансляция генерация программирование

Список использованных источников

1. Олифер В.Г. Сетевые операционные системы / Учебник. -СПб.:Питер, 2006.

2. Филипп Н. Хислей Генерация высококачественного кода для программ, написанных на СИ

Приложение Б Тестовые задания

1. Одинаково управлять независимо от их конкретных физических характеристик позволяет принцип:

генерации

умолчания

защиты

функциональной избыточности

независимости программ от внешних устройств

перемещаемости

Правильные ответы:

-: генерации

-: умолчания

-: защиты

-: функциональной избыточности

+: независимости программ от внешних устройств

-: перемещаемости

2. Наращиваемая, модифицируемая ОС позволяет не только использовать возможности генерации, но и вводить в ее состав новые модули, совершенствовать существующие. Такова характеристика принципа:

открытости

наращиваемости

умолчания

прозрачности

функциональной избыточности

развития

перемещаемости

Правильные ответы:

-: открытости

+: наращиваемости

-: умолчания

-: прозрачности

-: функциональной избыточности

+: развития

-: перемещаемости

3. Наличие в составе ОС альтернативных однотипных компонент (мониторов, драйверов, загрузчиков и т.п.) соответствует принципу:

наращиваемости

умолчания

прозрачности

функциональной избыточности

развития

открытости

Правильные ответы:

-: наращиваемости

-: умолчания

-: прозрачности

+: функциональной избыточности

-: развития

-: открытости

4. В ОС выделяется некоторая часть важных модулей, которые должны быть всегда в оперативной памяти для эффективной организации вычислительного процесса. Эта основа ОС называется ядром. Такова характеристика принципа:

генерации

умолчания

функциональной избыточности

функциональной избирательности

перемещаемости

Правильные ответы:

-: генерации

-: умолчания

-: функциональной избыточности

+: функциональной избирательности

-: перемещаемости

5. В идеале код ОС должен легко переноситься на разные типы процессоров и разные аппаратные платформы. Это характеристика свойства:

независимости

открытости кода

переносимости

универсальности

многоплатформенности

Правильные ответы:

-: независимости

-: открытости кода

+: переносимости

-: универсальности

+: многоплатформенности

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

распространение

надежность

производительность

устойчивость

Правильные ответы:

-: распространение

-: надежность

+: производительность

-: устойчивость

7. Если два процесса используют обобщенный ресурс (например, память), и действия над ним в составе процессов не должны выполняться параллельно, то между этими процессами возникает отношение...

приоритетности

предшествования

порядка

взаимного исключения

очередности

Правильный ответ:

-: приоритетности

-: предшествования

-: порядка

+: взаимного исключения

-: очередности

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

программе

подпрограмме

подсистеме ОС

процедуре

функции ОС

Правильный ответ:

-: программе

-: подпрограмме

-: подсистеме ОС

-: процедуре

+: функции ОС

9. При использовании языка высокого уровня функция ОС вызывается так же, как и пользовательские подпрограммы, требуя задания в соответствующем порядке определенных:

значений

значений полей

величин

символов

аргументов

Правильный ответ:

-: значений

-: значений полей

-: величин

-: символов

+: аргументов

10. При использовании языка высокого уровня функция ОС вызывается так же, как и пользовательские подпрограммы, требуя задания определенных аргументов в соответствующем:

поле

месте

массиве

диапазоне значений

порядке

Правильный ответ:

-: поле

-: месте

-: массиве

-: диапазоне значений

+: порядке

11. Командный язык ОС включает директивы управления пакетными:

заданиями

процессами

режимами

процедурами

файлами

Правильные ответы:

+: типы и классы единиц вычислительной работы

-: выбор пользователя

+: приоритеты запросов

+: дисциплина обслуживания

+: дополнительные соглашения владельцев процессов

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

мониторами

сервисными программами

утилитами

обслуживающими программами

программами-помощниками

Правильный ответ:

-: мониторами

-: сервисными программами

+: утилитами

-: обслуживающими программами

-: программами-помощниками

13. Группы, на которые обычно подразделяются вспомогательные модули ОС:

утилиты

драйверы

системные обрабатывающие программы

сервисные программы

библиотеки процедур различного назначения

Правильные ответы:

+: утилиты

-: драйверы

+: системные обрабатывающие программы

+: сервисные программы

+: библиотеки процедур различного назначения

14. Как и обычные приложения, все … модули ОС обращаются к функциям ядра посредством системных вызовов.

Правильный ответ:

вспомогательные

15. Чтобы добавить новую высокоуровневую функцию ОС, достаточно разработать соответствующее …, не модифицируя важнейших функций ядра.

Правильный ответ:

приложение

16. При работе важных приложений ОС в привилегированном режиме производительность...

понижается

не изменяется

остается прежней

остается приемлемой

не имеет значения

повышается

Правильный ответ:

-: понижается

-: не изменяется

-: остается прежней

-: остается приемлемой

-: не имеет значения

+: повышается

17. При работе важных приложений ОС в привилегированном режиме защита ОС от них...

усиливается

остается прежней

не имеет значения

теряет смысл

ослабляется

Правильный ответ:

-: усиливается

-: остается прежней

-: не имеет значения

-: теряет смысл

+: ослабляется

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

Правильный ответ:

привилегированном

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

однонаправленными

двунаправленными

от одного ко многим

от многих к одному

любыми

Правильный ответ:

-: однонаправленными

-: двунаправленными

-: от одного ко многим

-: от многих к одному

+: любыми

20. В многослойной структуре ОС отдельный модуль может выполнить свою работу либо самостоятельно, либо обратиться за помощью к нижележащему слою через межслойный…:

модуль сопряжения

блок

переход

буфер

интерфейс

Правильный ответ:

-: модуль сопряжения

-: блок

-: переход

-: буфер

+: интерфейс

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

вышележащему

любому вышележащему

любому

соседнему

нижележащему

Правильный ответ:

-: вышележащему

-: любому вышележащему

-: любому

-: соседнему

+: нижележащему

22. Многослойная организация ОС существенно … ее разработку, так как позволяет сначала сверху вниз определить функции слоев и межслойные интерфейсы, затем при реализации снизу вверх наращивать мощность функций слоев.

Правильный ответ:

упрощает

23. Способ взаимодействия … в реальной ОС может отличаться от типового варианта многослойной структуры.

Правильный ответ:

слоев

24. Для ускорения работы многослойного ядра иногда может происходить непосредственное обращение сверху к функциям нижних слоев, минуя... слои.

Правильный ответ:

промежуточные

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

Правильный ответ:

привилегированный

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

Правильный ответ:

программных

27. Программные прерывания часто используются для выполнения ограниченного числа вызовов функций ядра ОС - … вызовов.

Правильный ответ:

системных

28. Пользователь может воспринимать виртуальную машину в одном из двух вариантов: языковое представление, …. представление.

Правильный ответ:

структурное

29. Главное внимание пользователя сосредоточено на языке программирования, а виртуальная машина воспринимается им как "черный ящик", выполняющий его программы, … виртуальной машины его не интересует.

Правильный ответ:

структура

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

процессор

бесконечная память

ограниченная память

несколько процессоров

устройства ввода-вывода

произвольное число идеальных устройств ввода-вывода

Правильные ответы:

-: процессор

+: бесконечная память

-: ограниченная память

+: несколько процессоров

-: устройства ввода-вывода

+: произвольное число идеальных устройств ввода-вывода

31. Основным конструктивным и согласующим элементом при реализации той или иной дисциплины диспетчеризации, куда заносятся и откуда извлекаются запросы, является:

список

стек

очередь

таблица диспетчеризации

кортеж

Правильный ответ:

-: список

-: стек

+: очередь

-: таблица диспетчеризации

-: кортеж

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

по определенным правилам

случайным образом

по умолчанию

по важности

по сроку обслуживания

Правильный ответ:

+: по определенным правилам

-: случайным образом

-: по умолчанию

-: по важности

-: по сроку обслуживания

33. На содержание дисциплины формирования очереди влияют:

типы и классы единиц вычислительной работы

выбор пользователя

приоритеты запросов

дисциплина обслуживания

дополнительные соглашения владельцев процессов

Правильные ответы:

+: типы и классы единиц вычислительной работы

-: выбор пользователя

+: приоритеты запросов

+: дисциплина обслуживания

+: дополнительные соглашения владельцев процессов

34. Увеличение числа слоев ядра ведет к некоторому замедлению его работы за счет межслойного взаимодействия, а уменьшение - … расширяемость и логичность системы.