Статическое распределение.

1) Отсутствие блочности программы: объекты в порядке как встречаются в программе.

2) Есть блоки, но нет подпрограмм. Все переменные делятся на глобальные и локальные. В первую очередь выделяется память под глобальные. Используется стек. Используется 700 байт. Если при входе в блок выделяется память, при выходе – освобождается.

3) С подпрограммами. Пусть есть две подпрограммы: f и g. Причем в f есть обращение к g.

Пример: Х®У: если блок У в блоке Х или вызывается Х в У. Как оптимизировать память? Граф подправляется: для " вершины, начиная от корня, высчитываются

существующие пути, идущие в эту вершину. Если их много, то вычеркиваются дуги, имеющие наименьший вес. Q ®Р (предшествует).

Правила расширения графа: - предшествование.

1) P ® N & N Ì R Þ P ® R

2) M Ì P & P ® N Þ M ® N

A(5)

/ \

Q(3) T(4)

|

P(2)

/ \

M(3) L(4)

|

R(2)

|

N(5)

Задачу оптимизации памяти решаем сведением к задаче сетевого планирования.

На этом графе строится дерево длиннейших путей. Алгоритм не всегда корректен? Распределение памяти происходит во время трансляции.

Динамическое распределение. Выделяются:

1. Магазинное распределение: в рекурсивных процедурах иобъектах, динамически определяющихся блоках. В этом случае поле переменных организуется как стек М, полями которого являются компоненты вектора, являющегося локальным объектом блока. Адрес каждого объекта определяется базой (адресом начала вектора), вычисляемой в момент загрузки программы, и смещением (адрес внутри вектора), вычисляемым во время трансляции. Такая адресация позволяет довольно просто вычислять адреса объектов. Наряду с этим магазином создается магазин S адресов текущих локальных объектов. Сюда записывается адрес для смещения. После этого свободный текущий адрес увеличивается на размер локальных объектов этого блока. Номер блока записывается в М. После выхода из блока верхушка S? освобождается.

2. Существенно динамическое распределение: требование выделить память в самой программе. Поле переменных делится на магазин и кучу. Куча и магазин растут навстречу друг другу, надо следить, чтобы они не накладывались друг на друга. Куча определяется списком, поэтому экономное использование памяти.

Динамическая поддержка. Сгенерированная программа должна вычислять какие-то функции, распределять память, реагировать на различные ситуации. Часть действий осуществляется ОС, часть управляющим монитором.

7. ОРГАНИЗАЦИЯ ТРАНСЛЯТОРА.

7.1. Схема процесса трансляции.

1) Лексический анализ. На выходе: лексическая свертка + таблица имен. Ошибки: неверные лексемы.

2) Синтаксический анализ. Вместо имен один идентификатор a. Определяет структуру программы. Строит дерево разбора. Здесь КС-грамматика. Ошибки: отсутствующие скобки, лишние; перевранные слова.

3) Контекстный анализ. На входе: дерево разбора и таблица имен с их атрибутами. Определяет типы. Строит атрибутное дерево. Ошибки: не хватает атрибутов, несовместные атрибуты, двойное объявление переменной.

4) Генерация кода. а) генерация промежуточного кода,

б) оптимизация кода, в) генерация объектного кода.

Такая схема не всегда выдерживается. Часто работа совмещается, т.е. иногда вся трансляция проходит за один просмотр. Каждый просмотр - это отдельный блок, в оперативной памяти блоки сменяют друг друга.

Иногда транслятор делают в виде модульных сопрограмм. Это более сложная, но значительно более гибкая организация транслятора. При трансляции можно сделать, чтобы синтаксический анализ по мере надобности вызывал лексический анализ.

Проблемы передачи информации:

1. Блок вызывает другой, передавая ему информацию;

2. Есть несколько блоков, передача идет через монитор.

7. 2. 0днопроходный транслятор.

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

Требования к языку программирования:

1) определяющие вхождения идут раньше операций (описание предшествует операциям);

2) отсутствие динамических объектов.

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

7. З. Двухпроходная схема трансляции.

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

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

7. 4. Многопросмотровая схема трансляции.

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

Пример: IFА=В then ошибка в синтаксическом анализе при встрече then.

Подходы к исправлению ошибки: посчитать, сколько элементарных операций нужно, чтобы текст был синтаксически правильным (в данном случае поставить пробел между IF и А).

Не нашли, что искали? Воспользуйтесь поиском: