Внутренние формы представления программы

Мы уже говорили о том, что внутренняя форма - это промежуточная форма представления исходной программы, пригодная (1) для простой машинной обработки (операторы располагаются в том же порядке, в котором они и будут исполняться); (2) для интерпретации. Рассмотрим, как представимы во внутренней форме некоторые наиболее употребительные операторы. Начнем с польской формы.

ПОЛЬСКАЯ ФОРМА

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

Если R является идентификатором или константой, то его значение заносится в стек и осуществляется считывание следующего символа (правило "<операнд>::=идентификатор").

Если R - бинарный оператор, то он применяется к двум верхним операндам в стеке, и затем они меняются на полученный результат (правило "<операнд>::=<операнд><операнд><оператор>").

Если R - унарный оператор, то он применяется к верхнему символу в стеке, который затем заменяется на полученный результат (правило "<операнд>::=<операнд><оператор>").

Упрощенно алгоритм вычисления польской формы (ПФ) выглядит так:

R:= getchar

while R!= # do

case R of

                   'идентификатор': push(R)

                   'бин.оператор':   pop(B), pop(A), Tmp:= R(A,B), push(Tmp)

                   'унарн.оператор': pop(A), Tmp:= R(A), push(Tmp)

endcase

R:= getchar

endwhile

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

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

 

Безусловные переходы

Безусловный переход на метку (аналог GOTO L)

L $BRL (Branch to label)

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

Безусловный переход на символ

C $BR

Под символом здесь понимается номер позиции (индекс) в массиве, содержащем польскую форму.

 

Условные переходы

<операнд1> <операнд2> $BR xZ|$BRM|$BRP|$BRMZ|$BRPZ|

<операнд1> - значение арифметического выражения,

<операнд2> - номер или место символа в польской цепочке (адрес).

$BRx – код оператора. При этом можно ввести самые разнообразные условия перехода. Например:

$BRZ - переход по значению 0,

$BRM - переход по значению <0,

$BRP - переход по значению >0,

$BRMZ - переход по значению <=0,

$BRPZ - переход по значению >=0,

и т.п.

При выполнении условия перехода в качестве следующего символа берется тот символ, адрес которого определяется вторым операндом. В противном случае работа продолжается как обычно.

 

Условные конструкции

IF <выражение> THEN <инстр1> ELSE <инстр2>

В ПФ мы имеем:

<выражение> <c₁> $BRZ <инстр₁> <c₂> $BR <инстр₂>

Предполагается, что для любого выражения 0 означает "ложь", а неравенство нулю - "истина". Здесь

<c₁> - номер символа, с которого начинается <инстр₂>,

<c₂> - номер символа, следующего за <инстр₂>,

$BR - оператор безусловного перехода на символ,

$BRZ - оператор перехода на символ c₁, если значение <выражение> равно нулю).

Обратите внимание на то, что при выполнении операторов перехода из стека лишь извлекается необходимое количество символов, а обратно ничего не возвращается.

Понятно, что применение ПФ для условной конструкции в виде

<выр> <инстр1> <инстр2> $IF

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

 

Описание массивов

Пусть дано описание массива

ARRAY A[L1..U1,...,Lk..Uk]

в ПФ оно представляется в виде

L1 U1... Lk Uk A $ADEC,

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