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

⇐ ПредыдущаяСтр 22 из 23Следующая ⇒

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

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

a b c - * b c - * +: =

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

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

: = a + * b - c * b - c

Рассмотрим детальнее одну из реализаций префиксного представления - Лидер [12]. Лидер - это аббревиатура от " ЛИнеаризованное ДЕРево". Это машинно-независимая префиксная запись. В Лидере сохраняются все объявления и каждому из них присваивается свой уникальный номер, который используется для ссылки на объявление. Рассмотрим пример.

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 intvar intvar intprocbody 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 endend

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

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	Конец тела модуля

⇐ Предыдущая 14 15 16 17 18 19 20 212223 Следующая ⇒

Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2025 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал