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

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

Исключение избыточных вычислений (лишних операций) заключается в нахождении и удалении из объектного кода операций, которые повторно обрабатывают одни и те же операнды.

Операция линейного участка с порядковым номером i считается лишней операцией, если существует идентичная ей операция с порядковым номером j, j< i и никакой операнд, обрабатываемый операцией с порядковым номером i, не изменялся никакой другой операцией, имеющей порядковый номер между i и j.

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

Рассмотрим алгоритм исключения лишних операций для триад.

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

• изначально для каждой переменной ее число зависимости равно 0, так как в начале работы программы значение переменной не зависит ни от какой триады;

• после обработки i-й триады, в которой переменной А присваивается некоторое значение, число зависимости A (dep(A)) получает значение i, так как значение А теперь зависит от данной i-й триады;

• при обработке i-й триады ее число зависимости (dep(i)) принимается равным значению 1+ (максимальное_из_чисел_зависимости_операндов).

Таким образом, при использовании чисел зависимости триад и переменных можно утверждать, что если i – я триада идентична j-й триаде (j<i), то i – я триада считается лишней в том и только в том случае, когда dep(i) = dep(j).

Алгоритм исключения лишних операций использует в своей работе триады особого вида SAME(j,O). Если такая триада встречается в позиции с номером i, то это означает, что в исходной последовательности триад некоторая триада i идентична триаде j.

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

1. Если какой-то операнд триады ссылается на особую триаду вида SAME(j,0), то он заменяется на ссылку на триаду с номером j (*j).

2. Вычисляется число зависимости текущей триады с номером i, исходя из чисел зависимости ее операндов.

3. Если в просмотренной части списка триад существует идентичная j-я триада, причем j < i и dep(i) = dep(j), то текущая триада i заменяется на триаду особого вида SAME(j,O).

4. Если текущая триада есть присваивание, то вычисляется число зависимости соответствующей переменной.

Рассмотрим работу алгоритма на примере:

D:= D + C*B;

A:= D + C*B;

C:= D + C*B;

Этому фрагменту программы будет соответствовать следующая последовательность триад:

1: * (C, B)

2: + (D, ^1)

3::= (D, ^2)

4: * (C, B)

5: + (D, ^4)

6::= (A, ^5)

7: * (C, B)

8: + (D, ^7)

9::= (C, ^8)

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

Таблица 4.2. Пример работы алгоритма исключения лишних операций

Теперь, если исключить триады особого вида SAME(j,O), то в результате выполнения алгоритма получим следующую последовательность триад:

1: * (C, B)

2: + (D, ^1)

3::= (D, ^2)

4: + (D, ^1)

5::= (A, ^4)

6::= (C, ^4)

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

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

Общий алгоритм генерации и оптимизации объектного кода

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

Алгоритм должен выполнить следующую последовательность действий:

• построить последовательность триад на основе дерева вывода;

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

• выполнить оптимизацию кода методом исключения лишних операций для линейных участков результирующей программы;

• преобразовать последовательность триад в последовательность команд на языке ассемблера (полученная последовательность команд и будет результатом выполнения алгоритма).

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

В данной работе алгоритм преобразования триад в команды языка ассемблера предлагается разработать самостоятельно. В тривиальном виде такой алгоритм заменяет каждую триаду на последовательность соответствующих команд, а результат ее выполнения запоминается во временной переменной с некоторым именем (например TMPi, где i – номер триады). Тогда вместо ссылки на эту триаду в другой триаде будет подставлено значение этой переменной. Однако алгоритм может предусматривать и оптимизацию временных переменных.[8]8
  Детально алгоритм порождения ассемблерного кода на основе последовательности триад рассмотрен в примере курсовой работы.


[Закрыть]

Требования к выполнению работы

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

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

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

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

1. Получить вариант задания у преподавателя.

2. Изучить алгоритм генерации объектного кода по дереву синтаксического разбора.

3. Разработать схемы СУ-перевода для операций исходного языка в соответствии с заданной грамматикой.

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

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

6. Разработать алгоритм преобразования последовательности триад в заданный объектный код (по согласованию с преподавателем).

7. Подготовить и защитить отчет.

8. Написать и отладить программу на ЭВМ.

9. Сдать работающую программу преподавателю.

Требования к оформлению отчета

Отчет должен содержать следующие разделы:

• Задание по лабораторной работе.

• Краткое изложение цели работы.

• Запись заданной грамматики входного языка в форме Бэкуса—Наура.

• Описание схем СУ-перевода для операций исходного языка в соответствии с заданной грамматикой.

• Пример генерации и оптимизации последовательности триад на основе простейшей исходной программы.

• Текст программы (оформляется после выполнения программы на ЭВМ).

Основные контрольные вопросы

• Что такое транслятор, компилятор и интерпретатор? Расскажите об общей структуре компилятора.

• Как строится дерево вывода (синтаксического разбора)? Какие исходные данные необходимы для его построения?

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

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

• Расскажите, что такое синтаксически управляемый перевод.

• Объясните работу алгоритма генерации последовательности триад по дереву синтаксического разбора на своем примере.

• За счет чего обеспечивается возможность генерации кода на разных объектных языках по одному и тому же дереву?

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

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

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

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

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

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

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

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

Варианты заданий соответствуют вариантам заданий для лабораторной работы № 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, если логическое выражение имеет ненулевое значение;

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

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

4. Для полного условного оператора порождается команда безусловного перехода в конец оператора.

5. Для полного условного оператора порождается блок кода № 3, соответствующий операциям после лексемы else (пятая нижележащая вершина), – для этого должна быть рекурсивно вызвана функция порождения кода для шестой нижележащей вершины.

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

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

Для того чтобы реализовать эти схемы, необходимы два типа триад: триада условного перехода и триада безусловного перехода.

Эти два типа триад реализуются следующим образом:

• IF(<операнд1>,<операнд2>) – триада условного перехода;

• JMP(1,<операнд2>) – триада безусловного перехода.

У триады IF первый операнд может быть переменной, константой или ссылкой на другую триаду, второй операнд – всегда ссылка на другую триаду. Триада IF передает управление на триаду, указанную вторым операндом, если первый операнд равен нулю, иначе управление передается на следующую триаду.

У триады JMP первый операнд не имеет значения (для определенности он всегда будет равен 1), второй операнд – всегда ссылка на другую триаду. Триада JMP всегда передает управление на триаду, указанную вторым операндом.

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

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

Тем не менее функция генерации списка триад должна обрабатывать и эти операции.

Они должны обрабатываться следующим образом:

• для вершины, у которой первая нижележащая вершина – открывающая скобка, вторая нижележащая вершина – узел дерева (не концевая вершина) и третья нижележащая вершина – закрывающая скобка, должна рекурсивно вызываться функция порождения кода для второй нижележащей вершины;

• для вершины, у которой первая нижележащая вершина – узел дерева (не концевая вершина) и вторая нижележащая вершина – точка с запятой, должна рекурсивно вызываться функция порождения кода для первой нижележащей вершины.

Пример генерации списка триад

Возьмем в качестве примера входную цепочку:

if a and b or a and b and 345 then a:= 5 or 4 and 7;

В результате лексического и синтаксического разбора этой входной цепочки будет построено дерево синтаксического разбора, приведенное на рис. 4.2.

Этому дереву будет соответствовать следующая последовательность триад:

1: and (a, b)

2: and (a, b)

3: and (^2, 345)

4: or (^1, ^3)

5: if (^4, ^9)

6: and (4, 7)

7: or (5, ^6)

8::= (a, ^7)

9:…

В этой последовательности два линейных участка: от триады 1 до триады 5 и от триады 6 до триады 9.

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

1: and (a, b)

2: and (a, b)

3: and (^2, 345)

4: or (^1, ^3)

5: if (^4, ^9)

6: C (4, 0)

7: C (5, 0)

8::= (a, 5)

9:…

Если удалить триады типа С, то эта последовательность примет следующий вид:

1: and (a, b)

2: and (a, b)

3: and (^2, 345)

4: or (^1, ^3)

5: if (^4, ^7)

6::= (a, 5)

7:…

Рис. 4.2. Дерево синтаксического разбора цепочки «if a and b or a and b and 345 then a:= 5 or 4 and 7;».

После оптимизации методом исключения лишних операций получим последовательность триад:

1: and (a, b)

2: same (^1, 0)

3: and (^1, 345)

4: or (^1, ^3)

