Префиксная и постфиксная записи

Триады

Тетрады

Компиляторы. Генерация кода. Триады. Тетрады. Префиксная и постфиксная записи. Три формы объектного кода.

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

· генерация промежуточного кода;

· генерация собственно машинного кода

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

Представляет собой запись операций в форме из 4 составляющих:

<операция> (<операнд_1>,<операнд_2>,<результат>)

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

(-a+b)*(c+d)

можно представить тетрады следующим образом:

-a = 1

1+b=2

c+d=3

2*3=4

Представляют собой запись операций в форме 3 составляющих

<операция> (<операнд_1>,<операнд_2>

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

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

a+b+c*d

можно представить, как в виде тетрад:

В префиксной нотации каждый знак операции ставится перед своими операндами, а в постфиксной – после. В этом и состоит их основное отличие от обычной (инфиксной) записи, когда операция проставляется между операндами. Например, инфиксное выражение a+b в префиксной нотации примет вид +ab, а в постфиксной ab+.

(a+b)*(c+d)

в префиксной записи будет выглядеть

*+ab+cd

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

Получение постфиксного или префиксного представления возможно разными путями. В частности используется алгоритм стека, который в простейшем случае сведется к:

1. сохранению идентификатора, когда он встретится при чтении слева направо;

2. помещению в стек знака операции;

3. в момент встречи конца выражения выдача из стека знака операции, который находится на вершине.

Другой метод в получении постфиксного выражения из выражения, представленного в виде бинарного дерева. Например, выражение

(a+b)*c+d

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

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

1. обход левого поддерева снизу:

2. обход правого поддерева снизу:

3. посещение корня.

что дает в результате

ab+c*d+