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

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

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

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

Триады обладают следующими преимуществами:

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

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

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

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

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

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

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

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

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