4.3. ТРАНСЛЯЦИЯ ВЫРАЖЕНИЙ

4.3.1. ПОЛЬСКАЯ ЗАПИСЬ

Первые процедурно-ориентированные языки программирования высокого уровня предназначались для решения инженерных и научно-технических задач, в которых широко применяются методы вычислительной математики. Значительную часть программ решения таких задач составляют арифметические и логические выражения. Поэтому трансляцией выражений занимались очень многие исследователи и разработчики трансляторов. Начиная с 1952 г., когда была опубликована работа Г. Рутисхаузера [51], в которой впервые предлагался метод трансляции арифметических выражений, разработано много различных методов. Сейчас классическим стал метод трансляции выражений, основанный на использовании промежуточной обратной польской записи, названной так в честь польского математика Яна Лукашевича, который впервые использовал эту форму представления выражений в математической логике. Однако в существующих трансляторах используются и другие методы.

Рассмотрим сущность обратной польской записи на примере. Простое арифметическое выражение с вещественными переменными а + b × с - d / (а + b) можно представить в виде обратной польской записи: а b c × + d a b + / -.

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

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

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

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

Таблица 4.3
ПРИМЕР ВЫЧИСЛЕНИЯ ВЫРАЖЕНИЯ В ОБРАТНОЙ ПОЛЬСКОЙ ЗАПИСИ

Результат выполнения операции фиксируется в виде рабочей переменной вида r_j. После очередной операции рабочая переменная r₁ или r₂ вычеркивается, освободившуюся рабочую переменную можно использовать вновь для записи результата операции. Использование каждый раз свободной рабочей переменной с минимальным номером экономит количество занятых рабочих переменных. Такой пример экономии рабочих ячеек приведен в табл. 4.3. Это же правило используют в трансляторах.

4.3.2. АЛГОРИТМ ПЕРЕВОДА ОБРАТНОЙ ПОЛЬСКОЙ ЗАПИСИ В МАШИННЫЕ КОМАНДЫ

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

В двух рассмотренных примерах встречались двухместные операции и одноместная операция изменения знака. Каждая такая операция, как правило, заменяется одной или двумя машинными командами (в зависимости от адресности машины). В общем случае операция R может иметь k операндов (k >= l). На машине такая операция должна заменяться группой машинных команд. Будем считать, что к моменту генерирования машинных команд проведено распределение памяти и каждый операнд представлен соответствующим адресом или ссылкой на таблицу имен, содержащую адрес операнда. Аналогично, для каждой рабочей переменной известен ее адрес.

Для трансляции выражения из обратной польской записи в машинные команды используется стек операндов (СО) с указателем i. В исходном состоянии стек операндов пуст, а указатель i = 1. Будем также считать, что в исходном состоянии номер первой свободной рабочей переменной j = 1.

Алгоритм трансляции состоит в следующем.

1. Взять очередной символ S из обратной польской записи выражения.

2. Если S — операнд, то занести S в СО[i], выполнить i := i + 1 и перейти к пункту 1, иначе перейти к пункту 3.

3. Если S — не знак операции, то перейти к пункту 4, иначе, если S — знак операции R, выполнить следующее:

3А. Среди элементов стека CO[i - k], ..., CO[i - 1], где k — число операндов операции R, найти рабочую переменную с минимальным номером l. Если в рассматриваемых элементах стека нет рабочих переменных, то положить l = j.

3Б. Записать машинные команды, реализующие оператор присваивания r₁ := R(CO[i - k], ..., CO[i - 1]). Здесь R(x₁, ..., x_k) — результат выполнения операции R над операндами x₁, ..., x_k.

3В. Занести символ r_l в СО[i - k].

3Г. Выполнить i := i - k + 1 и j := l + 1. Перейти к пункту 1.

4. Если запись выражения исчерпана, то трансляция закончена. Стек операндов должен содержать только переменную r_l, в противном случае нужно записать информацию об ошибке в таблицу ошибок.

Для реализации пункта 3Б приведенного алгоритма используются заранее подготовленные «заготовки» групп машинных команд, в которые требуется лишь подставить адреса операндов (или значения самоопределенных операндов), взятые из стека операндов. Эту подстановку выполняет подпрограмма, соответствующая рассматриваемой операции R. Надо, однако, отметить, что используемая подпрограмма определяется не только знаком операции R, но и типом операндов.

4.3.3. ПЕРЕВОД ПРОСТЫХ АРИФМЕТИЧЕСКИХ ЛОГИЧЕСКИХ ВЫРАЖЕНИЙ В ОБРАТНУЮ ПОЛЬСКУЮ ЗАПИСЬ

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

Известно несколько методов получения обратной польской записи. Обзор различных методов дан в книге Б. Ренделла и Л. Рассела «Реализация Алгола-60» [26]. Один из наиболее эффективных методов предложен в 1960 г. голландским ученым Е. В. Дикстрой.

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

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

Таблица 4.5
ПРИОРИТЕТЫ ОГРАНИЧИТЕЛЕЙ

Ограничители Приоритеты ( [ if 0 := ) ] , then else 1 2 OR 3 AND 4 NOT 5 > >= = != <= < 6 + - 7 / × ± 8

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

Рис. 4.5. Использование стека операций для перевода выражений в обратную польскую запись

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

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

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

После просмотра всех символов входной строки происходит выталкивание всех оставшихся в стеке символов и дописывание их к выходной строке.

Пример. Перевести в обратную польскую запись выражение а + b × с - d / (а + b).

4.3.5. УКАЗАТЕЛИ ФУНКЦИЙ

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

Выражение y - f(x, y + 1, z) содержит указатель функции с идентификатором f.

Введем операцию ФУНКЦИЯ, операнды которой — идентификатор функции и значения (или идентификаторы) ее аргументов, а результат — значение функции (точнее, адрес значения функции).

Очевидно, в обратной польской записи целесообразно вместе со знаком операции ФУНКЦИЯ указывать количество операндов. Это облегчает последующую трансляцию указателя функции в машинные команды и позволяет контролировать правильность обращения к функции (соответствие числа фактических и формальных параметров).