Семестр: Отладка разработанного ПО и оформление протоко-
В строке ...SiSj... символы Si и Sj входят в одну и ту
В множество L(U) самых левых символов нетерминального
Пусть между некоторыми двумя символами Si и Sj сущес-
I i 1
Не предусмотрен выход при выполнении условия R > R , так как
Потом повторяется п. 5
Если выполнение шага 4 пpиведет к тому, что значения всех
Перевод инфиксной записи в польскую. Всякий раз, когда в
Когда редуцируется основа XY..Z, тетрады для всех нетер-
Опреанды и операторы
Если сканируемый символ - унарный оператор, то он приме-
А * В + С * D => *, A, B, T1 ┐ тетрады располагаются в
Устраняет недостатки программы,вызванные небрежностью или
Проверяется
непртиворечивость типов получателя и ис-
ДИСПЛЕЙ
Выделение памяти под рамку в процессе трансляции
ОРГАНИЗАЦИЯ ПАМЯТИ ВО ВРЕМЯ ТРАНСЛЯЦИИ
Алгоритм Биледи
Возможные параметры описания переменных и процедур
Навигация
ДИСПЛЕЙ
Проектирование трансляторов
319724
знака
0
таблиц
0
изображений
1. ДИСПЛЕЙ
1.1 Взаимодействие Дисплея и стека
После выяснения структуры (и значения) программы необходимо
выделить место в памяти для значений переменных и т.п. и помес-
тить соответствующие адреса, где это необходимо, в таблицу симво-
лов. Фаза распределения памяти почти не зависит от языка и маши-
ны и практически одинакова для подавляющего большинства языков,
имеющих блочную структуру и реализуемых на многих типичных ЭВМ.
Распределение памяти, по существу, заключается в отображении зна-
чений, появляющихся в программе, на запоминающем устройстве маши-
ны. Если допустить, что мы реализуем типичный язык с блочной
структурой, а машина имеет линейное запоминающее устройство, то
наиболее подходящим устройством, на котором мы будем базировать
распределение памяти, представляет стек или память магазинного
типа.
Ниже мы рассмотрим классическую структуру стека времени про-
гона для локального распределения памяти и покажем, как можно
произвести глобальное распределение памяти в отдельной области,
называемой "кучей".
В каждом компиляторе предусмотрена схема распределения памя-
ти, которая до некоторой степени зависит от компилируемого языка.
В Фортране память, выделенная для значений идентификаторов, ни-
когда не освобождается, так что здесь подходящей структурой для
нее является одномерный массив. Если считается, что массив имеет
левую и правую стороны, память можно выделять слево направо. При
этом применяется указатель, показывающий первый свободный эле-
мент в массиве. Например, в результате описания
INTEGER A,B,X,Y
выделяется память, как показано на рис. 20.1.
┌───┬───┬───┬───┬───────────────
│ A │ B │ X │ Y │
└───┴───┴───┴───┴───────────────
^
│
Рис. 20.1 Схема выделения памяти в Фортране
Такая схема не учитывает тот факт, что рабочая память (па-
мять для промежуточных результатов) используется неоднократно и
весьма неэффективна (в смысле использования объема памяти) для
языка с блочной структурой.
В языке, имеющем блочную структуру, память обычно высвобож-
дается при выходе из блока, которому она выделена. В этом случае
оптимальным решением было бы разрешить указателю в вышеприведен-
ном примере отодвигаться обратно влево при высвобождении памяти.
Такой механизм распределения эквивалентен стеку времени прогона
или памяти магазинного типа, хотя принято показывать стек запол-
няющимся снизу вверх.
│ │ │ │ │ │ (1) begin real x,y
│ │ │ │ │ │ .
│ │ ├───┤ ├───┤ .
│ │ │ d │ │ q │ .
│ │ ├───┤ ├───┤ (2) begin int c,d
│ │ │ c │ │ p │ .
├───┤ ├───┤ ├───┤ .
│ │ │ │ │ │ end;
│ │ │ │ │ │ (3) begin int p,q
│ Y │ │ Y │ │ Y │
├───┤ ├───┤ ├───┤ .
│ │ │ │ │ │ .
│ │ │ │ │ │ end;
│ X │ │ X │ │ X │ .
└───┘ └───┘ └───┘ .
end.
(1) (2) (3)
Рис. 20.2 Схема распределения памяти под переменные в раз-
личные моменты в программе на языке с блочной структурой
На рис. 20.2 показаны "моментальные снимки" стека фрагмента
программы во время прогона.
Часть стека, соответствующую определенному блоку, называют
РАМКОЙ стека. Считается, что указатель стека показывает на его
первый свободный элемент.
Кроме указателя стека, требуется также указатель на дно те-
кущей рамки (УКАЗАТЕЛЬ РАМКИ). При входе в блок этот указатель
устанавливается равным текущему значению указателя стека. При вы-
ходе из блока сначала указатель стека устанавливается равным зна-
чению, соответствующему включающему блоку.
Указатель рамки включающего блока может храниться в нижней
части текущей рамки стека, образуя часть статической цепи или
(как мы будем считать) массива, который называется ДИСПЛЕЕМ.
Его можно использовать для хранения во время прогона указа-
телей на начало рамок стека, соответствующих всем текущим блокам
(рис. 20.3).
│ │
│ │
│ │
│ │ ├───┤
│ │ │ q │
│ │ ├───┤
│ │ │ p │
│ │ /───> ├───┤
│ │ / │ │
├──┤ / │ Y │
│ │──/ ├───┤
├──┤ │ │
│ │─────────> │ X │
└──┘ └───┘
Дисплей Стек
Рис. 20.3 Схема связи Дисплея и стека во время выполнения
без учета динамически выделяемой памяти
Это несколько упрощает перенастройку указателя рамки при вы-
ходе из блока.
Если бы вся память была статической, адреса времени прогона
могли бы распределяться во время компиляции, и значения элемен-
тов дисплея также были бы известны во время компиляции.
Рассмотрим следующий отрезок программы на языке Алгол-60:
...
begin int n; read(n);
[1:n] int numbers;
real p;
begin real x,y;
...
Место для numbers должно выделяться в первой рамке стека, а
для x и y - в рамке над ней. Но во время компиляции неизвестно,
где должна начинаться вторая рамка, так как не известен размер
чисел.
Одно из решений в этой ситуации - иметь два стека: один для
статической памяти, распределяемой в процессе компиляции, а дру-
гой - для динамической памяти, распределяемой в процессе прогона.
Однако этого обычно не делают, возможно, из-за тех проблем, кото-
рые возникают в связи с наличием более чем одного увеличивающего-
ся и уменьшающегося стека во время прогона.
Другое решение заключается в том, чтобы при компиляции выде-
лять статическую память в каждом блоке в начале каждой рамки, а
при прогоне - динамическую память над статической в каждой рамке.
Это значит, что когда происходит компиляция, мы все еще не знаем,
где начинаются рамки (кроме первой), но можем распределять стати-
ческие адреса относительно начала определенной рамки. При прого-
не точный размер рамок, соответствующих включающим блокам, извес-
тен, так что при входе в блок нужный элемент дисплея всегда мож-
но установить так, чтобы он указывал на начало новой рамки (рис.
20.4).
│ Рамка 2
│ │ │
│ │ │
│ │ /
├───────┤ \
│ y │ Динами- │
├───────┤ │
│ x │ ческая │
/───> ├───────┤ │
│ │ / │ Числа │ память > Рамка 1
│ │ / │ │ │
├─────┤ / ├───────┤ - - - - │
│ │/ │ p │ Стати- │
├─────┤ ├───────┤ ческая │
│ │──\ │ n │ память │
└─────┘ \────> └───────┘ /
Дисплей Стек
Рис. 20.4 Схема связи Дисплея и стека во время выполнения с
учетом динамически выделяемой памяти
На этом рисунке массив занимает только динамическую память.
Однако некоторая информация о массиве обычно известна во время
компиляции, например, его размерность (а следовательно, и число
границ - две на каждую размерность), и при выборке определенного
элемента массива она может потребоваться. Во многих языках сами
границы могут быть не известны при компиляции, но почти наверня-
ка мы знаем их число, и для значений этих границ можно выделить
статическую память. Тогда мы вправе считать, что массив состоит
из статической и динамической частей. Статическая часть массива
может размещаться в статической части рамки, а динамическая - в
динамической. Кроме информации о границах, в статической части
может храниться указатель на сами элементы массива. Модифицируем
рис. 20.4 в рис. 20.5 с учетом этих особенностей.
│ Рамка 2
│ │ │
│ │ │
│ │ /
├────────┤ \
│ y │ Динами- │
├────────┤ │
│ x │ ческая │
/───> ├────────┤ │
│ │ / │Элемен- │ часть > Рамка 1
│ │ / │ты чисел│ │
├─────┤ / ┌─> ├────────┤ - - - - │
│ │/ │ │ p │ Стати- │
│ │ │ ├────────┤ │
│ │ │ │ Стат. │ │
│ │ └───│ часть │ ческая │
│ │ │ чисел │ │
├─────┤ ├────────┤ │
│ │──\ │ n │ часть │
└─────┘ \────> └────────┘ /
Дисплей Стек
Рис. 20.5 Схема связи Дисплея и стека во время выполнения с
учетом представления массивов в виде статической и динамической
частей
Похожие работы
... работы. В ходе работы над дипломным проектом разработан транслятор. Проблема создания такого транслятора является очень актуальной, т.к. многим пользователям САПР необходимо доступ к технической документацию, которую удобнее хранить на удаленных серверах в формате HTML. Поэтому степень положительного эффекта от выполнения дипломного проекта научно-исследовательского характера 1=6.5. В ...
... направления, активно развиваемого сейчас в разных коллективах и странах. Отталкиваясь от трансформационной модели смешанных вычислений и от своих работ в области трансляции и оптимизации программ, Ершов определяет концепцию трансформационной машины. Трансформационная машина есть абстрактное вычислительное устройство, выполняющее программы в некотором "сверхязыке", действиями которого являются ...
... 166, 16 Mb RAM, Windows 95 Вывод В ходе разработки курсового проекта я ближе ознакомился с теорией МП- трансляторов, научился писать программы - конструкторы для построения МП – транслятора по его параметрам с последующей проверкой задаваемых цепочек, закрепил знания по системному программированию. Разрабатывая программу, я научился применять знания дискретной математике, что облегчает ...
... позволяет связывать твёрдотельные модели, сборки или чертежи, созданные с помощью SolidWorks 97, с файлами других приложений, что значительно расширяет возможности автоматизации процесса проектирования. С помощью технологии OLE можно использовать информацию, полученную в других приложениях Windows, для управления моделями и чертежами SolidWorks. Например, размеры модели могут быть рассчитаны в ...
0 комментариев