Схемы су-перевода

Выше был описан принцип СУ-перевода, позволяющий получить линейную последовательность команд результирующей программы или внутреннего представления программы в компиляторе на основе результатов синтаксического разбора. Теперь построим вариант алгоритма генерации кода, который получает на входе дерево операций и создает по нему фрагмент объектного кода для линейного участка результирующей программы. Рассмотрим примеры схем СУ-перевода для арифметических операций. Эти схемы достаточно просты, и на их основе можно проиллюстрировать, как выполняется СУ-перевод в компиляторе при генерации кода.

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

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

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

-- оба нижележащих узла дерева — листья, помеченные операндами;

--- только левый нижележащий узел является листом дерева;

--- только правый нижележащий узел является листом дерева;

---оба нижележащих узла не являются листьями дерева.

Рассмотрим построение двух видов внутреннего представления по дереву вывода:

--- построение списка триад по дереву вывода;

--- построение ассемблерного кода по дереву вывода.

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

Пример схемы су-перевода дерева операций на язык ассемблера

B качестве языка ассемблера возьмем язык ассемблера процессоров типа Intel 80x86. При этом будем считать, что операнды могут быть помещены в 16-разрядные регистры процессора и в коде результирующей объектной программы могут использоваться регистры AX (аккумулятор) и DX (регистр данных), а также стек для хранения промежуточных результатов.

Функцию, реализующую перевод узла дерева в последовательность команд ассемблера, назовем Code. Входными данными функции должна быть информация об узле дерева операций. B ее реализации на каком-либо языке программирования эти данные можно представить в виде указателя на соответствующий узел дерева операций. Выходными данными является последовательность команд языка ассемблера. Будем считать, что она передается в виде строки, возвращаемой в качестве результата функции.

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

Каждой допустимой арифметической операции будет соответствовать своя команда на языке ассемблера. Если взять в качестве примера операции сложения (+), вычитания (-), умножения (*) и деления (/), то им будут соответствовать команды add, sub, mul и div. Причем в ассемблере Intel 80x86 от типа операции зависит не только тип, но и синтаксис команды (операции mul и d1 v в качестве первого операнда всегда предполагают регистр процессора AX, который не нужно указывать в команде). Соответствующая команда должна записываться вместо act при порождении кода в зависимости от типа узла дерева.

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

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

Рассмотрим в качестве примера выражение A:=B*C+D-B*10. Соответствующее ему дерево вывода приведено на рис. 14.5.

Построим последовательность команд языка ассемблера, соответствующую дереву операций на рис. 14.5. Согласно принципу СУ-перевода, построение начинается от корня дерева. Для удобства иллюстрации рекурсивного построения последовательности команд все узлы дерева помечены от Ul до U5. Рассмотрим последовательность построения цепочки команд языка ассемблера по шагам рекурсии. Эта последовательность приведена ниже.

Полученный объектный код на языке ассемблера, очевидно, может быть оптимизирован. Вопросы оптимизации результирующего кода рассмотрены далее в разделе «Оптимизация кода. Основные методы оптимизации».

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

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

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

Указанных проблем можно избежать, если порождать код не в виде цепочки команд ассемблера, а в виде последовательности команд машинно-независимого метода внутреннего представления программы — например, тетрад или триад.