Обращение к элементу массива и вызовы подпрограмм

Конструкция A[<выр>,..,<выр>] записывается в виде

<выр>.. <выр> A $SUBS

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

Методика обращения к элементу массива представляется очень важной для понимания того, как происходит вызов функций и процедур. Дело в том, что при обращении к функции нам также необходимо извлекать откуда-то необходимое количество аргументов. А количество их мы можем определить по содержимому таблицы имен. Поэтому вызов функции вида f(x₁,x₂) в польской форме записи будет выглядеть как

x₁ x₂ f $CALL,

где x₁ и x₁ – аргументы, f - имя функции, $CALL – команда передачи управления по адресу, определяемому именем функции. При этом предполагается, что мы заранее занесли в таблицу имен информацию о том, сколько и каких аргументов у функции f, а также ее адрес – индекс начала кода подпрограммы в массиве польской формы.

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

 

Циклы

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

FOR I=N1 TO N2 DO Operator

может быть сконструирован на исходном языке:

I:= N1;

L1: IF I>N2 THEN GOTO L2;

Operator;

I:=I+1;

GOTO L1;

L2:

Тем не менее, если необходимо реализовать этот цикл как оператор языка, то в польской форме записи он будет выглядеть так:

 

Рассмотрим фрагмент программы:

BEGIN

INTEGER K;

ARRAY A[1..I-J];

K:= 0;

L:    IF I>J THEN

              K:= K+A[I-J]*6

ELSE

BEGIN

                   I:= I+1;

                   I:= I+1;

                   GOTO L;

END

END.

 

Добавим еще два оператора без операндов - $BLOCK ("начало блока") и $BLOCKEND ("конец блока"). Эти операторы иногда очень важны – в некоторых языках программирования с их помощью можно вводить локальные, "внутриблоковые" переменные, вызывать автоматически деструкторы и т.п. Кроме того, нам понадобится оператор присваивания ":=", который ничего не заносит обратно в стек. Польская форма нашего фрагмента будет выглядеть так:

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

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

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

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

ТЕТРАДЫ

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

$BLOCK                           (10) + K, T4, T5

- I, J, T1                             (11):= T5,, K

$BOUNDS 1, T1               (12) $BR 18

$ADEC A                          (13) + I, 1, T6

:= 0,, K                              (14):= T6,, I

- I, J, T2                             (15) + I, 1, T7

$BMZ 13, T2                     (16):= T7,, I

- I, J, T3                             (17) $BRL L

* A[T3], 6, T4                   (18) $BLOCKEND

 

Здесь используются следующие операторы:

Оператор	Операнды	Описание
$BR	i	переход на i-ю тетраду
$BZ (BP,BM)	i, P	переход на i-ю тетраду, если P=0 (P>0,P<0)
$BG (BL,BE)	i, P1, P2	переход на i-ю тетраду, если P1>P2 (P1<P2,P1=P2)
$BRL	P	переход на тетраду, номер которой задан в P-м элементе таблицы символов
$BOUNDS	P1, P2	P1 и P2 описывают граничную пару массива
$ADEC	P	Массив описан в P. Если размерность массива равна n, то этой тетраде должны предшествовать n операторов $BOUNDS, задающих n граничных пар

С тетрадой номер 9 могут возникнуть определенные проблемы. Трудности связаны с использованием аргумента в виде переменной с индексом. Решение может заключаться в использовании той же методики, что и в случае описания массивов.

Введем пару операторов типа

$AINDX I

$AGET A, R

$AINDX заносит аргумент I (индекс массива) в специальный стек – стек индексов. Это необходимо для того, чтобы команда $AGET смогла вычислить адрес элемента массива A, используя содержимое стека индексов, и занести значение этого элемента в R. В этот же момент может происходить и очистка стека (по мере извлечения необходимого количества аргументов)

Например, выражение "A[1,2]+B[J]" будет представлено в виде

$AINDX 1

$AINDX 2

$AGET A, T1

$AINDX J

$AGET B, T2

+ T1, T2, T3

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

ОПТИМИЗАЦИЯ ПРОГРАММ

Оптимизация программ – это очень объемная тема, на которую написаны (и пишутся до сих пор) многочисленные труды. Здесь мы лишь вкратце затронем этот вопрос.

Различают два основных вида оптимизации – машинно-зависимую (МЗО) и машинно-независимую (МНЗО):

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

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

Оптимизации подлежат:

время выполнения;

емкостные ресурсы (память).

Существуют 4 основных типа машинно-независимой оптимизации МНЗО.

 

I. Исключение общих подвыражений (оптимизация линейных участков)

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

(11) представить выражение в форме, пригодной для обнаружения общих подвыражений;

(12) определить эквивалентность двух и более подвыражений;

(13) исключить повторяющиеся;

(1) изменить команды так, чтобы учесть это исключение.

Например, пусть выражение A = c*d*(d*c+b) записано в виде тетрад:

1) * c d T1

2) * d c T2

3) + T2 b T3

4) * T1 T3 T4

5) = A T4

Упорядочим операнды в алфавитном порядке (там, где это возможно):

1. * c d T1

2. * c d T2

3. + T2 b T3

4. * T1 T3 T4

5. = A T4

Далее определим границы операторов и найдем общие подвыражения (это (1) и (2)) и затем исключим подвыражение (2). После чего заменим далее везде T2 на T1:

* c d T1

+ T1 b T3

* T1 T3 T4

= A T4

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