1.3.Перевод в опз переменных с индексами

Пусть требуется вычислить выражение (b + a[i+1, j] * c + d ).

Адрес переменной с индексами дает функция упорядочения.

Пусть массив А: array [i₁..k₁, …, i_n..k_n] хранится в виде вектора, определяемого описанием B: array [1..N] , где

_n

N = ∏ (k_m - i_m + 1).

^m=1

Функция упорядочения позволяет по индексам элемента исходного массива A[j₁,…, j_n] вычислить соответствующий индекс элемента l массива В.

_n

l = 1 + ∑(j_m - i_m ) D_m , где при отображении массива А в массив В «строками» (т.е. быс-

^m=1

трее меняется последней индекс) - D_n = 1 и D_m = ( k_m+1 – i_m+1 + 1 ) D_m+1, m = n-1, …, 1 ,

а при отображении «столбцами» - D₁ = 1 и D_m = ( k_m-1 – i_m-1 + 1 ) D_m-1, m = 2, …, n .

Для определения адреса хранения a элемента A[j₁,…, j_n] в случае, когда вектор B имеет базу b, формулу функции упорядочения целесообразно преобразовать к виду

_n

a = b + c +( ∑ j_mD_m) t ,

^m=1

_n

где c = ( ∑ i_mD_m ) t, а t – размер элемента массива в байтах.

^m=1

Постоянная величина c, как и коэффициенты D_m зависит только от значений граничных пар в описании массива А.

Для вычисления адреса элемента массива нужно знать базу отображающего вектора b, размерность массива n и n целых чисел. При отображении «строками» это коэффициенты:

c, D₁ , …, D_n-1 ,

коэффициент D_n здесь всегда равен 1.

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

Для распределения памяти необходимо знать число элементов в каждом массиве N. При отображении массива «строками» N = D₀ = (k₁ – i₁ + 1) D₁ .

Все перечисленные величины хранятся в виде так называемого «определяющего вектора» массива. Для массивов с одинаковыми описаниями – определяющий тоже вектор один.

Введем операцию АДРЕС ЭЛЕМЕНТА МАССИВА (АЭМ), результат выполнения которой – адрес элемента массива, а операнды – идентификатор массива и значения индексных выражений.

Будем обозначать операцию АЭМ символами k], где k – количество операндов, а ] – знак операции.

Если n – число индексов, то k = n + 1.

Тогда ОПЗ выражения (b + a[i+1, j]) * c + d будет выглядеть следующим образом:

b a i 1 j + 3 ] + c * d + .

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

Запятая, разделяющая индексные выражения, выталкивает из стека все знаки операций до ближайшей открывающей индексной скобки исключительно. Каждая запятая добавляет в счетчик операндов операции АЭМ единицу.

1.4.Получение опз для указателей функций

Пусть имеется выражение y – f (x, y+1, z).

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

Будем обозначать операцию ФУНКЦИЯ парой символов kΦ, где k – количество операндов.

Тогда ОПЗ выражения примет вид: y f x y 1 + z 4 Φ - .

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

Чтобы отличить открывающую круглую скобку в начале списка фактических параметров от круглой скобки в выражении, можно использовать специальную переменную состояния F (признак функции). Эта переменная обычно имеет значение 0. В момент появления идентификатора функции она принимает значение 1, а после занесения в стек круглой скобки и начального значения счетчика операндов, равного 2, вновь принимает значение 0.

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

Если функция употребляется без параметров, то указатель функции, как и все идентификаторы, будет перенесен непосредственно в выходную строку.

Одновременно переменная состояния F примет значение 1. Если следующий символ не круглая скобка, то признаку F присваивается значение 0, а в выходную строку заносится запись 1Φ в знак того, что операция ФУНКЦИЯ имеет всего один операнд – идентификатор функции.