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

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

Модуль 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, которая предельно проста и в комментариях не нуждается.

Модуль, реализующий алгоритмы оптимизации

Модуль TrdOpt реализует два алгоритма оптимизации списка триад:

• методом свертки объектного кода;

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

Алгоритмы, реализованные в модуле TrdOpt, в общем случае не зависят от входного языка, однако они обрабатывают триады типа «присваивание» (в данной реализации – TRDASSIGN). Кроме того, границы линейных участков, на которых работают эти алгоритмы, зависят от триад условного и безусловного перехода (в данной реализации – TRDIF и TRDJMP). Сами алгоритмы требуют для себя триад специального типа, которые в данном случае реализованы как TRDC и TRDSAME.

В итоге реализация алгоритмов оптимизации зависит от следующих типов триад:

• триад присваивания;

• триад условного и безусловного перехода;

• триад специальных типов.

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

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

Кроме функций, реализующих алгоритмы оптимизации, модуль TrdOpt содержит две структуры данных:

• TConstInfo – для хранения информации о значениях переменных;

• TDepInfo – для хранения информации о числах зависимости переменных.