Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Линеаризованные представления
|
|
В качестве промежуточных представлений весьма распространены линеаризованные представления деревьев. Линеаризованное представление позволяет относительно легко хранить промежуточное представление во внешней памяти и обрабатывать его. Наиболее распространенной формой линеаризованного представления является польская запись - префиксная (прямая) или постфиксная (обратная).
Постфиксная запись - это список вершин дерева, в котором каждая вершина следует (при обходе снизу-вверх слева-направо) непосредственно за своими потомками. Дерево на рис. 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 | Конец тела модуля |
|
|