5: if (^4, ^7)

6::= (a, 5)

7:…

Если удалить триады типа same, то эта последовательность примет следующий вид:

1: and (a, b)

2: and (^1, 345)

3: or (^1, ^2)

4: if (^3, ^6)

5::= (a, 5)

6:…

После применения оптимизации получаем последовательность из пяти триад. Это на 37,5 % меньше, чем в исходной без применения оптимизации последовательности, состоявшей из восьми триад. Следовательно, объем результирующего кода и время его выполнения в данном случае сократятся примерно на 37,5 % (слово «примерно» указано здесь потому, что разные триады могут порождать различное количество команд в результирующем коде, а потому соотношения между количеством триад и между количеством команд объектного кода могут немного различаться).

Можно еще обратить внимание на то, что алгоритм оптимизации методом исключения лишних операций не учитывает особенности выполнения логических и арифметических операций. Методами булевой алгебры последовательность операций «a and b or a and b and 345» можно преобразовать в «a and b» точно так же, как последовательность операций «a-b + a-b-345» – в «a-b-346», что было бы эффективней, чем варианты, которые строит алгоритм оптимизации методом исключения лишних операций. Но для таких преобразований нужны алгоритмы, ориентированные на особенности выполнения логических и арифметических операций [1, 2, 7].

Реализация генератора списка триад

Разбиение на модули

Так же, как и для лабораторных работ № 2 и 3, модули, реализующие генератор списка триад, в лабораторной работе № 4 разделены на две группы:

• модули, программный код которых не зависит от входного языка;

• модули, программный код которых зависит от входного языка.

В первую группу входят модули:

• Triads – описывает структуры данных для представления триад;

• TrdOpt – реализует два алгоритма оптимизации: методом свертки объектного кода и методом исключения лишних операций;

• FormLab4 – описывает интерфейс с пользователем.

Во вторую группу входят модули:

• TrdType – описывает допустимые типы триад и их текстовое представление;

• TrdMake – строит список триад на основе дерева синтаксического разбора;

• TrdCal с – обеспечивает вычисление значений для триад разных типов при свертке объектного кода.

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

Кроме этих модулей для реализации лабораторной работы № 4 используются следующие программные модули:

• TblElem и FncTree – позволяют работать с комбинированной таблицей идентификаторов (созданы при выполнении лабораторной работы № 1);

• LexType, LexElem, и LexAuto – обеспечивают работу лексического распознавателя (созданы при выполнении лабораторной работы № 2);

• SyntRule и SyntSymb – обеспечивают работу синтаксического распознавателя (созданы при выполнении лабораторной работы № 3).

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

Модуль описания допустимых типов триад

Модуль TrdType содержит структуры данных, которые описывают допустимые типы триад.

Он содержит следующие важные типы данных и переменные:

• TTriadType – перечисление всех возможных типов триад;

• TriadStr – массив строковых обозначений для всех типов триад;

• TriaD1ineSet – множество тех триад, которые являются линейными операциями (оно важно для оптимизации и для порождения кода).

Модуль описания структур данных для триад

Модуль Triads содержит структуры данных, которые описывают триады и список триад. Эти структуры зависят от реализации компилятора, но не зависят от входного языка.

Он содержит следующие важные структуры данных:

• TOperand – описывает операнд триады;

• TTriad – описывает триаду и все связанные с нею данные;

• TTriaD1ist – описывает список триад.

Структура TOperand описывает операнд триады. Она содержит следующие данные:

• ОрТуре – тип операнда, который может принимать три значения:

– OPC0NST – константа;

– OPVAR – переменная (идентификатор);

– OPLINK – ссылка на другую триаду;

• и дополнительную информацию по операнду:

– ConstVal – значение (для константы);

– VarLink – ссылка на таблицу идентификаторов (для переменной);

– TriadNum – номер триады (для ссылки на триаду).

Один из вопросов, который необходимо было решить при реализации операндов триад, состоял в следующем: что использовать для описания ссылки на триаду – непосредственно ссылку на тип данных (указатель) или номер триады в списке?

Оба варианта имеют свои преимущества и недостатки:

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

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

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

Структура TTriad описывает триаду и все связанные с ней данные. Она содержит следующие поля данных:

• TriadType – тип триады (один из перечисленных в типе TTriadType в модуле TrdType);

