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

Триады представляют собой запись операций в форме из трех составляющих: операция и два операнда. Например, в строковой записи триады могут иметь вид: <операция>(<операнд1>,<операнд2>). Особенностью триад является то, что один или оба операнда могут быть ссылками на другую триаду в том случае, если в качестве операнда данной триады выступает результат выполнения другой триады. Поэтому триады при записи последовательно нумеруют для удобства указания ссылок одних триад на другие (в реализации компилятора в качестве ссылок можно использовать не номера триад, а непосредственно ссылки в виде указателей – тогда при изменении нумерации и порядка следования триад менять ссылки не требуется).

Например, выражение A:=B-C+D-B-10, записанное в виде триад, будет иметь вид:

1: * (B, C)

2: + (^1, D)

3: * (B, 10)

4: – (^2, ^3)

5::= (A, ^4)

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

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

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

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

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

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

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

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

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

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

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

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

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