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

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

Так же, как и для лабораторных работ № 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', взятого из текущего нетерминального символа дерева:

• для правил 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 – для хранения информации о числах зависимости переменных.

Обе эти структуры построены на основе структуры TAddVarInfo, описанной в модуле TblElem (этот модуль был создан при выполнении лабораторной работы № 1), и предназначены для хранения информации, связанной с переменной в таблице идентификаторов.

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

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

Каждая из этих структур имеет одно поле, которое и предназначено для хранения информации. Для доступа к этому полю используются виртуальные функции и связанные с ними свойства, которые переопределяют функции и свойства типа данных TAddVarInfo.

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

Теперь можно сравнить два подхода к хранению дополнительной информации:

1. Хранение информации внутри структур данных (реализовано для триад).

2. Хранение внутри структур данных только ссылок (указателей), а самой информации – во внешних структурах.

Первый подход имеет следующие преимущества:

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

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

В то же время первый подход имеет ряд недостатков:

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

• обеспечивается меньшая гибкость в обработке информации.

Второй подход имеет следующие преимущества:

• можно хранить разнородную информацию в зависимости от потребностей на каждой стадии компиляции;

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

• обеспечивается более гибкая обработка информации (например, легко реализуется понятие «отсутствие данных» в алгоритме оптимизации методом свертки объектного кода через пустую ссылку nil).

Но и он имеет ряд недостатков:

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

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

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

Алгоритмы оптимизации реализованы в модуле TrdOpt в виде двух процедур:

• OptimizeConst – для оптимизации методом свертки объектного кода;

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

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

• С (TRDC) – при оптимизации методом свертки объектного кода;

• Same (TRDSAME) – при оптимизации методом исключения лишних операций.

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

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

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