Выражение

a + b + c X d

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

a + b = 1 c X d = 2 1 + 2 = 3

и в виде троек:

a + b c X d 1 + 2

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

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

a : = b

в виде четверки представляется как

a : = b = 1

а виде тройки - как

a : = b

Аналогично условие предложение

if a then b else c fi

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

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

Префиксная нотация известна также как польская запись (по названию страны ее изобретателя Лукашевича), и постфиксная - как обратная польская запись. С помощью этих нотаций записывать более сложные выражения. Например, выражение

(a + b) X (c + d)

в префиксной форме записывается следующим образом:

x+ ab + cd

а в постфиксной так:

ab + cd + X

Каждый знак операции в префиксной нотации ставится непосредственно перед своими операндами, а в постфиксной после них.

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

Перегруппировку в результате преобразования

(a + b) X (c + d) в ab + cd + X

Можно осуществлять с помощью стека. Алгоритм такого преобразования хорошо известен (см. [50]). Это преобразование можно выполнить также на основании грамматики инфиксных выражений. В данном случае оно сведется к трем действиям:

1) напечатать идентификатор, когда он встретится при чтении инфиксного выражения слева направо;

2) поместить в стек знак операции, когда он встретиться;

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

Этот метод подобен методу, описанному в гл. 6, которой применялся для получения четверок, и читателю предлагается закодировать его.

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

(a + b) X c + d

Представляется в помощью бинарного дерева так, как показано на рис. 10.1. Чтобы получить представление префиксного выражения, дерево обходят сверху в порядке, определенном Кнутом[37]:

посещение корня;

обход левого поддерева сверху;

обход правого поддерева сверху; что дает

+ X + abcd

Для получения постфиксного представления дерево обходят снизу. По Кнуту это выглядит так:

обход левого поддерева снизу; обход правого поддерева снизу; посещение корня.

В результате имеем:

Рис. 10.1

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

Тип - команды параметры

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

STANDOPII + , A, B, C

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

Промежуточный код пишется на относительно низком уровне. Он аналогичен коду, использованному [10] для реализации Алгола 68. Обтчно выдвигается условие, чтобы промежуточный код отражал структуру реализуемого языка.

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

Адрес на время прогона обычно соотносится со стеком, и каждый такой адрес можно представить тройкой вида

(тип-адреса, номер блока, смещение).

Тип-адреса может быть прямым или косвенным (т.е. адрес может содержать значение или указатель на значение) и ссылаться на рабочий стек или стек