Всего за 133 руб. Купить полную версию
• функцию проверки совпадения двух триад 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', взятого из текущего нетерминального символа дерева:
• для правил 2 и 5 – схема полного условного оператора;
• для правила 3 – схема неполного условного оператора;
• для правил 4 и 6 – схема оператора присваивания;
• для правил 7, 8 и 10 – схема для бинарных линейных операций;
• для правила 13 – схема для скобок;
• в остальных случаях – схема для точки с запятой.
Функция MakeTriaD1istNOP содержит две вспомогательные функции:
• функцию MakeOperand для порождения кода, связанного с дочерним узлом дерева (одним из операндов);
• функцию MakeOperation, реализующую схему СУ-перевода для бинарных линейных операций в зависимости от типа операции.
Для построения кода для нижележащих нетерминальных символов по дереву функция MakeTriaD1istNOP рекурсивно вызывает сама себя. Этот вызов реализован в функции MakeOperand, если нижележащий узел является нетерминальным символом, а также напрямую для узлов, связанных со скобками и с точкой с запятой (как было рассмотрено ранее при построении схем СУ-перевода).
Модуль вычисления значений триад на этапе компиляции
Модуль TrdCalc содержит функцию, которая вызывается, когда необходимо вычислить значение триады на этапе компиляции. Эта функция нужна для алгоритма оптимизации методом свертки объектного кода. Она зависит от типов триад, которые зависят от входного языка, поэтому вынесена в отдельный модуль.
Модуль содержит одну-единственную функцию CalcTriad, которая предельно проста и в комментариях не нуждается.