• Operands – массив операндов триады (из двух операндов типа TOperand);

• Info – дополнительная информация о триаде для алгоритмов оптимизации;

• IsLinked – флаг, сигнализирующий о том, что на триаду имеется ссылка из другой триады, обеспечивающей передачу управления (типа IF или JMP).

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

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

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

Флаг наличия ссылки важен для определения границ линейных участков программы при оптимизации: если на какую-то триаду есть ссылка из триад типа IF или JMP, значит, на нее может быть передано управление. Такая триада является возможной точкой входа участка программы, а потому – границей линейного участка.

Кроме перечисленных данных структура TTriad содержит следующие процедуры и функции:

• конструктор Create для создания триады;

• функцию проверки совпадения двух триад IsEqual;

• функцию MakeString, формирующую строковое представление триады для отображения триад на экране;

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

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

Структура данных TTriaD1ist описывает список триад и методы работы с ним. Как и некоторые списки, рассмотренные ранее (в лабораторных работах № 2 и 3), она построена на основе динамического массива типа TList из библиотеки VCL системы программирования Delphi 5. В этой структуре нет никаких данных (используются только данные, унаследованные от класса TList), но с ней связаны методы, необходимые для работы со списком триад:

• функция очистки списка триад (Clear) и деструктор для освобождения памяти при удалении списка триад (Destroy);

• функция записи списка триад в текстовом представлении в список строк для отображения списка триад на экране (WriteToList);

• функция удаления триады из списка (DelTriad);

• функция GetTriad и свойство Triads для доступа к триадам в списке по их порядковому номеру.

Следует отметить, что функция записи списка триад в список строк (WriteToList) последовательно вызывает функцию MakeString для записи в список строк каждой триады из списка триад. Функция удаления триады из списка (DelTriad) освобождает память, занятую удаляемой триадой, а кроме того, следит за тем, чтобы при удалении триады флаг метки (IsLinked) от удаляемой триады был корректно переставлен на следующую по списку триаду.

Кроме трех перечисленных структур данных в модуле Triads описана также функция DelTriadTypes, которая выполняет удаление из списка триад всех триад заданного типа. Эта функция необходима только для наглядной иллюстрации работы алгоритмов оптимизации. Для этого надо удалять из списка триад триады с типами С и same, которые не порождают результирующего кода.

Удаление триад из списка можно выполнить в виде двух вложенных циклов:

• первый обеспечивает просмотр всего списка триад;

• второй обеспечивает изменение номеров всех ссылок и всех последующих триад в списке при удалении какой-либо триады.

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

Поэтому функция удаления триад из списка реализована другим путем. Она выполняет два просмотра списка триад:

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

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

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

Модуль построения списка триад по дереву синтаксического разбора

Модуль TrdMake содержит функцию, которая строит список триад на основе дерева синтаксического разбора. Эта функция работает с типами триад, описанными в модуле TrdType, и со структурами данных, описанными в модуле Triads. Дерево синтаксического разбора описано структурами данных из модуля SyntSymb, который был создан при выполнении лабораторной работы № 3. Функция построения списка триад на основе синтаксического дерева зависит от входного языка, а потому вынесена в отдельный модуль.

Модуль содержит одну функцию, доступную извне, – MakeTriaD1ist. Входными данными этой функции являются:

• symbTop – ссылка на корень синтаксического дерева, по которому строится список триад;

• listTriad – список, в который должны быть записаны построенные триады.

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

Функция MakeTriaD1ist выполняет построение списка триад, добавляет в конец списка триад завершающую триаду типа NOP (No Operation – Нет операции), чтобы корректно обрабатывать ссылки на конец списка триад, а также обеспечивает расстановку флагов IsLinked для всех триад в списке.

Функция MakeTriaD1ist построена на основе внутренней функции модуля TrdMake – MakeTriaD1istNOP, которая и выполняет главные действия по порождению списка триад. Эта функция обрабатывает те же входные данные и имеет такой же результат выполнения, что и функция MakeTriaD1ist.

Функция MakeTriaD1istNOP реализует схемы СУ-перевода, которые были рассмотрены выше. Выбор схемы СУ-перевода происходит по номеру правила остовной грамматики G', взятого из текущего нетерминального символа дерева: