Линеаризованные представления

В качестве промежуточных представлений весьма распространены линеаризованные представления деревьев. Линеаризованное представление позволяет относительно легко хранить промежуточное представление во внешней памяти и обрабатывать его. Наиболее распространенной формой линеаризованного представления является польская запись - префиксная (прямая) или постфиксная (обратная).

Постфиксная запись - это список вершин дерева, в котором каждая вершина

следует (при обходе снизу-вверх слева-направо) непосредственно за своими потомками. Дерево на рис.8.1, а, в постфиксной записи может быть представлено следующим образом:

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

аналогично вычислению выражения в постфиксной записи с использованием стека.

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

Рассмотрим детальнее одну из реализаций префиксного представления - Лидер [9]. Лидер - это аббревиатура от «ЛИнеаризованное ДЕРево». Это машинно-независимая префиксная запись. В Лидере

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

      module M;
      var X,Y,Z: integer;
      procedure DIF(A,B:integer):integer;
         var R:integer;
         begin R:=A-B;
               return(R);
         end DIF;
      begin Z:=DIF(X,Y);
      end M.

<
Этот фрагмент имеет следующий образ в Лидере.

     program 'M'
     var int
     var int
     var int
     procbody proc int int end int
        var int
        begin assign var 1 7 end
                     int int mi par 1 5 end par 1 6 end
              result 0 int var 1 7 end
              return
        end
     begin assign var 0 3 end int
           icall 0 4 int var 0 1 end
           int var 0 2 end end
     end

Рассмотрим его более детально:

program 'M'		Имя модуля нужно для редактора связей.
var int		Это образ переменных X, Y, Z;
var int		переменным X, Y, Z присваиваются номера
var int		1, 2, 3 на уровне 0.
procbody proc		Объявление процедуры с двумя
int int end		целыми параметрами, возвращающей целое.
int		Процедура получает номер 4 на уровне 0 и
		параметры имеют номера 5, 6 на уровне 1.
var int		Переменная R имеет номер 7 на уровне 1.
begin		Начало тела процедуры.
assign		Оператор присваивания.
var 1 7 end		Левая часть присваивания (R).
int		Тип присваиваемого значения.
int mi		Целое вычитание.
par 1 5 end		Уменьшаемое (A).
par 1 6 end		Вычитаемое (B).
result 0		Результат процедуры уровня 0.
int		Результат имеет целый тип.
var 1 7 end		Результат - переменная R.
return		Оператор возврата.
end		Конец тела процедуры.
begin		Начало тела модуля.
assign		Оператор присваивания.
var 0 3 end		Левая часть - переменная Z.
int		Тип присваиваемого значения.
icall 0 4		Вызов локальной процедуры DIF.
int var 0 1 end		Фактические параметры X
int var 0 2 end		и Y.
end		Конец вызова.
end		Конец тела модуля.

Содержание раздела