Системное программное обеспечение. Лабораторный практикум

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

• Объясните, почему генерацию программы приходится проводить в два этапа: генерация и оптимизация.

• Какие существуют методы оптимизации объектного кода?

• Что такое триады и для чего они используются? Какие еще существуют методы для представления объектных команд?

• Объясните работу алгоритма свертки. Приведите пример выполнения свертки объектного кода.

• Что такое лишняя операция? Что такое число зависимости?

• Объясните работу алгоритма исключения лишних операций. Приведите пример исключения лишних операций.

Варианты заданий

Варианты заданий соответствуют вариантам заданий для лабораторной работы № 3. Для выполнения работы рекомендуется использовать результаты, полученные в ходе выполнения лабораторных работ № 2 и 3.

Пример выполнения работы

Задание для примера

В качестве задания для примера возьмем язык, заданный КС-грамматикой G({if,then,else,a,=,or,xor,and,(,),},{S,F,_£,£), C},P,S) с правилами Р:

S → F;

F → if-then T else F | if E then F | a:= E

T → if-then T else T | a:= E

E → E or D | E xor D | D

D → D and С | С

С → a | (E)

Жирным шрифтом в грамматике и в правилах выделены терминальные символы.

Этот язык уже был использован для иллюстрации выполнения лабораторных работ № 2 и № 3.

Результатом примера выполнения лабораторной работы № 4 будет генератор списка триад. Преобразование списка триад в ассемблерный код рассмотрено далее в примере выполнения курсовой работы (см. главу «Курсовая работа»).

Построение схем СУ-перевода

Все операции, которые могут присутствовать во входной программе на языке, заданном грамматикой G, по смыслу (семантике) можно разделить на следующие группы:

• логические операции (or, xor и and);

• оператор присваивания;

• полный условный оператор (if…then… else…) и неполный условный оператор (if… then…);

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

Рассмотрим схемы СУ-перевода для всех перечисленных групп операций.

СУ-перевод для линейных операций

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

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

Примечание.

На самом деле возможен другой вариант вычисления логических операций в том случае, когда они являются операциями булевой логики и их операндами могут быть только значения «Истина» (1) и «Ложь» (0). Здесь этот вариант не рассматривается. Более подробно о нем сказано в разделе «Курсовая работа», когда строятся схемы СУ-перевода для логических операций, а также можно обратиться к литературе [2].

СУ-перевод для оператора присваивания

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

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

СУ-перевод для условных операторов

Для условных операторов генерация кода должна выполняться в следующем порядке:

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

2. Порождается команда условного перехода, которая передает управление в зависимости от результата вычисления логического выражения:

• в начало блока кода № 2, если логическое выражение имеет ненулевое значение;